0

I am very new to the algorithm. I just came to know about backtracking algorithm and saw a video for knight tour problem on youtube. The video solve the problem with knight starting from initial position as (0,0). I tried to implement it for any random position. This worked perfectly for 6*6 grid and i got output for 7*7 grid after 2 minutes. For 8*8 grid i waited for around 15 minutes but i didn't get any output. I tried to debug it using printf before calling solve function recursively.But i could not figure out anything. I don't know any optimization technique. I have just finished with my basic programming course in c.

Given code works perfectly if n is 8 and knight start from (0,0) position.In the place of solve(0,0,1) if i use solve(3,4,1) it does not give any output. 

#include<stdio.h>
#include<stdlib.h>

#define n 8

int solve(int,int,int);
int nextx(int ,int);
int nexty(int,int);
void print(void);


int grid[n][n]={0};

int main()
{
print();
printf("\n\n");
solve(3,2,1);
print();

return 0;
}
int solve(int x,int y,int number)
{
  if(number>(n*n)) return 1;
  int  move=0;

  if(grid[x][y]==0)
  {
        while(move<8)
        {
            if((nextx(x,move)!=-1)&&(nexty(y,move)!=-1))
               {
                 grid[x][y]=number;

                  if(solve(nextx(x,move),nexty(y,move),number+1))
                       return 1;

              }
              move++;
        }
        grid[x][y]=0;
  }

   return 0;

}

int nextx(int x,int move)
{
if(move==0) x=x+1;
else if(move==1) x=x+2;
else if(move==2) x=x+2;
else if(move==3) x=x+1;
else if(move==4) x=x-1;
else if(move==5) x=x-2;
else if(move==6) x=x-2;
else if(move==7) x=x-1;

if(x<0||x>(n-1))
    return (-1);
else

   return(x);

}
int nexty(int y,int move)
{
if(move==0) y=y-2;
else if(move==1) y=y-1;
else if(move==2) y=y+1;
else if(move==3) y=y+2;
else if(move==4) y=y+2;
else if(move==5) y=y+1;
else if(move==6) y=y-1;
else if(move==7) y=y-2;

if(y<0||y>(n-1))
    return (-1);
else
return(y);

}

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

}
Mukul
  • 310
  • 1
  • 6
  • 13
  • See this answer: https://stackoverflow.com/a/18074034/8513665 and also this Wiki link to "warnsdorf's rule" about taking the path of fewest options: https://en.wikipedia.org/wiki/Knight's_tour#Warnsdorf%27s_rule – Christian Gibbons Apr 17 '18 at 20:31
  • "output for 7*7 grid after 2 minutes. For 8*8 grid i waited for around 15 minutes" --> Consider using a different `n` for rows and columns, then code could try a 7*8 board before attempting the 8*8. – chux - Reinstate Monica Apr 17 '18 at 21:26
  • Tip: Add `static int depth = 0;if (number > depth) { printf("Depth %d\n", depth); depth = number; print(); }` to the beginning of `solve(int x, int y, int number)` to see how well code is progressing. – chux - Reinstate Monica Apr 17 '18 at 21:54

0 Answers0