Dancing Links for Killer Sudoku Cages and Jigsaw

Jean-Christophe

I recently added a generator for cages and jigsaw to my software JSudoku.

It's using DLX to find an exact cover of the grid with polyominoes.

I won't discuss generating the polyominoes, finding their transformations, symmetries and other properties which is a fun project by itself.

D. Knuth's papers describes well how to setup DLX for this. In brief : we have 81 columns for the 81 cells. There will be many rows, one for each polyomino (cage) at a particular location, orientation... Each row contains one node per cell linked to the corresponding column.

To generate a layout at random, I randomly shuffle the rows within each column. I also shuffle the columns linked to the root node. I then let DLX find a solution and interrupt it after the first solution found.

Generating Cages for Killer

For killer we want to mix polyominoes of various size. The number of polyominoes grows exponentially as their number of cells grows. There are only 2 fixed dominoes, 6 fixed triominoes but 760 fixed heptominoes, 2725 fixed octominoes and 9910 fixed nonominoes (jigsaw).

At the corners and along the sides of the grid, I filter all polyominoes which would produce too small an "island" of uncovered cells. eg an L shaped triomino at the upper right corner would leave a single uncovered cell. So I skip these. I also skip all polyominoes with a hole, a ring shape. This filtering isn't an absolute necessity since DLX will immediatly hit a contradiction if it were to choose such a row, but it helps reducing the number of rows to create, in particular for Jigsaw.

Assume we want a killer with cages of up to 7 cells. If we put all possible fixed polyominoes at all locations, we would get too many rows for the larger ones, thousands of them. The solution found by DLX will tend to include too many large cages since DLX will see a lot of rows with large polyominoes and only a few with 2 or 3 cells. So I randomly skip some of the largers polyominoes.

This filtering helps reducing the number of rows with large polyominoes. But it isn't enough to get a "reasonable" amount of large cages. For instance, we may want to have at most 4 cages with 6 cells or more.

So I implemented extra DLX columns to limit this amount of large cages using a subclass of the Column class. I've put the Cover() and Uncover() functions as methods of the regular Column class. Then I implemented a subclass AtMostColumn with a counter for maximum number of rows which may be chosen. This subclass overwrites Cover() to decrement the counter. It will only call Cover() of its Column superclass when reaching zero but does nothing else otherwise. Uncover() does the reverse.

With this AtMostColumn subclass, I can control the maximum amount of rows (here cages) that may be chosen within the column. This column should not be linked to the root node. It should be optional / non-primay, otherwise DLX will try to cover it once and only once.

In addition to the 81 columns for the cells, I have 3 or 4 AtMostColumn. Each row (cage) contains an additional node into the AtMostColumn corresponding to its number of cells. We may have one such AtMostColumn for all cages of 6 cells or more, or any other configuration.

Generating symmetric grids

Symmetric grids imposes more constraints since the cages goes in pairs (or by 4 or 8). Chosing one cage forces to choose the symmetric one(s). Depending the symmetry, some locations for some cages are invalid because cages cannot overlap partially, intersects each other. Either the symmetric cages are disjoints or self symmetric, equal to itself when turned (or flipped).

I can see two approaches to symmetric grids:

1. We setup DLX for all the cells and put all symmetric cages in the same DLX row. Chosing one will automatically choose the symmetric cage(s). As far as DLX is concerned, nothing else needs to be done. But we want to know which "half" of the symmetry the node belongs to. So I added an ID to the node to distinguish them.

2. Another approach : We setup DLX for only half of the cells (or a quater or 1/8) and then reconstruct the symmetical pieces from the solution found by DLX. I got this idea later and did not try it, but it may be easier to setup.

Whichever the case we have to take care of symmetric cages which partially overlap, keeping only those which are disjoint or self-symmetric. I always put rows for all the self-symmetric cages. I do not randomly skip the large ones since there are only a few valid ones.

I made several tests with various symmetries, combined or not, and found that it's easier to generate grids with rotational symmetry than it is with axial/flipped symmetry. For rotational symmetry, the only "area" highly constrained is the center. For axial symmetry, all the cells along the axis of symmetry are highly constrained, there are only a few valid cages there. Combining several axial symmetries is even harder : eg both left-right and top-bottom or both diagonals (transpose).

Generating Jigsaw
Using DLX for this is probably not the best approach, but it can be done.

Comments, ideas... are welcome.
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.

CJ · Posted: Wed Apr 09, 2008 12:43 am Post subject:

Adak · Posted: Wed Apr 09, 2008 1:10 am Post subject:

Jean-Christophe · Posted: Wed Apr 09, 2008 12:07 pm Post subject:

tarek · Posted: Sat Apr 12, 2008 11:08 am Post subject:

I recently started generating & rating sudoku variants.

I also was planning to generate templates 1st. for irregular shaped sectors & Killers

My questions:

1. do you always succeed in finding a valid KILLER for each templete.

2. Would it be better to keep a "pool" of templates rather than generating them

3. I've seen some bizzarre cage shapes (connected diagonally), are these in common use ?

thanx

tarek

Jean-Christophe · Posted: Sat Apr 12, 2008 3:28 pm Post subject:

My answers:

1. No, in particular for templates with many rectangular cages. It's even worse if most cages are rectangular with same orientation. During the generation of filled killers, I do some filtering to avoid deadly patterns (like Unique Rectangle). It helps a lot to avoid killers with multiple solutions and works fine most of the times, but some templates will still produce multiple solutions. Note: a killer has fewer UR's than a vanilla sudoku because different cages may break the UR pattern. Since this deadly pattern filtering is not a standard DLX procedure, it's not easy to undo at backtrack since every change must be undone in the exact reverse order it was done such as to revert the DLX structure to a consistent state.

2. I don't know. It's not way I go since I always generate a template.

3. Not very common, but it can be done easilly by also adding one cell (pixel) at the right and below. It's the way I build them. Warning: there are a huge number of diagonal polyominoes for large sizes (eg 147941 diagonal polyominoes with 8 cells).
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.

tarek · Posted: Sat Apr 12, 2008 7:03 pm Post subject:

Thanx JC,

Just to recap on your killer generation

1. template generation
2. filled grid to satisfy cage constraints (No sum constarint at this stage) (DLX not needed Question

)
3. cage sums calculated
4. Remove all clues
5. check for unique solution (cage & sum constarints applied, DLX needed)

is this how you do it ?

tarek

Jean-Christophe · Posted: Sun Apr 13, 2008 6:08 am Post subject:

Yes, tarek.

Except for step 2. I also use DLX to generate a filled grid. I setup DLX with all candidates for all cells. With 9 optional columns for each cage to ensure no digit is duplicated. These are optional/secondary columns which are not linked to the root node (like diagonals for the N Queen problem). I then shuffle columns and rows at random then start searching for solutions. It stop at the first solution found. During the search, I filter UR's as described above.
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.

tarek · Posted: Sun Apr 13, 2008 9:08 am Post subject:

Jean-Christophe · Posted: Sun Apr 13, 2008 2:26 pm Post subject:

tarek · Posted: Thu Apr 17, 2008 3:26 pm Post subject:

I'll see how it goes when I have time Mad

Thanx again

tarek