C++ program showing Knight’s Tour iterative algorithm using ASCII chars for demonstration.
// ? 2017 TheFlyingKeyboard and released under MIT License // theflyingkeyboard.net #include <iostream> #include <string> #include <vector> #ifdef _WIN32 #include <windows.h> #include <conio.h> #endif using namespace std; void generateBoard(const int size, vector<string> &board); void printBoard(vector<string> board); void solveBoard(int knightXPos, int knightYPos, vector<string> board); int calculatePossibleMoves(int nextKnightXPos, int nextKnightYPos, vector<string> board); bool checkIfCanMove(int nextKnightXPos, int nextKnightYPos, int moveNum, vector<string> board); void clearConsole(); char getChar(); const int knightMoves[8][2] = { { 2, 1 }, { 1, 2 }, { -1, 2 }, { -2, 1 }, { -2, -1 }, { -1, -2 }, { 1, -2 }, { 2, -1 } }; int main() { int size; int yPosition; vector<string> board; cout << "Knight's tour algorithm" << endl; cout << "TheFlyingKeyboard.net 2017" << endl; cout << "Enter size of a board" << endl; cin >> size; if (size > 4) { generateBoard(size, board); cout << "Enter Knight's X position: "; cin >> size; cout << "Enter Knight's Y position: "; cin >> yPosition; board[yPosition][size] = 1; //Smiley face solveBoard(size, yPosition, board); } else { cout << "Size of board must be > 4" << endl; getChar(); } return 0; } void generateBoard(const int size, vector<string> &board) { string stringToAdd; board.clear(); for (int i = 0; i < size; i++) { stringToAdd += ' '; } for (int i = 0; i < size; i++) { board.push_back(stringToAdd); } } void printBoard(vector<string> board) { for (int i = 0; i < board.size(); i++) { cout << board[i] << endl; } } void solveBoard(int knightXPos, int knightYPos, vector<string> board) { vector<int> moves; int smallestNumber = 0; int smallestNumberIndex = 0; int xMove = 0; int yMove = 0; for (int i = 0; i < board.size() * board.size(); i++) { printBoard(board); cout << "Turn number: " << i << endl; cout << "Press any key to continue..." << endl; moves.clear(); for (int j = 0; j < 8; j++) { xMove = knightXPos + knightMoves[j][1]; yMove = knightYPos + knightMoves[j][0]; if (checkIfCanMove(knightXPos, knightYPos, j, board)) { moves.push_back(calculatePossibleMoves(xMove, yMove, board)); } else { moves.push_back(-1); } } smallestNumber = 8; smallestNumberIndex = 0; for (int j = 0; j < moves.size(); j++) { if ((moves[j] < smallestNumber) && moves[j] >= 0) { smallestNumber = moves[j]; smallestNumberIndex = j; } } board[knightYPos][knightXPos] = 'X'; knightXPos += knightMoves[smallestNumberIndex][1]; knightYPos += knightMoves[smallestNumberIndex][0]; board[knightYPos][knightXPos] = 1; getChar(); clearConsole(); } } int calculatePossibleMoves(int nextKnightXPos, int nextKnightYPos, vector<string> board) { int moves = 0; for (int i = 0; i < 8; i++) { if (checkIfCanMove(nextKnightXPos, nextKnightYPos, i, board)) { moves++; } } return moves; } bool checkIfCanMove(int nextKnightXPos, int nextKnightYPos, int moveNum, vector<string> board) { int xMove = nextKnightXPos + knightMoves[moveNum][1]; int yMove = nextKnightYPos + knightMoves[moveNum][0]; if ((xMove >= 0 && xMove < board.size()) && (yMove >= 0 && yMove < board.size()) && board[yMove][xMove] != 'X' && board[yMove][xMove] != 1) { return true; } else { return false; } } void clearConsole() { //Clears console #ifdef _WIN32 //Windows system("CLS"); #else //Others system("clear"); #endif } char getChar() { //Gets input from keyboard char input; #ifdef _WIN32 //Windows input = _getch(); if (input == 0 || input == 0xE0) input = _getch(); //In case of input error #else //Others cin >> input; #endif return input; }
C++ Knight’s Tour Iteration Algorithm
Why don’t you use a class to represent ‘board’?
I know it would be a lot better, I will work on that program more 🙂
it steps on the same square twice in some instances, when you fill in 7 for the board size and 6, 5 as coordinates for example.
It is probably due to the initial placing of knight. You can find more about it here: https://stackoverflow.com/questions/31411487/knights-tour-on-a-5-x-5-board-start-from-any-square