Description

I recently received a pull request adding support for secondary columns to my implementation of DLX. I must confess that these were new to me because I didn't make it to the end of the original paper. I have now added my own support for this feature to DlxLib. As such, I thought I would try to solve Ripple Effect puzzles because this is what motivated the originator of the pull request mentioned above. It took me a while to figure out how to apply DLX to Ripple Effect puzzles but I finally got there.

I also have another project which makes use of secondary columns - see TetraSticks.

Details of the DLX Matrix

Primary columns

• One primary column per position (row/col) in the grid. These primary columns ensure that the grid is fully populated i.e. every position in the grid is filled exactly once.

• One primary column for each value in each room. These primary columns ensure that every room is fully populated and that there are no duplicate values in a room. For example, a room with four cells must contain one each of 1, 2, 3 and 4.

Secondary columns

There are four sets of secondary columns for each unique number that appears in the grid. For example, if the grid consists of a mixture of rooms with 1, 2, 3, 4 and 5 cells, then the solved puzzle will contain a mixture of 1s, 2s, 3s, 4s and 5s. In this case, we will have 4 x 5 = 20 sets of secondary columns. The number of columns in each set of secondary columns will be numRows x numCols. These sets of secondary columns are used to enforce the proximity constraints. This is best explained using an example. Say we have a 5 x 5 grid with position (0, 0) at bottom left. Lets say that we have a 2 at (1, 3):

-----
-2---
-----
-----
-----

The first set of secondary columns represents the position of the 2 itself plus the positions above that must not contain another 2 (one of these lies off the grid):

-x---   (01000)
-x---   (01000)
-----   (00000)
-----   (00000)
-----   (00000)

0000000000000000100001000

The second set of secondary columns represents the position of the 2 itself plus the positions below that must not contain another 2:

-----   (00000)
-x---   (01000)
-x---   (01000)
-x---   (01000)
-----   (00000)

0000001000010000100000000

The third set of secondary columns represents the position of the 2 itself plus the positions to the left that must not contain another 2 (one of these lies off the grid):

-----   (00000)
xx---   (11000)
-----   (00000)
-----   (00000)
-----   (00000)

0000000000000001100000000

The fourth set of secondary columns represents the position of the 2 itself plus the positions to the right that must not contain another 2:

-----   (00000)
-xxx-   (01110)
-----   (00000)
-----   (00000)
-----   (00000)

0000000000000000111000000

I refer to these up/down/left/right values as the 'ripples' caused by placing a value. Maybe this is why they are called Ripple Effect puzzles ?

Of the 20 sets of secondary columns, only 4 of them will be populated in any particular row. The other 16 sets of secondary columns will be filled with 0s. So in other words, we have a set of secondary columns for each of the following:

• the up/down/left/right ripples of placed 1s
• the up/down/left/right ripples of placed 2s
• the up/down/left/right ripples of placed 3s
• the up/down/left/right ripples of placed 4s
• the up/down/left/right ripples of placed 5s

Screenshot

There is a Ripple Effect Tutorial. This is a screen grab of the puzzle used in the tutorial:

This is a screenshot of RippleEffectDlxConsole solving the above puzzle:

This is a shot of the WPF app solving the same puzzle:

WPF App TODO List

• Get basic window working with background and grid
• Draw the cells of a room
• Draw the border around a room
• Draw a number in a cell
• Draw an initial value in a cell (like drawing a number but needs to look slightly different)
• Solve the puzzle on a different thread
• Render the solution
• Render the search steps
• Add a Solve button
• Add a Cancel button
• Add a slider to control the speed at which the search steps are displayed

Links

• Ripple Effect (puzzle) on Wikipedia
• Puzzles > Ripple Effect [Nikoli]
• Sample problems of Ripple Effect puzzle [nikoli.com]
• DLX
• Algorithm X
• DlxLib