c - Knight's tour algorithm

Question

So I have to write this algorithm (this version does not need to end in the same spot that knight started), and I got it to work, but it's too slow. It works with starting positions x=0 and y=0 for size=8, but if I try to manipulate x and y to for example 2 and 4 it doesn't end after a few minutes. Can anyone help?

#include <stdio.h>
#define size 8
int ruch_x[]={ -1,  1, -2,  2, -2,  2, -1,  1}; //arrays of possible knight moves, for example 2nd move is [1,2]//
int ruch_y[]={  2,  2,  1,  1, -1, -1, -2, -2};

int done(int szach[][size])
{
   for(int i=0;i<size;i++)
   {
      for(int j=0;j<size;j++)
      {
         if(szach[i][j]==0)
            return 0;
      }
   }
   return 1;
}
//licz - variable for counting knights moves//
void konik(int szach[][size], int x, int y, int licz)
{
    szach[x][y]=licz;
    if(licz<size*size){
        for(int i=0;i<=7;i++){ //loop that checks every possible knight move//
            if(szach[x+ruch_x[i]][y+ruch_y[i]]==0&&x+ruch_x[i]>=0&&x+ruch_x[i]<size&&y+ruch_y[i]>=0&&y+ruch_y[i]<size)
// checking if candidat was already visited and if it's not outside of the board//
            {
                konik(szach, x+ruch_x[i], y+ruch_y[i], licz+1);}}}

    if(done(szach)==1) return; //checking if whole board is filled with numbers, if yes then skip zeroing current move//
    szach[x][y]=0;
}

int main()
{
    int i, j, x,y;
    printf("set x
");
    scanf("%d", &x);
    printf("set y
");
    scanf("%d", &y);

    int szach[size][size];
    for(i=0;i<size;i++) {  //zeroing array//
            for(j=0;j<size; j++) {
                    szach[i][j]=0; }}
    konik(szach, x, y, 1);

    for(int i=0;i<size;i++) {
            for(int j=0;j<size; j++) {
                    printf("%d	",szach[j][i]); }
            printf("

");}
    printf("
");
    return 0;
}

Answer 1

It is probably a bad idea to simply brute-force, as the number of possible sequences can exceed 10^50 for 8x8 board.

Knight's tour article on wikipedia has decent information on the problem, I would recommend to start from there.

One of the most famous heuristics for finding Hamiltonian Path is the following: from any node u order the neighbours in non-decreasing order by their degrees in the graph. Let's say from u the knight can move to p and q (i.e. u has two neighbours), then in your recursion consider initially p if it has less available neighbours than q. This usually leads to to significant optimizations, especially if the graph has a lot of Hamilton Paths as in this case.

Regarding your code. You don't need to call done() everytime. If at any moment licz >= size*size, then you know that you found your answer. You can store a global boolean done instead for example. This should help a little bit, but won't help in all cases.

P.S. If you need any single solution for your project, I would recommend to store a single Hamilton cycle, and for any x,y just simply shift the sequence to get a valid solution.