More Sudoku.

Little sudoku update. So, I’ve been working on various algorithms to try and work towards solving a pretty knotty problem with respect to Sudoku. It’s turning out to be much more difficult than expected.

I have a “naive” algorithm which gets correct results for smaller board sizes, but which will not complete for a regular sudoku board in my lifetime.

I have a “clever” algorithm, which is slower for small boards, but bigger for fast ones. Unfortunately, it gets wrong results (for reasons I understand), which is not the end of the world, and fixable – it misses some cases.

However, the clever algorithm also seems to get inconsistent results: if I swap a board where the squares are filled with an equivalent board where the squares are empty, I should get the same answer, and I don’t. Debugging in progress: I have probably taken a shortcut somewhere that I shouldn’t have done.

I have also attempted a modest improvement at improving the speed of the exact cover algorithm by improving how it picks constraints. To my astonishment, unless the number of constraints is very large, and the subset of them which change is quite small, it’s actually not any quicker than the naive algorithm, which is n/2 cost.

Regardless, both algorithms are too slow, and I also have some more unusual-ish ideas about how to make a faster algorithm. The only problem it takes so much code to try out each new idea and then find whether it works or is bust. Perseverance will be required!

Once I have a good algorithm, then I can start thinking about distributing it across lots of CPU’s.

Leave a Reply

Your e-mail address will not be published. Required fields are marked *