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\n");
    scanf("%d", &x);
    printf("set y\n");
    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\t",szach[j][i]); }
            printf("\n\n");}
    printf("\n");
    return 0;
}

Answer 1

This is by no means an answer, just an idea that might be helpful.

I remember that for some sizes a simple spiral pattern will fill the outer edge of the board and reduce the problem to a simpler one with size smaller by 4.

You can use this idea to simplify your problem. For example, fill a 8x3 and a 8x5 board instead of a 8x8 board (you will have to update your algorithm to look for suitable ending position).

Answer 2

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.

Answer 3

ile's suggestions seem good. When I implemented just the one to consider first the candidates with lowest degree (number of possible moves from the position) in the graph (approximated by heading for the nearest of the four corners), the run time to find a solution for starting position x=2 and y=4 dropped from ten and a half hours to one minute and 15 seconds. The program changes are:

// arrays of possible knight moves, for example 2nd move is [1,2]
// rearranged so that adjacent moves differ by 45 angular degrees
int ruch_x[]={  2,  1, -1, -2, -2, -1,  1,  2};
int ruch_y[]={  1,  2,  2,  1, -1, -2, -2, -1};

#include <stdlib.h>

//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)
    {   static char firstmove[2][2][2] = { 1, 0, 6, 7, 2, 3, 5, 4 };
        int m = firstmove[x<size/2][y<size/2][abs(size-1-x*2)<abs(size-1-y*2)];
        for (int s=0; s<=7; s++) //loop that checks every possible knight move//
        {   static int ply[8] = { 0, -1, 1, -2, 2, -3, 3, -4 };
            int i = m+ply[s];   // firstmove towards corner, then back and forth
            if (i < 0) i += 8;
            else
            if (i > 7) i -= 8;
            // checking if candidate ...
            if (x+ruch_x[i]>=0&&x+ruch_x[i]<size    // not outside of the board
             && y+ruch_y[i]>=0&&y+ruch_y[i]<size
             && szach[x+ruch_x[i]][y+ruch_y[i]]==0  // not already visited
               )
                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;
}

By the way, the original program's behavior was not strictly defined, because szach[x+ruch_x[i]][y+ruch_y[i]] was checked before the check that x+ruch_x[i], y+ruch_y[i] is not outside of the board array.