Kanoodle, IQ Fit, and Dancing Links

Introduction

During a recent vacation flight, my nephews had a couple of interesting puzzles to occupy them on the plane: Kanoodle and IQ Fit. In both cases, the objective is to arrange a set of colored pieces so that they exactly fill a rectangular grid, as in the following figure showing an example solution to the Kanoodle puzzle:

Example solution to Kanoodle puzzle.

Example solution to Kanoodle puzzle.

The IQ Fit version uses a smaller 5-by-10 grid, and only 10 pieces instead of 12… but the pieces are three-dimensional, so that some of the spherical “vertices” of the pieces may poke down through the bottom of the tray.  (For reference, following is Python code specifying the configurations of pieces for both puzzles.)

kanoodle = {
    'Green': ((1, 1, 0), (1, 2, 0), (2, 2, 0), (2, 3, 0), (2, 4, 0)),
    'Cyan': ((1, 1, 0), (1, 2, 0), (1, 3, 0), (2, 3, 0), (3, 3, 0)),
    'Purple': ((1, 1, 0), (1, 2, 0), (1, 3, 0), (1, 4, 0)),
    'Yellow': ((1, 1, 0), (1, 2, 0), (2, 2, 0), (3, 1, 0), (3, 2, 0)),
    'Orange': ((1, 1, 0), (2, 1, 0), (2, 2, 0), (2, 3, 0)),
    'Blue': ((1, 2, 0), (2, 2, 0), (3, 2, 0), (4, 1, 0), (4, 2, 0)),
    'Pink': ((1, 1, 0), (1, 2, 0), (1, 3, 0), (1, 4, 0), (2, 3, 0)),
    'Gray': ((1, 2, 0), (2, 1, 0), (2, 2, 0), (2, 3, 0), (3, 2, 0)),
    'Magenta': ((1, 1, 0), (1, 2, 0), (2, 2, 0), (2, 3, 0), (3, 3, 0)),
    'Red': ((1, 1, 0), (1, 2, 0), (2, 1, 0), (2, 2, 0), (2, 3, 0)),
    'White': ((1, 1, 0), (2, 1, 0), (2, 2, 0)),
    'LightGreen': ((1, 1, 0), (1, 2, 0), (2, 1, 0), (2, 2, 0))
    }

iq_fit = {
    'Green': ((1, 1, 0), (2, 1, 0), (2, 2, 0), (3, 1, 0),
              (1, 1, -1), (2, 1, -1)),
    'Magenta': ((1, 1, 0), (1, 2, 0), (1, 3, 0), (2, 2, 0),
                (2, 3, 0), (1, 1, -1)),
    'Cyan': ((1, 1, 0), (1, 2, 0), (1, 3, 0), (1, 4, 0),
             (2, 2, 0), (1, 2, -1), (1, 3, -1)),
    'LightGreen': ((1, 1, 0), (1, 2, 0), (2, 2, 0), (3, 1, 0),
                   (3, 2, 0), (3, 2, -1)),
    'Blue': ((1, 4, 0), (2, 1, 0), (2, 2, 0), (2, 3, 0), (2, 4, 0),
             (2, 2, -1), (2, 4, -1)),
    'Purple': ((1, 1, 0), (1, 2, 0), (1, 3, 0), (2, 2, 0),
               (1, 1, -1), (1, 3, -1)),
    'Yellow': ((1, 1, 0), (1, 2, 0), (2, 1, 0), (2, 2, 0), (2, 3, 0),
               (2, 4, 0), (2, 4, -1)),
    'Pink': ((1, 1, 0), (1, 2, 0), (1, 3, 0), (1, 4, 0), (2, 1, 0),
             (2, 2, 0), (1, 2, -1)),
    'Orange': ((1, 3, 0), (2, 1, 0), (2, 2, 0), (2, 3, 0), (2, 4, 0),
               (2, 1, -1), (2, 3, -1)),
    'Red': ((1, 4, 0), (2, 1, 0), (2, 2, 0), (2, 3, 0), (2, 4, 0),
            (2, 1, -1), (2, 4, -1))
    }

A natural question to ask is: which puzzle is harder?  For example, which puzzle has more possible solution configurations?  Can we count them all?  It turns out that we can, using Donald Knuth’s “Dancing Links” (DLX) algorithm (see references below).  But the motivation for this post is to describe another interesting application of DLX: before attempting an exact count, we can first estimate the number of solutions, to determine whether it is even worth trying to enumerate them.

Exact Cover

The Kanoodle and IQ Fit puzzles are examples of the more general exact cover problem: given a matrix of 0s and 1s, does it have a set of rows containing exactly one 1 in each column?  Many other problems may also be reduced to that of finding an exact cover: SudokuLangford sequences, and graph colorings are just a few examples.

Often the most interesting part of solving many of these problems is figuring out the transformation to an exact cover instance.  That is, how do we construct a 0-1 matrix representing our problem, so that a set of rows containing exactly one 1 in each column corresponds to a solution to our problem?  In the case of Kanoodle (and IQ Fit is similar), there are two “kinds” of columns: one column for each of the 12 puzzle pieces, and one column for each position in the 5-by-11 rectangular grid.  Each row of the matrix represents a possible placement of one of the pieces, with a single 1 in the corresponding “piece” column, and additional 1s in the corresponding occupied “position” columns.  A set of rows solving the exact cover problem will have exactly one row for each piece, oriented and positioned so that all of the grid positions are occupied by exactly one piece.

Considering all possible placements of all pieces, the Kanoodle puzzle has a total of 1789 rows and 67 columns, while the IQ Fit puzzle has 3440 rows and 60 columns.  (David Austin wrote a great AMS Feature Column on this same topic, suggesting that the Kanoodle puzzle has 2222 rows; there are a couple of bugs in his implementation, however, yielding some extra invalid piece placements and some missing valid ones.)

Dancing Links (DLX)

Now that we have a matrix representing our exact cover problem, we can feed it to Knuth’s Dancing Links algorithm (referred to as DLX), which is essentially “just” a backtracking depth-first tree search for all possible solutions, but with a “doubly-doubly” linked list sparse matrix representation that allows very efficient undo operations.  I won’t bother with details here, especially since Knuth’s paper is so readable.

My implementation is available in the usual location here, as well as on GitHub.  There isn’t much there; the search algorithm itself follows Knuth’s pseudocode nearly verbatim, right down to the variable names.

There are quite a few DLX implementations in the wild already, but I ended up writing my own for several reasons.  First, the matrix row and column identifiers should be of generic types; the “real” problem is rarely represented in terms of simple consecutive integer matrix indices.  Second, it seemed reasonable to be able to construct the sparse matrix by adding 1s individually, in any order.  Although the diagrams in Knuth’s paper suggest a nice “weaving loom” look to the data structure, there is no need to preserve any particular order relation on the rows or columns.  Third, although I didn’t use it for this analysis, it was relatively simple to add support for “secondary,” or optional columns, which must be covered at most once, instead of exactly once.  (As discussed in Knuth’s paper, the N queens problem is a natural example where this is handy.)

Estimating Tree Size

Finally, and most importantly, I wanted to try using the Monte Carlo sampling technique, mentioned briefly in Knuth’s DLX paper, to estimate the size of the search tree without actually exploring all of it.  As Knuth puts it (see Reference (3) below):

Sometimes a backtrack program will run to completion in less than a second, while other applications seem to go on forever. The author once waited all night for the output from such a program, only to discover that the answers would not be forthcoming for about 1,000,000 centuries.

The sampling algorithm is pretty simple: take a random walk from the root of the tree to a leaf, at each step recording the (out-)degree d_k of the current vertex at depth k, and selecting a child vertex (at depth k+1) uniformly at random.  It is not difficult to show by induction that the expected value of the resulting product of degrees along the sample path equals the total number of leaves in the tree.

Furthermore, the expected value of the product d_0 d_1 d_2 ... d_{k-1} for some fixed k equals the total number of vertices at depth k in the tree… as long as we define d_j=0 for depths j beyond the length of the (possibly shorter) sample path.

This algorithm almost feels like cheating; we are trying to estimate the size of an entire tree, when there are whole chunks of it that we may never explore!

The following figure shows the result of 2 million such random paths through the Kanoodle DLX search tree.  The blue points indicate the current running estimate of the total number of solutions– more precisely, the number of tree vertices at depth 12.

Monte Carlo estimate of number of Kanoodle solutions (blue), with actual number of solutions (red).

Monte Carlo estimate of number of Kanoodle solutions (blue), with actual number of solutions (red).

In this case, the couple of minutes needed to collect the random samples turned out to be longer than the 30 seconds to simply traverse the entire tree, yielding exactly 371,020 different solutions to the Kanoodle puzzle (shown in red above).

The IQ Fit puzzle was more interesting; the following figure again shows the running estimate (in blue) of the number of leaf vertices at depth 10 in the DLX search tree.

Monte Carlo estimate of number of IQ Fit solutions (blue), with actual number of depth 10 terminal vertices (red), and actual number of solutions (green).

Monte Carlo estimate of number of IQ Fit solutions (blue), with actual number of depth 10 terminal vertices (red), and actual number of solutions (green).

Using this estimate of what turned out to be exactly 254,531,140 vertices at depth 10 (shown in red above), I expected to get an exact count via a full tree traversal in about 6 hours.  However, just an hour and a half later, my program had already stopped, reporting that there were only 67,868,848 solutions (shown in green), about one-fourth what I expected.  What was going on?

After further investigation, I realized that, unlike the Kanoodle puzzle, it is possible to arrange the three-dimensional IQ Fit pieces so that all 10 pieces fit into the grid… but with some spaces still left unfilled.  These non-solution arrangements account for the remaining three-fourths of the leaf vertices at depth 10 in the tree.

References:

  1. Austin, D., Puzzling Over Exact Cover Problems, American Mathematical Society Feature Column, December 2009 (HTML)
  2. Knuth, D., Dancing Links, Millenial Perspectives in Computer Science, 2000, p. 187-214 (arXiv)
  3. Knuth, D., Estimating the efficiency of backtrack programs, Mathematics of Computation, 29 (1975), p. 121–136 (PDF)
This entry was posted in Uncategorized. Bookmark the permalink.

17 Responses to Kanoodle, IQ Fit, and Dancing Links

  1. Suppose you were to modify your program to generate new puzzles, but with the constraint that there be only one solution, like Sudoku. Would the result still be an interesting puzzle or would the solution be boringly obvious (example: a two-piece “puzzle”)? Or maybe there are no one-solution puzzles if you limit yourself to the same number of pieces.

    • Good question– yes, in fact the “real” problems in the accompanying puzzle booklets have exactly this form. For example, this is one of the most difficult “Genius level” Kanoodle puzzles, where you are given the location of 6 of the 12 pieces, and you must fill the remainder of the grid with the other 6 pieces. Although the Kanoodle booklet does not explicitly say this anywhere, it can be verified (using the push() method to specify a “partial solution”) that the solution is indeed unique.

      All of the most advanced problems in the Kanoodle booklet start with 6 pieces; I wonder if this is the minimum? That is, does *any* initial placement of 5 or fewer pieces yield either 0 or >=2 solutions?

      Maybe not– to make things more interesting, most of the most advanced “Wizard level” puzzles in the IQ Fit booklet start with just 2 of the 10 pieces! (Some of them start with 3 or even 4 pieces.) However, those starting pieces aren’t “bunched together” in a contiguous region of the grid like they are in the Kanoodle problems. Instead, they are more spread out, which intuitively might make it easier to ensure a unique solution. Perhaps there are similarly difficult Kanoodle problems that start with just 2 or 3 pieces more spread out across the grid.

  2. Pingback: Analysis of (hexagonal) Battleship | Possibly Wrong

  3. Pingback: Generating Mini-Crosswords | Possibly Wrong

  4. Sean Law says:

    I’ve implemented my own version of the dancing links algorithm and it works exactly as described for the exact cover scenario. So, for a simple sparse matrix:

    [0, 1, 0]
    [0, 0, 1]
    [1, 0, 0]
    [1, 1, 0]
    [0, 1, 1]
    [1, 1, 1]

    the sets of rows that result in an exact cover (all columns having at most one 1) are:
    [0, 1, 2], [1, 3], [2, 4], and [5]

    However, the details regarding the secondary columns is a bit vague. From what I could gather from various Knuth/non-Knuth resources, it says that all you need to do is:

    ” The only difference is that we initialize the data structure by making
    a circular list of the column headers for the primary columns only. The header for each
    secondary column should have L and R fields that simply point to itself. The remainder
    of the algorithm proceeds exactly as before, so we will still call it algorithm DLX.”

    After making these changes to how the matrix is represented and then setting the first column as a secondary column (columns 2 and 3 are primary), I end up with the following sets of rows as solutions:

    [0, 1], [1, 3], [4], and [5]

    While all of these are valid solutions and some overlap with exact the exact cover solutions, it appears that other solutions are missing (i.e., some of those from the exact cover solution set):

    [0, 1, 2] and [2, 4]

    Perhaps this is a misunderstanding on my part but am I missing something conceptually or is Knuth’s explanation incomplete?

    • Sean Law says:

      I’d appreciate it if you could test out this case and tell me if your implementation can handle generate the full set of solutions with secondary columns. That’ll at least confirm whether or not my implementation is correct. Thanks!

    • I ran your test cases and confirms that the output agrees in both cases. The idea of the secondary columns is that they *may* be included in a solution (at most once), but they don’t *have* to be. The effect of the “optimized” approach is that no solutions will be generated that include rows with *only* secondary column positions set to 1.

      If you want to include these, you can take the approach described immediately following your quoted paragraph from Knuth’s paper: “A generalized cover problem can be converted to an equivalent exact cover problem if we simply append one row for each secondary column, containing a single 1 in that column.”

  5. Bryan H. says:

    A friend and I have been working through approaches to finding all of the solutions to the Kanoodle puzzle too. My code only finds ~154K solutions, however, and thinks it finished — far short of your stated 371K solutions. By any chance do you have those solutions posted anywhere I can download them and compare them to see where I fell short?

    • You can re-generate my solutions as follows: using the code here, run examples/boards.py to generate the inputs (kanoodle.txt is the one we want, the others are instances of other puzzles), then build the C++ code (e.g., g++ test_dlx.cpp), and run “test_dlx kanoodle.txt -2 > solutions.txt” (mode==-2 lists all solutions; see the comment header for other modes to just count them, estimate them, etc.).

      If you’re not familiar with the Python or C++ environments, let me know and we can agree on a convenient representation of solutions. (That is, for example, one of the solutions output above is (46, 43, 53, 145, 596, 379, 18, 1625, 850, 285, 81, 678), which only makes sense if we map each integer in [0..1788] to a particular colored piece in a particular position and orientation. See boards.py for my approach to this mapping; but if something else is more convenient let’s discuss.)

      • Bryan H. says:

        Impressive, I was able to recreate your set of solutions in <5 minutes. My code takes hours to find the 154K solutions so obviously I have much to learn!

        After poking through the code it's not obvious to me how to map your integer to a piece placement. You don't happen to have a routine that will convert an integer back to a list of ( piece_id, x, y ) tuples by any chance?

  6. @Bryan, I updated board_cover() in boards.py to also return the list of rows, so that an integer k in the solution corresponds to rows[k], which is a tuple of the name (i.e., color) of the piece and a tuple of grid positions.

    • Bryan H. says:

      @possiblywrong — ok, so I dumped the solutions from your tool, and the very first solution says that it has both placements 12 and 14. If I’m interpreting the output of todays update to board_cover(), both of those are piece C (blue), which seems to indicate that it’s placing the C piece twice. Do you see that?

      • I’m guessing that you perhaps (1) ran the *original* boards.py to generate inputs kanoodle.txt, (2) ran “test_dlx kanoodle.txt -2 > solutions.txt” to generate a list of solutions, then (3) ran the *updated* boards.py to get the integer-to-piece rows[] mapping? Instead, re-run test_dlx with the *updated* kanoodle.txt output from the new version of boards.py. If that doesn’t correct the disconnect, please let me know and we’ll track down the problem.

        This was me trying to be helpful :). That is, in the original implementation, the rows container starts life as a *set*, which handles elimination of duplicate positioning/orientation of pieces as we move/rotate them throughout the grid. But when that set is *enumerated* to convert it to a sparse zero-one matrix for input to test_dlx.exe, the result is an *arbitrary* ordering of the rows (i.e., integer-to-piece mapping), that in general can even vary from one run of boards.py to the next (see here).

        Now that we’re exposing that rows container, we convert it to a sorted(rows) list, which guarantees that its order will be deterministic and repeatable… but we have to re-run test_dlx.exe to get solutions that correspond to this new/fixed row ordering.

      • Bryan H. says:

        That fixed it, thx.

        I have no understanding how this code could possibly be 25000 times more efficient than mine at finding solutions. Trying to parse DK’s dancing links, it seems like it’s just a method of adding and removing pieces from the solution quickly… Is the code really just brute-force trying every combination of every placement of every piece? And with dancing links it’s just ridiculously fast?

  7. You’re right that the “dancing links” part is really just a very efficient “undo” operation. More importantly than this, though, the perhaps unintuitive challenge with problems like this is that, as Knuth describes in his paper, “Any systematic rule for choosing [a branch in depth-first-search] in this procedure will find all solutions, but some rules work much better than others.” The idea is that we want to hit dead-ends in the backtracking search as “shallowly” as possible. Again from Knuth, the idea of his Algorithm X is “choosing, at each stage of a backtrack procedure, a subproblem that leads to the fewest branches, whenever this can be done efficiently.”

    • B. Harris says:

      Just a quick follow-up — my friend and I both managed to create solvers using python that generate the full set of solutions. Mine runs in about 191 seconds, which is *far* slower than yours, but fast enough to not inhibit me.

      We made some density plots for each of the pieces to see where each piece tends to be placed the most often, and have identified many 2-piece “starts” where there is only a single solution. I’m still running the tool to see if there are any single-piece starts with a single solution, i.e., if you put piece X in a certain spot, there’s only one solution after that. I suspect there aren’t any, but I haven’t confirmed that yet.

      I’m also curious what … say… 5-piece start results in the largest number of unique solutions, meaning if you started someone with that board they have the easiest job of finishing.

      I realized this problem is a little bit like an ant colony climbing up a tree looking for fruit on the branches. The ants can search every branch, which will take a long time (what else do they have to do), but if they could figure out how to eliminate branches without searching them that could save them a huge amount of time.

      I still have no clue how your tool actually attacks this problem to identify dead-ends as shallowly as possible. My tool borrows an idea from my friend and takes the “L” (“+”-shaped) piece and moves it around the top left quadrant, then tries to fill in the remaining pieces, starting in the top left corner. Switching to this approach, I went from a few dozen solutions a second to like 1800 solutions per second (not all of them unique).

      Thanks for the fun problem, help, and discussion!

  8. Mugur says:

    I tried another approach. Using 10 lookup tables for each position of the pieces on the board using simple for-next loops, I try to put the pieces on the board in the free spaces. If a piece cannot be placed, the tests with the rest of the parts are abandoned because a piece cannot be placed on a smaller surface board than the initial test.
    If a piece has been successfully placed then a check is made not to create spaces smaller than a piece or in which it is impossible to place pieces by using another 11-th lookup table ( for the moment it has 313 entries ) . If impossible spaces are created then give up testing the rest of the pieces and start another loop.
    Thus running ( just for fun) on a PIC16F18857 microcontroller running at 32 MHz (8 MIPS) , starting from a purple part position (there are 228 possible positions but 114 unique starting positions without rotations) all positions are calculated in about 3 days with the remaining 9 pieces.
    In total about 1 year all 1.14 x 10 exp 22 positions of the parts are tested

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.