c++ - How to optimize Knight's tour algorithm? -

i code knight's tour algorithm in c++ using backtracking method. seems slow or stuck in infinite loop n > 7 (bigger 7 7 chessboard).

the question is: time complexity algorithm , how can optimize it?!

---

the knight's tour problem can stated follows:

given chess board n × n squares, find path knight visits every square once.

here code :

#include <iostream> #include <iomanip> using namespace std;  int counter = 1; class horse { public:   horse(int);   bool backtrack(int, int);   void print(); private:   int size;   int arr[8][8];   void mark(int &);   void unmark(int &);   bool unvisited(int &); };  horse::horse(int s) {   int i, j;   size = s;   for(i = 0; <= s - 1; i++)     for(j = 0; j <= s - 1; j++)       arr[i][j] = 0; }  void horse::mark(int &val) {   val = counter;   counter++; }  void horse::unmark(int &val) {   val = 0;   counter--; }  void horse::print() {   cout<< "\n - - - - - - - - - - - - - - - - - -\n";   for(int = 0; <= size-1 ;i++){     cout <<"| ";     for(int j = 0; j <= size-1 ;j++)       cout << setw(2) << setfill ('0') << arr[i][j]<< " | ";         cout << "\n - - - - - - - - - - - - - - - - - -\n";     } }  bool horse::backtrack(int x, int y) {    if(counter > (size * size))     return true;    if(unvisited(arr[x][y])){         if((x-2 >= 0) && (y+1 <= (size-1)))         {             mark(arr[x][y]);             if(backtrack(x-2, y+1))                 return true;             else                 unmark(arr[x][y]);         }     if((x-2 >= 0) && (y-1 >= 0))         {             mark(arr[x][y]);             if(backtrack(x-2, y-1))                 return true;             else                 unmark(arr[x][y]);         }         if((x-1 >= 0) && (y+2 <= (size-1)))         {             mark(arr[x][y]);             if(backtrack(x-1, y+2))                 return true;             else                 unmark(arr[x][y]);         }     if((x-1 >= 0) && (y-2 >= 0))         {             mark(arr[x][y]);             if(backtrack(x-1, y-2))                 return true;             else                 unmark(arr[x][y]);         }         if((x+2 <= (size-1)) && (y+1 <= (size-1)))         {             mark(arr[x][y]);             if(backtrack(x+2, y+1))                 return true;             else                 unmark(arr[x][y]);         }         if((x+2 <= (size-1)) && (y-1 >= 0))         {             mark(arr[x][y]);             if(backtrack(x+2, y-1))                 return true;             else                 unmark(arr[x][y]);         }     if((x+1 <= (size-1)) && (y+2 <= (size-1)))         {             mark(arr[x][y]);             if(backtrack(x+1, y+2))                 return true;             else                 unmark(arr[x][y]);         }         if((x+1 <= (size-1)) && (y-2 >= 0))         {             mark(arr[x][y]);             if(backtrack(x+1, y-2))                 return true;             else                 unmark(arr[x][y]);         }       }     return false; }  bool horse::unvisited(int &val) {   if(val == 0)     return 1;   else         return 0; }   int main() {    horse example(7);   if(example.backtrack(0,0))   {     cout << " >>> successful! <<< " << endl;     example.print();   }   else     cout << " >>> not possible! <<< " << endl;  } 

output example (n = 7) above this:

since @ each step have 8 possibilities check , has done each cell (minus last one) time complexity of algorithm o(8^(n^2-1)) = o(8^(n^2)) n number of squares on edges of checkboard. precise worst case time complexity (time taken explore possibilities if none found or if last one).

as optimizations there can 2 types of improvements:

implementation improvements

you're calculating x-2, x-1, x+1, x+2 , same y @ least double of times. can suggest rewrite things this:

int sm1 = size - 1; int xm2 = x - 2; int yp1 = y + 1; if((xm2 >= 0) && (yp1 <= (sm1))){     mark(arr[x][y]);     if(backtrack(xm2, yp1))         return true;     else         unmark(arr[x][y]); }  int ym1 = y-1; if((xm2 >= 0) && (ym1 >= 0)){     mark(arr[x][y]);     if(backtrack(xm2, ym1))         return true;     else         unmark(arr[x][y]); } 

note reusing of precalculated values in subsequent blocks. i've found more effective especting; meaning variable assignment , recall faster doing operation again. consider saving sm1 = s - 1; , area = s * s; in constructor instead of calculating each time.

however (being implementation improvement , not algorithm improvement) not change time complexity order divide time factor. mean time complexity o(8^(n^2)) = k*8^(n^2) , difference in lower k factor.

algorithm improvements

i can think this:

• for each tour starting on in cell in diagonals (like starting in (0,0) in example) can consider first moves being on 1 of 2 half checkboards created diagonal.
  • this beacouse of simmetry or exists 2 simmetric solutions or none.
  • this gives o(4*8^(n^2-2)) cases same remains non simmetric ones.
  • note again o(4*8^(n^2-2)) = o(8^(n^2))
• try interrupt rush if global condition suggests solution impossible given current markings.
  • for example horse cannot jump 2 bulk columns or rows if have 2 bulk marked columns (or rows) , unmarked cells on both sides you're sure there no solution. consider can checked in o(n) if mantain number of marked cells per col/row updated. if check after each marking you're adding o(n*8^(n^2)) time not bad if n < = 8. workaround not check alwais maybe every n/8 markings (checking counter % 8 == 4 example or better counter > 2*n && counter % 8 == 4
• find other ideas cleverly interrupt search remember backtrack algorithm 8 options have nature of being o(8^(2^n)).

bye