|
|
Examples of these kind of problems are:
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 p pieces we have to describe in
how many ways it can be fitted in the locations. This is called the
number of orientations, the numbers o_i. For each of
the orientations we have to specify which locations it occupies.
In the above description each orientation is given on a separate line
(indented with 4 spaces). It starts with a number m_i,j
indicating how many locations are occupied by this orientation, followed
by the numbers of the locations: l_i,j,k.
(The indentation is only for clarity reasons; all the numbers could
also be given on a single line.)
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 5
Another 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:
{ S: P -> L*
| S partitions L and All p in P (S(p) in F(p)) }
The puzzle can then be reformulated as a graph problem
(under certain conditions).
Let graph G(O, E) be defined by:
O = Union p in P F(p)
E = { {o1, o2}
| Exists p in P ({o1, o2} subset F(p))
or (o1 ne o2 and o1 intersection o2 ne empty)
}
The problem can now be stated as finding a subset of O with equal
size of L, such that no two vertices in O are connected by
edge in E. This sounds very much like one of the known NP-complete
problems.
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 dimensions gives the number of dimensions of
the puzzle. This can either be 1, 2, or 3. If the dimension is 2, the
z-coordinates need to be omitted. If the dimension is 1, then only
the x-coordinate has to be given.
The parameter use-colours indicates wheter the locations
are marked with a colour which has to match with the part of the piece
containing it. The value can either be 0 or 1. In case it is 0 all
c-values need to be omitted. If it is 1, c-values need to be given
in the form of numbers. The v-values which are need to be given for
each piece, indicates the degree of freedom by which the piece can
be moved around. A value of 1 indicates that the piece can only be
moved. A value of 2 indicates that the piece can also be rotated
in the x-y-plane. A value of 3 indicates that the piece can be rotated
in any of the 24 different orientations. Even with a two dimensional
puzzle a v-value of 3 makes sense. It means that the piece can also
be put in the puzzle upside-down. Not all pieces need to have the
same v-value. Sometimes a single a-symetric piece can be given
a value of 1 to eliminate all iso-morphic solutions with respect
to the locations.
Example descriptions are:
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.