// --------------------------------------------------------------
// In chess a knight moves in an 'L' pattern, for example:
// 
//    [ ][ ][ ][ ][ ][ ][ ][ ]
//    [ ][ ][x][ ][x][ ][ ][ ]
//    [ ][x][ ][ ][ ][x][ ][ ]
//    [ ][ ][ ][K][ ][ ][ ][ ]
//    [ ][x][ ][ ][ ][x][ ][ ]
//    [ ][ ][x][ ][x][ ][ ][ ]
//    [ ][ ][ ][ ][ ][ ][ ][ ]
//    [ ][ ][ ][ ][ ][ ][ ][ ]
// 
// Given a board with dimensions (n, m) and a
// starting position (row, column) find a path whereby
// the knight can traverse every square on the board
// without landing on any square more than once.
//
// We start by setting up a table of all available legal moves
// starting from each of the n * m squares.
//
// We then begin from our starting square and try each
// legal move recursively continuing this process until
// we either run out of possibilities or succeed
// in finding a solution.
//
// Here is an example path found by this program
// using an 8 x 8 chess board:
//
//    64 49 22 37 24 35 60 31
//    51 38 63 34 61 32 25  8
//    48 21 50 23 36  9 30 59
//    39 52  1 62 33 58  7 26
//    20 47 18 43 16 27 10 29
//    53 40 55  2 57  4 13  6
//    46 19 42 17 44 15 28 11
//    41 54 45 56  3 12  5 14
//
// Note that all numbers from 1 -> 64 are present
// and for each number 'n' the square containing the
// next number 'n + 1' is always reachable via the
// 'L' pattern discussed above.
//
// To compile this code:
//    unix : g++ -W -Wall knight.cpp
//    win32: cl -W3 -GX knight.cpp
// --------------------------------------------------------------

/*****************************************************************
 * C/C++ Headers, Using Declarations
 *****************************************************************/

#include <vector>
#include <stdio.h>

using std::vector;

/*****************************************************************
 * Local Defines
 *****************************************************************/

#define DEFAULT_ROWS    8
#define DEFAULT_COLUMNS 8

/*****************************************************************
 * Local Structs/Typedefs
 *****************************************************************/

struct Move
{
   int mRow;
   int mColumn;

   Move(int row, int column) : mRow(row), mColumn(column) {}
};

typedef vector<Move>      Moves;
typedef vector<Moves>     MovesList;
typedef vector<MovesList> MovesListList;

typedef vector<bool>   Flags;
typedef vector<Flags>  FlagsList;
typedef vector<int>    Values;
typedef vector<Values> ValuesList;

/*****************************************************************
 * Declaration Of Class: Knight
 *****************************************************************/

class Knight
{
   public:
      Knight();
      Knight(int rows, int columns);
      bool findSolution(int startRow, int startColumn, ValuesList &order);

   private:
      void init(int rows, int columns);
      void doMove(int currentRow, int currentColumn);

   private:
      bool          mFirst;
      int           mRows;
      int           mColumns;
      MovesListList mLegalMoves;
      FlagsList     mUsed;
      ValuesList    mOrder;
      int           mSquaresVisited;
      bool          mSolutionFound;
};

/*****************************************************************
 * Definition Of Class: Knight
 *****************************************************************/

Knight::Knight()
{
   init(DEFAULT_ROWS, DEFAULT_COLUMNS);
}

Knight::Knight(int rows, int columns)
{
   init(rows, columns);
}

bool Knight::findSolution(int startRow, int startColumn, ValuesList &order)
{
   if(mFirst)
   {
      mFirst = false;
   }
   else
   {
      for(int i = 0; i < mRows; i ++)
      {
         for(int j = 0; j < mRows; j ++)
         {
            mUsed[i][j]  = false;
            mOrder[i][j] = 0;
         }
      }
   }

   mSquaresVisited = 0;
   mSolutionFound  = false;

   doMove(startRow, startColumn);

   if(mSolutionFound)
      order = mOrder;

   return(mSolutionFound);
}

void Knight::init(int rows, int columns)
{
   mFirst   = true;
   mRows    = rows;
   mColumns = columns;

   // the set of legal moves (in terms of row/column offsets)
   // that a knight can make

   int offsets[][2] =
   {
      {  2,  1 }, {  2, -1 }, { -2,  1 }, { -2, -1 },
      {  1,  2 }, {  1, -2 }, { -1,  2 }, { -1, -2 }
   };

   int nOffsets = sizeof(offsets) / sizeof(offsets[0]);

   for(int i = 0; i < mRows; i ++)
   {
      Flags     theFlags;
      Values    theValues;
      MovesList theList;

      for(int j = 0; j < mColumns; j ++)
      {
         theFlags.push_back(false);
         theValues.push_back(0);

         Moves theMoves;

         for(int k = 0; k < nOffsets; k ++)
         {
            int r = i + offsets[k][0];
            int c = j + offsets[k][1];

            // only record as legal moves
            // those moves that keep the knight within
            // the boundaries of the board

            if(r >= 0 && r < rows && c >= 0 && c < columns)
               theMoves.push_back(Move(r, c));
         }

         theList.push_back(theMoves);
      }

      mUsed.push_back(theFlags);
      mOrder.push_back(theValues);
      mLegalMoves.push_back(theList);
   }
}

void Knight::doMove(int currentRow, int currentColumn)
{
   // If we've not found our solution yet ...

   if(!mSolutionFound)
   {
      // If mSquaresVisited ever gets up to (mRows * mColumns)
      // we've found a solution

      ++mSquaresVisited;

      // Record that we've visited this square to prevent
      // returning to it a second time and record the
      // traversal order number for this square.

      mUsed[currentRow][currentColumn]  = true;
      mOrder[currentRow][currentColumn] = mSquaresVisited;

      if(mSquaresVisited == mRows * mColumns)
      {
         mSolutionFound = true;
      }
      else
      {
         // Try all legal moves we can from the current
         // position unless we've visited the square
         // in question already.

         int i = 0;
         int n = mLegalMoves[currentRow][currentColumn].size();

         while(i < n)
         {
            Move m = mLegalMoves[currentRow][currentColumn][i];

            if(!mUsed[m.mRow][m.mColumn])
               doMove(m.mRow, m.mColumn);

            i++;
         }
      }

      // If we're still solution free, undo our visit to this
      // square so that we're again allowed to land upon it
      // via other candidate solution paths.

      if(!mSolutionFound)
      {
         --mSquaresVisited;

         mUsed[currentRow][currentColumn]  = false;
         mOrder[currentRow][currentColumn] = 0;
      }
   }
}

/*****************************************************************
 * main
 *****************************************************************/

int main()
{
   int startRow    = 3;
   int startColumn = 2;
   int rows        = DEFAULT_ROWS;
   int columns     = DEFAULT_COLUMNS;

   Knight theKnight(rows, columns);

   char *line =
      "================================="
      "=================================";

   printf(
      "%s\n"
      "Board Size       : %d rows, %d columns\n"
      "Starting Position: %d, %d\n"
      "%s\n",
      line,
      rows, columns,
      startRow, startColumn,
      line
   );

   ValuesList order;

   if(!theKnight.findSolution(startRow, startColumn, order))
   {
      printf("No Solution Found\n");
   }
   else
   {
      for(int i = 0; i < rows; i ++)
         for(int j = 0; j < columns; j ++)
            printf("%3d%s", order[i][j], j + 1 == columns ? "\n" : "");
   }

   return(0);
}