马踏棋盘问题

马踏棋盘问题(骑士周游问题)

定义：将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。

这是实际上和八皇后是同一种性质的问题，都用到了回溯的思想，有接进行下一个，不行了退回去，在进行尝试。

#include<stdio.h>#include<stdlib.h>  #include<conio.h> #define CHESS_SIZE 8 int chessBoard[CHESS_SIZE][CHESS_SIZE] = {0}; int cnt = 1;     // 记录马的位置  int n = 1;  int move[8][2]={       {1,-2},{2,-1},      {2,1},{1,2},      {-1,2},{-2,1},      {-2,-1},{-1,-2}      }; void showChessBoard();void traverseChessBoard(int x,int y);void traverseChessBoard(int x,int y)   //执行过程  {      int i;	int a;    int b;	int cnt;    for(i = 0;i < CHESS_SIZE;i++){          a = x + move[i][0];          b = y + move[i][1];          if(a >= 0 && a < CHESS_SIZE && b >= 0 && b < CHESS_SIZE && !chessBoard[a][b]){               chessBoard[a][b] = ++cnt;              if(cnt < 64){				traverseChessBoard(a,b);                  }                     // 递归              else{  				showChessBoard();                }                      chessBoard[a][b] = 0;//修改ab的值归为0                  cnt--;  		}	}  }	void showChessBoard()          //输出马踏棋盘  {	int i;	int j;    PRintf("输出第%d组解：/n",n++);      for(i = 0;i < CHESS_SIZE;i++){          for(j = 0;j < CHESS_SIZE;j++)              printf("%3d ",chessBoard[i][j]);      printf("/n");      }  }  void main(void){	chessBoard[0][0] = 1;      traverseChessBoard(0,0);}