In "Guess Theory" I mentioned that I had encountered the "bad guess syndrome" for some minimal Samurai puzzles, when solving them with a DLX solver.

The normal solving method, for both computers and humans, is to solve as far as possible in each individual grid, using the "feedback" obtained by solving cells and/or getting candidate eliminations on the overlapping boxes to identify further solving/elimination possibilities.

When the puzzle is minimal, however, this local-grid solving method will typically not be able to complete the puzzle, and so we need some other method.

For single grids we would normally use T&E (backtracking), of course. But how to apply this to Samurai? One obvious way is to treat the puzzle as a single grid. This grid has 21 x 21 cells, of which only 369 are actually used. The 369 cells are all members of normal Sudoku houses in their local grids, but cells in the overlapped boxes belong to houses in two grids. This is easily transformed into an exact cover model for a DLX solver, or any T&E solver for that matter.

For the most part this does the job nicely, and solves most puzzles, even minimal ones, in a second or 2. But when it gets "bad guess syndrome", it might take 10-25 minutes! This problem needs sorting out, and there are at least 3 ways we might look at to solve it:

- A: implement a better NCS (next candidate selection) strategy for the T&E / backtracking solver

- B: use a different solver (eg SAT)

- C: use a direct method, such as "4CS", which I will describe below

Option B

I have to thank creint here for pointing out that SAT is actually very good at these particular puzzles - modelling the problem is easy, just as it is for DLX. This is the case for any exact cover problem, really. But because SAT solvers seem terribly slow, when used for 9x9 puzzles, compared to other methods, I had stopped using it, as I suspect many others have.

On larger grids, and particularly here for the Samurai case, it's a different story. The larger grid size here is NOT combined with extended domains (it's still a "1 to 9" puzzle), and in fact most minimal puzzles I have tested take less than a second. This includes creating the CNF and cranking up the SAT solver software. When you have an "inline" SAT solver that can be called directly from code, it's even faster. You might say that SAT is particularly "tuned" for this particular problem.