#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;
 }