The Knight's Tour problem in C isn't working for me

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
    }
}

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