Knight\'s Tour - backtracking algorithm Given an initial board position, determi

Question

Knight's Tour - backtracking algorithm
Given an initial board position, determine a sequence of moves by a knight that visits every square of the chessboard exactly once. Write a program that takes as input an initial board position and determines a sequence of moves by a knight that visits each square of the board exactly once.

http://books.google.com/books?id=LAU-BKWYdFYC&pg=PA393&lpg=PA393&dq=knights+tour+c%2B%2B+ds+malik&source=bl&ots=f8weP8wlZc&sig=CvTvye2fQSDWgAFpcxf39HZcuTk&hl=en&ei=e_cqTtyXNJCitgeLh5nXAg&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBUQ6AEwAA#v=onepage&q&f=false

Chapter 6 problem 19

Explanation / Answer

please rate - thanks

sample run

Enter initial row (0-7): 0
Enter initial column (0-7): 0
   1 12   9   6   3 14 17 20
10   7   2 13 18 21   4 15
31 28 11   8   5 16 19 22
64 25 32 29 36 23 48 45
33 30 27 24 49 46 37 58
26 63 52 35 40 57 44 47
53 34 61 50 55 42 59 38
62 51 54 41 60 39 56 43
Press any key to continue . . .

#include <iostream>
#include <iomanip>
using namespace std;
#define SIZE 8
void print(int [][SIZE]);
bool solve(int[][SIZE],int,int,int);
int main()
{int i,j,row,col;
int board[SIZE][SIZE];
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
    board[i][j]=0;
cout<<"Enter initial row (0-7): ";
cin>>row;
cout<<"Enter initial column (0-7): ";
cin>>col;
solve(board,row,col,0);
system("pause");
return 0;
}
void print(int board[][SIZE])
{int i,j;
for (i=0;i<SIZE;i++)
{for(j=0;j<SIZE;j++)
     cout<<setw(4)<<board[i][j];
   cout<<endl;
}
}
bool solve(int board[][8],int m,int n,int last)
{int i,j,mpi,npj;
board[m][n]=++last;
if(last==SIZE*SIZE)
     {print(board); // solved
     return true;
     }
for(i=-2;i<=2;i++)
    if(i!=0)
       for(j=-2;j<=2;j++)
          if(j!=0&&(i+j)%2!=0)
             {mpi=m+i;
             npj=n+j;
             if(mpi>=0&&mpi<SIZE&&npj>=0&&npj<SIZE&&board[mpi][npj]==0&&solve(board,mpi,npj,last))
                  return true;
             }
board[m][n]=0;
return false;
}

Related Questions

Navigate

• Browse (All)
• Browse K
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.