Su Doku & Dancing Links

2017/11/21 code puzzles sudoku

I'm trying to practice some problem solving, and November 2017's Jane Street puzzle reminds me of a class of problem I usually solve, but with what seems to be too much effort and ad-hoc technique.

I had success with the referenced puzzle from May 2017, but I always feel like I am doing something wrong compared to how a true-blue mathematician would approach the problem. In particular, I always think about the enticingly-named "Dancing Links" techinque from Donald Knuth, associated with the equally intriguingly-named "Algorithm X".

The easiest way to develop some intuition about where I'm wrongheaded is to compare some elegant solution by a CS Master to a solution I've already coded myself. And it turns out that a McGill student, Ali Assaf, has put up precisely that online, many years ago. And I keep my old records from past challenges, so I dug up something dated July 2015 and compared to that.

The happy surprise is that benchmarking his approach and my existing approach with the project prompt from Project Euler's Problem #96 shows that my solver isn't actually any slower, it's just way uglier and less versatile! Silver linings!

To begin with, I have some completely unnecessary stuff. Obviously an abstract algorithm cannot depend on such hard-coded relationship delineation, so this must go.

I also glossed over some printing and reading functions, which just leaves the solver function itself. Like the relationship-finder, it's very non-generic. The first part is the deterministic sequential culling part of the algorithm, and the second part does iterative guesses. Notice the clunky recursion via Sudoku(self) and immediately swapping a row 😅. However, we later find that the idea old me had wasn't actually so bad after all.

Compare to Ali's solution:

I note that up until here, grid hasn't been used, so this is just an abstract definition of a completely generic Su Doku problem. exact_cover is only used in this location, so we may as well peek:

Interesting. X contains all the conditions that need to be fulfilled, and this here lays out which choices could possibly fulfill that condition. Reminds me of the Mahjong in Tichu.

Anyway, thus far the problem is purely generic, it contains no info about any particular Su Doku. We filter this universe of possibility into the subset corresponding to a particular Su Doku, using select.

This function has a mirror function deselect. Again, maybe good to peek at both here:

select returns the "columns" removed (not columns in the same sense as in normal Su Doku, btw), for usage in the solver algorithm, but it also modifies the universe sent to it. Perhaps it would be a bit clearer if instead of mutating X, it returned a new X which was then assigned. Maybe for a Haskell implementation some other time.

deselect just takes said columns and reinserts them. Here we note that it is the universe X that is continuously being modified, but Y is always untouched and used for reference.

Then we carry on in the main solver body:

And how does the solver work?

not X is the clear condition.

The heuristic for guesses.