I am working on the Knight’s Tour problem. In my program the user can select a number n equal to 3 or higher. The number will determine the table’s size by n*n in a two-dimensional array. Then the knight will start it’s tour based on the starting points given by the user as long as they are higher or equal to 0.
My problem comes when the knight has come to a dead end (as of turn number 12 in the visualization table in the output). I want to somehow track it’s movements so that I can block the dead end, go back a step and try from there. I’ve figured out that I might need a three-dimensional array so that I can save all the turn numbers in each square. But then again I need an ArrayList witch isn’t static. Any suggestions will be appreciated. Here’s my code:
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. Turn: " + turns);
if (takeTour(x-2, y+1))
{
return true;
}
else
{
return false;
}
}
// 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. Turn: " + turns);
if (takeTour(x-2, y-1))
{
return true;
}
else
{
return false;
}
}
// 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. Turn: " + turns);
if (takeTour(x-1, y-2))
{
return true;
}
else
{
return false;
}
}
// 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. Turn: " + turns);
if (takeTour(x+1, y-2))
{
return true;
}
else
{
return false;
}
}
// 2 Right, 1 Up
if (x < squares -2 && y > 0 && table[x+2][y-1] == 0)
{
moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Up. Turn: " + turns);
if (takeTour(x+2, y-1))
{
return true;
}
else
{
return false;
}
}
// 2 Right, 1 Down
if (x < squares -2 && y < squares -1 && table[x+2][y+1] == 0)
{
moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Down. Turn: " + turns);
if (takeTour(x+2, y+1))
{
return true;
}
else
{
return false;
}
}
// 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. Turn: " + turns);
if (takeTour(x+1, y+2))
{
return true;
}
else
{
return false;
}
}
// 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. Turn: " + turns);
if (takeTour(x-1, y+2))
{
return true;
}
else
{
return false;
}
}
/*
I need some code here before it gives up searching
*/
// If we'd tried every single paths
// and we still end up here, there's no solution
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 < 3 )
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();
}
}
}
My output for a 4*4 table looks like this:
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. Moving 2 Right, 1 Down. Turn: 1 X: 2, Y: 1. Moving 2 Left, 1 Down. Turn: 2 X: 0, Y: 2. Moving 2 Up, 1 Right. Turn: 3 X: 1, Y: 0. Moving 2 Right, 1 Down. Turn: 4 X: 3, Y: 1. Moving 2 Left, 1 Down. Turn: 5 X: 1, Y: 2. Moving 2 Up, 1 Right. Turn: 6 X: 2, Y: 0. Moving 2 Left, 1 Down. Turn: 7 X: 0, Y: 1. Moving 2 Right, 1 Down. Turn: 8 X: 2, Y: 2. Moving 2 Left, 1 Down. Turn: 9 X: 0, Y: 3. Moving 2 Up, 1 Right. Turn: 10 X: 1, Y: 1. Moving 2 Right, 1 Up. Turn: 11 Did not find any way to complete Knights Tour! 1 4 7 12 8 11 2 5 3 6 9 0 10 0 0 0
Advertisement
Answer
When trying different possibilities on BackTracking you need to check them all in every recursion step. In the code you provide in a single step you only try one possibility and then return. Doing this you are not able to explore all the possibilities.
My suggestion is to change the function arguments to accept the current position (x,y) and a boolean array for the positions that have been previously visited. If you need to construct the path of the final valid solution, I also suggest to add the step count (the number of steps you have done) and a int array to store which position has been visited in which step.
Next I provide a solution which is not the most efficient. In fact, you can try to prune the backtracking possibilities to avoid the recurssion explosion (cpu efficiency) and you can try to avoid some copies of the matrixes (memory efficiency).
package knightsTour;
import java.util.Scanner;
public class KnightsTour {
private static final int[] MOVE_X = new int[] { -2, -2, -1, -1, +1, +1, +2, +2 };
private static final int[] MOVE_Y = new int[] { +1, -1, +2, -2, +2, -2, +1, -1 };
private final int SQUARES;
private final int INIT_X;
private final int INIT_Y;
private int[][] path;
public KnightsTour(int squares, int x, int y) {
this.SQUARES = squares;
this.INIT_X = x;
this.INIT_Y = y;
}
public int[][] getPath() {
return this.path;
}
public boolean takeTour() {
boolean[][] visited = new boolean[this.SQUARES][this.SQUARES];
for (int i = 0; i < this.SQUARES; ++i) {
for (int j = 0; j < this.SQUARES; ++j) {
visited[i][j] = false;
}
}
visited[this.INIT_X][this.INIT_Y] = true;
this.path = new int[this.SQUARES][this.SQUARES];
return takeTourBT(this.INIT_X, this.INIT_Y, 0, visited, this.path);
}
private boolean takeTourBT(int posX, int posY, int step, boolean[][] visited, int[][] path) {
debug(step, visited);
if (checkIfFinished(visited)) {
return true;
}
// Increase the step count
++step;
// Try recursively (cut when a branch success)
boolean success = false;
for (int i = 0; i < MOVE_X.length && !success; ++i) {
int nextX = posX + MOVE_X[i];
int nextY = posY + MOVE_Y[i];
if (nextX >= 0 && nextX < this.SQUARES && nextY >= 0 && nextY < this.SQUARES && !visited[nextX][nextY]) {
// Next position is valid and has not been visited
// Mark position
visited[nextX][nextY] = true;
// Call
boolean branchSuccess = takeTourBT(nextX, nextY, step, visited, path);
if (branchSuccess) {
// We are comming back from the good solution, mark the path
path[nextX][nextY] = step;
}
success = success | branchSuccess;
// Unmark the position for next try
visited[nextX][nextY] = false;
}
}
return success;
}
// Adds some verbose for debugging
private void debug(int step, boolean[][] visited) {
System.out.println("*********************** STEP " + String.valueOf(step) + " ***********************");
for (int i = 0; i < this.SQUARES; ++i) {
for (int j = 0; j < this.SQUARES; ++j) {
if (visited[i][j]) {
System.out.print("X ");
} else {
System.out.print(". ");
}
}
System.out.println("");
}
System.out.println("*******************************************************");
}
// Checks if all squares is used
private boolean checkIfFinished(boolean[][] visited) {
for (int i = 0; i < this.SQUARES; ++i) {
for (int j = 0; j < this.SQUARES; ++j) {
if (!visited[i][j]) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
// Process arguments
int squares = 0;
int x = 0;
int y = 0;
try (Scanner sc = new Scanner(System.in)) {
System.out.print("Number of squares: ");
squares = Integer.parseInt(sc.nextLine());
if (squares < 3) {
throw new Exception("[ERROR] Invalid number of squares");
}
System.out.println("Note: Start values is from 0 -> n-1" + "n0,0 is at top left side");
System.out.print("X start value: ");
x = Integer.parseInt(sc.nextLine());
if (x < 0 || x > squares - 1) {
throw new Exception("[ERROR] Invalid start x position");
}
System.out.print("Y start value: ");
y = Integer.parseInt(sc.nextLine());
if (y < 0 || y > squares - 1) {
throw new Exception("[ERROR] Invalid start y position");
}
} catch (Exception e) {
// Error occurred, exit
System.err.println("Killing process");
System.exit(1);
}
// Initialize the KnightsTour
KnightsTour kt = new KnightsTour(squares, x, y);
// Make the tour
boolean success = kt.takeTour();
// Post process
if (success) {
System.out.println("The tour was sucessfull!");
} else {
System.out.println("Did not find any way to complete Knights Tour!");
}
int[][] path = kt.getPath();
for (int i = 0; i < path.length; ++i) {
for (int j = 0; j < path[i].length; ++j) {
String stepSTR = (path[i][j] < 10) ? "0" + String.valueOf(path[i][j]) : String.valueOf(path[i][j]);
System.out.print(stepSTR + " ");
}
System.out.println("");
}
}
}
Try this code with size 5 and start position (0,0).
Notice that:
- You can enable/disable the debug iteration by commenting the debug call
- I compacted the way you perform the moves with 2 arrays to avoid replications but for the sake of clarity you can unroll it again.
- On each recursion step, before going depth, we check if we can perform moves, we mark the next position and proceed. On the way back, we unmark the position, check whether the move reached a successfull step or not and reconstruct the good solution if needed.