aspose file tools*
The moose likes Java in General and the fly likes Knight Tour, Does the recursive call get placed inside the if block? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Knight Tour, Does the recursive call get placed inside the if block?" Watch "Knight Tour, Does the recursive call get placed inside the if block?" New topic
Author

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

Jon Bud
Greenhorn

Joined: Jan 29, 2009
Posts: 12
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.





pete stein
Bartender

Joined: Feb 23, 2007
Posts: 1561
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
Marshal

Joined: Mar 22, 2005
Posts: 41890
    
  63
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".


Ping & DNS - my free Android networking tools app
pete stein
Bartender

Joined: Feb 23, 2007
Posts: 1561
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Knight Tour, Does the recursive call get placed inside the if block?