華榮道演算法

Ⅵ 請問華容道問題的解法,非高手勿進!

華容道問題用計算機求解，一般採用廣度搜索的方法，其原理很簡單，就是把下一步可能有的走法全部算出來，比如第一步有五種走法，將這五種走法的下一步走法分別算出來，可能會有三十步，在繼續將這三十步走法的下一步走法分別算出來，可能會更多，以此類推，直到達到目標狀態（曹操在出口位置）為止。

在解華容道的問題上，我覺得有兩個問題比較棘手。

其一、演算法的效率。

其二、獲得最優解法。

我是這樣解決的：

1、 要提高演算法的效率，首先要知道演算法的瓶頸在什麼地方，在得出每一個狀態（走完一步各個棋子的位置）都要和前面的狀態進行比較，以保證不重復，隨著步數的增多，狀態數會大幅度增加，這是，和前面的狀態比較這一過程成了整個演算法的效率。解決的辦法，從兩個地方著手，其一，增加每一步比較的速度。在程序中，用5*4的數組表示一個狀態，這樣，每一次比較要比較二十個數，因為數組中每個數定義從0-7，用三個二進制位可以表示，3*20=60位，用一個64位數就可以表示（有的資料說用四個位元組就可以，我實在想不出來），這樣每次比較一個64位數就可以了。其二、減少比較的狀態，這是提高效率的關鍵。比較的時候不要和前面所有的狀態都進行比較，只要和前兩步的所有狀態進行比較就可以了。經過以上的優化，在解橫刀立馬時，大約需要一，兩秒鍾就可以了，（我的機器，賽揚1.1OC1.46）。

2、 獲得最優解法，比如橫刀立馬是81步，這里的一步指移動一個棋子，可以把一個卒子向一個方向移動兩格，或者卒子拐彎移動兩格，或者一個將向一個方向移動兩格（橫將橫著移，豎將豎著移）都是一步。獲得最優解法的關鍵是把下一步可能有的走法全部算出來，不能遺漏。我是根據空格來算走法的的，分三種情況：

① 、卒子拐彎移動，如果有連著兩個空格（橫向的），則如果在它的上面或下面（有四個位置）有卒子的話，那麼可以拐彎移動，有四種走法。如果兩個空格是豎向的，那麼，空格的左右如果有卒子，也可以拐彎移動，也有四種走法。

②、向一個方向移動兩格，這里可能出現的情況有：卒子向一個方向移動兩格，橫將橫著移兩格，豎將豎著移兩格

③、考慮向一個方向移動一格的情況，這里情況很多，我不一一列舉了。

以上的演算法很麻煩，很大一部分程序用來寫這個了，如果大家有更簡單的，可以告訴我，但一個原則，必須把所有的走法全部考慮。

另外，說一下我在寫程序時的小插曲。程序快寫好時，運行時發現，每解一次，內存使用會增加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 <string>
#include <windows.h>
#include "HRD_Calculate.h"

char str[80];
PAINTSTRUCT pa;
HDC hdc,memdc;
RECT rect;
HBITMAP hbit;
HBRUSH hbrush;
HPEN hpen;
POINT point;
hrd_calculate hrd; // User declarations
int current_step;
unsigned __int8 display_node[5][4];

/* Declare Windows procere */
LRESULT CALLBACK WindowProcere (HWND, UINT, WPARAM, LPARAM);

/* Make the class name into a global variable */
char szClassName[ ] = "WindowsApp";

int WINAPI WinMain (HINSTANCE hThisInstance,
HINSTANCE hPrevInstance,
LPSTR lpszArgument,
int nFunsterStil)

{
HWND hwnd; /* This is the handle for our window */
MSG messages; /* Here messages to the application are saved */
WNDCLASSEX wincl; /* Data structure for the windowclass */

/* The Window structure */
wincl.hInstance = hThisInstance;
wincl.lpszClassName = szClassName;
wincl.lpfnWndProc = WindowProcere; /* This function is called by windows */
wincl.style = CS_DBLCLKS; /* Catch double-clicks */
wincl.cbSize = sizeof (WNDCLASSEX);

/* Use default icon and mouse-pointer */
wincl.hIcon = LoadIcon (NULL, IDI_APPLICATION);
wincl.hIconSm = LoadIcon (NULL, IDI_WINLOGO);
wincl.hCursor = LoadCursor (NULL, IDC_ARROW);
wincl.lpszMenuName = NULL; /* No menu */
wincl.cbClsExtra = 0; /* No extra bytes after the window class */
wincl.cbWndExtra = 0; /* structure or the window instance */
/* Use Windows's default color as the background of the window */
wincl.hbrBackground = (HBRUSH) COLOR_BTNFACE;

/* Register the window class, and if it fails quit the program */
if (!RegisterClassEx (&wincl))
return 0;

/* The class is registered, let's create the program*/
hwnd = CreateWindowEx (
0, /* Extended possibilites for variation */
szClassName, /* Classname */
"華容道", /* Title Text */
WS_OVERLAPPED|WS_CAPTION|WS_SYSMENU, /* default window */
CW_USEDEFAULT, /* Windows decides the position */
CW_USEDEFAULT, /* where the window ends up on the screen */
544, /* The programs width */
375, /* and height in pixels */
HWND_DESKTOP, /* The window is a child-window to desktop */
NULL, /* No menu */
hThisInstance, /* Program Instance handler */
NULL /* No Window Creation data */
);

/* Make the window visible on the screen */
ShowWindow (hwnd, nFunsterStil);

/* Run the message loop. It will run until GetMessage() returns 0 */
while (GetMessage (&messages, NULL, 0, 0))
{
/* Translate virtual-key messages into character messages */
TranslateMessage(&messages);
/* Send message to WindowProcere */
DispatchMessage(&messages);
}

/* The program return-value is 0 - The value that PostQuitMessage() gave */
return messages.wParam;
}

/* This function is called by the Windows function DispatchMessage() */

LRESULT CALLBACK WindowProcere (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam)
{
int initx=20,inity=20,grid=50,interspace=3,arc=25;
int i,j,m=0;
char s[100];

switch (message) /* handle the messages */
{
case WM_CREATE:
{

CreateWindow("BUTTON","解題",WS_CHILD|WS_VISIBLE|BS_PUSHBUTTON,350,150,100,
30,hwnd,(HMENU)1000,((LPCREATESTRUCT) lParam)->hInstance,NULL);
CreateWindow("BUTTON","自定義布局",WS_CHILD|WS_VISIBLE|BS_PUSHBUTTON,350,90,100,
30,hwnd,(HMENU)1001,((LPCREATESTRUCT) lParam)->hInstance,NULL);
CreateWindow("EDIT","27732773144115510660",WS_CHILD|WS_VISIBLE|ES_NUMBER|WS_BORDER,350,50,165,
20,hwnd,(HMENU)1002,((LPCREATESTRUCT) lParam)->hInstance,NULL);

GetClientRect(hwnd,&rect);

hdc=GetDC(hwnd);
memdc=CreateCompatibleDC(hdc);
hbit=CreateCompatibleBitmap(hdc,rect.right,rect.bottom);
SelectObject(memdc,hbit);

hbrush = (HBRUSH) GetStockObject(WHITE_BRUSH);
SelectObject(memdc, hbrush);

//hpen = (HPEN) GetStockObject(BLACK_PEN);
//SelectObject(memdc, hpen);
ReleaseDC(hwnd,hdc);
///////////////////////////////////////
display_node[0][0]=GENERAL1;
display_node[0][1]=CAOCAO;
display_node[0][2]=CAOCAO;
display_node[0][3]=GENERAL2;

display_node[1][0]=GENERAL1;
display_node[1][1]=CAOCAO;
display_node[1][2]=CAOCAO;
display_node[1][3]=GENERAL2;

display_node[2][0]=GENERAL3;
display_node[2][1]=GENERAL5;
display_node[2][2]=GENERAL5;
display_node[2][3]=GENERAL4;

display_node[3][0]=GENERAL3;
display_node[3][1]=SOLDIER;
display_node[3][2]=SOLDIER;
display_node[3][3]=GENERAL4;

display_node[4][0]=SOLDIER;
display_node[4][1]=BLANK;
display_node[4][2]=BLANK;
display_node[4][3]=SOLDIER;
break;
}
case WM_TIMER:
{
if(current_step<hrd.depth)
current_step++;
else
{
current_step=0;
KillTimer(hwnd,1);
Sleep(2000);
}
for( i=0;i<5;i++)
for( j=0;j<4;j++)
display_node[i][j]=hrd.out[current_step].state[i][j];

InvalidateRect(hwnd, NULL, 0);
break;
}

case WM_COMMAND:
if(HIWORD(wParam)==BN_CLICKED)
switch (LOWORD(wParam))
{
case 1000:
{
//hrd= new hrd_Calculate;
hrd.InitState(display_node);
if( hrd.SearchNode())
{
sprintf(s, "解題成功!\n\n解題深度：%d 節點數:%d", hrd.depth,hrd.totalnodes);
MessageBox(hwnd,s,"華容道",MB_OK);
hrd.OutputStep();
current_step=0;
SetTimer(hwnd, 1,700, NULL);
}
else
{
sprintf(s,"此局無解") ;
MessageBox(hwnd,s,"華容道",MB_OK);
}
break;
}
case 1001:
{
GetDlgItemText(hwnd,1002,str,80);

for (i=0;i<5;i++)
for(j=0;j<4;j++)
{
display_node[i][j]=(int)(str[m])-0x30;
m++;
}
InvalidateRect(hwnd, NULL, 1);
break;
}
}
break;
case WM_PAINT:
{
hdc = BeginPaint(hwnd,&pa);
PatBlt(memdc, 0, 0, rect.right, rect.bottom, PATCOPY);

//Draw
for (i=0;i<5;i++)
for(j=0;j<4;j++)
{
if (display_node[i][j]==SOLDIER)
RoundRect(memdc,inity+j*grid+j*interspace,initx+i*grid+i*interspace,
inity+(j+1)*grid+j*interspace,initx+(i+1)*grid+i*interspace,arc,arc);
if (display_node[i][j]>=GENERAL1 && display_node[i][j]<=GENERAL5)
{
if (i<4)
if (display_node[i][j]==display_node[i+1][j])
RoundRect(memdc,inity+j*grid+j*interspace,initx+i*grid+i*interspace,
inity+(j+1)*grid+j*interspace,initx+(i+2)*grid+(i+1)*interspace,arc,arc);
if (j<3)
if (display_node[i][j]==display_node[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]==CAOCAO)
if (i<4 && j<3)
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);
EndPaint(hwnd,&pa);
break;
}
case WM_DESTROY:
{
PostQuitMessage (0); /* send a WM_QUIT to the message queue */
DeleteDC(memdc);
DeleteObject(hbit);
break;
}
default: /* for messages that we don't deal with */
return DefWindowProc (hwnd, message, wParam, lParam);
}

return 0;
}
///HRD_Calculate.h 的程序寫法
/////////////////////////////////////////////////
//華容道解法1.0.0.1
//此解法可得出最優解
//橫刀立馬 81步
//最後修改時間 2004.9.22 晚上
//
/////////////////////////////////////////////////
#include "HRD_Calculate.h"

hrd_calculate::hrd_calculate()
{
//申請狀態表空間
first= new s_node[MAX_NODES];
}

hrd_calculate::~hrd_calculate()
{
delete[] first;
}

void hrd_calculate::NodeToSNode(node * pnode,s_node* psnode)
{
int i,j;
__int8 hgeneral=8,vgeneral=9;
node * tnode= new node;
*tnode=*pnode;

for( i=0;i<5;i++)
for( j=0;j<4;j++)
{
if (tnode->state[i][j]>=GENERAL1 && tnode->state[i][j]<=GENERAL5)
{
if (j<3)
if (tnode->state[i][j] == tnode->state[i][j+1])
{
tnode->state[i][j]=hgeneral;
tnode->state[i][j+1]=hgeneral;
}

if(i<4)
if(tnode->state[i][j] == tnode->state[i+1][j])
{
tnode->state[i][j]=vgeneral;
tnode->state[i+1][j]=vgeneral;
}
}
}
for( i=0;i<5;i++)
for( j=0;j<4;j++)
{
if(tnode->state[i][j]==hgeneral) tnode->state[i][j]=HGENERAL;
if(tnode->state[i][j]==vgeneral) tnode->state[i][j]=VGENERAL;
}

psnode->prior=(s_node *)pnode->prior;
psnode->state=0;
psnode->ext_state=0;
for( i=0;i<5;i++)
for( j=0;j<4;j++)
{
psnode->state += pnode->state[i][j];
psnode->ext_state += tnode->state[i][j];
if (!(i==4 && j==3)) psnode->state = psnode->state<<3;
if (!(i==4 && j==3)) psnode->ext_state = psnode->ext_state<<3;
}

delete tnode;

}

void hrd_calculate::SNodeToNode(s_node* psnode,node * pnode)
{
__int64 temp,s;
s = psnode->state;
pnode->prior=(node*)psnode->prior;
for(int i=4;i>=0;i--)
for(int j=3;j>=0;j--)
{
temp = s & 0x0000000000000007;
pnode->state[i][j]= temp ;
s = s >>3 ;
}
}

void hrd_calculate::OutputStep()
{
node * outfirst,* outlast,*p;

outfirst=&out[0];
outlast=outfirst+(depth);
p=outlast;

while ( p>=outfirst)
{
SNodeToNode(last,p);
last=last->prior;
p--;
};

}

bool hrd_calculate::SearchNode()
{
int nextnodes;
node * tnode=new node;
int total;
while(true)
{
nextnodes=0;
table[depth+1]=(unsigned int)(last+1);
for ( ;search<=current_last ; search++)
{
SNodeToNode(search,tnode);
tnode->prior=(node *)search;

total=SearchOneNode(tnode);
nextnodes +=total;
if (total==SUCCESS)
{
delete tnode;
return true;
}

}
if (nextnodes==0)
{
delete tnode;
return false;
}

depth++;
current_last=last;
}

}

int hrd_calculate::AddNode(node c)
{
s_node *p;
s_node *snode=new s_node;

if (depth<=3) p=first;
else p=(s_node*)table[depth-1];
NodeToSNode(&c,snode);
for (;p<=last;p++)
if (p->ext_state== snode->ext_state)
{
delete snode;
return ADD_NO_NODE;
}

//加入節點
last++;
last->prior=snode->prior;
last->state=snode->state;
last->ext_state=snode->ext_state;
totalnodes++;
delete snode;

if (c.state[3][1]==CAOCAO && c.state[4][2]==CAOCAO )
return SUCCESS;
else
return ADD_ONE_NODE;
}

void hrd_calculate::InitState(unsigned __int8 state[5][4])
{

//設定初始狀態
node initnode;
initnode.prior=0; //沒有上一步
for(int i=0;i<5;i++)
for(int j=0;j<4;j++)
initnode.state[i][j]=state[i][j];

////////////////////
NodeToSNode(&initnode,first);
////////////
last=first;
search=first;
current_last=first;
depth=1;
totalnodes=1;
table[0]=0;
table[depth]=(unsigned int)first;
}
int hrd_calculate::SearchOneNode(node *c)
{
int i,j;
int next_nodes=0;
node t;

for(i=0;i<5;i++)
for(j=0;j<4;j++)
{
if (c->state[i][j]==BLANK)
{
///////////////////////////////////////////////////////////////////////////////
//直走兩步
if (j<3)
{
if (c->state[i][j+1]==BLANK)
{
if (j>0)//左邊兵右移兩格
{
if (c->state[i][j-1] == SOLDIER)
{
t=*c; t.prior=c->prior;
t.state[i][j-1]=BLANK;
t.state[i][j+1]=SOLDIER;
switch (AddNode(t))
{
case SUCCESS: return SUCCESS;
case ADD_ONE_NODE: next_nodes++;
}
}
}
if (j<2)//右邊兵左移兩格
{
if (c->state[i][j+2]==SOLDIER)
{
t=*c; t.prior=c->prior;
t.state[i][j+2]=BLANK;
t.state[i][j]=SOLDIER;
switch (AddNode(t))
{
case SUCCESS: return SUCCESS;
case ADD_ONE_NODE: next_nodes++;
}
}
}
if (j==2)//左邊將右移兩格
{
if (c->state[i][j-1]>=GENERAL1 && c->state[i][j-1]<=GENERAL5 && c->state[i][j-1]==c->state[i][j-2])
{
t=*c; t.prior=c->prior;
t.state[i][j]=c->state[i][j-1];
t.state[i][j+1]=c->state[i][j-1];
t.state[i][j-1]=BLANK;
t.state[i][j-2]=BLANK;
switch (AddNode(t))
{
case SUCCESS: return SUCCESS;
case ADD_ONE_NODE: next_nodes++;
}
}
}
if (j==0)//右邊將左移兩格
{
if (c->state[i][j+2]>=GENERAL1 && c->state[i][j+2]<=GENERAL5 && c->state[i][j+2]==c->state[i][j+3])
{
t=*c; t.prior=c->prior;
t.state[i][j]=c->state[i][j+2];
t.state[i][j+1]=c->state[i][j+2];
t.state[i][j+2]=BLANK;
t.state[i][j+3]=BLANK;
switch (AddNode(t))
{
case SUCCESS: return SUCCESS;
case ADD_ONE_NODE: n

Ⅶ 華容道的擺法及名稱和解法

名稱：橫刀立馬

橫刀立馬是華容道的最優解法，一共有81步，由計算機通過窮舉法得出。

解法按照下圖每小格一步一步操作即可，每張圖18步，最後一張圖9步。

1、1-18步。

(7)華榮道演算法擴展閱讀

最早系統研究游戲華容道的是蘇州大學數學教授許蒓舫先生。1952年，他在《數學漫談》中對這個游戲作了詳細的分析，總結出8條規則。這8條可以歸納為以下4點：

1、四個小兵必須兩兩在一起，不要分開；

2、曹操，關羽，大將移動時前面應有兩個小兵開路；

3、曹操移動時後面還應有兩個小兵追趕；

4、以上三種狀況，其中各塊都可局部（不妨礙其他地方）任意移動。

在此基礎上，許蒓舫提出了100步解法。下就是許先生的解法，可能由於初始狀況的不同，這里只需要98步。