Hello, OnlineGDB Q&A section lets you put your programming query to fellow community users. Asking a solution for whole assignment is strictly not allowed. You may ask for help where you are stuck. Try to add as much information as possible so that fellow users can know about your problem statement easily.

How to do backtracking code? where am I wrong?

+3 votes
asked Jul 9, 2021 by npatel300 (1,440 points)
#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] = 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;

}

1 Answer

0 votes
answered Jul 9, 2021 by Peter Minarik (55,660 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[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
    int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
    result[0][0] = 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 npatel300 (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 Peter Minarik (55,660 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.

Check out the relevant Wikipedia page: https://en.wikipedia.org/wiki/Knight%27s_tour

Finding all the possible scenarios with the naive implementation (you and I did) would take years on PCs.

But the 5x5 is doable in OK time
Welcome to OnlineGDB Q&A, where you can ask questions related to programming and OnlineGDB IDE and and receive answers from other members of the community.
...