﻿ Knight's tour
The knight's tour

The knight's tour is a chess problem, whose goal is to visit exactly once all squares of an empty chessboard using the knight piece. This puzzle is well known since the middle ages – it was described by arab scholar Al-Adli in his work Kitab ash-shatranj (Book of chess).

The knight's tour has a surprisingly high number of solutions. For a common chessboard (8x8 squares), there exist 33 439 123 484 294 unoriented paths, through which the knight can go.

## Solution

The most simple solution to this puzzle is backtracking algorithm. Naive backtracking tends to be slow, because it can easily reach dead-end and has to reevaluate many decisions.

We can optimize the naive algorithm using the Warnsdorff's rule. When the knight has to choose next step, it will always proceed to the square, from which it has the fewest onwards moves. This heuristic reduces the probability that the knight won't be able to visit some square.

## Number of solutions

 Size of the chessboard Number of unoriented solutions 3x1 3x2 3x3 3x4 3x5 3x6 3x7 3x8 3x9 3x10 3x11 3x12 3x13 0 0 0 16 0 0 104 792 1 120 6 096 21 344 114 496 257 728

## Code

``` /**
* Backtracking Knight's tour solver
* @author Pavel Micka
*/
public class KnightsTour {

/**
* Indicator that the square was not visited yet
*/
private static int NOT_VISITED = -1;
/**
* Width of the chessboard
*/
private int xSize;
/**
* Height of the chessboard
*/
private int ySize;
/**
* Numver of solutions
*/
private int solutionsCount;
/**
* Solution board
* 0 -> Initial position of the knight
* 1 -> first move
* 2 -> second move
* .
* .
* .
* n -> n-th move
*/
private int[][] solutionBoard;

public static void main(String[] args) {
for (int i = 1; i < 20; i++) {
KnightsTour kt = new KnightsTour(3, i);
kt.solve();
System.out.println("<td>"+kt.solutionsCount+"</td>");
}
}

/**
* Constructor
* @param xSize width of the chessboard
* @param ySize height of the chessboard
*/
public KnightsTour(int xSize, int ySize) {
solutionsCount = 0;

this.xSize = xSize;
this.ySize = ySize;

solutionBoard = new int[ySize][xSize];
for (int i = 0; i < ySize; i++) {
for (int j = 0; j < xSize; j++) {
solutionBoard[i][j] = NOT_VISITED;
}
}
}

/**
* Solve the knight's tour
*/
public void solve() {
for (int i = 0; i < ySize; i++) {
for (int j = 0; j < xSize; j++) {
takeTurn(j, i, 0);
solutionBoard[i][j] = NOT_VISITED; //reset the square
}
}
}

/**
* Return possible destinations of the knight
* @param x x coord of the knight
* @param y y coord of the knight
* @return possible destinations of the knight
*/
private List<Coords> getFields(int x, int y) {
List<Coords> l = new ArrayList<Coords>();
if (x + 2 < xSize && y - 1 >= 0)
l.add(new Coords(x + 2, y - 1)); //right and upward
if (x + 1 < xSize && y - 2 >= 0)
l.add(new Coords(x + 1, y - 2)); //upward and right
if (x - 1 >= 0 && y - 2 >= 0)
l.add(new Coords(x - 1, y - 2)); //upward and left
if (x - 2 >= 0 && y - 1 >= 0)
l.add(new Coords(x - 2, y - 1)); //left and upward
if (x - 2 >= 0 && y + 1 < ySize)
l.add(new Coords(x - 2, y + 1)); //left and downward
if (x - 1 >= 0 && y + 2 < ySize)
l.add(new Coords(x - 1, y + 2)); //downward and left
if (x + 1 < xSize && y + 2 < ySize)
l.add(new Coords(x + 1, y + 2)); //downward and right
if (x + 2 < xSize && y + 1 < ySize)
l.add(new Coords(x + 2, y + 1)); //right and downward
return l;
}

/**
* Perform the move
* @param x destination x coord
* @param y destination y coord
* @param turnNr number of the move
*/
private void takeTurn(int x, int y, int turnNr) {
solutionBoard[y][x] = turnNr;
if (turnNr == (xSize * ySize) - 1) {
solutionsCount++;
printSolution();
return;
} else {
for (Coords c : getFields(x, y)) {
if (solutionBoard[c.getY()][c.getX()] == NOT_VISITED) {
takeTurn(c.getX(), c.getY(), turnNr + 1);
solutionBoard[c.getY()][c.getX()] = NOT_VISITED; //reset the square
}
}
}
}

/**
* Print out the solution
*/
private void printSolution() {
System.out.println("Solution #" + solutionsCount);
for (int i = 0; i < solutionBoard.length; i++) {
for (int j = 0; j < solutionBoard[i].length; j++) {
System.out.print(solutionBoard[i][j] + " ");
}
System.out.println("");
}
System.out.println("");
}

/**
* @return the solutionsCount
*/
public int getSolutionsCount() {
return solutionsCount;
}

/**
* Represents coordinates
*/
private class Coords {
private int x;
private int y;

public Coords(int x, int y) {
this.x = x;
this.y = y;
}

/**
* @return the x
*/
public int getX() {
return x;
}

/**
* @param x the x to set
*/
public void setX(int x) {
this.x = x;
}

/**
* @return the y
*/
public int getY() {
return y;
}

/**
* @param y the y to set
*/
public void setY(int y) {
this.y = y;
}
}
}
```
``` #include <iostream>
#include <vector>

using namespace std;
/**
* Backtracking Knight's tour solver
* @author Pavel Micka
*/
class KnightsTour {
private:
/**
* Indicator that the square was not visited yet
*/
static const int NOT_VISITED = -1;
/**
* Width of the chessboard
*/
int xSize;
/**
* Height of the chessboard
*/
int ySize;
/**
* Number of solutions
*/
int solutionsCount;
/**
* Solution array
* 0 -> Initial knight position
* 1 -> first move
* 2 -> second move
* .
* .
* .
* n -> n-th move
*/
int ** solutionBoard;

/**
* Represent coordinates
*/
class Coords {
private:
int x;
int y;
public:
Coords(int x, int y) {
this->x = x;
this->y = y;
}

/**
* @return the x
*/
int getX() {
return x;
}

/**
* @param x the x to set
*/
void setX(int x) {
this->x = x;
}

/**
* @return the y
*/
int getY() {
return y;
}

/**
* @param y the y to set
*/
void setY(int y) {
this->y = y;
}
};

/**
* Return possible destinations of the knight
* @param x x coord of the knight
* @param y y coord of the knight
* @param v vector reference, where the coordinates will be stored
*/
void getFields(int x, int y, vector<Coords> &v) {
if (x + 2 < xSize && y - 1 >= 0)
v.push_back(Coords(x + 2, y - 1)); //right and upward
if (x + 1 < xSize && y - 2 >= 0)
v.push_back(Coords(x + 1, y - 2)); //upward and right
if (x - 1 >= 0 && y - 2 >= 0)
v.push_back(Coords(x - 1, y - 2)); //upward and left
if (x - 2 >= 0 && y - 1 >= 0)
v.push_back(Coords(x - 2, y - 1)); //left and upward
if (x - 2 >= 0 && y + 1 < ySize)
v.push_back(Coords(x - 2, y + 1)); //left and downward
if (x - 1 >= 0 && y + 2 < ySize)
v.push_back(Coords(x - 1, y + 2)); //downward and left
if (x + 1 < xSize && y + 2 < ySize)
v.push_back(Coords(x + 1, y + 2)); //downward and right
if (x + 2 < xSize && y + 1 < ySize)
v.push_back(Coords(x + 2, y + 1)); //right and downward
}

/**
* Perform the move
* @param x destination x coord
* @param y destination y coord
* @param turnNr number of the move
*/
void takeTurn(int x, int y, int turnNr) {
solutionBoard[y][x] = turnNr;
if (turnNr == (xSize * ySize) - 1) {
solutionsCount++;
printSolution();
return;
} else {
vector<Coords> v;
getFields(x, y, v);
for(unsigned i = 0; i < v.size(); i++){
if (solutionBoard[v.at(i).getY()][v.at(i).getX()] == NOT_VISITED) {
takeTurn(v.at(i).getX(), v.at(i).getY(), turnNr + 1);
solutionBoard[v.at(i).getY()][v.at(i).getX()] = NOT_VISITED; //reset square
}
}
}
}

/**
* Print out the solution
*/
void printSolution() {
cout << "Reseni #" << solutionsCount << "\\n" ;
for (int i = 0; i < ySize; i++) {
for (int j = 0; j < xSize; j++) {
cout << solutionBoard[i][j] << " ";
}
cout << "\\n";
}
cout << "\\n";
}

public:
/**
* Constructor
* @param xSize width of the chessboard
* @param ySize height of the chessboard
*/
KnightsTour(int xSize, int ySize) {
solutionsCount = 0;

this->xSize = xSize;
this->ySize = ySize;

solutionBoard = new int*[ySize];
for(int i = 0; i < ySize; i++){
solutionBoard[i] = new int[xSize];
for (int j = 0; j < xSize; j++) {
solutionBoard[i][j] = NOT_VISITED;
}
}
}
~KnightsTour(){
for(int i = 0; i < ySize; i++) delete[] solutionBoard[i];
delete[] solutionBoard;
}

/**
* Solve the Knight's tour
*/
void solve() {
for (int i = 0; i < ySize; i++) {
for (int j = 0; j < xSize; j++) {
takeTurn(j, i, 0);
solutionBoard[i][j] = NOT_VISITED; //reset pole
}
}
}

/**
* @return the solutionsCount
*/
int getSolutionsCount() {
return solutionsCount;
}
};

int main(int argc, char* argv[]) {
KnightsTour t(3, 14);
t.solve();
system("pause");
return 0;
}

```