Write a program to find a series of knight\'s moves on a 3 X 3 chessboard from a
ID: 3733653 • Letter: W
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
import java.util.ArrayList;
import java.util.List;
public class Chess {
//All 8 Possible Moves of a knight
int[] xPos = {-1,-1,1,1,2,2,-2,-2};
int[] yPos = {-2,2,-2,2,-1,1,-1,1};
/**
* Method used to get Position in a grid based on value of matrix
* @param x
* @return
*/
public int[] getPos(int x) {
int[] ar = new int[2];
x--;
ar[0] = x/3;
ar[1] = x%3;
return ar;
}
/**
* Method which checks whether Position to next move is valid
* @param xPos
* @param yPos
* @return
*/
public boolean isValid(int xPos,int yPos) {
if(xPos >=0 && xPos <=2 && yPos >=0 && yPos <=2)
return true;
else
return false;
}
/**
* Method which converts Position of grid back to integer value in Matrix
* @param xPos
* @param yPos
* @return
*/
public int convert(int xPos,int yPos) {
return xPos*3 + yPos + 1;
}
/**
* Method which returns the path in form of List
* @param x
* @param y
* @param al
* @param bool
* @return
*/
public List<Integer> path(int x,int y,List<Integer> al,boolean[] bool){
bool[x - 1] = true;
if(x == y)
return al;
else {
int[] ar = getPos(x);
for(int i=0;i<8;i++) {
if(isValid(ar[0] + xPos[i],ar[1] + yPos[i])){
int num = convert(ar[0] + xPos[i],ar[1] + yPos[i]);
if(!bool[num - 1]) {
bool[num - 1] = true;
List<Integer> newList = new ArrayList<>(al);
newList.add(x);
newList = path(num,y,newList,bool);
if(newList.size()!=0)
return newList;
bool[num - 1] = false;
}
}
}
return new ArrayList<>();
}
}
/**
* Method used to print Grid
* @param num
*/
public void printGrid(int num) {
for(int count = 1;count<=9;count++) {
if(count == num)
System.out.print("K ");
else
System.out.print(count+" ");
if(count%3 == 0)
System.out.println();
}
System.out.println();
}
/**
* Method for displaying moves from list
* @param al
* @param endPos
*/
public void displayPath(List<Integer> al,int endPos) {
al.stream().forEach(i -> printGrid(i));
printGrid(endPos);
}
public static void main(String[] args) {
Chess chess = new Chess();
boolean[] bool = new boolean[9];
int startPos = 2;
int endPos = 1;
List<Integer> al = chess.path(startPos,endPos, new ArrayList<>(), bool);
chess.displayPath(al,endPos);
}
}
Output :
1 K 3
4 5 6
7 8 9
1 2 3
4 5 6
K 8 9
1 2 3
4 5 K
7 8 9
K 2 3
4 5 6
7 8 9
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.