[Java] Dancing Links: Algorithm X not working as expected!

Question

I have implemented the algorithm X using Dancing Links in Java, however, I'm getting unexpected results, that is I'm having dupes of rows of results which are not exact covers.

My code can be found at http://pastebin.com/m4cd3817f .

I have previously posted a chunk of code in which the wonderful community of StackOverflow helped me find a bug which I would never find (due to the lack of experience).

I have been at this for 5 days, understanding, coding, and now debugging it. I'm at my wits end at how I can make it work.

It would be awesome if you guys could spare some time to help this frustrated chump out :)

Thanks!

Answer 1

Write test cases for your code. For example, start with a solved Sudoku. Select a single cell and erase it. Run your algorithm and check that it in fact fills the missing cell with the correct value.

When that works, write another test that takes the same base Sudoku and erases two cells. Then three.

When it works for five cells, try a different Sudoku.

When you got that to work, too, try a Sudoku on the level "easy".

Gradually present harder problems to your code. Write tests for individual methods to make sure they do what they're supposed to do (and still do after a change you made). That will help you to debug your code and make sure it works and stays working.

Check out JUnit to learn how to automate the running of tests and the result verification.