The code seems fine to me, but the output is too short and the answer is no when it should be yes (starting at a,0, the knight should be able to tour the entire board)
By the way, the reason my positionsVisted array is [9][9] is because I wanted the values to be 1-8, to match the output.
public class KnightChessRiddle {
static // given a chess board and a 0,0 starting point, can a knight pass through
// all the the squares without passing
// a square twice
int[][] positionsVisited = new int[9][9];
static int positionX = 1;
static int positionY = 1;
boolean stop = false;
static boolean continUe = false;
static int moveCounter = -1;
public static void main(String[] args) {
if (recursive(1, 1, 0)) {
System.out.println("yes");
}
else System.out.println("no");
}
public static boolean recursive(int x, int y, int moveType){
if (x>8||x<=0||y>8||y<=0) return false;
if (positionsVisited[x][y]==1) {
return false;
}
positionX = x;
positionY = y;
positionsVisited[positionX][positionY]++;
char c;
c='a';
switch (positionX) {
case 1:
c='a';
break;
case 2:
c='b';
break;
case 3:
c='c';
break;
case 4:
c='d';
break;
case 5:
c='e';
break;
case 6:
c='f';
break;
case 7:
c='g';
break;
case 8:
c='h';
break;
default:
break;
}
moveCounter++;
System.out.println("doing move "+moveType+" move count: "+moveCounter);
System.out.println("Knight is in "+ c +","+positionY);
try {
Thread.sleep(100);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
if (recursive(positionX+2, positionY+1, 1)) {
return true;
}
else if (recursive(positionX+1, positionY+2, 2) ) {
return true;
}
else if (recursive(positionX+2, positionY-1, 3) ) {
return true;
}
else if (recursive(positionX+1, positionY-2, 4)) {
return true;
}
else if (recursive(positionX-2, positionY+1, 5)) {
return true;
}
else if (recursive(positionX-1, positionY+2, 6)) {
return true;
}
else if (recursive(positionX-2, positionY-1, 7)) {
return true;
}
else if (recursive(positionX-1, positionY-2, 8)) {
return true;
}
else return false;
}
This is the output of the program:
doing move 0 move count: 0 Knight is in a,1 doing move 1 move count: 1 Knight is in c,2 doing move 1 move count: 2 Knight is in e,3 doing move 1 move count: 3 Knight is in g,4 doing move 2 move count: 4 Knight is in h,6 doing move 5 move count: 5 Knight is in f,7 doing move 1 move count: 6 Knight is in h,8 doing move 8 move count: 7 Knight is in g,6 doing move 4 move count: 8 Knight is in h,4 doing move 5 move count: 9 Knight is in f,5 doing move 2 move count: 10 Knight is in g,7 doing move 4 move count: 11 Knight is in h,5 doing move 5 move count: 12 Knight is in f,6 doing move 1 move count: 13 Knight is in h,7 doing move 5 move count: 14 Knight is in f,8 doing move 7 move count: 15 Knight is in d,7 doing move 4 move count: 16 Knight is in e,5 doing move 4 move count: 17 Knight is in f,3 doing move 2 move count: 18 Knight is in g,5 doing move 4 move count: 19 Knight is in h,3 doing move 5 move count: 20 Knight is in f,4 doing move 4 move count: 21 Knight is in g,2 doing move 7 move count: 22 Knight is in e,1 doing move 6 move count: 23 Knight is in d,3 doing move 3 move count: 24 Knight is in f,2 doing move 3 move count: 25 Knight is in h,1 doing move 6 move count: 26 Knight is in g,3 doing move 5 move count: 27 Knight is in e,4 doing move 5 move count: 28 Knight is in c,5 doing move 1 move count: 29 Knight is in e,6 doing move 5 move count: 30 Knight is in c,7 doing move 1 move count: 31 Knight is in e,8 doing move 8 move count: 32 Knight is in d,6 doing move 5 move count: 33 Knight is in b,7 doing move 1 move count: 34 Knight is in d,8 doing move 8 move count: 35 Knight is in c,6 doing move 1 move count: 36 Knight is in e,7 doing move 1 move count: 37 Knight is in g,8 no
Advertisement
Answer
Except problem with “all is visited” check I see at least one more problem, which is in class fields. When algorithm passes one branch of recursion, it marks some squares as visited, and since this information is class field, when it fails current branch and starts another, it sees all invalid information from previous attempts.
What if you try to pass positionsVisited, positionX and positionY as method arguments and remove it from class fields, so each method call will have it’s own actual copy?
Final version
public class KnightChessRiddle {
private final static Map<Integer, Character> letters = new HashMap<>();
static {
letters.put(0, 'a');
letters.put(1, 'b');
letters.put(2, 'c');
letters.put(3, 'd');
letters.put(4, 'e');
letters.put(5, 'f');
}
public static void main(String[] args) {
if (recursive(0, 0, 0, new boolean[6][6], 1, "")) {
System.out.println("yes");
} else {
System.out.println("no");
}
}
private static boolean allVisited(boolean[][] positionsVisited) {
for (int i = 0; i < positionsVisited.length; i++) {
for (int j = 0; j < positionsVisited.length; j++) {
if (!positionsVisited[i][j]) {
return false;
}
}
}
return true;
}
private static boolean recursive(int positionX, int positionY, int moveType,
boolean[][] positionsVisited, int moveCounter, String currentMoves) {
// checks
if (allVisited(positionsVisited)) {
System.out.println(currentMoves);
return true;
}
if (positionX > 5 || positionX < 0 || positionY > 5 || positionY < 0) {
return false;
}
if (positionsVisited[positionX][positionY]) {
return false;
}
// make move
positionsVisited[positionX][positionY] = true;
char c = letters.get(positionX);
currentMoves += "" + c + (positionY + 1) + " (move type: " + (moveType + 1) + ")rn";
if (recursive(positionX + 2, positionY + 1, 1, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
return true;
} else if (recursive(positionX + 1, positionY + 2, 2, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
return true;
} else if (recursive(positionX + 2, positionY - 1, 3, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
return true;
} else if (recursive(positionX + 1, positionY - 2, 4, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
return true;
} else if (recursive(positionX - 2, positionY + 1, 5, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
return true;
} else if (recursive(positionX - 1, positionY + 2, 6, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
return true;
} else if (recursive(positionX - 2, positionY - 1, 7, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
return true;
} else if (recursive(positionX - 1, positionY - 2, 8, cloneArray(positionsVisited), moveCounter + 1, currentMoves)) {
return true;
} else {
return false;
}
}
private static boolean[][] cloneArray(boolean[][] src) {
boolean[][] newPositions = new boolean[src.length][src.length];
for (int i = 0; i < src.length; i++) {
System.arraycopy(src[i], 0, newPositions[i], 0, src[0].length);
}
return newPositions;
}
}
Here is the working variation with 6×6 board. With 8×8 board calculations take too much time on my machine. Maybe it can be faster if you randomize move selection.