I’m trying to solve the knight’s tour problem using backtracking. I think the algorithm I have should work. I’ve tried but I can’t figure out why it isn’t working. It results in an infinite loop.
However if I comment out the line that back track solutionBoard[dst.x][dst.y]=-1; it works!
I just don’t understand why!
Any help would be appreciated.
private int solutionBoard[][] = new int [8][8];
// The eight possible moves a knight can make from any given position
private static final Point[] MOVES = new Point[] { new Point(-2, -1),
new Point(-2, 1), new Point(2, -1), new Point(2, 1),
new Point(-1, -2), new Point(-1, 2), new Point(1, -2),
new Point(1, 2) };
private int count = 0;
public KnightsTour_DFS(){
// board is 0- 7
//initialize visited
for(int i =0; i<8;i++){
for(int j = 0; j< 8; j++){
solutionBoard[i][j] = -1;
}
}
solutionBoard[0][0]=count++;
if(findTour(0, 0)){
System.out.println("Tour found!!");
printSolution();
}
}
public boolean findTour(int x, int y){
if(x <0 || y <0 || x>7 || y > 7 ){
return false;
}
if(count == 64){
//we've covered all node
return true;
}
for(int i = 0; i < this.MOVES.length; i++){
Point dst = new Point(x + MOVES[i].x, y + MOVES[i].y);
if(canMove(dst)){
solutionBoard[dst.x][dst.y]=count++;
if(findTour(dst.x, dst.y)){
System.out.println("Solution shown on boardn");
return true;
}
else{
count --;
solutionBoard[dst.x][dst.y]=-1;
}
}
}
return false;
}
private void printSolution() {
System.out.println("Solution shown on boardn");
for (int[] rows : solutionBoard) {
for (int r : rows) {
System.out.printf("%2d ", r);
}
System.out.println();
}
}
public boolean canMove(Point destination){
if(destination.x<0 || destination.y<0 || destination.x>7|| destination.y>7){
return false;
}
if(solutionBoard[destination.x][destination.y] != -1){
//already visited
return false;
}
return true;
}
Advertisement
Answer
Your algorithm seems to work just fine, yielding correct results for smaller problem instances, like a 5×5 or 7×7 board. It seems like the 8×8 board is just too big for the brute force / backtracking approach.
Still, you can simplify your findTour method, making it easier to understand and to debug:
public boolean findTour(int x, int y, int c) {
solutionBoard[x][y] = c;
if (c == size*size) {
return true;
}
for (Point p : MOVES) {
Point dst = new Point(x + p.x, y + p.y);
if (canMove(dst) && findTour(dst.x, dst.y, c + 1)) {
return true;
}
}
solutionBoard[x][y] = -1;
return false;
}
Example-Output for findTour(0, 0, 1) with size = 7 (need to adapt all code to variable size!)
1 14 3 38 5 34 7 12 39 10 33 8 37 26 15 2 13 4 25 6 35 40 11 32 9 36 27 44 19 16 21 24 45 48 29 22 41 18 31 28 43 46 17 20 23 42 47 30 49
Still better: Use one of the other algorithms mentioned in the Wikipedia article, for example the rather simple Warnsdorff heuristic: “We move the knight so that we always proceed to the square from which the knight will have the fewest onward moves.” We can achieve this by sorting the moves…
public Point[] sortedPoints(final int x, final int y) {
Point[] sorted = Arrays.copyOf(MOVES, MOVES.length);
Arrays.sort(sorted, new Comparator<Point>() {
public int compare(Point p1, Point p2) {
return Integer.signum(nextMoves(p1) - nextMoves(p2));
};
private int nextMoves(Point p) {
Point dst = new Point(x + p.x, y + p.y);
if (canMove(dst)) {
int s = 0;
for (Point m : MOVES) {
Point dst2 = new Point(dst.x + m.x, dst.y + m.y);
if (canMove(dst2)) {
s++;
}
}
return s;
} else {
return 999;
}
}
});
return sorted;
}
… and changing the successors-loop to for (Point p : sortedPoints(x, y)). Results:
size findTour calls without and with heuristic 5x5 76497 25 7x7 8947880 49 8x8 ??? 64 20x20 ??? 400
Indeed, for all the sizes I tried, the findTour method was called exactly size^2 times, i.e. it found the tour on first try, without backtracking at all.