C++ program showing Knight’s Tour iterative algorithm using ASCII chars for demonstration.

Content not available.
Please allow cookies by clicking Accept on the banner

// © 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
Tagged on:         

2 thoughts on “C++ Knight’s Tour Iteration Algorithm

  • October 9, 2017 at 6:06 am
    Permalink

    Why don’t you use a class to represent ‘board’?

    Reply
    • October 9, 2017 at 7:13 am
      Permalink

      I know it would be a lot better, I will work on that program more 🙂

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

This website stores some user agent data. These data are used to provide a more personalized experience and to track your whereabouts around our website in compliance with the European General Data Protection Regulation. If you decide to opt-out of any future tracking, a cookie will be set up in your browser to remember this choice for one year. I Agree, Deny
504

By continuing to use the site, you agree to the use of cookies. You can read more about it the Cookies&Privacy Policy Section Above. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this. You can read more about it the Cookies&Privacy Policy Section.

Close