+3 votes

#include <iostream>

using namespace std;

#define N 8

int knight_func(int x, int y, int movei, int result[N][N], int xMove[], int yMove[]);

int check(int x, int y, int result[N][N])

{

return (x >= 0 && x < N && y >= 0 && y < N && result[x][y] == -1);

}

void result(int result[N][N])

{

for (int x = 0; x < N; x++)

{

for (int y = 0; y < N; y++)

cout << " "<< result[x][y] << " ";

cout << endl;

}

}

int knight_func()

{

int result[N][N];

for (int x = 0; x < N; x++)

for (int y = 0; y < N; y++)

result[x][y] = -1;

int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };

int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

result[0][0] = 1;

if (knight_func(0, 0, 2, result, xMove, yMove) == -1)

{

cout << "false";

return 0;

}

else

{

cout << "Knight Tour found: " << endl;

for (int x = 0; x < N; x++)

{

for (int y = 0; y < N; y++)

{

printf("\t%d", result[x][y]);

}

printf("\n");

}

}

return 0;

}

int knight_func(int x, int y, int movei, int result[N][N], int xMove[N], int yMove[N])

{

if (movei == N * N)

return 1;

for (int k = 0; k < 8; k++)

{

int next_x = x + xMove[k];

int next_y = y + yMove[k];

if (check(next_x, next_y, result))

{

result[next_x][next_y] = movei;

if (knight_func(next_x, next_y, movei + 1, result, xMove, yMove) == 1)

return 1;

else

result[next_x][next_y] = -1;

}

}

return 0;

}

int main()

{

knight_func();

return 0;

}

using namespace std;

#define N 8

int knight_func(int x, int y, int movei, int result[N][N], int xMove[], int yMove[]);

int check(int x, int y, int result[N][N])

{

return (x >= 0 && x < N && y >= 0 && y < N && result[x][y] == -1);

}

void result(int result[N][N])

{

for (int x = 0; x < N; x++)

{

for (int y = 0; y < N; y++)

cout << " "<< result[x][y] << " ";

cout << endl;

}

}

int knight_func()

{

int result[N][N];

for (int x = 0; x < N; x++)

for (int y = 0; y < N; y++)

result[x][y] = -1;

int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };

int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

result[0][0] = 1;

if (knight_func(0, 0, 2, result, xMove, yMove) == -1)

{

cout << "false";

return 0;

}

else

{

cout << "Knight Tour found: " << endl;

for (int x = 0; x < N; x++)

{

for (int y = 0; y < N; y++)

{

printf("\t%d", result[x][y]);

}

printf("\n");

}

}

return 0;

}

int knight_func(int x, int y, int movei, int result[N][N], int xMove[N], int yMove[N])

{

if (movei == N * N)

return 1;

for (int k = 0; k < 8; k++)

{

int next_x = x + xMove[k];

int next_y = y + yMove[k];

if (check(next_x, next_y, result))

{

result[next_x][next_y] = movei;

if (knight_func(next_x, next_y, movei + 1, result, xMove, yMove) == 1)

return 1;

else

result[next_x][next_y] = -1;

}

}

return 0;

}

int main()

{

knight_func();

return 0;

}

0 votes

We have talked about this in http://question.onlinegdb.com/10407/how-to-do-backtracking-code-where-am-i-wrong.

Your code works fine and finds a solution for the 8x8 chess board starting from 0, 0.

I don't see the "-1" you're talking about.

Now I see what you meant. I just looked at the output and saw the chessboard and didn't validate all the results.

I have my own version of the problem (based on your solution, refactored here and there) and it works fine. So I compared it to yours to understand what going on.

Your problem is that in your knight_func() you return 1 (true), when you enter this function with movei being the last move.

But this is wrong because when you enter knight_func(), you haven't set your correct step into the given cell in the chessboard. That happens only later in line: result[next_x][next_y] = movei;

So your code could be fixed by saying that you're done when you're trying to do a step that is larger than the number of cells on the chessboard, as every existing step have already been validated (by the check() function).

```
int knight_func(int x, int y, int movei, int result[N][N], int xMove[N], int yMove[N])
{
if (movei == N * N + 1)
return 1;
for (int k = 0; k < 8; k++)
{
int next_x = x + xMove[k];
int next_y = y + yMove[k];
if (check(next_x, next_y, result))
{
result[next_x][next_y] = movei;
if (knight_func(next_x, next_y, movei + 1, result, xMove, yMove) == 1)
return 1;
else
result[next_x][next_y] = -1;
}
}
return 0;
}
```

commented
Jul 11
by
npatel300
(1,440 points)

When I run the code, it gives me 8 * 8 solution, but one of the number is -1, but the number should be 64. I am not able to figure out.

...