Hinomaru is a beautiful puzzle in which "the goal is to put the 12 two-sided domino-shaped pieces into the tray such that the patterns on the face-up sides form a picture of Hinomaru, the Japanese national flag (i.e., a large, solid red disk in the middle of a white field.)".It looks temptingly simple: "It's a red disk made out of only 12 pieces, how hard can it be?". But in fact it can be maddeningly difficult to solve by hand. Several of my friends have spent many fruitless hours on this puzzle. It lures you in with its deceptive simplicity, and keeps you going by making it seem that you're always just one piece away from a solution.
However, the answer set solver clingo makes short work of this puzzle. It took about 30 minutes to program the solution: hinomaru.lp. It is based on the observation that there are only a few locations — usually four, but as few as two and as many as six — where each piece can contribute to the final image. If we place every piece in one of its possible locations, then we will have solved the puzzle.
Running the solver:
$ clingo hinomaru.lp
Answer: 1
p("D",6263) p("H",5161) p("F",2122) p("K",2333) p("E",5253) p("G",4344)
p("J",3242) p("C",3141) p("A",2434) p("B",5464) p("I",1112) p("L",1314)
SATISFIABLE
Models : 1+
Time : 0.010
Prepare : 0.000
Prepro. : 0.000
Solving : 0.010
In this solution, piece "A" occupies squares (2,4) and (3,4), piece "B" occupies squares (5,4) and (6,4), and so forth. I decided not to make solver output which side of each piece faces up, because (a) it's obvious when putting the piece in its location that only one side works in that location, and (b) there are no standard names for the faces (though the puzzle's designer did provide names for the pieces).
Is the solution really unique up to rearranging face-up pieces? That is, given one solution, is it possible to get another solution by using the other face of one or more pieces? Change the line
p(Piece, Loc) :- piecefaceloc(Piece, Face, Loc).to
p(Piece, Face) :- piecefaceloc(Piece, Face, Loc).And re-run:
clingo hinomaru.lp --project 0 Answer: 1 SATISFIABLE ...There's only one answer set, so the solution is indeed unique.
How many different ways are there to arrange those faces to create a solution? Change the code back and run:
$ clingo --project hinomaru.lp 0 ... Models : 96 ...
While we're at it, in how many different ways could the 12 pieces be arranged on the board, regardless of whether they form a disc or not? First we'll count the number of different ways in which a 6x4 board can be tiled with indistinguishable dominoes which are blank on both sides. I'm sure there's a better way to do this, but an easy — though computationally inefficient — approach is to use clingo.
Here's dominoes.lp:
#const xmax=6.
#const ymax=6.
#const ndominos=xmax * ymax / 2.
possibleplacement(X,Y,X+1,Y) :- X=1..xmax-1,Y=1..ymax.
possibleplacement(X,Y,X,Y+1) :- X=1..xmax,Y=1..ymax-1.
square(X,Y) :- X=1..xmax,Y=1..ymax.
% Select the valid placements.
ndominos { placement(X1,Y1,X2,Y2) : possibleplacement(X1,Y1,X2,Y2) } ndominos.
% Each placement uses two squares.
coveredsquare(X1,Y1) :- placement(X1,Y1,X2,Y2).
coveredsquare(X2,Y2) :- placement(X1,Y1,X2,Y2).
% There must be no uncovered squares.
:- square(X,Y), not coveredsquare(X,Y).
#hide. #show placement/4.
Running the solver:
$ clingo dominoes.lp 0 ... Models : 281 ...
Okay, so for each of those 281 ways to tile the board with dominoes, we can replace the dominoes with puzzle pieces in 12! ways, and we can choose which sides are face up in 212 ways. Now 281 · 12! · 212 is about 5.5 · 1014, so good luck trying to solve Hinomaru by placing pieces randomly!
No comments:
Post a Comment