knight.cpp

// 巡回騎士問題 Knight's tour

#include <iostream> 
#include <iomanip>

using namespace std;

#define N 5

// 盤
int b[N][N];

// 移動規則
int dx[8]={2, 1,-1,-2,-2,-1, 1, 2};
int dy[8]={1, 2, 2, 1,-1,-2,-2,-1};

// １つ目が見つかったかどうかのフラグ
bool f1=false; 

// 盤面表示
void printBoard()
{
	for(int j=0; j<N; j++){
		for(int i=0; i<N; i++){
			cout << setw(3) << b[i][j];
		}
		cout << endl;
	}
	cout << endl;
}

// (x,y)から移動できる場所を探す
void search(int x, int y)
{
	static int ct=0;
	
	// すでに答えが見つかってれば探索しない
	if(f1) return;
	// すでに訪れていれば探索しない
	if(b[x][y]!=0) return;
	
	// 訪問したことにする(順番を入れる)
	b[x][y]=++ct;
	// ２５番目だったら表示して終了
	if(ct==N*N){
		printBoard();
		f1=true;
	}else{
		// ８方向に移動を試みる
		for(int i=0; i<8; i++){
			// 盤面をはみ出していなかったら
			if(x+dx[i]>=0 && x+dx[i]<N && y+dy[i]>=0 && y+dy[i]<N){
				// 移動する
				search(x+dx[i], y+dy[i]);
			}
		}
		// ここに来るということは移動に失敗したのでクリア
		b[x][y]=0;
		ct--;
	}
}

main()
{
	// 初期化
	for(int j=0; j<N; j++){
		for(int i=0; i<N; i++){
			b[i][j]=0;
		}
	}
	
	//左上から探索
	search(0,0);
}