The New Sudoku Players' Forum

[Mathimagics]

.
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.

[Mathimagics]

Option C


This is "4CS", a four-corner direct solving method. The idea is simple - choose one of the 4 corner boxes of the middle grid (the boxes that overlap the corner grids), and enumerate the "Box Completions". A box completion is a set of 9 values that can be placed in the box, with the following properties:

• it gives a unique solution to the outer grid

and

• it gives a valid solution to the middle grid

For each box completion, we recursively test the other 3 corners, using the accumulated corner settings of the middle grid. When testing the last (4th) corner, the middle grid validity test should be replaced with a "unique solution" test.

This works particularly well for me because I can now use my fast 9x9 grid solver throughout - by choosing the initial corner box with the least number of possible completions, my solve times for two of the worst-case puzzles that I had found for DLX, the solve times were reduced from 1500s / 350s to 0.06s / 0.09s.

[tarek]

Hi Mathimagics and well done,

When you say Unique solution for a subgrid then surly it is a special case as there will be cases when a unique solution is only present for the entire puzzle but none of the subgrids would have a unique solution without having information from the rest of the puzzle.

The best samurai design IMO requires that if one subgrid's clues were to be removed then none of the other subgrids can be solved even when combined together. This means that each subgrid needs all the other subgrids to solve.

Tarek

[Hajime]

First you eliminatie all candidates of all Sudokus, using methods of your liking. Then you solve singles in row, col, box, diagonal, etc of all Sudokus.
Finally you start all over again. This is Sisesuso way of working in a large grid containing all Sudokus. With regard to brute force it first selects the Sudokus with the most givens, then within that Sudoku select the cell with the least candidates.

[Mathimagics]

Hello Hajime,

This method is for cases where all available techniques (singles, etc) have been applied to all grids, and this has been repeated until there are no more eliminations to be found, and yet the puzzle remains unsolved. The puzzles are not cases which are intended for human solving - one might begin with such a puzzle, and wish to "reduce" it to a minimal form - we might be trying to find out what is the minimum number of clues that are needed, for example.

Speed then becomes a major consideration, since we must perform many of these "hard" solve operations as we remove more clues. The "4CS" method is one possible way of doing this quickly.


Hello tarek,

My brief outline of the method was perhaps too brief!

A fundamental property of a valid Samurai puzzle is this - if you fix the contents of any of the 4 overlapped boxes, then the corresponding outer "subgrid" (I call this a "corner grid", as opposed to the "middle grid") becomes an independent 9x9 puzzle, since there is nothing in the other 4 grids that can possibly affect it.

Therefore, we can test various settings for these boxes, by solving the corresponding "corner grid" as a stand-alone 9x9 puzzle - if this box setting does not produce a unique solution, then it cannot be the right setting, and so we can move on and try another one instead.

[tarek]

A fundamental property of a valid Samurai puzzle is this - if you fix the contents of any of the 4 overlapped boxes, then the corresponding outer "subgrid" (I call this a "corner grid", as opposed to the "middle grid") becomes an independent 9x9 puzzle, since there is nothing in the other 4 grids that can possibly affect it.

Ahhh... Now I see what you were after. That is true. Very clever

Tarek

[Hajime]

If you fix the upperleft box of the middle grid with 1-9 and then you solve the upper left corner grid, then it is possible that at the next (upper right) box you get stuck. The first box holds the wrong 1-9. Another 1-9 must be in the upperleft box together with another solution of the upper left corner grid. Most terrible is when you discover the faulty situation in the fourth box . This is possible, is it?

[Mathimagics]

Hello Hajime!

My algorithm description was definitely too brief!

I will try to explain how it works using "pseudo-code" … I will refer to the middle grid as MG, and the 4 corner grids (clockwise) as G1 … G4. The overlapped (corner) boxes are CB1 … CB4. A "setting" for CB# is some particular way to fill in that corner box.

The "+" operator indicates "union", so G1 + CB1 means G1 with CB1 filled in.

Top level

• for each CB1 setting:
  
  if (MG + CB1) has at least 1 solution, AND (G1 + CB1) has a unique solution then call Search( 2, MG + CB1)

Search(n, MG)

• for each CBn setting:
  
  if n = 4 then
  
  if (MG + CBn) has a unique solution AND (Gn + CBn) has a unique solution then
  
  • add 1 to Samurai-Solution counter
  • if SS counter > 1 then abort ("Multiple Solutions)
  else (n = 2 or 3)
  
  if (MG + CBn) has at least 1 solution, AND (Gn + CBn) has a unique solution, then call Search( n+1, MGn + CBn)

All "solution tests" are applied only to 9x9 puzzles (corner or middle grid).

At each level of Search, ie (2, 3, 4), the MG parameter has one more box added, so the number of ways of filling in CBn are greatly reduced.

The "faulty situation" you describe cannot occur, as we only consider box settings that are valid for the current MG (which has with boxes 1, 2 progressively filled in) AND which also give a unique solution in the next corner grid. Only when both these conditions hold true do we call the next level.

[EDIT] I have since found that the "has a unique solution" conditions above are insufficient - they really all have to be "has any solution" - otherwise false positives can result. See the post below.

[Hajime]

That code will do very well. All I state that a first unique solution for CB1 is not enough and you may have to go for a next solution. I wonder if this also will also be applicable for larger Gattai, starting at a corner/sudoku-with-one common box. Looking for a unique grid solution implies that you need to explore all solutions (stop at 2, which is error) and discover that there is only 1.

[tarek]

That code will do very well. All I state that a first unique solution for CB1 is not enough and you may have to go for a next solution. I wonder if this also will also be applicable for larger Gattai, starting at a corner/sudoku-with-one common box. Looking for a unique grid solution implies that you need to explore all solutions (stop at 2, which is error) and discover that there is only 1.

My impression is that Mathimagics described technique leads to significantly reducing solving times. It is one part of the process not the entire process.

Tarek

[Mathimagics]

.. a first unique solution for CB1 is not enough and you may have to go for a next solution.

This is true, and the recursion I described does this. At the top level, all possible settings for CB1 are tested, and those that produce a unique solution in corner grid 1 are then checked with a call to Search.

The enumeration/recursion must test all combinations, unless at some stage we have evidence that implies a second solution to the complete (5 grid) puzzle, in which case we can terminate (abort) the process.

For larger gattai's, the basic idea would still work, but implementation would be more complicated, due to multiple overlapping grids. Samurai is a particularly simple model to implement. It is a single (middle) grid, surrounded by 4 corner grids each of which has a single overlapping corner box. Once these corner grids become joined to others managing the recursion is probably a non-trivial exercise … and not one I am likely to pursue any time soon!

Cheers
MM

[Hajime]

Hi Mathemagics, your 4CS algorithm is very clever. I will pursue this after my holidays.

[Mathimagics]

Option B

... 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.

Thanks to blue, I have identified a flaw in my CNF encoder, which didn't affect the validity of the CNF generated, but slowed it down dreadfully for Sudoku 16x16's.

My two hardest Samurai's (JSB-MinimalA, JSB-MinimalB) are now solved by SAT (via a MiniSAT dll) in 0.08s and 0.234s respectively, so it's really very quick! 4CS solves both in around 0.09s, and so they are much closer than I previously thought.

At this stage I think a proper "4CS" vs SAT benchmark test is needed. I need to get a suitable benchmark dataset of minimal puzzles together first, then we will see!

[m_b_metcalf]

Option C

This is "4CS", a four-corner direct solving method. The idea is simple - choose one of the 4 corner boxes of the middle grid (the boxes that overlap the corner grids), and enumerate the "Box Completions". A box completion is a set of 9 values that can be placed in the box, with the following properties:

• it gives a unique solution to the outer grid

and

• it gives a valid solution to the middle grid

For each box completion, we recursively test the other 3 corners, using the accumulated corner settings of the middle grid. When testing the last (4th) corner, the middle grid validity test should be replaced with a "unique solution" test.

I've been away for a while, and was interested to see this approach described. In fact, I have
already used this method to solve some very hard samurais, for instance this one from ruud:

Code: Select all

..9.7..8....6...2.6.5.4.....6.5.3...8.1.....7...8..9.4.....4...95...........65... 1  ruud samurai #1
8.9....1.....4...8..1.62....2.5..43.37..8.........6.........3.5...6.3.......7.8.. 2
.............1........6..........5.1.62..5.......9..32...4..........1......3.2... 3 
6...4.......57....2.7.........8...4..73.9...2..6..5.9....3..5.91..6......8....2.. 4
...7...4......2.9....5....37.2.6.......37.....9....35......4..628...3.....1...5.. 5 


This fails to advance using logic techniques and goes into guess mode:

Code: Select all

  .  .  .  .  .  .  2  1  6
  .  .  .  5  1  .  9  8  7
  .  .  .  .  6  .  4  5  3
  .  .  .  .  .  .  5  .  1
  .  6  2  1  .  5  .  .  .
  .  .  .  .  9  .  .  3  2
  .  .  .  4  .  .  .  2  .
  .  2  .  .  .  1  .  .  .
  .  .  .  3  .  2  .  .  .     middle sub-puzzle with guessed box 3


which solves it completely, using logic to finish it off. I have seen no puzzle that fails to yield to a successful guess in just one corner.

A further example is this X-samurai, also from ruud:

Code: Select all

.1.6.8....9..3...........2...5...........6...4.83.7.....................9..8.4... TL
...3.8.9.....1..3..4.............7.....4........7.28.1.....................2.3..5 TR   Ronin, an
....7.......................61...72...........28...35.......................9.... M
9..5.4.....................5.18.2........7.....7.............6..5..6.....7.3.9... BL
...1.6..7.....................9.27.3...3...........4...1...........9..2....6.5.3. BR   X-samurai from ruud


Logic solves 1 cell and then we guess:

Code: Select all

  .  .  .  .  7  .  .  .  .
  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .
  .  6  1  .  .  .  7  2  .
  .  .  .  .  .  .  .  .  .
  .  2  8  .  .  .  3  5  .
  .  .  .  .  .  .  8  9  4
  .  .  .  .  .  .  5  6  2
  .  .  .  .  9  .  1  7  3     middle sub-puzzle with guessed box 9


yielding a complete solution using logic to finish it off.

However, there is an intermediate approach. This is a hard puzzle that I generated myself:

Code: Select all

.93.78........5.6..7....1.8..6..92....2.8..91.........9.........38......2..4.3...  TL
....59........1...8..6....44....7.8.9.......3.1...5..2....1..5.....7.9......9.21.  TR
....6.......9........1......9.....677...8.4.3....5........1......................  M
29..5....7.5.68.............4......6....81.....2....9....92..4......3.....6.1.7..  BL
...7..........1......526....8....213....6..9.......7...6...8.7253..........39....  BR


and that similarly can be cracked by a single guess:

Code: Select all

  .  1  .  .  6  .  7  8  9
  .  .  .  9  .  .  1  3  2
  .  .  .  1  .  .  6  5  4
  .  9  .  .  .  1  5  6  7
  7  .  .  .  8  .  4  .  3
  .  .  .  .  5  .  .  .  .
  .  .  .  .  1  .  .  .  .
  .  2  .  .  .  .  .  .  6
  .  .  .  .  9  .  .  .  .    middle sub-puzzle with guessed box 3


But this puzzle yields to an alternative technique: use a brute-force solver to find all the solutions
to a sub-puzzle, keeping a tally of the common cells in the solutions. Here we have, for the bottom-left sub-puzzle,

Code: Select all

Cell count = 24
  2  9  .  .  5  7  .  .  .
  7  3  5  4  6  8  .  2  .
  .  .  .  .  .  .  .  .  .
  .  4  .  .  .  .  .  .  6
  .  .  .  .  8  1  .  .  .
  .  .  2  .  .  .  .  9  .
  .  .  .  9  2  .  .  4  .
  .  .  .  .  .  3  .  .  .
  .  .  6  .  1  .  7  .  .


Code: Select all

brute found 58 solutions
common cell count = 26
  2  9  .  .  5  7  .  .  .
  7  3  5  4  6  8  9  2  1
  .  .  .  .  .  .  .  .  .
  .  4  .  .  .  .  .  .  6
  .  .  .  .  8  1  .  .  .
  .  .  2  .  .  .  .  9  .
  .  .  .  9  2  .  .  4  .
  .  .  .  .  .  3  .  .  .
  .  .  6  .  1  .  7  .  .


which is sufficient progress to allow a solution to be found by logic (the extra clues are also in the middle sub-puzzle).

Note that the box-guessing technique cannot be used to minimize a puzzle with clues in the overlap boxes. If a puzzle is already minimal and such a clue is tested for redundancy the method will give a false positive.

Regards,

Mike

[creint]

Puzzle 1 and 3 are solvable with logic form my solver.
The harder ones should contain corners that have as much solutions as possible when filling the shared box from the middle puzzle.
For logic not to work should mean that clues are far from each other, so that more guess depth is needed to find exclusions.