   # Discrete Piece Fitting puzzles

Many puzzle problems can be expressed as Descrete Piece Fitting (DPF) puzzles. Intuitively these kind of puzzles are stated as: you are given a set of pieces, and a frame with open locations, and you have to attempt to put all the pieces in the frame, such that all open locations are occupied.

Examples of these kind of problems are:

Assume that the locations are numbered from 0 to (l-1), where l is the number of locations. Then for each piece there will be a number of possible orientations by which the piece can be fitted in the frame. Each orientation can be described by listing the locations covered.

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
```

## Mathematical formulation

In mathematical terms, DPF puzzles can be descrived as:

Given:

• Set of pieces P
• Set of locations L
• Fit function F: P -> L**
Requested:
```     { 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
```

## The contest

Write a program which can find all solutions for DPF puzzles in the most efficient way.

Here is my program.

## Paper by Donald E. Knuth

Of course, one should not be surprised if Donald E. Knuth did write a paper about a certain computer science and math problem that one is interested in. But this time, I was really surprised when I read his paper called Dancing Links dealing about the subject. (Thanks to Bob McNelly for pointing me to this article.) In this paper, he shows that the DPF puzzles can be mapped onto the exact cover problem, which is known to be NP-complete. He also gives a very efficient algorithm for solving exact cover problems. Although I did not compare his program with mine with respect to execution time, I get the feeling that his is more efficient than mine. He also shows how to extend it, such that it can deal with puzzles where locations can be left empty.

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.

## Geometric puzzle representation

Because most of the DPF puzzles are related to puzzles made from real three-dimensional pieces, there exist a more compact representation which describes the geometrics of the pieces and the frame in coordinates. We used the following format:
```<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.

# 845 Combinations

(This puzzle was brought to my attention by Bob McNelly.) For the original description of the "845 Interestingly Combinations" puzzle (Taiwan: R.O.C. Patent 66009), click here. It carries a Chinese title, "Dr. Dragon's Intelligence Profit System." There is also a page in Japanees available, which has much nicer graphics. The puzzle is available from www.puzzletts.com.

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.

# Domino puzzles

Domino puzzles consist of a grid in which 42 squares are marked with a number ranging from 0 to 6. Each number occurs exactly 6 times. The question to answer is whether all the squares with a number can be covered with the domino stones from a normal set of dominos, in such a way that the numbers match the number of dots on the domino stones.

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 6
```
There 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.

# Morse Alphabet Reordering Puzzle

If you would send the letters of the alphabet in the alphabetic order using the
morse code you get a sequence of 82 dots and stripes. How many non-alphabetic orderings of the letters of the alphabet exists, which when send in morse code would result in the same sequence (ignoring the pauzes between individual letters)?

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.