# Backtracking — Knight’s Tour Problem

Objec­tive : A knight’s tour is a sequence of moves of a knight on a chess­board such that the knight vis­its every square only once. If the knight ends on a square that is one knight’s move from the begin­ning square (so that it could tour the board again imme­di­ately, fol­low­ing the same path), the tour is closed, oth­er­wise it is open. (Source : http://en.wikipedia.org/wiki/Knight%27s_tour)

Exam­ple:

Path-foll0wed-by-Knight-to-cover-all-the-cells

Approach:

• Cre­ate a solu­tion matrix of the same struc­ture as chessboard.
• Start from 0,0 and index = 0. (index will rep­re­sent the no of cells has been cov­ered by the knight)
• Check cur­rent cell is not already used if not then mark that cell (start with 0 and keep incre­ment­ing it, it will show us the path for the knight).
• Check if index = N*N-1, means Knight has cov­ered all the cells. return true and print the solu­tion matrix.
• Now try to solve rest of the prob­lem recur­sively by mak­ing index +1. Check all 8 direc­tions. (Knight can move to 8 cells from its cur­rent posi­tion.) Check the bound­ary con­di­tions as well
• 8-moves-of-a-Knight

• If none of the 8 recur­sive calls return true, BACKTRACK and undo the changes ( put 0 to cor­re­spond­ing cell in solu­tion matrix) and return false.
• See the code for bet­ter understanding.

Code:

```Output:
00   59   38   33   30   17   08   63
37   34   31   60   09   62   29   16
58   01   36   39   32   27   18   07
35   48   41   26   61   10   15   28
42   57   02   49   40   23   06   19
47   50   45   54   25   20   11   14
56   43   52   03   22   13   24   05
51   46   55   44   53   04   21   12

```

#### You may also like...

• Jo Smith

The solu­tion pre­sented works quickly (mil­lisec­onds). How­ever, note that choice of order­ing of the pos­si­ble moves affects how quickly the result comes back.

For exam­ple, this alter­na­tive order­ing of moves doesn’t seem to ever return a result:

// go left and up
if (canMove(row — 1, col­umn — 2, N)
&& findPath(row — 1, col­umn — 2, index + 1, N)) {
return true;
}
// go left and down
if (canMove(row + 1, col­umn — 2, N)
&& findPath(row + 1, col­umn — 2, index + 1, N)) {
return true;
}
// go right and up
if (canMove(row — 1, col­umn + 2, N)
&& findPath(row — 1, col­umn + 2, index + 1, N)) {
return true;
}
// go down and right
if (canMove(row + 2, col­umn + 1, N)
&& findPath(row + 2, col­umn + 1, index + 1, N)) {
return true;
}
// go up and left
if (canMove(row — 2, col­umn — 1, N)
&& findPath(row — 2, col­umn — 1, index + 1, N)) {
return true;
}
// go down and left
if (canMove(row + 2, col­umn — 1, N)
&& findPath(row + 2, col­umn — 1, index + 1, N)) {
return true;
}
// go right and down
if (canMove(row + 1, col­umn + 2, N)
&& findPath(row + 1, col­umn + 2, index + 1, N)) {
return true;
}
// go up and right
if (canMove(row — 2, col­umn + 1, N)
&& findPath(row — 2, col­umn + 1, index + 1, N)) {
return true;
}

• Rox­ana Sarbu

What is the expla­na­tion for this , because , the­o­ret­i­cally , it should “enter ” in one of the cases above;
It depends on the start point also?
Thanks!

• Hore Hores

I noticed that if you changed the ini­tial start­ing point in this code, the result gets a lit­tle weird. The 00 spot is some­where ran­dom, and not con­nected with 01. Any thoughts?