Write a program to find a series of knight\'s moves on a 3 X 3 chessboard from a

Question

Write a program to find a series of knight's moves on a 3 X 3 chessboard from any square to any square, if such a series of moves exists. (This is a simplified version of what is known as the "knight's tour problem".)

The board can be represented as follows:
1 2 3
4 5 6
7 8 9

Prompt the user with a printout of the board and then prompt for and input a start number and a goal number.

Output either a message stating that no such path is possible (to or from square 5), or a list of squares in the order moved, starting with the start number and ending with the goal number.

Print out the solution as a series of boards, with K replacing each of the squares where the knight moves, for example, for moves from 1 to 7:
K 2 3
4 5 6
7 8 9

1 2 3
4 5 K
7 8 9

1 2 3
4 5 6
K 8 9

The moves can be represented by hardcoding them into a boolean method, returning true for the following pairs of parameter values:
(1, 8)    (1,6)    (6,1)    (6,7)
(2, 9)    (2,7)    (7,2)    (7,6)
(3, 4)    (3,8)    (8,3)    (8,1)
(4, 9)    (4,3)    (9,2)    (9,4)

You must use recursion to solve the problem.

The base case is that there is a path from X to X, for any X. Represent this as path(X,X), which returns a list of squares in the order moved, in this case, an ArrayList<Integer> with one element: X.

The recursive step for finding path(X,Y) is that move(X,Z) exists and path(Z,Y) exists, path(X,Y) returns the result of adding X as the first value of the ArrayList<Integer> returned by path(Z,Y).

You will need a ArrayList<Boolean> to keep track of which moves have been used, to avoid going in circles. Set all 9 (or 10) cells to false first, then set each to true when it has been visited. Then, you can check to see if each value has been visited before.

Explanation / Answer

Please find the answer

#include<iostream>
#define N 3
using namespace std;

// defines a structure for chess moves
typedef struct chess_moves {
// 'x' and 'y' coordinates on chess board
int x,y;
}chess_moves;

// displays the knight tour solution
void printTour(int tour[N][N]) {
int i,j;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
cout<<tour[i][j]<<" ";
}
cout<<endl;
}
}

// check if the next move (as per knight's constraints) is possible
bool isMovePossible(chess_moves next_move, int tour[N][N]) {
int i = next_move.x;
int j = next_move.y;
if ((i >= 0 && i < N) && (j >= 0 && j < N) && (tour[i][j] == 0))
return true;
return false;
}

// recursive function to find a knight tour
bool findTour(int tour[N][N], chess_moves move_KT[],
chess_moves curr_move, int move_count) {
int i;
chess_moves next_move;
if (move_count == N*N-1) {
// Knight tour is completed i.e all cells on the
// chess board has been visited by knight once
return true;
}

// try out the possible moves starting from the current coordinate
for (i = 0; i < N; i++) {
// get the next move
next_move.x = curr_move.x + move_KT[i].x;
next_move.y = curr_move.y + move_KT[i].y;

if (isMovePossible(next_move, tour)) {
// if the move is possible
// increment the move count and store it in tour matrix
tour[next_move.x][next_move.y] = move_count+1;
if (findTour(tour, move_KT, next_move, move_count+1) == true) {
return true;
}
else {
// this move was invalid, try out other possiblities
tour[next_move.x][next_move.y] = 0;
}
}
}
return false;
}

// wrapper function
void knightTour() {
int tour[N][N];
int i,j;

// initialize tour matrix
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
tour[i][j] = 0;
}
}

// all possible moves that knight can take
chess_moves move_KT[16] = { {1, 8}, {1,6}, {6,1}, {6,7},
{2, 9}, {2,7} , {7,2} ,{7,6} ,
{3, 4} ,{3,8} ,{8,3} , {8,1} ,
{4, 9} , {4,3} , {9,2} , {9,4} };

// knight tour starts from coordinate (0,0)
chess_moves curr_move = {0,0};

// find a possible knight tour using a recursive function
// starting from current move
if(findTour(tour, move_KT, curr_move, 0) == false) {
cout<<" Knight tour does not exist";
}
else {
cout<<" Tour exist ... ";
printTour(tour);
}
}

// main
int main() {
knightTour();
cout<<endl;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.