title: Knight Tour C++
body: <p>I am trying to solve Knight Tour Problem using recursive Backtracking. Can someone help me optimize my code. My code works till 6X6 board. . After N=7 it takes almost infinite time to solve .
  Here is my code :</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include "genlib.h"
  #include "grid.h"
  #include "vector.h"
  #include &lt;iomanip&gt;
  
  const int NOT_VISITED = -1;
  //Size of the board
  const int N = 6;
  const int N2 = N*N;
  
  typedef Grid&lt;int&gt; chess;
  
  struct position{
      int row;
      int col;
  };
  
  //Initializes the board and makes each and every
  //square value as NOT_VISITED
  void initializeBoard(chess &amp;board)
  {
      for(int i=0;i&lt;board.numRows();i++)
          for(int j=0;j&lt;board.numCols();j++)
              board[i][j] = NOT_VISITED;
  }
  
  //Returns true if the square is visited;
  bool visited(chess &amp;board,position square)
  {
      return board[square.row][square.col ] != NOT_VISITED;
  }
  
  //Returns true if the givien position variable is outside the chess board
  bool outsideChess(chess &amp;board, position square)
  {
      if(square.row &lt;board.numRows() &amp;&amp; square.col &lt;board.numCols() &amp;&amp; square.row &gt;=0 &amp;&amp; square.col &gt;=0)
          return false;
      return true;
  }
  
  void visitSquare(chess &amp;board,position square,int count)
  {
      board[square.row] [square.col] = count;
  }
  
  void unVisitSquare(chess &amp;board,position square)
  {
      board[square.row] [square.col] = NOT_VISITED;
  }
  
  position next(position square,int irow, int icol)
  {
      square.row += irow;
      square.col += icol;
      return square;
  }
  Vector&lt;position&gt; calulateNextSquare(chess board,position square)
  {
      Vector&lt;position&gt; list;
      for(int i=-2;i&lt;3;i=i+4)
      {
          for(int j=-1;j&lt;2;j=j+2)
          {
              list.add(next(square,i,j));
              list.add(next(square,j,i));
          }
      }
      return list;
  
  }
  
  bool knightTour(chess &amp;board,position square, int count)
  {
      //cout&lt;&lt;count&lt;&lt;endl;
      //Base Case if the problem is solved;
      if(count&gt;N2)
          return true;
      if(outsideChess(board,square))
          return false;
      //return false if the square is already visited
      if(visited(board,square))
          return false;
      visitSquare(board,square,count);
      Vector&lt;position&gt; nextSquareList = calulateNextSquare(board,square); 
      for(int i=0;i&lt;nextSquareList.size();i++)
          if(knightTour(board, nextSquareList[i], count+1))
              return true;
      unVisitSquare(board,square);
      return false;
  }
  
  
  void printChess(chess &amp;board)
  {
      for(int i=0;i&lt;board.numRows();i++)
      {
          for(int j=0;j&lt;board.numCols();j++)
              cout&lt;&lt;setw(4)&lt;&lt;board[i][j];
          cout&lt;&lt;endl;
      }
  }
  
  
  int main()
  {
      chess board(N,N);
      initializeBoard(board);
      position start;
      start.row = 0; start.col = 0;
      if(knightTour(board,start,1))
          printChess(board);
      else
          cout&lt;&lt;"Not Possible";
      return 0;
  }
  </code></pre>
  
  <p>i am using Stanford 106B Libraries( grid is a 2 dimensional vector )
  Visual studio 2008 Blank project with required library files <a href="https://docs.google.com/viewer?a=v&amp;pid=explorer&amp;chrome=true&amp;srcid=0BwLe9NJT8IreNWU0N2M5MGUtY2UxZC00ZTY2LWE1YjQtMjgxYzAxMWE3OWU2&amp;hl=en" rel="nofollow">https://docs.google.com/viewer?a=v&amp;pid=explorer&amp;chrome=true&amp;srcid=0BwLe9NJT8IreNWU0N2M5MGUtY2UxZC00ZTY2LWE1YjQtMjgxYzAxMWE3OWU2&amp;hl=en</a></p>