I’ve been working on a school project and can not figure out the problem. The problem that the knight jumps back where it was in the the last step when a dead end occurs.
I’ve added the output for a 4×4 test and you can clarly see that the knight jumps back to turn number 11 when it sees that there’s a dead-way from number 12. It then continues from turn number 11 and “solves the tour”.
Also I’m unsure how to continue if a pattern don’t solve the problem. Because then I need to somehow log that pattern so that I don’t go in the same pattern all over again. Sorry for my bad Engligh and thanks in advance.
package knightsTour; import java.util.Scanner; import java.util.ArrayList; public class KnightsTour { private static int turns = 0; private static ArrayList<String> moves = new ArrayList<String>(); private static int squares; private static int table[][]; private static boolean takeTour(int x, int y) { // Checks if all squares is used. If true, algorithm will stop if (checkIfFinished()) return true; table[x][y] = ++turns; // 2 Left, 1 Down if (x > 1 && y < squares -1 && table[x-2][y+1] == 0) { moves.add("X: " + x + ", Y: " + y + ". Moving 2 Left, 1 Down"); if (takeTour(x-2, y+1)) { return true; } } // 2 Left, 1 Up if (x > 1 && y > 0 && table[x-2][y-1] == 0) { moves.add("X: " + x + ", Y: " + y + ". Moving 2 Left, 1 Up"); if (takeTour(x-2, y-1)) { return true; } } // 2 Up, 1 Left if (y > 1 && x > 0 && table[x-1][y-2] == 0) { moves.add("X: " + x + ", Y: " + y + ". Moving 2 Up, 1 Left"); if (takeTour(x-1, y-2)) { return true; } } // 2 Up, 1 Right if (y > 1 && x < squares -1 && table[x+1][y-2] == 0) { moves.add("X: " + x + ", Y: " + y + ". Moving 2 Up, 1 Right"); if (takeTour(x+1, y-2)) { return true; } } // 2 Right, 1 Up if (x < squares -2 && y > 0 && table[x+2][y-1] == 0) { System.out.println("x:" + x + ", y:" + y + " (2r,1u)moving to x:" + (x+2) + ", y:" + (y-1)); moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Up"); if (takeTour(x+2, y-1)) { return true; } } // 2 Right, 1 Down if (x < squares -2 && y < squares -1 && table[x+2][y+1] == 0) { System.out.println("x:" + x + ", y:" + y + " (2r,1d)moving to x:" + (x+2) + ", y:" + (y+1)); moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Down"); if (takeTour(x+2, y+1)) { return true; } } // 2 Down, 1 Right if (y < squares -2 && x < squares-1 && table[x+1][y+2] == 0) { moves.add("X: " + x + ", Y: " + y + ". Moving 2 Down, 1 Right"); if (takeTour(x+1, y+2)) { return true; } } // 2 Down, 1 Left if (y < squares -2 && x > 0 && table[x-1][y+2] == 0) { moves.add("X: " + x + ", Y: " + y + ". Moving 2 Down, 1 Left"); if (takeTour(x-1, y+2)) { return true; } } return false; } // Checks if all squares is used private static boolean checkIfFinished() { for (int i = 0; i < squares; i++) { for (int j = 0; j < squares; j++) { if (table[i][j] == 0) return false; } } return true; } // Made this to save code from 3 duplicates private static void invalidNumber() { System.out.println("Invalid number! Killing proccess"); System.exit(0); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("Number of squares: "); squares = Integer.parseInt(sc.nextLine()); if (squares < 1 ) invalidNumber(); System.out.println("Note: Start values is from 0 -> n-1" + "n0,0 is at top left side"); System.out.print("X start value: "); int x = Integer.parseInt(sc.nextLine()); if (x < 0 || x > squares -1) invalidNumber(); System.out.print("Y start value: "); int y = Integer.parseInt(sc.nextLine()); if (y < 0 || y > squares -1) invalidNumber(); sc.close(); table = new int[squares][squares]; boolean tourComplete = takeTour(x, y); for (String s : moves) { System.out.println(s); } if (!tourComplete) System.out.println("Did not find any way to complete Knights Tour!"); // Print the table with the move-numbers for (int i = 0; i < squares; i++) { for (int j = 0; j < squares; j++) { System.out.printf("%4d", table[j][i]); } System.out.println(); } } }
Here’s the output for a 4×4:
Number of squares: 4 Note: Start values is from 0 -> n-1 0,0 is at top left side X start value: 0 Y start value: 0 x:0, y:0 (2r,1d)moving to x:2, y:1 x:1, y:0 (2r,1d)moving to x:3, y:1 x:0, y:1 (2r,1d)moving to x:2, y:2 x:1, y:1 (2r,1u)moving to x:3, y:0 x:1, y:1 (2r,1d)moving to x:3, y:2 x:1, y:2 (2r,1d)moving to x:3, y:3 X: 0, Y: 0. Moving 2 Right, 1 Down X: 2, Y: 1. Moving 2 Left, 1 Down X: 0, Y: 2. Moving 2 Up, 1 Right X: 1, Y: 0. Moving 2 Right, 1 Down X: 3, Y: 1. Moving 2 Left, 1 Down X: 1, Y: 2. Moving 2 Up, 1 Right X: 2, Y: 0. Moving 2 Left, 1 Down X: 0, Y: 1. Moving 2 Right, 1 Down X: 2, Y: 2. Moving 2 Left, 1 Down X: 0, Y: 3. Moving 2 Up, 1 Right X: 1, Y: 1. Moving 2 Right, 1 Up X: 1, Y: 1. Moving 2 Right, 1 Down X: 3, Y: 2. Moving 2 Left, 1 Down X: 1, Y: 1. Moving 2 Down, 1 Right X: 1, Y: 2. Moving 2 Right, 1 Down Did not find any way to complete Knights Tour! 1 4 7 12 8 11 2 5 3 6 9 13 10 14 15 16
Advertisement
Answer
I figured out the problem! I had to put else blocks in every 8th if(takeTour(x+-a, y+-b)) statements inside the takeTour(int x, int y), and then return false. Now I just wonder how I will be able to track the pattern so that I can go back one step and try a new one