# How to do backtracking code? where am I wrong?

#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 = { 2, 1, -1, -2, -2, -1, 1, 2 };

int yMove = { 1, 2, 2, 1, -1, -2, -2, -1 };

result = 0;

/* Start from 0,0 and explore all tours using

solveKTUtil() */

if (knight_func(0, 0, 1, result, xMove, yMove) == 0) {

cout << "false";

return 0;

}

else

(result);

return 0;

}

int knight_func(int x, int y, int movei, int result[N][N],

int xMove[N], int yMove[N])

{

int k, next_x, next_y;

if (movei == N * N)

return 1;

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

next_x = x + xMove[k];

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;

}

answered Jul 9, 2021 by (77,930 points)
edited Jul 9, 2021 by Peter Minarik

Your code works, actually. If finds the first viable series of steps for an N x N chessboard.

If you replace the (result); with an actual function that prints out the result array than you can see it worked.

Maybe you can try to find all possible solutions, not just one of them. ;)

One more thing: I'm not sure if you're supposed to find a solution for starting from one of the corner, or you can start from anywhere (because the latter is not covered by your code). If my code is correct for a 4x4 chess board, there are 1728 different ways to cover with the knight (assuming 90 degree rotations are different solutions).

Some general tips for posting questions:

• It is a good idea to tell what your program is supposed to do, so others won't have to spend time figuring out what it may be doing.
• Include what you think is wrong with your code. Specify your question. What do you think is supposed to happen but does not happen (or vice versa).
• You can use Format/Formatted to make your piece of code look better.

Good luck!

Your code after reformatting (using Format/Formatter) would look like this:

```#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 = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove = { 1, 2, 2, 1, -1, -2, -2, -1 };
result = 0;

/* Start from 0,0 and explore all tours using solveKTUtil() */
if (knight_func(0, 0, 1, result, xMove, yMove) == 0)
{
cout << "false";
return 0;
}
else
{
std::cout << "Solution: " << std::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;
}```
commented Jul 9, 2021 by (1,440 points)
I have to find solution from starting one of the corner, not from anywhere. How should I suppose to do it? I am confused.
commented Jul 10, 2021 by (77,930 points)
Right now you are starting from one of the corners (top left: 0, 0).

If you'd need to cover every possible scenario, then you need to try to start from all locations, when you finished the previous one.

So check 0,0; then 0,1; then 0, 2; .... then 1, 0; then 1, 1, ...; and so on.

Finding all the possible solutions can be time-consuming.