aspose file tools*
The moose likes Java in General and the fly likes Knight's tour recursively in Java? NPlease help Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Knight Watch "Knight New topic
Author

Knight's tour recursively in Java? NPlease help

Jon Bud
Greenhorn

Joined: Jan 29, 2009
Posts: 12
This is a program I have to write trying to solve the knights tour in java. It is a brute force algorithm version of it. It has to be recursive. So this is what I have, I just get stack overflow exception though so I know I screwed the damn recursive function up (traverse). I suck at modeling problems using recursion and I need help on what to do to get his thing to work.
Please help me, I tried writing this thing out already. But it doesn't work. Recursion is one of the reasons why I switched out of a CS major to a COE major.

The board is basically modeled on a 2d array.

[edit]Add code tags. CR[/edit]
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19719
    
  20

First of all, don't you want all the recursive calls inside traverse actually return the results of those calls?

Second, after adding a line that simply prints ver and hor, your code seems to be jumping from (0,0) to (2,1) and back again, over and over. You should include a check to see if you haven't already accessed the field you want to jump to.
Untested:

However, that causes a NullPointerException. The reason is, it only checks out one possible path. If it fails that path null is returned and all other paths are not checked.

For such a brute force attempt, for a point you should check all available options (a.k.a. all unvisited positions you can reach from that point). If the first fails, check the second. If that fails, check the third, etc. This is called Backtracking. It has bad performance though: O(M^N) with M being the number of options per field and N being the number of fields; in this case you potentially have to check 8^64 possibilities.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Jon Bud
Greenhorn

Joined: Jan 29, 2009
Posts: 12
Thank you for your prompt reply Rob. I haven't tried it yet, but your input is greatly appreciated.
If I continued with your pattern after your comment //ect Won't the complier yell at me for not returning a type int[][] because all the returns are inside conditional blocks or should I just return a null reference at the end of the function. Thanks.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19719
    
  20

You always need to return something (or throw an exception), and null is mostly a good return value to indicate a non-valid return value. Just remember to check if it is null or NullPointerExceptions are sure to happen.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Knight's tour recursively in Java? NPlease help