马踏棋盘问题

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

定义：将马随机放在国际象棋的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;
    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);
}