//http://w...content-available-to-author-only...s.org/archives/12916
#include <stdio.h>
#define N 8
int isSafe(int x, int y, int soln[][N])
{
if(x>=0 && x<N && y>=0 && y<N && soln[x][y]==-1){
return 1;
}
return 0;
}
int generateMoves(int x, int y, int moveNum, int soln[][N], int xMoves[], int yMoves[])//making move number 'moveNum' from x and y.
{
if(moveNum == N*N){
return 1;
}
else{
int i, nextX, nextY;
for(i=0; i<8; ++i){
nextX = x + xMoves[i];
nextY = y + yMoves[i];
if(isSafe(nextX, nextY, soln)){
soln[nextX][nextY] = moveNum;
if( generateMoves(nextX, nextY, moveNum+1, soln, xMoves, yMoves) ){
return 1;
}
else{
soln[nextX][nextY] = -1;
}
}
}
return 0;
}
}
void printSoln(int soln[][N])
{
int i, j;
for(i=0; i<N; ++i){
for(j=0; j<N; ++j){
printf("%2d ", soln[i][j]);
}
printf("\n");
}
}
void moveKnight()
{
int soln[N][N];
int i, j;
for(i=0; i<N; ++i){
for(j=0; j<N; ++j){
soln[i][j] = -1;
}
}
int xMoves[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMoves[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
soln[0][0] = 0; //making the first move i.e. putting the knight at (0, 0)
if( generateMoves(0, 0, 1, soln, xMoves, yMoves) ){
printSoln(soln);
}
else{
printf("\nNOT POSSIBLE\n");
}
}
int main()
{
moveKnight();
return 0;
}
Ly9odHRwOi8vdy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4ucy5vcmcvYXJjaGl2ZXMvMTI5MTYKCiNpbmNsdWRlIDxzdGRpby5oPgojZGVmaW5lIE4gOAoKaW50IGlzU2FmZShpbnQgeCwgaW50IHksIGludCBzb2xuW11bTl0pCnsKCWlmKHg+PTAgJiYgeDxOICYmIHk+PTAgJiYgeTxOICYmIHNvbG5beF1beV09PS0xKXsKCQlyZXR1cm4gMTsKCX0KCXJldHVybiAwOwp9CgppbnQgZ2VuZXJhdGVNb3ZlcyhpbnQgeCwgaW50IHksIGludCBtb3ZlTnVtLCBpbnQgc29sbltdW05dLCBpbnQgeE1vdmVzW10sIGludCB5TW92ZXNbXSkvL21ha2luZyBtb3ZlIG51bWJlciAnbW92ZU51bScgZnJvbSB4IGFuZCB5Lgp7CglpZihtb3ZlTnVtID09IE4qTil7CgkJcmV0dXJuIDE7Cgl9CgllbHNlewoJCWludCBpLCBuZXh0WCwgbmV4dFk7CgkJZm9yKGk9MDsgaTw4OyArK2kpewoJCQluZXh0WCA9IHggKyB4TW92ZXNbaV07CgkJCW5leHRZID0geSArIHlNb3Zlc1tpXTsKCQkJCgkJCWlmKGlzU2FmZShuZXh0WCwgbmV4dFksIHNvbG4pKXsKCQkJCXNvbG5bbmV4dFhdW25leHRZXSA9IG1vdmVOdW07CgkJCQlpZiggZ2VuZXJhdGVNb3ZlcyhuZXh0WCwgbmV4dFksIG1vdmVOdW0rMSwgc29sbiwgeE1vdmVzLCB5TW92ZXMpICl7CgkJCQkJcmV0dXJuIDE7CgkJCQl9CgkJCQllbHNlewoJCQkJCXNvbG5bbmV4dFhdW25leHRZXSA9IC0xOwoJCQkJfQoJCQl9CgkJfQoJCXJldHVybiAwOwoJfQp9Cgp2b2lkIHByaW50U29sbihpbnQgc29sbltdW05dKQp7CglpbnQgaSwgajsKCWZvcihpPTA7IGk8TjsgKytpKXsKCQlmb3Ioaj0wOyBqPE47ICsrail7CgkJCXByaW50ZigiJTJkICIsIHNvbG5baV1bal0pOwoJCX0KCQlwcmludGYoIlxuIik7Cgl9Cn0JCgp2b2lkIG1vdmVLbmlnaHQoKQp7CglpbnQgc29sbltOXVtOXTsKCWludCBpLCBqOwoJZm9yKGk9MDsgaTxOOyArK2kpewoJCWZvcihqPTA7IGo8TjsgKytqKXsJCgkJCXNvbG5baV1bal0gPSAtMTsKCQl9Cgl9CgkKICAgIGludCB4TW92ZXNbXSA9IHsgIDIsIDEsIC0xLCAtMiwgLTIsIC0xLCAgMSwgIDIgfTsKICAgIGludCB5TW92ZXNbXSA9IHsgIDEsIDIsICAyLCAgMSwgLTEsIC0yLCAtMiwgLTEgfTsKIAoJc29sblswXVswXSA9IDA7IC8vbWFraW5nIHRoZSBmaXJzdCBtb3ZlIGkuZS4gcHV0dGluZyB0aGUga25pZ2h0IGF0ICgwLCAwKQoJaWYoIGdlbmVyYXRlTW92ZXMoMCwgMCwgMSwgc29sbiwgeE1vdmVzLCB5TW92ZXMpICl7CgkJcHJpbnRTb2xuKHNvbG4pOwoJfQoJZWxzZXsKCQlwcmludGYoIlxuTk9UIFBPU1NJQkxFXG4iKTsKCX0KfQoKaW50IG1haW4oKQp7Cgltb3ZlS25pZ2h0KCk7CglyZXR1cm4gMDsKfQ==