Why we need backtracking for The Knight’s tour problem? Can we do it by using only recursion? i have tried to do it but it give wrong answer and i am not able to figure out where code or logic goes wrong.
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int[][] ans=new int[8][8];
for(int d=0;d<8;d++){
for(int e=0;e<8;e++){
ans[d][e]=-1;
}
}
int[] x={2,1,-2,1,-1,-2,-1,2};
int[] y={1,2,1,-2,-2,-1,2,-1};
func(x,y,ans,7,7,1);
}
public static void func(int[] x,int[] y,int[][] ans,int i,int j,int count){
if(count==64){
for(int d=0;d<8;d++){
for(int e=0;e<8;e++){
System.out.print(ans[d][e]+" ");
}
System.out.println();
}
}
if(ans[i][j]!=-1){
return;
}
else{
ans[i][j]=count;
for(int u=0;u<8;u++){
if(i+x[u]>=0 && i+x[u]< 8 && j+y[u]>=0 && j+y[u]<8){
func(x,y,ans,i+x[u],j+y[u],count+1);
}
}
}
return;
}
}
The need for back-tracking in the knights tour problem is critical. The fact that you have not implemented your back-tracking in your code is the main reason why it does not work.
To fix it you must at least clear the position at the end of your method. I.e when you do ans[i][j] = count you must balance that with a ans[i][j] = -1 to clear that square - you are not doing this.
That is not the only problem with your code but it is the main one.
Alternatives to back-tracking exist. You can create a new board at ever recursion level which is a copy of the current board but that is generally considered wasteful of memory.
Here's the code I ended up with:
// The board size.
private static final int SIZE = 8;
// Contents of board squares when empty.
private static final int EMPTY = -1;
// The 8 possible x,y moves for the knight.
private static final int[] x = {2, 1, -2, 1, -1, -2, -1, 2};
private static final int[] y = {1, 2, 1, -2, -2, -1, 2, -1};
public static void printBoard(int[][] board) {
// Print out the board.
for (int d = 0; d < SIZE; d++) {
for (int e = 0; e < SIZE; e++) {
System.out.print(board[d][e] + " ");
}
System.out.println();
}
}
public static boolean knightsMove(int[][] board, int i, int j, int count) {
boolean finished = false;
// Only step onto empty squares that are on the board.
if (i >= 0 && i < SIZE && j >= 0 && j < SIZE && board[i][j] == EMPTY) {
// Mark my route.
board[i][j] = count;
// Count up.
count += 1;
// Are we done?
if (count > SIZE * SIZE) {
System.out.println("=== Solution ===");
// Print the solution.
printBoard(board);
// Finished now.
return true;
}
if (count == SIZE * SIZE) {
// Nearly there - print something to show progress.
System.out.println("=== Try === (" + i + "," + j + ")=" + count);
// Print the current state.
printBoard(board);
}
// Look around to try all moves from here.
for (int u = 0; u < x.length && !finished; u++) {
// Try the next place.
finished = knightsMove(board, i + x[u], j + y[u], count);
}
// Clear my trail - you missed this.
board[i][j] = EMPTY;
} else {
// Cannot go there.
return false;
}
return finished;
}
public static void knightsMove() {
int[][] board = new int[SIZE][SIZE];
// Clear to EMPTY.
for (int d = 0; d < board.length; d++) {
for (int e = 0; e < board[d].length; e++) {
board[d][e] = EMPTY;
}
}
// Start at (7,7) with count 1.
knightsMove(board, 7, 7, 1);
}
Be patient - it takes a long time to complete - as you would expect. On my PC it takes about 20 minutes to get to:
=== Solution ===
29 42 51 60 27 22 17 24
50 59 28 41 52 25 20 15
43 30 61 26 21 16 23 18
62 49 58 53 40 19 14 7
57 44 31 48 33 8 3 10
36 63 34 39 54 11 6 13
45 56 37 32 47 2 9 4
64 35 46 55 38 5 12 1
I made the following changes:
x and y arrays static - they do not need to be parameters.static final EMPTY to indicate empty.boolean result when finished to stop the search there.board and knightsMove.SIZE for board size.Please do not use this code for your homework - you will learn much more by doing this yourself and understanding why each part works.