A year ago I introduced this Doodle Fit game to my roommate Victor. We were playing it all day long. To stop the addiction, we then wrote a program to find the answers, which successfully destroyed the interest in playing the game. Got some time to rethink the problem last night. Here goes an interesting alternative to solve Doodle Fit, using 0-1 integer programming.
The rule of the game is simple: fit a set of given blocks into a given shape (no rotation). For example, try to fit the three blocks into the two-square shape.
This solution is pretty easy. Put the red block to the bottom-right corner and the green block to the left-most, leaving the blue block in the middle.
Let’s see how to model the game using a set of constraints. We use to denote whether to place the top-left corner of the block at : 1 for yes and 0 for no. Take the red block for an example. Since it can only be placed at two cells, or , this means that one and only one of and is 1. In other words, their sum must be 1. We have similar constraints for the other two blocks.
Additionally, each cell will be covered by one and only one block. For example, the top-left cell can be covered by either the green block placed at , or the blue block placed at ; it cannot be covered by the red block. So the sum of and must be 1. We have such a constraint for each cell, as follows.
I wrote a script doodle-fit.py
to automate the steps.
Prepare an input file
two specifying the shape and the
blocks, split by
---, as follows.
## #### ## --- * ** --- * * --- * **
Then generate the constraints using the script,
which writes them to
two.mod in the GNU MathProg language.
$ python doodle-fit.py < two > two.mod
Invoke a solver to get a solution. I use GLPK here.
You may try to add
glpsol to solve the constraints
with the SAT solver instead.
$ glpsol --math two.mod -w two.sol GLPSOL: GLPK LP/MIP Solver, v4.47 Parameter(s) specified in the command line: --math two.mod -w two.sol Reading model section from two.mod... 24 lines were read Generating b0... Generating b1... Generating b2... Generating c00... Generating c01... Generating c10... Generating c11... Generating c12... Generating c13... Generating c22... Generating c23... Model has been successfully generated GLPK Integer Optimizer, v4.47 11 rows, 9 columns, 32 non-zeros 9 integer variables, all of which are binary Preprocessing... 11 rows, 9 columns, 32 non-zeros 9 integer variables, all of which are binary Scaling... A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00 Problem data seem to be well scaled Constructing initial basis... Size of triangular part = 8 Solving LP relaxation... GLPK Simplex Optimizer, v4.47 11 rows, 9 columns, 32 non-zeros * 0: obj = 0.000000000e+00 infeas = 0.000e+00 (3) OPTIMAL SOLUTION FOUND Integer optimization begins... + 0: mip = not found yet >= -inf (1; 0) + 0: >>>>> 0.000000000e+00 >= 0.000000000e+00 0.0% (1; 0) + 0: mip = 0.000000000e+00 >= tree is empty 0.0% (0; 1) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.1 Mb (121133 bytes) Writing MIP solution to `two.sol'... 22 lines were written
Make sure you see something like
OPTIMAL SOLUTION FOUND
in the output. If the SAT solver is used, you should see
SATISFIABLE. Otherwise, go back to check the input file,
or send me a bug report.
Finally, display the solution
two.sol using the script again.
$ python doodle-fit.py two.sol < two 12 1220 00
Now you can ``enjoy’’ the game.