aspose file tools*
The moose likes Java in General and the fly likes Recursive backtracking has been implemented how can I simulate arriving a spot on a chessboard once Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Recursive backtracking has been implemented how can I simulate arriving a spot on a chessboard once" Watch "Recursive backtracking has been implemented how can I simulate arriving a spot on a chessboard once" New topic
Author

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

Jon Bud
Greenhorn

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

Lucas Franceschi
Ranch Hand

Joined: Nov 10, 2008
Posts: 106

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


Lucas Franceschi
Software Developer for SGI Sistemas, lukas1596@gmail.com
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 39530
    
  27
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.


Ping & DNS - updated with new look and Ping home screen widget
Jon Bud
Greenhorn

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

Joined: Mar 22, 2005
Posts: 39530
    
  27
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
Greenhorn

Joined: Jan 29, 2009
Posts: 12
Just wanted to thank Ulf Dittmer for constantly helping me through this knight tour problem.


Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 39530
    
  27
You're welcome.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Recursive backtracking has been implemented how can I simulate arriving a spot on a chessboard once
 
Similar Threads
Recursive Problem.
recursion
array of array help
Knight Tour, Does the recursive call get placed inside the if block?
Knight's tour recursively in Java? NPlease help