Question

Concepts: multi-dimension array and the Knight's Tour Problem

A chess board consists of an 8 x 8 "array" of squares:

int board[ROW][COL]={0};

A knight may move perpendicular to the edges of the board, two squares in any of the 4 directions, then one square at right angles to the two-square move. The following lists all 8 possible moves a knight could make from board [3][3]:

board[5][4] or

board[5][2] or

board[4][5] or

board[4][1] or

board[1][4] or

board[1][2] or

board[2][5] or

board[2][1] or

Write a function named LegalMove, in class knight, which accepts a ROW and COL parameter for the

knight's current position, and a move number parameter (see table above) for the proposed new position.

The method should return true if the proposed move is legal, and false if not legal. The method should also pass reference parameters set by the method to the ROW and COL coordinates of the destination square if the move is legal.

You will need at least the following variables:

A function should initialize row and col to passed values, and should initialize the offsets array to the array differences (+/- 1 or 2) for row and col for each of the 8 moves.

GetLegalMoves() should fill the moves array with the move number (1-8) and each legal move that is possible from row, col, and return the number of moves in the array (0-8) and store this value in countLegalMoves.

Write some driver code in main that will place a knight at a given position, and test some possible moves (including some off-the-board moves).

If you have time, code the ClearBoard and the ShowBoard methods as well. It might be even more interesting to start on a full brute-force type Knight's Tour program. I say start on, becuase there is not enough time in a class period for even a fast programmer to complete such a program.

Answer 1

#include<bits/stdc++/h>
using namespace std;

/*
Utility function to check if a position is on board or not
*/
bool ifOnboard( int r, int c){
   if ( r>=0 && r<8 && c>=0 && c<8 )   //if it is in array range then it is on board
       return 1;
   else return 0;
}

/*
It checks if particular move according to the given table
is legal or not w.r.t the given current position of knight in
input parameters.
*/
bool LegalMove(int r, int c, int moveNo){
   //cases for every move
   switch(move){
       case 1:
           r+=2;
           c+=1;
           break;
       case 2:
           r+=2;
           c-=1;
           break;
       case 3:
           r+=1;
           c+=2;
           break;
       case 4:
           r+=1;
           c-=2;
           break;
       case 5:
           r-=2;
           c+=1;
           break;
       case 6:
           r-=2;
           c-=1;
           break;
       case 7:
           r-=1;
           c+=2;
           break;
       case 8:
           r-=1;
           c-=2;
           break;  
   }
   if ( ifOnboard(r,c) )
       return 1;
   else return 0;
}
/*
It will change value of the array with respective move, according to table,
if it is a legal move and it also return the count of the legal moves
where knight can move from its current position.
(r,c) is the position of the knight
*/
int GetLegalMoves( int** arr, int r, int c ){
    int count;       //count of legal moves from position arr[r][c]
   //we are marking every legal position in array as move number according to the table.
   if ( ifOnboard(r+2,c+1) ) {
       arr[r+2][c+1]=1;
       count++;
   }
   if ( ifOnboard(r+2,c-1) ) {
       arr[r+2][c-1]=2;
       count++;
   }
   if ( ofOnboard(r+1,c+2) ) {
       arr[r+1][c+2]=3;
       count++;
   }
   if ( ofOnboard(r+1,c-2) ) {
       arr[r+1][c-2]=4;
       count++;
   }
   if ( ifOnboard(r-2,c+1) ) {
       arr[r-2][c+1]=5;
       count++;
   }
   if ( ofOnboard(r-2,c-1) ) {
       arr[r-2][c-1]=6;
       count++;
   }
   if ( ifOnboard(r-1,c+2) ) {
       arr[r-1][c+2]=7;
       count++;
   }
   if ( ifOnboard(r-1,c-2) ) {
       arr[r-1][c-2]=8;
       count++;
   }
   return count;
}

//Driver program for testing
int main(){

   int arr[8][8]={0};   //declaration of 2d array initialised with all 0

   cout<< LegalMove(7,1,1) ;
   cout<< LegalMove(5,4,5) ;
   cout<< LegalMove(7,6,8) ;
   cout<< GetLegalMoves(arr,2,5) ;
  

   return 0;
}