#include <iostream>
#include <stdio.h>
using namespace std;
#define N 8
void OutputArr(int A[N][N])
{
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
cout << A[i][j] << " ";
}
cout << endl;
}
}
// Check if the move is available
int isSafe(int x, int y, int A[N][N])
{
if(x >= 0 &&
y >= 0 &&
x < N &&
y < N &&
A[x][y] == -1) // If the square is still not visited
return 1;
return 0;
}
int BackTrack(int sol[N][N], int xMove[N], int yMove[N], int x, int y,
int Move)
{
int k, next_x, next_y;
if(Move == N * N){
return true;
}
// Try all next moves
for(k = 0; k < N; k++){
next_x = x + xMove[k];
next_y = y + yMove[k];
if(isSafe(next_x, next_y, sol)){
sol[next_x][next_y] = Move;
if(BackTrack(sol, xMove, yMove, next_x, next_y, Move + 1) == true){
return true;
}
else // Backtrack, mark that the path is fail
sol[next_x][next_y] = -1;
}
}
return false;
}
bool Solve()
{
int sol[N][N];
// Set up the "board"
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
sol[i][j] = -1;
}
}
// Square that the Knight can move to
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
// Where the knight starts
sol[0][0] = 0;
if(BackTrack(sol, xMove, yMove, 0, 0, 1) == false){
cout << "No solution." << endl;
return false;
}
else{
OutputArr(sol);
}
return true;
}
int main()
{
Solve();
getchar();
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RkaW8uaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBOIDgKCgoKdm9pZCBPdXRwdXRBcnIoaW50IEFbTl1bTl0pCnsKCiAgICBmb3IoaW50IGkgPSAwOyBpIDwgTjsgaSsrKXsKCWZvcihpbnQgaiA9IDA7IGogPCBOOyBqKyspewoJCWNvdXQgPDwgQVtpXVtqXSA8PCAiICI7Cgl9Cgljb3V0IDw8IGVuZGw7Cn0KfQoKLy8gQ2hlY2sgaWYgdGhlIG1vdmUgaXMgYXZhaWxhYmxlCmludCBpc1NhZmUoaW50IHgsIGludCB5LCBpbnQgQVtOXVtOXSkKewoJaWYoeCA+PSAwICYmCgkgICB5ID49IDAgJiYKCSAgIHggPCBOICYmCgkgICB5IDwgTiAmJgoJICAgQVt4XVt5XSA9PSAtMSkgLy8gSWYgdGhlIHNxdWFyZSBpcyBzdGlsbCBub3QgdmlzaXRlZAoJCXJldHVybiAxOwoJcmV0dXJuIDA7Cn0KCmludCBCYWNrVHJhY2soaW50IHNvbFtOXVtOXSwgaW50IHhNb3ZlW05dLCBpbnQgeU1vdmVbTl0sIGludCB4LCBpbnQgeSwKCWludCBNb3ZlKQp7CglpbnQgaywgbmV4dF94LCBuZXh0X3k7CglpZihNb3ZlID09IE4gKiBOKXsKCQlyZXR1cm4gdHJ1ZTsKCX0KCiAgICAvLyBUcnkgYWxsIG5leHQgbW92ZXMKZm9yKGsgPSAwOyBrIDwgTjsgaysrKXsKCW5leHRfeCA9IHggKyB4TW92ZVtrXTsKCW5leHRfeSA9IHkgKyB5TW92ZVtrXTsKCWlmKGlzU2FmZShuZXh0X3gsIG5leHRfeSwgc29sKSl7CgkJc29sW25leHRfeF1bbmV4dF95XSA9IE1vdmU7CgkJaWYoQmFja1RyYWNrKHNvbCwgeE1vdmUsIHlNb3ZlLCBuZXh0X3gsIG5leHRfeSwgTW92ZSArIDEpID09IHRydWUpewoJCQlyZXR1cm4gdHJ1ZTsKCQl9CgkJZWxzZSAvLyBCYWNrdHJhY2ssIG1hcmsgdGhhdCB0aGUgcGF0aCBpcyBmYWlsCgkJCXNvbFtuZXh0X3hdW25leHRfeV0gPSAtMTsKCX0KfQpyZXR1cm4gZmFsc2U7Cn0KCmJvb2wgU29sdmUoKQp7CglpbnQgc29sW05dW05dOwoKICAgIC8vIFNldCB1cCB0aGUgImJvYXJkIgpmb3IoaW50IGkgPSAwOyBpIDwgTjsgaSsrKXsKCWZvcihpbnQgaiA9IDA7IGogPCBOOyBqKyspewoJCXNvbFtpXVtqXSA9IC0xOwoJfQp9CgovLyBTcXVhcmUgdGhhdCB0aGUgS25pZ2h0IGNhbiBtb3ZlIHRvCmludCB4TW92ZVs4XSA9IHsgIDIsIDEsIC0xLCAtMiwgLTIsIC0xLCAgMSwgIDIgfTsKaW50IHlNb3ZlWzhdID0geyAgMSwgMiwgIDIsICAxLCAtMSwgLTIsIC0yLCAtMSB9OwoKLy8gV2hlcmUgdGhlIGtuaWdodCBzdGFydHMKc29sWzBdWzBdID0gMDsKCmlmKEJhY2tUcmFjayhzb2wsIHhNb3ZlLCB5TW92ZSwgMCwgMCwgMSkgPT0gZmFsc2UpewoJY291dCA8PCAiTm8gc29sdXRpb24uIiA8PCBlbmRsOwoJcmV0dXJuIGZhbHNlOwp9CmVsc2V7CglPdXRwdXRBcnIoc29sKTsKfQpyZXR1cm4gdHJ1ZTsKfQoKaW50IG1haW4oKQp7CglTb2x2ZSgpOwogICAgZ2V0Y2hhcigpOwoJcmV0dXJuIDA7Cn0=