I found a wooden puzzle in my mother's bookshelf. This is all there is to it:
All pieces can be moved freely. A single piece:
Each piece has one corner each in the colors Red, Green, Blue, and Yellow. The goal is to match colors of adjacent corners. Solving this becomes a neat programming exercise.
Brute Force
How long would it take to just enumerate all solutions? There are 8 pieces and 8 locations, which gives us 8! = 40320 permutations. However, the puzzle can be rotated 180 degrees and be identical, so it's just 20160 permutations of the pieces. The individual pieces can also be turned in 4 different directions independently of each other. So for each permutation, we have 4^8 = 2^16 = 65536 turns. In total we have 8! / 2 * 2^16 ~ 1.3 billion solutions. So it takes about the same amount of time for the computer to solve it by brute force, as for a person to solve it manually.
MIP
The problem is naturally modeled as a constraint problem. For MIP, one can use one binary variable for each combination of location, piece, and turn. In total, 8*8*4 = 256 variables. There are 22 "conflict edges" where colors from two different pieces must match in an adjacent corner.
The most numerous constraints, however, are the structural constraints. We must ensure that each piece gets exactly one location, and vice versa. Each piece must also get exactly one turn. These constraints are all on the same form: a sum of a set of binary variables must equal 1. These are also called symmetric constraints.
For each corner of a location, we must know its color, as a function of the decision variables. This is necessary so that we can express the color matching constraints in terms of the decision variables. For each corner of a location (dot) and each color, I create one auxiliary variable. In total, that becomes 8*4*4 = 128 dot-by-color variables.
Pattern Picking constraints
The dot-by-color variables are bound to the decision variables using
pattern picking constraints. For each decision variable X and each dot-by-color variable Y, make the constraint:
If X dictates the same color for Y's dot as Y does, then:
X <= Y
Otherwise:
X + Y <= 1
How does this work? If X is 0, then Y can be either 0 or 1 without violating the constraints. However, if X is 1, then Y is forced to be 1 or 0 respectively, depending on which constraint is active. Note that we use the same Y variables for all decision variables, but they are cleverly bound together to all of them without risk for infeasible solutions.
Extra constraints for efficiency
It is implicit from the constraints on the pieces that for a given location, there will be exactly one dot per color, and one color per dot. This is something we can tell the solver beforehand, as constraints. This makes the solution go almost 4 times faster.
Result
The solution takes about 8 seconds for find with CBC, so it is not trivial for it.
Conclusion
Most constraints are for making the model internally self-consistent. These types of constraints arise from things that humans take for granted, such as the pieces being non-reusable. These internal constraints must be uncovered during the modeling process, and take a lot of time.
The pattern picking constraints are quite neat and abstract, and could possibly be packaged as part of a solver interface.
We can do some of the work for the solver by adding constraints that we can logically infer from the problem. This can be important for performance optimizing MIP models.
