0

I wrote this program that did something similar to the knight's tour problem and decided to try and get the same program to solve the knight's tour without changing too much of the code. Unfortunately I was not able to do it, not because it wasn't possible, but I just didn't really know what the problem was. I looked up other programs for the Knight's Tour Problem online and they seem to work on the same principles. So what's my problem exactly?

I run the code and nothing shows up. Basically the recursion keeps on going forever (it might stop at some point but it kept going for 3 minutes straight when I tested it, when it really shouldn't take more than a second or 2).

#include <stdio.h>
#include <stdlib.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 main(void)
{
    int board[SIDE][SIDE] = { NOT_VISITED };
    if (goHorsie(board, 0, 0, 1))
    {
        printf("Yes, the knight\'s tour problem is possible, here is the result:\n");
        printBoard(board);
    }
    else
    {
        printf("No, the knight\'s tour problem is not possible.\n");
    }
    return 0;
}


/*
This function checks if knight can travel through the entire board while only stepping on every square once.
input: the board, the position's x and y, and current step.
output: whether a path was found.
*/
int goHorsie(int board[][SIDE], int x, int y, int step)
{
    int res = FALSE;

    if (step == (SIDE * SIDE + 1))
    {
        res = TRUE;
    }
    else if (x >= SIDE || y >= SIDE || x < 0 || y < 0 || // out of the board
        board[x][y] != NOT_VISITED) // we were here already!
    {
        res = FALSE;
    }
    else
    {
        board[x][y] = step;
        step++;

        // changing order here will change the path, because once a condition is verified (TRUE) the rest aren't checked
        res = goHorsie(board, x + 2, y + 1, step) ||
            goHorsie(board, x + 2, y - 1, step) ||
            goHorsie(board, x + 1, y + 2, step) ||
            goHorsie(board, x + 1, y - 2, step) ||
            goHorsie(board, x - 2, y + 1, step) ||
            goHorsie(board, x - 2, y - 1, step) ||
            goHorsie(board, x - 1, y + 2, step) ||
            goHorsie(board, x - 1, y - 2, step);

        if (!res)
        {
            board[x][y] = NOT_VISITED;
        }
    }

    return res;
}


/*
This function prints the board.
input: board to print.
output: none.
*/
void printBoard(int board[][SIDE])
{
    int i = 0, j = 0;

    for (i = 0; i < SIDE; i++)
    {
        for (j = 0; j < SIDE; j++)
        {
            printf("%3d", board[i][j]);
        }
        printf("\n"); // go down a line
    }
}
mkrieger1
  • 19,194
  • 5
  • 54
  • 65
why
  • 37
  • 4
  • You should be more precise on what doens't work as expected in your program. *what's my problem exactly?* is not focused enough to make people help you. – M. Yousfi May 15 '23 at 21:15
  • @MustaphaYousfi updated the post, hopefully my problem is more understood now. – why May 15 '23 at 21:19
  • See e.g. https://stackoverflow.com/questions/7491333/my-knights-tour-algorithm-possibly-is-running-on-an-infinite-loop?rq=2#comment9068556_7491333 and https://stackoverflow.com/questions/8402648/how-to-improve-knights-tour-with-warnsdorffs-rule?rq=2 – Bob__ May 16 '23 at 00:13
  • 1
    It seems the order of the moves affects the speed of convergence by chance. Try: `res = goHorsie(board, x + 2, y + 1, step) || goHorsie(board, x + 1, y + 2, step) || goHorsie(board, x - 1, y + 2, step) || goHorsie(board, x - 2, y + 1, step) || goHorsie(board, x - 2, y - 1, step) || goHorsie(board, x - 1, y - 2, step) || goHorsie(board, x + 1, y - 2, step) || goHorsie(board, x + 2, y - 1, step);`. – tshiono May 16 '23 at 00:43

1 Answers1

1

There's nothing obviously wrong with your code. It would terminate with a solution. Eventually. After trying maybe 1050 moves. You need a better heuristic for picking the next move. Look at the Wikipedia page for Warnsdorff's rule.

Mark Adler
  • 101,978
  • 13
  • 118
  • 158
  • Glad to know my code wasn't necessarily the problem. Thank you! – why May 16 '23 at 11:11
  • 1
    Well, it kinda is. Not arriving at a solution until the heat death of the universe should be considered a bug. – Mark Adler May 16 '23 at 14:47
  • I meant more like a problem with my logic or a part of the code wasn't being executed like I intended it to, Sure you can consider it as a bug but because all I had to do was change the order of those lines I'll take that as a win. – why May 16 '23 at 15:44