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.

why am I getting -1 in my solution for 8*8 chessboard? Where is my mistake?

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

1 Answer

0 votes
answered Jul 11, 2021 by Peter Minarik (84,720 points)
edited Jul 15, 2021 by Peter Minarik

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.

Update

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, 2021 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.
commented Jul 12, 2021 by Peter Minarik (84,720 points)
Thanks, now I see what you meant by the -1 value. I've updated my original answer.
commented Jul 12, 2021 by npatel300 (1,440 points)
Thank you for the help. It worked.
commented Jul 12, 2021 by Peter Minarik (84,720 points)
My pleasure.
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.
...