The 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 3x1 3x2 3x3 3x4 3x5 3x6 3x7 3x8 3x9 3x10 3x11 3x12 3x13
Number of unoriented solutions 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;
 }
 
 

Sources








       
 

Place for your banner

Here is the position ready for our customer's banners.