DLX and samurai (five overlapping grids)

garthd

Hi

Just wondering if it's possible to use DLX to solve a samurai puzzle (five overlapping grids) and verify it has a single solution in one pass, or if you need to use DLX on each puzzle? In some cases I've seen some individual grids that have 900+ solutions - and I'm trying to work out how you could efficiently work through the various grids in a time effective way (its obviously fairly simple if you get one or more grids that have unique solutions when solved independently)

On this point, I'm assuming that any naked singles can be used to reduce possibilities before starting the DLX (e.g. naked singles are given and hence won't impact if a puzzle has multiple solutions - or does this not hold true for interlocking grids?)

m_b_metcalf

Jean-Christophe · Posted: Mon Apr 21, 2008 4:05 pm Post subject:

That's the way I go for overlapping variants. I setup one DLX for the whole samurai.

The DLX candidate rows in the overlapping cells will have 6 nodes since they belong to two sub-grids (2 sudoku rows and 2 sudoku columns).

Indeed, I went lazy and made two boxes for the overlapping regions, one for each sub-grid, hence they have 7 nodes. It's not a necessity, but doesn't really hurt since both boxes are identical.

Hope this helps
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.

garthd · Posted: Fri Aug 01, 2008 12:00 am Post subject:

Hi Jean-Christophe

Ok...I'm trying to modify some DLX code in visual basic - www.codeproject.com/KB/vb/Dancing_Links_Library.aspx to make it work for samurai puzzles. This code appears to be based on Stan Chesnutt's DLX implementation in java. At present, I'm trying to feed in the samurai by treating it as a 21x21 grid so that all five grids are input at once. I'm assuming from your comments that I'll need to modify the code so that there are 6 nodes throughout (rather than 4 nodes) to account for the portions of the overlapping grids. These additional 2 nodes would not be initialised (and hence ignored) unless they relate to an overlap - is this the correct way or how you do it? Would there be any other changes required to the vanilla 9x9 DLX code?

Jean-Christophe · Posted: Fri Aug 01, 2008 10:55 am Post subject:

Hi,

Make sure you understand how to setup DLX for vanilla sudoku. A samurai is not a 21x21 latin square. There are some voids. There are 9 candidates, not 21.

Any generic DLX implementation should work. I don't know the particular implementation you mention, but I've seen optimized implementations assuming each DLX candidate row has exactly 4 nodes. Such an optimization cannot be used for samurai and other variants like Sudoku-X since DLX candidate rows have a variable number of nodes.

I first create DLX columns for all cells and DLX row nodes for all candidates. I keep a reference to easilly access these. For a 3x3 samurai there are 369 cell columns and 369*9=3321 rows.

Then, I create 9 DLX columns for every house: row, column, box, diagonal, windoku, disjoint group... One DLX column per candidate. For each candidate and each cell in the house, I create a node linked to the corresponding DLX row node for the cell. For a 3x3 samurai there are 5*9*9=405 DLX columns for all samurai rows. Dito for all samurai columns. The 4 overlapping boxes could be defined only once, but it does not hurt defining them twice for the two sub-grids. So it could be (5*9-4)*9=369 or 405 DLX columns.

This defines the DLX structure for an empty puzzle with all candidates for all cells. To solve a particular puzzle, just filter the given clues like you would for vanilla sudoku.
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.

garthd · Posted: Fri Sep 12, 2008 6:26 am Post subject:

Thanks Jean-Christophe

The DLX code I was trying to use was indeed 'optimised' to assume four nodes. I have come up with an approach that allows me to apply this DLX implementation to solve samurai puzzles (and ensure they have a unique solution) by applying an iterative approach.

Step 1. Attempt to solve the grids 1,2, 4 and 5 - then the middle grid 3, using various logic based solving methods (excluding any methods that rely on uniqueness). Keep swapping solved cells/candidate eliminations between overlapping regions until no more progress can be made. This hopefully deduces a number of cell values or removes candidates, hence reducing the 'search space' for the next steps. This step will also solve many easier samurai puzzles without having to go to the following steps.
Step 2. For any grids that are still unsolved after step 1, attempt in turn to solve each individual grid using DLX. For speed reasons, this step is limited to searching for up to 1000 solutions and the DLX is setup to ensure solutions returned are consistent with the candidate possibilities remaining after step 1. If less than 1000 solutions are returned for one of the five puzzle grids, then the following substeps are performed in order.
a) If a unique solution found to a grid, update this grid and overlapping regions and return to step 1 and run the logic based methods again.
b) if there are less than 1000 solutions returned by DLX for grids 1,2,4 or 5, these are filtered by eliminating all non unique solutions. This is achieved by looking at the overlapping subgrid. If there are solutions that result in an identical overlapping subgrid, then all these solutions are removed - as these solutions would produce an overall samurai puzzle that would have multiple solutions for the grid in question. If this filtering results in no remaining solutions for the grid, exit as the puzzle cannot be solved. if this filtering results in a single solution, update overlapping regions and return to step 1.
c) If filtering at 2b still results in multiple solutions, another round of filtering occurs. This examines the available solutions and attempts to discern if there are unsolved cells that have values shared by all the remaining solutions. If so, update these values and return to step 1.

This manages to solve all of the samurai puzzles I have thrown at it so far. Admittedly you could run all the steps and not be able to verify a single solution exists, but I haven't hit this point yet.

m_b_metcalf · Posted: Fri Sep 12, 2008 8:53 am Post subject:

Note that you can advance each of the five grids individually by the following method: if there are multiple solutions process them all (not stopping at 1000), keeping a running tally of the cells that have identical values in all solutions. These values are then common to all solutions and therefore are part of the final solution. The grid in question, including its overlapping region, can be updated accordingly.

Regards,

Mike Metcalf