Examples of these kind of problems are:

- The Soma puzzle by Piet Hein.
- various polyomino problems.
- Eternity Puzzle
- 845 Combinations
- domino fittings
- cutting stick problems
- Morse alphabet reordering puzzles
- Latin Squares

A solution consist of a list of orientations, one for each piece, such that each of the locations occurs exactly once in all of the orientations. A solution can also be represented by listing which of the pieces (by name/number) cover which location.

A DPF puzzle can be represented in the following format as a text file:

<l> // number of locations <p> // number of pieces <o_1> // number of orientations for piece 1 <m_1,1> <l_1,1,1> .. <l_1,1,(m_1,1)> ... <m_1,(o_1)> <l_1,(o_1),1> .. <l_1,(o_1),(m_1,(o_1))> <o_2> // number of orientations for piece 2 ... .. <o_p> // number of orientations for piece p ...The first two lines specify the number of locations and the number of pieces. The following lines describe how the pieces can fit in the locations. For each of the

An example, may be the following rather trivial puzzle (a restricted domino fitting in a 2x3 frame):

6 3 2 2 0 1 2 2 3 3 2 0 2 2 2 4 2 4 5 2 2 1 3 2 3 5Another example (a cutting stick problem for sticks of length 4, 5, and 6) is:

5 3 2 1 3 2 0 2 3 1 4 2 0 3 2 1 2 3 2 0 4 2 1 3 3 0 1 2

Given:

- Set of pieces
*P* - Set of locations
*L* - Fit function
*F*`:`*P*->*L*^{**}

{The puzzle can then be reformulated as a graph problem (under certain conditions). Let graphS:P->L^{*}|SpartitionsLandAllpinP(S(p)inF(p)) }

The problem can now be stated as finding a subset ofO=Union_{p in P}F(p)E= { {o_{1},o_{2}} |ExistspinP({o_{1},o_{2}}subsetF(p))or(o_{1}neo_{2}ando_{1}intersectiono_{2}neempty) }

For the second problem the adjecency matrix looks like:

| ------+---------------- 3 | x x x 0 2 | x x x x x 4 | x x x 0 3 | x x x x x x x 1 2 | x x x x x 0 4 | x x x x x 1 3 | x x x x x 0 1 2 | x x x x x

Here is my program.

I developed a program to covert DPF puzzle descriptions into exact covering problems. I also developed a program for solving exact covering problems that is optimized for finding one solution, not all possible solutions, as the one that was developed by Knuth. This program also uses dangling links in its implementation.

<dimensions> <use-colours> <l> // nr locations <x_1> <y_1> <z_1> <c_1> // position and colour // first location .... <x_l> <y_l> <z_l> <c_l> <p> // nr pieces <l_1> <v_1> // description first piece <x_1,1> <y_1,1> <z_1,1> <c_1,1> .... <x_1,l_1> <y_1,l_1> <z_1,l_1> <c_1,l_1> <l_2> <v_2> .... <l_p> <v_p> <x_p,1> <y_p,1> <z_p,1> <c_p,1> ....The parameter

Example descriptions are:

- Soma puzzle
- Pentominos in 5x4x3
- Pentominos in 15x4
- 845 Combinations (See below for details.)
- A domino puzzle
- Morse alphabet puzzle
- Twelve pentominos and one quatromino in 4x4x4 cube
- Small Chinese Wooden Puzzle in 3x5: solutions
- Small Chinese Wooden Puzzle in 3x5: solutions

A program which can transform puzzles given in the compact format
into the DPF puzzle format is `gen_dpfp.c`.

After some private communications, Bob produced a
geometric puzzle representation
for this puzzle. With this he found 92 unique solutions,
of which 9 appeared to be bogus solutions due to crossing
pieces. There are actually 83 unique solutions, as is
also reported by Donald. E. Knuth in his paper
*Dancing Links*. (In Knuths terminology
this puzzle is called a tetra-stick puzzle.)

There is no easy way to remodel the puzzle such that
the bogus solutions do not appear, because for this
we need to change the definition such that certain
positions may be covered with at most one piece,
whereas now each position should be covered with
exactly one piece. Bob has written a C-program
called `to845.c`, which
will post-process the output and filter out the bogus
solutions. Bob also discovered that for the rightmost
solution on the second row of the instructions there
are only 16 solutions, not 26 as listed. This makes
the total number of solutions equal to 835, not 845.

In the following domino puzzle all the marked squares form a 6 by 7 rectangle:

0 0 0 2 0 3 0 4 0 1 2 1 3 1 4 1 0 5 0 6 2 2 2 4 5 1 6 1 2 3 4 3 2 5 2 6 4 4 4 6 5 4 6 3 4 5 6 5 1 1 3 3 3 5 6 6There are 20160 different solutions to this domino puzzle. The big questions is: Is there an arrangement with more solutions? A Seemingly Trivial Problem I think.

This puzzle is equivalent to the this DPF puzzle. (There are 8574 solutions to this one.)

If you furthermore require that none of the characters may be send at exact the original position, you get a much restricted puzzle, which is represented as this DPF puzzle, and only has 48 solutions.

My home page