馬踏棋盤問題(騎士周游問題)

定義：將馬隨機(jī)放在國(guó)際象棋的8×8棋盤Board[0～7][0～7]的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。要求每個(gè)方格只進(jìn)入一次，走遍棋盤上全部64個(gè)方格。

這是實(shí)際上和八皇后是同一種性質(zhì)的問題，都用到了回溯的思想，有接進(jìn)行下一個(gè)，不行了退回去，在進(jìn)行嘗試。

#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)   //執(zhí)行過程  {      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);}