# Knight Tour

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152``` ```/* Filename: knightour.cpp Author : Piyush Kumar To Compile: use g++ knightour.cpp -O3 -o knight To Run : ./knight The purpose of this program is to demonstrate some simple C++ features. (Copy constructor, operator overloading <<, friend function) It also shows how to implement simple backtracking/recursive solutions. Written for : OOP in C++ Class, COP 3330, FSU. Our problem: From an arbitrary starting position, find a knight's tour for a given size grid. What is a knight tour? (From wikipedia) A knight's tour of a chessboard (or any other grid) is a sequence of moves (i.e., a tour) by a knight chess piece (which may only make moves which simultaneously shift one square along one axis and two along the other) such that each square of the board is visited exactly once (i.e., a Hamiltonian path). The output is a solution for the knights tour problem in a sxs chessboard. If you find any bugs, please let me know. Note: For the 8x8 board, and with first piece at location (7,0), it takes about 5 minutes on my home machine (Pentium 4 2.99Ghz). Beware: If you are looking for an efficient knightour solver, this solution is going to disappoint you. You should try using an explicit stack and less space for a more efficient solution. */ #include #include #include using namespace std; const int move={1,2, 2,1, 2,-1, 1,-2, -1,-2, -2,-1, -2,1, -1,2}; class tour { vector< vector< int > > board; int sx, sy, size; public: bool findtour(tour& , int ); // Constructor tour(int s = 5, int startx = 0, int starty = 0) :sx(startx), sy(starty), size(s) { // Get the board to size x size board.resize(size); for(int i = 0; i < size; ++i) board[i].resize(size); // Fill the board with -1s for(int i = 0; i < size; ++i) for(int j = 0; j < size; ++j) board[i][j] = -1; // Move 0 board[sx][sy] = 0; // Solve the problem if(!findtour(*this, 0)) cout << "No solutions found\n"; } // Copy constructor tour(const tour& T): sx(T.sx), sy(T.sy), size(T.size){ this->board.resize(size); for(int i = 0; i < size; ++i) board[i].resize(size); // Copy the board for(int i = 0; i < size; ++i) for(int j = 0; j < size; ++j) board[i][j] = T.board[i][j]; } // Function to output class to ostream friend std::ostream& operator<< ( std::ostream& os, const tour& T ); }; // Implementation of the overloaded << which is a friend of tour... std::ostream& operator<<( std::ostream& os, const tour& T ){ os << endl; int size = T.size; os << " +"; for(int i = 0; i < size*5-1; ++i) os << "-"; os << "+\n"; for(int i = 0; i < size; ++i){ os << " | "; for(int j = 0; j < size; ++j) os << setw(2) << T.board[i][j] << " | "; os << endl; os << " +"; for(int i = 0; i < size*5-1; ++i) os << "-"; os << "+\n"; } return os; } // A recursive function to find the knight tour. bool tour::findtour(tour& T, int imove){ if(imove == (size*size - 1)) return true; // make a move int cx = T.sx; int cy = T.sy; int cs = T.size; for ( int i = 0; i < 8; ++i){ int tcx = cx + move[i]; int tcy = cy + move[i]; if ( // Is this a valid move? (tcx >= 0) && (tcy >= 0) && (tcx < cs) && (tcy < cs) && // Has this place been visited yet? (T.board[tcx][tcy] == -1) ){ tour temp(T); temp.board[tcx][tcy] = imove+1; temp.sx = tcx; temp.sy = tcy; if(findtour(temp, imove+1)) { cout << "Solution found\n"; cout << temp << endl; exit(1); } } // legal move? } // for return false; } int main(void){ tour T; return 0; } ```