华容道每一级的全过程
下面的走法遵循了L.E.Hordern的记录方法，即在大多数情况下，指示走哪颗棋子就够了，只有少数情况下，指示怎么走就够了。这由以下符号表示。l向左；r向右；U upd向下；！只需走一格；#必须转(最小的一块)。没有这些符号，就意味着直走到底(一两个方块)。棋子数见图1。当然，这只是指出了如何过关，我们不必死记硬背这些步骤。关键是研究通关的必要条件，达到通关的目的。
(1)在水平和垂直方向上
6 4 5 7 # 9 6 8 3 5 7 9 L 2 A 7 5 1 7 L A 2 4 5 9 L 4 5 8 # 3 1 9 L 4 5 8 # 3 1 9 L 4 5 # 2A 9 # 4 1 3 6 8 5 2 A 9 7 4 3 5 8 8 6D 3 A 9 1 7 4 3 3 1 2 2 6 r 5 # 8 A 9 1 7
守口如瓶
5 7 l 2 A 1 3 6 4 1 A 2 7 # 9 8 4 1 6 # 4 1 6 5 # 7 9 6 # 1 4 7 # 9 5 # 2 A 7 # 9 4 1 8 6D 5 2 A 7 3 9 1 5 6 7 654 38+0 4D 1 A 7 1 3 9
(3)守口如瓶。
7 # 9 8 6 # 3 1 A 2 4 7 R 2 A 1 3 6 # 8 9 7 # 4 A 5 6 # 8 9 7 # 8 9 3 6 # 51 6 U 5 1 A 4 81 2U 8 1 1 1 79 3 5 2 8 7 # 4 A 2 # 8 7 # 4 A 2 # 8 5 3 9 1 7 4 A 2 6 8 3 6 3 6 7 A 2 1 6 8 3 5 A 2 1 6 4 A 7 1 A 2 3 8 4 9 1 # A
(4)第二层设防
9 L8 # 4 2 A 1 3 5 2 4 8 9 6 7 2 5 3 1 L， A 4 5 2 7 6 9 8 2 7 6 7 8 7 8 7 9 3 6 5 8 4 A 6 5 3 8 9 4 A 6 1 5 8 A 6 1 1 5 8 3 4 7 2 u 9 7 2 A 6 1 4 A 6 3 2 6 7 7 9 A 1 3 2 6 7 9 A 1 3 2 8 5 3 6 7 9 A 1 A 9 7 1 # A 4 3 3 3 3 2 8 A 1 4 3 1 # 4 3 9 7 8 6D A 6 2 1 4 3 9 7 6 8 A 9 7 8
(5)最高机密
7 5 3 2 1 4 6 7 L A 1 # 4 6 7 1 3 5 9 8 A 1 4 2 5 3 # 4 7 R 6 2 4 1 A 8 9 3D 5 1 4 2 7 U 6 U 6 U A 1 3 9 8 3D 1D 7D 6D 2 5 4 9 8 3 65438+
(六)三军联防
6 7 4 3 7 # 3 4 2 1 A 7 5 8 4 6 9 # 6 4 8 3 9 L 2 1 A 5 # 3 8 9 U 4 6 2 1 A5 7
3 9 # A 1 2 4 6 8 9 A 1 2 4 6 9 # A 3 7 5 1 2 4 6 9 8 A 4 6 8 # A
(7)阻塞动脉
5 9 6 7 4 2 A 3 7 5 6 9 8 4 2D A 3 1 7 5 6 9 8 4 2D A 1 3D 7 5 6 9 8 4 2 A
(8)包装好了
9 7 6 8 9 U 7 6 5 4 8 9 U 5 4 9 A 1 3 # 8 A 1 2 9 1 4 5 A 3 # 21 # 4 5 6 7 A 5 4 1 # 2 3 # 5 4 2 1 9D 3 8 4 A 7 6 65 438+0 # 9 3 8 8 # 5 4 A 1 9 6 7 65438
(9)四路入侵(原67步，11 66步)
A 4 3 # 2 A 4 3 # 1 5 2 # 7 6 A 3 # 1 2 # 7 6 9 8 A 6 7 2 0 # 1 3 # 6 7 1 2 5D 3 4 6 7 A 8 9 2 # 5 3 4 # 6 7 A 2 5 9 8 2 5D A 7 A 2 5 9 8 2 5D A 7 6 6 1 4 3 U 9 8 5 2 A 9 8 2 # 2 A
华容道的问题是用电脑解决的。一般采用广度搜索的方法。原理很简单，就是把所有可能的下一步棋都算出来。比如第一步有五步棋。如果把这五步棋的下一步棋分开算，可能有三十步。如果继续分别计算这三十步的下一步棋，可能会更多，以此类推，直到达到目标状态(曹操在退场位置)。
关于解决华容道的问题，我认为有两个棘手的问题。
第一，算法的效率。
第二，求最优解。
我是这样解决的:
1.为了提高算法的效率，首先要知道算法的瓶颈在哪里，然后将每个状态(每一步后棋子的位置)与前一个状态进行比较，保证不重复。随着步数的增加，状态的数量会大大增加，也就是说与前一个状态比较的过程就变成了整个算法的效率。解决办法是从两个地方入手。第一，提高每一步的对比速度。程序中用一个5*4的数组来表示一个状态，这样每次比较需要比较20个数字，因为数组中的每个数字都定义为0-7，可以用三个二进制数来表示，3*20=60，可以用一个64位的数字来表示(有的数据说四个字就够了，但我实在想不出来)，这样一次可以比较一个64位的数字。其次，减少攀比状态是提高效率的关键。对比的时候，不要和前面所有的状态对比，只和前面两步所有的状态对比。经过以上优化后，马上解决横刀大概一两秒(我的机器，赛扬1.1OC1.46)。
2.求最优解，比如横刀一下子81步，这里一步是指移动一个棋子，可以将一个棋子向一个方向移动两格，或者将一个棋子向一个角落移动两格，或者将一个棋子向一个方向移动两格(横刀横向移动，竖刀纵向移动)。得到最优解的关键是计算下一步所有可能的走法，不要错过。我按照空间计算运动，分为三种情况:
(1)、棋子转身移动，如果有两个空格(横)，那么如果它的上方或下方有棋子(有四个位置)，那么你就可以转身移动，有四种移动方式。如果两个空格是垂直的，那么如果空格的左右两边都有棋子，他们也可以转身移动，有四种移动方式。
(2)向一个方向移动两个方块。这里可能的情况包括:棋子向一个方向移动两格，水平移动两格，垂直移动两格。
(3)、考虑往一个方向移动一格，这里有很多情况，我就不一一列举了。
上面的算法很麻烦，很大一部分程序都是用来写这个的。有更简单的可以告诉我，但是作为原则，所有的方式都要考虑。
另外，说说我写节目的时候的一个小插曲。当程序快完成的时候，发现每解决一次，内存占用就会增加7，8兆。后来发现，每次释放分配的内存，其实都是在函数里分配了几十个字节。由于反复调用，泄露的内存会很可观。以后要注意用指针分配内存。(C用malloc，C++用new)，必须发布，而且会坏。@
程序是用dev-C++ 4.9.9.0编译的(可以从网上下载，只有十几兆)。因为dev C++没有框架之类的东西，所以直接用window API写接口。生成的可执行文件很小，68 K，另外可以在程序中自定义布局，用5*4的数字表示。其中0-空格，1-卒，2对6将军，7曹操。
最后附上所有源代码。
main.cpp程序是:
# include & lt字符串& gt
# include & ltwindows.h & gt
#包含" HRD_Calculate.h "
字符串[80]；
油漆结构pa；
HDC hdc，memdc
RECT矩形；
HBITMAP hbit
HBRUSH hbrush
HPEN hpen；
点点；
hrd _计算HRD；//用户声明
int当前_步骤；
unsigned _ _ int 8 display _ node[5][4]；
/*声明Windows过程*/
LRESULT回调WindowProcedure (HWND，UINT，WPARAM，LPARAM)；
/*将类名转换成全局变量*/
char SZ class name[]= " windows app "；
int WINAPI WinMain(hin instance hThisInstance，
HINSTANCE hPrevInstance，
LPSTR lpszArgument，
int nFunsterStil)
{
HWND hwnd/*这是我们窗口的句柄*/
MSG消息；/*此处保存应用程序的消息*/
WNDCLASSEX wincl/* window class的数据结构*/
/*窗口结构*/
wincl.hInstance = hThisInstance
wincl . lpsz class name = SZ class name；
wincl . lpfnwndproc = window procedure；/*此函数由windows调用*/
wincl.style = CS _ DBLCLKS/*捕捉双击*/
wincl . CB size = sizeof(WNDCLASSEX)；
/*使用默认图标和鼠标指针*/
wincl.hIcon = LoadIcon (NULL，IDI _应用)；
wincl.hIconSm = LoadIcon (NULL，IDI _ WINLOGO)；
wincl.hCursor = LoadCursor (NULL，IDC _ ARROW)；
wincl.lpszMenuName = NULL/*没有菜单*/
wincl . cbclsextra = 0；/*窗口类后没有额外的字节*/
wincl . cbwndextra = 0；/*结构或窗口实例*/
/*使用Windows的默认颜色作为窗口的背景*/
wincl . HBR background =(HBRUSH)COLOR _ BTN face；
/*注册窗口类，如果失败，退出程序*/
如果(！register classex(& amp；wincl))
返回0；
/*类已注册，让我们创建程序*/
hwnd = CreateWindowEx(
0，/*变体的扩展可能性*/
szClassName，/* Classname */
《华容道》，/*标题文字*/
WS _ OVERLAPPED | WS _ CAPTION | WS _ SYSMENU，/*默认窗口*/
CW_USEDEFAULT，/* Windows决定位置*/
CW_USEDEFAULT，/*窗口在屏幕上的最终位置*/
544，/*程序宽度*/
375，/*和以像素为单位的高度*/
HWND_DESKTOP，/*该窗口是桌面的子窗口*/
空，/*没有菜单*/
hThisInstance，/*程序实例处理程序*/
NULL /*没有窗口创建数据*/
);
/*使窗口在屏幕上可见*/
ShowWindow (hwnd，nFunsterStil)；
/*运行消息循环。它将一直运行，直到GetMessage()返回0 */
while(GetMessage(& amp；消息，NULL，0，0))
{
/*将虚拟按键消息翻译成字符消息*/
翻译消息(& amp消息)；
/*将消息发送到窗口过程*/
dispatch message(amp；消息)；
}
/*程序返回值为PostQuitMessage()给出的值*/
return messages.wParam
}
/*此函数由Windows函数DispatchMessage() */调用
LRESULT回调窗口过程(HWND hwnd，UINT消息，WPARAM wParam，LPARAM lParam)
{
int initx=20，inity=20，grid=50，interspace=3，arc = 25
int i，j，m = 0；
char s[100]；
开关(消息)/*处理消息*/
{
案例WM_CREATE:
{
CreateWindow("BUTTON "，"解决问题"，ws _ child | ws _ visible | bs _ push BUTTON，350，150，100，
30，hwnd，(HMENU)1000，((LPCREATESTRUCT)lParam)-& gt；hInstance，NULL)；
CreateWindow("BUTTON "，"自定义布局"，ws _ child | ws _ visible | bs _ push BUTTON，350，90，100，
30，hwnd，(HMENU)1001，((LPCREATESTRUCT)lParam)-& gt；hInstance，NULL)；
CreateWindow("EDIT "，" 27732773144115510660 "，WS _ CHILD | WS _ VISIBLE | ES _ NUMBER | WS _ BORDER，350，50，165，
20，hwnd，(HMENU)1002，((LPCREATESTRUCT)lParam)-& gt；hInstance，NULL)；
GetClientRect(hwnd & amp；rect)；
hdc = GetDC(hwnd)；
memdc = CreateCompatibleDC(hdc)；
hbit = CreateCompatibleBitmap(hdc，rect.right，rect . bottom)；
SelectObject(memdc，hbit)；
HBRUSH =(HBRUSH)GetStockObject(WHITE _ BRUSH)；
SelectObject(memdc，HB rush)；
//hpen =(HPEN)GetStockObject(BLACK _ PEN)；
//SelectObject(memdc，hpen)；
ReleaseDC(hwnd，hdc)；
///////////////////////////////////////
display _ node[0][0]= general 1；
display _ node[0][1]=草草；
display _ node[0][2]=草草；
显示_节点[0][3]=一般2；
display _ node[1][0]= general 1；
display _ node[1][1]=草草；
display _ node[1][2]=草草；
显示_节点[1][3]=一般2；
显示_节点[2][0]=一般3；
显示_节点[2][1]=一般5；
显示_节点[2][2]=一般5；
显示_节点[2][3]=一般4；
显示_节点[3][0]=一般3；
display _ node[3][1]=士兵；
display _ node[3][2]=士兵；
显示_节点[3][3]=一般4；
display _ node[4][0]=士兵；
display _ node[4][1]=空白；
display _ node[4][2]=空白；
display _ node[4][3]=士兵；
打破；
}
案例WM_TIMER:
{
if(current _ step & lt；hrd .深度)
current _ step++；
其他
{
current _ step = 0；
KillTimer(hwnd，1)；
睡眠(2000)；
}
for(I = 0；我& lt5;i++)
for(j = 0；j & lt4;j++)
显示节点[I][j]= HRD . out[当前步骤]。国家[I][j]；
invalidaterestall(hwnd，NULL，0)；
打破；
}
案例WM_COMMAND:
if(HIWORD(wParam)==BN_CLICKED)
开关(低字(wParam))
{
案例1000:
{
//HRD = new HRD _ Calculate；
hrd。InitState(display _ node)；
如果(hrd。SearchNode())
{
Sprintf(s，“问题成功解决！\ n \ n \解决问题的深度:%d节点数:%d "，hrd.depth，HRD . total nodes)；
MessageBox(hwnd，s，“华容道”，MB _ OK)；
hrd。output step()；
current _ step = 0；
SetTimer(hwnd，1，700，NULL)；
}
其他
{
Sprintf(s，“这个游戏无解”)；
MessageBox(hwnd，s，“华容道”，MB _ OK)；
}
打破；
}
案例1001:
{
GetDlgItemText(hwnd，1002，str，80)；
for(I = 0；我& lt5;i++)
for(j = 0；j & lt4;j++)
{
display _ node[I][j]=(int)(str[m])-0x 30；
m++；
}
invalidaterestall(hwnd，NULL，1)；
打破；
}
}
打破；
案例WM_PAINT:
{
hdc = begin paint(hwnd & amp；pa)；
PatBlt(memdc，0，0，rect.right，rect.bottom，pat copy)；
//绘制
for(I = 0；我& lt5;i++)
for(j = 0；j & lt4;j++)
{
if(display _ node[I][j]= =士兵)
RoundRect(memdc，inity+j*grid+j*interspace，initx+i*grid+i*interspace，
inity+(j+1)*网格+j *空隙，initx+(I+1)*网格+I *空隙，弧，弧)；
if(display _ node[I][j]& gt；= general 1 & amp；& amp显示节点[I][j]& lt；=常规5)
{
如果(我& lt4)
if(显示节点[I][j]= =显示节点[i+1][j])
RoundRect(memdc，inity+j*grid+j*interspace，initx+i*grid+i*interspace，
inity+(j+1)*网格+j *空隙，initx+(I+2)*网格+(I+1)*空隙，弧，弧)；
if(j & lt；3)
if(显示节点[I][j]= =显示节点[i][j+1])
RoundRect(memdc，inity+j*grid+j*interspace，initx+i*grid+i*interspace，
inity+(j+2)* grid+(j+1)* interspace，initx+(I+1)* grid+I * interspace，arc，arc)；
}
if(display _ node[I][j]= =草草)
如果(我& lt4 & amp& ampj & lt3)
if(display _ node[I+1][j+1]= = CAOCAO)
RoundRect(memdc，inity+j*grid+j*interspace，initx+i*grid+i*interspace，
inity+(j+2)* grid+(j+1)* interspace，initx+(I+2)* grid+(I+1)* interspace，arc，arc)；
}
//////////////////////////////////
BitBlt(hdc，0，0，rect.right，rect.bottom，memdc，0，0，SRCCOPY)；
面漆(hwnd & amp；pa)；
打破；
}
案例WM_DESTROY:
{
PostQuitMessage(0)；/*向消息队列发送WM _ QUIT */
DeleteDC(memdc)；
delete object(hbit)；
打破；
}
默认值:/*对于我们不处理的邮件*/
返回DefWindowProc (hwnd，message，wParam，lParam)；
}
返回0；
}
///HRD_Calculate.h程序编写
/////////////////////////////////////////////////
//华容道解1.0.0.1
//这个解可以得到最优解。
//立即横刀81步
//最后修改于2004年9月22日晚。
//
/////////////////////////////////////////////////
#包含" HRD_Calculate.h "
hrd_calculate::hrd_calculate()
{
//申请state表空间
first=新s _ node[MAX _ NODES]；
}
hrd_calculate::~hrd_calculate()
{
先删除[]；
}
void HRD _ calculate::NodeToSNode(node * pnode，s_node* psnode)
{
int i，j；
__int8 hgeneral=8，v general = 9；
node * tnode=新节点；
* tnode = * pnode
for(I = 0；我& lt5;i++)
for(j = 0；j & lt4;j++)
{
if(tnode-& gt；state[i][j]>= general 1 & amp；& amptnode-& gt；state[I][j]& lt；=常规5)
{
if(j & lt；3)
if(tnode-& gt；state[I][j]= = tnode-& gt；状态[i][j+1])
{
tnode-& gt；state[I][j]= h general；
tnode-& gt；state[I][j+1]= h general；
}
如果(我& lt4)
if(tnode-& gt；state[I][j]= = tnode-& gt；state[i+1][j])
{
tnode-& gt；state[I][j]= vgeneral；
tnode-& gt；state[I+1][j]= vgeneral；
}
}
}
for(I = 0；我& lt5;i++)
for(j = 0；j & lt4;j++)
{
if(tnode-& gt；state[I][j]= = h general)tnode-& gt；state[I][j]= h general；
if(tnode-& gt；state[I][j]= = v general)tnode-& gt；state[I][j]= VGENERAL；
}
PS node-& gt；prior =(s _ node *)pnode-& gt；先验；
PS node-& gt；状态= 0；
PS node-& gt；ext _ state = 0；
for(I = 0；我& lt5;i++)
for(j = 0；j & lt4;j++)
{
PS node-& gt；state+= pnode-& gt；国家[I][j]；
PS node-& gt；ext _ state+= tnode-& gt；国家[I][j]；
如果(！(i = = 4 & amp& ampj = = 3))PS node-& gt；state = PS node-& gt；状态& lt& lt3;
如果(！(i = = 4 & amp& ampj = = 3))PS node-& gt；ext _ state = PS node-& gt；ext _ state & lt& lt3;
}
删除tnode
}
void HRD _ calculate::SNodeToNode(s _ node * PS node，node * pnode)
{
__int64 temp，s；
s = PS node-& gt；状态；
pnode-& gt；prior =(node *)PS node-& gt；先验；
for(int I = 4；我& gt=0;我-)
for(int j = 3；j & gt=0;j -)
{
温度= s & amp0x 00000000000000007；
pnode-& gt；state[I][j]= temp；
s = s & gt& gt3 ;
}
}
void hrd_calculate::OutputStep()
{
node * outfirst，* outlast，* p；
outfirst = & ampout[0]；
outlast=outfirst+(深度)；
p = outlast
while(p & gt；=outfirst)
{
SNodeToNode(last，p)；
last = last-& gt；先验；
p-；
};
}
bool hrd_calculate::SearchNode()
{
int nextnodes
node * tnode =新节点；
int total
while(真)
{
next nodes = 0；
table[depth+1]=(unsigned int)(last+1)；
for(；搜索& lt=当前_最后；搜索++)
{
SNodeToNode(搜索，tnode)；
tnode-& gt；先验=(节点*)搜索；
total = SearchOneNode(tnode)；
next nodes+=总计；
if(总计= =成功)
{
删除tnode
返回true
}
}
if (nextnodes==0)
{
删除tnode
返回false
}
深度++；
current _ last = last
}
}
int hrd_calculate::AddNode(节点c)
{
s _ node * p；
s _ node * snode =新s _ node；
if(深度& lt= 3)p =第一；
else p=(s_node*)表[深度-1]；
NodeToSNode(& amp；c，SnO de)；
for(；p & lt=最后；p++)
如果(p->；ext _ state = = s node-& gt；外部状态)
{
删除snode
返回添加节点；
}
//加入节点
last++；
最后-& gt；prior = s node-& gt；先验；
最后-& gt；state = s node-& gt；状态；
最后-& gt；ext _ state = s node-& gt；ext _状态；
total nodes++；
删除snode
if(c . state[3][1]= = CAOCAO & amp；& ampc . state[4][2]= =草草)
返回成功；
其他
返回添加一个节点；
}
void HRD _ calculate::InitState(unsigned _ _ int 8 state[5][4])
{
//设置初始状态
节点initnode
init node . prior = 0；//没有上一步。
for(int I = 0；我& lt5;i++)
for(int j = 0；j & lt4;j++)
init node . state[I][j]= state[I][j]；
////////////////////
NodeToSNode(& amp；initnode，first)；
////////////
last = first
搜索=第一；
current _ last = first
深度= 1；
total nodes = 1；
表[0]= 0；
table[depth]=(unsigned int)first；
}
int HRD _ calculate::SearchOneNode(node * c)
{
int i，j；
int next _ nodes = 0；
节点t；
for(I = 0；我& lt5;i++)
for(j = 0；j & lt4;j++)
{
if(c->；状态[I][j]= =空白)
{
///////////////////////////////////////////////////////////////////////////////
//直走两步
if(j & lt；3)
{
if(c->；状态[I][j+1]= =空白)
{
if(j & gt；0)//左边的士兵向右移动两格。
{
if(c->；状态[i][j-1] ==士兵)
{
t = * c；t.prior=c->先验；
t . state[I][j-1]=空白；
t . state[I][j+1]=士兵；
开关(AddNode(t))
{
案例成功:返回成功；
case ADD _ ONE _ NODE:next _ nodes++；
}
}
}
if(j & lt；2)//右边的士兵向左移动两格。
{
if(c->；状态[I][j+2]= =士兵)
{
t = * c；t.prior=c->先验；
t . state[I][j+2]= BLANK；
t . state[I][j]=士兵；
开关(AddNode(t))
{
案例成功:返回成功；
case ADD _ ONE _ NODE:next _ nodes++；
}
}
}
If (j==2)//左侧将向右移动两个空格。
{
if(c->；state[i][j-1]>= general 1 & amp；& ampc->；state[I][j-1]& lt；= GENERAL5 & amp& ampc->；state[I][j-1]= = c-& gt；状态[i][j-2])
{
t = * c；t.prior=c->先验；
t . state[I][j]= c-& gt；状态[I][j-1]；
t . state[I][j+1]= c-& gt；状态[I][j-1]；
t . state[I][j-1]=空白；
t . state[I][j-2]=空白；
开关(AddNode(t))
{
案例成功:返回成功；
case ADD _ ONE _ NODE:next _ nodes++；
}
}
}
If (j==0)//右侧将向左移动两个空格。
{
if(c->；state[i][j+2]>= general 1 & amp；& ampc->；state[I][j+2]& lt；= GENERAL5 & amp& ampc->；state[I][j+2]= = c-& gt；状态[i][j+3])
{
t = * c；t.prior=c->先验；
t . state[I][j]= c-& gt；状态[I][j+2]；
t . state[I][j+1]= c-& gt；状态[I][j+2]；
t . state[I][j+2]= BLANK；
t . state[I][j+3]= BLANK；
开关(AddNode(t))
{
案例成功:返回成功；
案例添加一个节点:n