Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Knight's tour recursively in Java? NPlease help

 
Jon Bud
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20495
54
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Jon Bud
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20495
54
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic