马 行 天 下
//这是一个欧拉提出的问题:国际象棋的棋盘上一个马,能否走64步正好走遍64个棋盘格子。
//我用最土的办法来搜索,这是一个典型的“深度优先搜索”(Depth-First-Search),我全部由数组来做,一个2维数组存走过的轨迹,一个数组存可
//以走的步数,再一个数组存每一层的最后一个选择,实际就是当前最底层的父亲。
//这是在McGill听Prfessor NewBurn 的课的唯一的收获,这位老教授是Game软件的专家,据说主持过IBM的“深蓝”与国际特级大师“卡斯帕罗夫”的
//对抗赛,可惜他的课程艰深,作业难做,我听课时,(当然是非法的。)加上我才7个学生,他对学生态度很好,总是说他担心学生会觉得作业太难会
//杀他。哈哈。。。也许阿。真怀念那个月的生活,一天听6门课,从8:30到4:30,每节课只有十分钟换教室,中午没吃饭,我几乎晕过去,下午困的要死,
//上一节课睡半截。不过一想到这是不要钱的,顿时觉得大赚特赚。
//这个小东东,我搞了快两天才完,还不知道对不对,哎,真失败!
//改进就是要能出结果,因为这样搜索是没有结果的因为,8^64是一个天文数字(当然,并不是每一步都有8个选择,有些出界,有些以前走过,但是可以
//看出这个问题的复杂性。)我粗略测试,估计电脑运行几万年也不会有结果,也不知道对不对。各位有兴趣不妨帮我检验一下,做做测试,很简单的,
只要下载解压缩并运行看看多长时间能有结果,在写信告诉我。
改进就是对产生的子节点排序,排序的原则是基于类似“权”值得概念,比如某一个点的权值是由能走到他的点的个数决定的,个数越多权值得优先级越低,
于是,我先将棋盘上所有点的“权”值存起来,当产生子树时候,先搜索优先级高的子树。
不过,好像还是有问题,搜索了两个结果后,(一个2百多万子节点,第二个约3千多万节点)第三个始终不出来。
#include <iostream> #include <cstdlib> #include <ctime> using namespace std; //ÕâÊÇÂíÒƶ¯µÄ×ø±ê¡£ struct Pos { int x; int y; }pos; //ÕâÊÇÆðʼλ×Ó¡£ struct Pos startPos; //ÆåÅ̵ĴóС const boardSize =6; //using even 7 will cost days running. //Âí¿ÉÒÔ×ßµÄ8¸ö²½×Ó¡£ enum Move { upright, upleft, downleft, downright, leftup, leftdown, rightup, rightdown }; //¼Í¼×ߵIJ½Êý¡£ int Tour[8 * boardSize * boardSize]= {0}; //ÕâÊÇËÑË÷µÄ²ãÊý£¬Ò²¾ÍÊÇÿһ²½µÄÖ¸±ê£¬ÒòΪÿһ²½¶¼¿ÉÄÜÓÐ8¸öÑ¡Ôñ¡£ÕâÀïÖ¸Ïò×îºóÒ»¸öλÖᣠint Level[boardSize*boardSize]={0}; //ÊÇ·ñÓн⣨ȫ¾Ö±äÁ¿²»ºÃ£© bool solution = false; //reading way of priority int getPriority(int x, int y); //from direction to priority int direction2Priority(int direction); //×ܵļÆÊýÆ÷¡£ int Counter = 0; //temp storage for possible move and sorting before save to Tour[]; int tempMove[8] = {0}; //storage for prioty for each square in chessboard int priority[boardSize][boardSize] = {0}; //²ãÊýµÄ¼ÆÊýÆ÷¡£ int Step = 0; //save possible move to tempMove[] with big to small priority //void saveTempMove(int &x, int &y, int moveNum); //assignment prioty for each square. void generatePriority(); //ÕâÊÇÆåÅÌ£¬ÓÃÀ´¼Ç¼Æå×ÓÊÇ·ñ×ß¹ýijһ¸öλ×Ó£¬0ΪûÓУ¬1Ϊ×ß¹ý¡£ int board[boardSize][boardSize] = {0}; //²úÉúÿһ²ãµÄ²½Êý¡£Èç²»ÄܲúÉú·µ»Ø¼Ù¡£ bool Generate(); //ÆÀ¹ÀÊÇ·ñÕÒµ½½á¹û¡£ bool Evaluate(); //²»ÄܲúÉú£¬¾ÍÍË»ØÒ»²½£¬ÖØвúÉú¡£ void Restore(); //¿´ÊÇ·ñÊÇÍ˻ص½ÉÏÒ»²ãÁË¡£ bool stepPoint(); //ÄÚ²¿·½·¨£¬²úÉúijÖÖ×ß·¨µÄ×ø±êÖµ¡£ void getMove(int direction, int &x, int &y); //°´ÕÕ²ÎÊýµÄ×ß·¨£¬Òƶ¯ÂíµÄ×ø±êλÖᣠvoid stepMove(int direction); //ÏÔʾÕýÈ·µÄ²½×Ó void displayMove(); //to see if the direction is possible move bool testMove(int direction);//test new move if within bound and unoccupied //³õʼ»¯¡£ void Initialize(int, int); int main() { int startTime=0; long tick =0; generatePriority(); for (int i =0; i< boardSize; i++) { for (int j=0; j< boardSize; j++) { tick =0; Initialize(i, j); startTime = time(0); while (!Evaluate()) { if (!Generate()) //²»ÄܲúÉú¾ÍÍË»ØÉÏÒ»²½¡£ { Restore(); //ÍË»ØÉÏÒ»²½¡£ if (Counter <= 0) //¼ìÑéÊÇ·ñÍ˻ص½Æðµã£¬±íÃ÷ÊÇ·ñÎ޽⡣ { cout<<"no solution for pos.x="<<startPos.x <<" and pos.y="<<startPos.y<<" total time is:" <<time(0) - startTime<<" tick is "<<tick<<" times"<<endl; break; } } tick++; // displayMove(); } cout<<" pos.x="<<startPos.x <<" and pos.y="<<startPos.y<<" total time is:" <<time(0) - startTime<<" tick is "<<tick<<" times"<<endl; if (solution) displayMove(); else cout<<"no solution!"<<endl; } } return 0; } void displayMove() { cout<<" A solution is as following:"<<endl; // cout<<" Starting from pos.x = "<<startPos.x<<" and pos.y = "<<startPos.y<<endl; cout<<" Total moves are "<<Counter<<endl; for (int i =0; i <= Step; i++) { cout<<" Tour["<<Level[i]<<"] "<<Tour[Level[i]]<<endl;//Êä³ö½á¹û¡£ } } int getPriority(int x, int y) { return priority[x][y]; } /* //x, y must return the smallest move pos which is the last one in array(big-->small) void saveTempMove(int &x, int &y, int moveNum) { int temp =0; for (int i=0; i< moveNum; i++) { if (getPriority(x, y) < priority[i])//??????????? { temp = priority[i]; priority[i] = while (i <= moveNum) { priority[ insertPriority(x, y); ; } } } */ void generatePriority() { int moves; for (int i =0; i< boardSize; i++) { for (int j=0; j< boardSize; j++) { moves =0; for (int direction =0; direction < 8; direction++) { if (testMove(direction)) { moves++; } } priority[i][j] = moves; } } } int direction2Priority(int direction) { int x, y; getMove(direction, x, y); return getPriority(x, y); } void Initialize(int x, int y) { startPos.x = x; startPos.y = y; for (int i=0; i< boardSize; i++) { for (int j=0; j < boardSize; j++) { board[i][j] =0; } } board[x][y] = 1; pos.x = x; pos.y = y; Step = 0; Counter = 0; Level[Step] = Counter; Tour[Counter] = -1; //ûÒâ˼µÄ¡£ solution = false; } void addStep() //Òƶ¯µ½Ð²㡣 { Step++; Level[Step] = Counter; } bool Evaluate() { if (Counter < 0) { cout<<"no"; solution =false; return true; } return (solution =(Step == boardSize * boardSize - 1)); } bool Generate() { int findPriority(int tempPriority, int start); void insertPriority(int curPos, int direction); void addStep(); int curPos=0, tempPriority; bool result = false; int row, col; int temp = Counter + 1; for (int direction =0; direction < 8; direction ++) { if (testMove(direction)) //²âÊÔ8¸ö·½Ïò¡£ { result = true; Counter ++; tempPriority = direction2Priority(direction); curPos = findPriority(tempPriority, temp); insertPriority(curPos, direction); } } if (result) //Òƶ¯µ½×îºóÒ»¸ö×ß·¨¡£ { // copyMoves(); getMove(Tour[Counter], row, col); pos.x = row; pos.y = col; board[row][col] = 1; //this is the point to move to. addStep(); } return result; } int findPriority(int tempPriority, int start) { for (int i=start; i < Counter; i++) { if (tempPriority >direction2Priority(Tour[i])) break; } return i; } void insertPriority(int curPos, int direction) { int hold=0, temp =0; hold = Tour[curPos]; Tour[curPos] = direction; for (int i = curPos + 1; i <= Counter + 1; i++) { temp = Tour[i]; Tour[i]= hold; hold = temp; } } bool stepPoint() { return (Counter == Level[Step - 1]); //²âÊÔÊÇ·ñÍ˻ص½ÉÏÒ»²ã¡£ } void Restore() { void counterMove(int lastMove); void moveStep(); board[pos.x][pos.y] = 0; //make unoccupied erase track counterMove(Tour[Counter]); //restore to parent pos Counter --; if (Counter <= 0) return; //back if (stepPoint()) //if it is parent { Step--; //use the upper level step Restore(); //keep going } else moveStep(); //simply make current node the step point } void moveStep() { Level[Step] = Counter; stepMove(Tour[Counter]); board[pos.x][pos.y] = 1; //Òƶ¯µ½ÐµľÍÒª±íʾÒѾռÓÃÁË¡£ } void getMove(int direction, int &x, int &y) { switch (direction) { case upleft: x = pos.x - 1; y = pos.y - 2; break; case upright: x = pos.x + 1; y = pos.y - 2; break; case downleft: x = pos.x - 1; y = pos.y + 2; break; case downright: x = pos.x + 1; y = pos.y + 2; break; case leftup: x = pos.x - 2; y = pos.y - 1; break; case leftdown: x = pos.x - 2; y = pos.y + 1; break; case rightup: x = pos.x + 2; y = pos.y - 1; break; case rightdown: x = pos.x + 2; y = pos.y + 1; break; } } bool testMove(int direction) { int x, y; getMove(direction, x, y); if ((x < boardSize)&&(x >= 0)&&(y < boardSize)&&(y >= 0)) //ÊÇ·ñ³ö½ç { if (board[x][y]== 0) //prevent x, y out of bound of board[][] if they are minus. so don't put logic op above. { return true; } } return false; } void stepMove(int direction) { int x, y; getMove(direction, x, y); pos.x = x; pos.y = y; } void counterMove(int lastMove) { int newMove; switch(lastMove) { case upleft: newMove = downright; break; case upright: newMove = downleft; break; case downleft: newMove = upright; break; case downright: newMove = upleft; break; case leftup: newMove = rightdown; break; case leftdown: newMove = rightup; break; case rightup: newMove = leftdown; break; case rightdown: newMove = leftup; break; } stepMove(newMove); }