Knight Tour, Does the recursive call get placed inside the if block?

[Jon Bud]

First, of all let me say that the function needs to be implements recursively, in java, and MUST FIND a knights tour ever single time. I've spend alot of time trying to implement this and have gone through about 4 functions for the traverse. Alright the specific question is, where can I put the traverse function call recursively so that the function will tour the entire chess. Board as it is now the knight only moves once and the program returns false. I've tried to methods to doing this, one jumping the knight into the square and then checking if the knight is still on the board, and two checking if the knight can jump to the square first and then jumping if the spot is valid.

I know that this flies against both the philosophy and regulations of javaranch. For details, please look here: DoYourOwnHomework

Please ask a specific question about your code that can be answered and you will likely quickly receive many helpful answers.

I'm sorry about not showing that I've shown effort. But, I've got to point in the program where I just have hit a BRICK WALL, I keep taking tid bids of advice from many people and try to apply them. These two functions are a result of applying my own knowledge about programming concepts and advice from others. And the program ends up producing bad output on me. I have a hard time understanding recursion.



I noticed that whenever the knight moves out of the bounds of the array the program justs ends because it can no longer enter into any of the if statements.
if(hor < 0...) in the first move hor ends up being -1 or -2 so program just returns false at the end. I don't know how to fix this though. Any ideas? I think this has to do with backtracking. I don't know how to get this program to backtrack correctly.

 public class KnightTour {

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

	
	public static boolean traverse(int count, int ver, int hor){
		//if we are in the proper bounds we can assign the value to the board
	    if(count >= 64){
	    	return true;
	    }
	    //up 2 left 1
		else if(hor <= 7 && hor >=0 && ver >= 0 && ver <= 7){
			board[ver][hor] = count;
			traverse(count+1,ver-2, hor -1);
		}
	    //up 2 right 1
		else if(hor <= 7 && hor >=0 && ver >= 0 && ver <= 7){
			board[ver][hor] = count;
			traverse(count + 1, ver-2, hor+1);
		}
	    //down 2 right 1
		else if(hor <= 7 && hor >=0 && ver >= 0 && ver <= 7){
			board[ver][hor] = count;
			traverse(count + 1, ver+2, hor+1);
		}
		//down 2 left 1
		else if(hor <= 7 && hor >=0 && ver >= 0 && ver <= 7){
			board[ver][hor] = count;
			traverse(count + 1, ver+2, hor-1);
		}
	    //left 2 down 1
		else if(hor <= 7 && hor >=0 && ver >= 0 && ver <= 7){
			board[ver][hor] = count;
			traverse(count + 1, ver+1, hor-2);
		}
	    //left 2 up 1
		else if(hor <= 7 && hor >=0 && ver >= 0 && ver <= 7){
			board[ver][hor] = count;
			traverse(count + 1, ver-1, hor-2);
		}
	    //right 2 down 1
		else if(hor <= 7 && hor >=0 && ver >= 0 && ver <= 7){
			board[ver][hor] = count;
			traverse(count + 1, ver+1, hor+2);
		}
		//right 2 up 1
		else if(hor <= 7 && hor >=0 && ver >= 0 && ver <= 7){
			board[ver][hor] = count;
			traverse(count + 1, ver-1, hor+2);
		}
		return false;
	}
	
	
	/*public static boolean traverse(int count, int ver, int hor){
	
	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] == 0 && traverse(count + 1, ver-2, hor-1))    
          return true;    
    //up 2 right 1
    else if(ver > 1 && hor < 7 && board[ver-2][hor+1] == 0 && traverse(count + 1,ver-2,hor+1))    
         return true;  
    
    //down 2 right 1
    else if(ver < 6 && hor < 7 && board[ver+2][hor+1]== 0 && traverse(count + 1,ver+2,hor+1))
    	 return true;
    //down 2 left 1
    else if(ver < 6 && hor > 0 && board[ver+2][hor-1]== 0 && traverse(count + 1,ver+2,hor-1))
    	 return true;
    
    //right 2 up 1
    else if(hor < 6 && ver > 0 && board[ver-1][hor+2]== 0 && traverse(count + 1,ver-1,hor+2))
    	 return true;
    //right 2 down 1
    else if(hor < 6 && ver < 7 && board[ver+1][hor+2]== 0 && traverse(count + 1,ver+1,hor+2))
    	return true;
    
    //left 2 up 1
    else if(hor > 1 && ver > 0 && board[ver-1][hor-2]== 0 && traverse(count + 1,ver-1,hor-2))
    	 return true;
    //left 2 down 1
    else if(hor > 1 && ver < 7 && board[ver+1][hor-2]== 0 && traverse(count + 1,ver+1,hor-2))
    	 return true;
    
    if(count >= 57)
    	globalCount = count;		//test to see how high the program gets to, it does not get past a count of 57;
	
    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] = 0;
			}
		}
	}
	public static void print(int[][] array){
		for(int i = 0; i < array[0].length; i++){
			System.out.println();
			for(int a = 0; a < array.length; a++){
				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;
	}

}    

[pete stein]

Jon Bud wrote:please have mercy and post a working version tested if possible that fulfill the above requirements.

I know that this flies against both the philosophy and regulations of javaranch. For details, please look here: DoYourOwnHomework

Please ask a specific question about your code that can be answered and you will likely quickly receive many helpful answers.

[Ulf Dittmer]

As it is, at most one of the 8 possible recursive calls can happen for any given position. You need to rearrange the code so that all 8 calls could potentially happen. This involves removing all the "else" keywords form the traverse method.

You should also check the return value of the recursive traverse calls. Whenever it returns "true", further execution should be stopped by calling "return true".

[pete stein]

The only other thing I'd suggest would be to order your potential paths based on how many paths branch out from next square. You want to try the path with the fewest branches first as this will more readily and quickly lead you to a solution. Otherwise you'll be either running your program all day, or more likely, running out of memory.