Find path to all 3 corners on a chessboard as a knight

user_14924147 0
Viewed 157

#include <stdio.h>

#define SIDE 8

#define VISITED 1
#define NOT_VISITED 0

#define FALSE 0
#define TRUE !FALSE

void printBoard(int board[][SIDE]);
int goHorsie(int board[][SIDE], int x, int y, int step, int cor1, int cor2, int cor3);

int main(void)
{

    int board[SIDE][SIDE] = { NOT_VISITED };
    int found = 0;

    found = goHorsie(board, 0, 0, 1, 0, 0, 0);

    if (found)
    {
        printf("Yes, there is a path from 0,0 through all corners! Here it is:\n");
        printBoard(board);
    }
    else
    {
        printf("No path from 0,0 through all corners\n");
        printBoard(board);
    }

    getchar();
    return 0;
}

int goHorsie(int board[][SIDE], int x, int y, int step, int cor1, int cor2, int cor3)
{
    int res = FALSE, check = 1;
    if (board[x][y] != NOT_VISITED //We were here already!
        || x >= SIDE || y >= SIDE || x < 0 || y < 0)
    {
        res = FALSE;
        check = 0;
    }

    if (x == 7 && y == 7)
    {
        printf("1)found!\n");
        cor1 = 1;
    }
    if (x == 7 && y == 0)
    {
        printf("2)found!\n");
        cor2 = 1;
    }
    if (x == 0 && y == 7)
    {
        printf("3)found!\n");
        cor3 = 1;
    }
    if (cor1 == 1 && cor2 == 1 && cor3 == 1)
    {
        printf("FOUND ALL!\n");
        return TRUE;
    }

    else if(check == 1)
    {
        board[x][y] = step;
        step++;
        res =
            goHorsie(board, x + 1, y - 2, step, cor1, cor2, cor3) ||
            goHorsie(board, x + 2, y + 1, step, cor1, cor2, cor3) ||
            goHorsie(board, x + 2, y - 1, step, cor1, cor2, cor3) ||
            goHorsie(board, x + 1, y + 2, step, cor1, cor2, cor3) ||
            goHorsie(board, x - 2, y + 1, step, cor1, cor2, cor3) ||
            goHorsie(board, x - 2, y - 1, step, cor1, cor2, cor3) ||
            goHorsie(board, x - 1, y + 2, step, cor1, cor2, cor3) ||
            goHorsie(board, x + 1, y - 2, step, cor1, cor2, cor3);
            
        if (!res)
        {
            board[x][y] = NOT_VISITED;
        }
    }
    return res;
}


void printBoard(int board[][SIDE])
{
    int i = 0, j = 0;
    for (int i = 0; i < SIDE; i++)
    {
        for (int j = 0; j < SIDE; j++)
        {
            printf("%3d", board[i][j]);
        }
        printf("\n");
    }
}

I'm using recursion to find the path to all 3 corners.

I ran the program for about 20min now and it's still didn't get to the solution.

Ik why its taking too long but not sure if it will even get me to the answer, and I think it's looping forever.

So my question is did I make the function right and will it eventually give me the right answer (the path to all 3 corners), or what do I need to change in order to get to the answer.

What I mean by 3 corners is: top right, bottom right and bottom left.

knights-tour chess recursion c
2 Answers

There may be other bugs but here is one:

if (board[x][y] != NOT_VISITED || x >= SIDE || y >= SIDE || x < 0 || y < 0)

Evaluation of this expression starts with board[x][y] != NOT_VISITED. At that time x and y may have values that are outside the board. So you do out-of-bounds access.

Check the values of x and y before accessing the array.

Like:

if (x >= SIDE || y >= SIDE || x < 0 || y < 0 || board[x][y] != NOT_VISITED)

Another issue is that you check for "found" before you check whether you have already visited that corner once. That will give some unexpected prints of "found".

This line:

if (x >= SIDE || y >= SIDE || x < 0 || y < 0 || board[x][y] != NOT_VISITED)

shall be the very first statement in the function.

One more bug

        goHorsie(board, x + 1, y - 2, step, cor1, cor2, cor3) ||
        goHorsie(board, x + 2, y + 1, step, cor1, cor2, cor3) ||
        goHorsie(board, x + 2, y - 1, step, cor1, cor2, cor3) ||
        goHorsie(board, x + 1, y + 2, step, cor1, cor2, cor3) ||
        goHorsie(board, x - 2, y + 1, step, cor1, cor2, cor3) ||
        goHorsie(board, x - 2, y - 1, step, cor1, cor2, cor3) ||
        goHorsie(board, x - 1, y + 2, step, cor1, cor2, cor3) ||
        goHorsie(board, x + 1, y - 2, step, cor1, cor2, cor3);

the first and the last line are using the same expression, i.e. x + 1 and y - 2. So your code doesn't cover all 8 moves. It uses one move twice.

I ran the program for about 20min now and it's still didn't get to the solution.

Once you have fixed the bugs reported above, you can give it a try... but don't be surprised if you still next no solution within 20 minutes.

The thing is that there are so many paths to check that even modern computers will spend quite some time solving this.

Consider this:

step 1: 8 paths
step 2: 8 paths
step 3: 8 paths
...
step 16: 8 paths

In total 281.474.976.710.656 paths.... okay, it's not that bad because many of these path will stop before getting to step 16 because the horse leaves the board or returns to the same position. But still... there are many paths to check.

And can it be done in 16 steps? What it it requires 20 steps.. that is 1.152.921.504.606.846.976 or could it even require 64 steps!? 8^64 paths to check...

So to find a solution you should think differently than just brute force checking.

By fixing the order the corner was to be visited and by setting some restriction on the direction to move, I came up with this:

enter image description here

This solution shows that you can visit all 4 corners in 20 moves.

user_43864270

This answer builds on the one by user 4386427, put them together to get a complete solution.

With int goHorsie(int board[][SIDE], int x, int y, int step, int cor1, int cor2, int cor3); you are always using copies of the information whether you found the three corners, from the current recursion. If you actually find one or two corners, but not all three in one recursive call, then the true values for those new finds are lost as soon as the recursion is left. In the next call you might find the missing corner(s) but not notice, because the info on previous finds is lost.

In order to keep infos on finds you could switch to pointer paramters.

int goHorsie(int board[][SIDE], int x, int y, int step, int* cor1, int* cor2, int* cor3);

and e.g. *cor1 = 1;

For that you need to introduce corresponding referencable variables inside main()

int maincor1 =0; etc.

and call from main() like found = goHorsie(board, 0, 0, 1, &maincor1, &maincor2, &maincor3);

and from inside still like

goHorsie(board, x + 1, y - 2, step, cor1, cor2, cor3)

which is identical code but uses the now pointer variables of same name as before.

user_77334180
Related