Recursive backtracking has been implemented how can I simulate arriving a spot on a chessboard once

[Jon Bud]

So, -1 value in a square represents a spot that has not been traversed already. However, as this code runs the knight tours the board, however, he does not do it by only visiting each square once. I think what happens is, once he gets caught some where he goes back a space and then checks if he can move in another direction, and he does. But, this is a violation of the rules because the square he goes back onto is already been visited. So, my question is, how can I realize this current function to perform the right tour were the knight goes through the entire board jumping onto each space only once. I thought this problem had to do with backtracking, and I though thats what I was doing but it ended up messing the way the knight moves. Thank you for your input.

  public class KnightTour {

	static int[][]board = new int[8][8];
	static int globalCount = 0;
	static int[][] countBoard = new int[8][8];
	static int moveCounter = 0; 
	
	public static void main(String[] args) {
		init(board);
		init(countBoard);
		
		System.out.println(traverseII(0,0,0));
		
		System.out.println(globalCount);
		print(countBoard);
		
		
	}
	
	
	
	

	
	
	
public static boolean traverseII(int count, int ver, int hor){
		
	countBoard[ver][hor] = moveCounter;
	moveCounter++;
			
	board[ver][hor] = count;		//store the count number at that location at the board
	
	if(count >= 64){
		return true;
	}
	
	//up 2 left 1
	else if (ver > 1 && hor > 0 && board[ver-2][hor-1] == -1 && traverseII(count + 1, ver-2, hor-1))  {  
          return true;    }
    //up 2 right 1
    else if(ver > 1 && hor < 7 && board[ver-2][hor+1] == -1 && traverseII(count + 1,ver-2,hor+1)){    
         return true;  }
	
    //down 2 right 1
    else if(ver < 6 && hor < 7 && board[ver+2][hor+1]== -1 && traverseII(count + 1,ver+2,hor+1)){
    	 return true;}
    //down 2 left 1
    else if(ver < 6 && hor > 0 && board[ver+2][hor-1]== -1 && traverseII(count + 1,ver+2,hor-1)){
    	 return true;}
    
    //right 2 up 1
    else if(hor < 6 && ver > 0 && board[ver-1][hor+2]== -1 && traverseII(count + 1,ver-1,hor+2)){
    	 return true;}
    //right 2 down 1
    else if(hor < 6 && ver < 7 && board[ver+1][hor+2]== -1 && traverseII(count + 1,ver+1,hor+2)){
    	return true;}
    
    //left 2 up 1
    else if(hor > 1 && ver > 0 && board[ver-1][hor-2]== -1 && traverseII(count + 1,ver-1,hor-2)){
    	 return true;}
    //left 2 down 1
    else if(hor > 1 && ver < 7 && board[ver+1][hor-2]== -1 && traverseII(count + 1,ver+1,hor-2)){
    	 return true;}
    
    return false;
	
}
	public static void init(int[][] array){
		for(int i = 0; i < array[0].length; i++){
			for(int a = 0; a < array.length; a++){
				array[i][a] = -1;
			}
		}
	}
	public static void print(int[][] array){
		boolean flag = false;
		for(int i = 0; i < array[0].length; i++){
			System.out.println();
			flag = false;
			for(int a = 0; a < array.length; a++){
				if(flag){
						System.out.print("   " + array[i][a]);
						flag = false;
				}
				else{
					if(array[i][a] < 10){
						System.out.print("  " + array[i][a]);
						flag = true;
					}
					else{
						System.out.print("  " + array[i][a]);
					}
				}
			}
		}
	}	
	public static boolean boardTraversed(int board[][]){
		//checks to see if board is not traversed
		for(int i = 0; i < board[0].length; i++)
			for(int a = 0; a < board.length; a++)
				if(board[i][a] == 0)
					return false;
		return true;
	}

}


  

[Lucas Franceschi]

well, you are right about backtracking.

if you want to have some examples, and some base for your program, try looking for the eight queens puzzle in java, there are a lot of distributed code out there, its a great example of backtracking..


i'm sorry i have no time for reading your full code, but that's my suggestion.

regards

[Ulf Dittmer]

Jon Bud wrote:once he gets caught some where he goes back a space and then checks if he can move in another direction, and he does. But, this is a violation of the rules because the square he goes back onto is already been visited.

Let's say the knight is on square A (now set to, say, 17). From there, it tries square B (which is set to 18). Now it discovers that from B no further moves are possible. Backtracking means that square B is eliminated, in other words, set to -1. That does not mean that square A is visited again - it's not, because it was never left. So there should not be a new check for the value of square A.

I think the previous code version you had would have made this easier to implement; consider moving the recursive call out of the if condition, and back into the if block.

[Jon Bud]

So your saying that at some point I have to have an extra conditional that will allow me to set back a square to untraversed, -1, if at that point the knight gets stuck. But, I can't visualize how to put this in. If I put it inside each and every if block don't I have to have a version for each case the knight can move.

Or,
Do I add this as an additional if else() or for that matter is this an else clause. In stead of just returning false at the end. Would say else{ array[ver][hor] = -1; return false;} would this cover the matter if the knight cannot find any other route then the only thing left to do is set the current value to -1, return false that he could not find a tour here. But, the part I'm really stuck on, is how do I end up going backwards in the code. How do I tell the knight to go backwards, in every case if he hits a dead end?
Thank you again.

[Ulf Dittmer]

So your saying that at some point I have to have an extra conditional that will allow me to set back a square to untraversed, -1, if at that point the knight gets stuck.

Yes. At the end of the method, just before the "return false", you need to unset the current field, because no further move from there is possible, yet the tour is not yet completed.

I just noticed that that's precisely what you're mentioning further down:

Would say else{ array[ver][hor] = -1; return false;} would this cover the matter if the knight cannot find any other route then the only thing left to do is set the current value to -1, return false that he could not find a tour here.

But, the part I'm really stuck on, is how do I end up going backwards in the code. How do I tell the knight to go backwards, in every case if he hits a dead end?

That's being done implicitly by undoing the setting of the knight on the current field. That marks this branch of the overall tree of possible moves as a dead end. All the other branches will continue to be explored, until they, too, hit a dead end, or the 64th step can be completed.

[Jon Bud]

Just wanted to thank Ulf Dittmer for constantly helping me through this knight tour problem.

[Ulf Dittmer]

You're welcome.