Hinomaru

by John Bohannon

The word maru means "round" in Japanese. It is the name of a popular internet cat.

The word is also part of hinomaru (sun round), the name of the Japanese flag.

But here, we refer to Hinomaru, the beautiful and challenging assembly puzzle created by Curtis Pavel.

These are the tiles:

And these are the flip side of those tiles:

The goal is to assemble the tiles into the Japanese flag.

Such a difficult puzzle... Python to the rescue!

Let's convert this into a bitmap:

Now, write a program that solves the Hinomaru puzzle.

Ever want to try out the numpy Python library? This puzzle makes for a very nice intro tutorial. Not only does numpy make this easier to code, it also runs much faster. (Hint: Depth-First Search, and beware of recursion.)

Here is the target solution as a Python-friendly list of tuples:

SOLUTION = [
    (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
    (0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0),
    (0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0),
    (0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0),
    (0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0),
    (0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0),
    (0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0),
    (0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0),
    (0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0),
    (0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0),
    (0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0),
    (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
]

And here are the 12 tiles, each as a 2-tuple of front and back:

TILES = [
    (
        ((1,1,1,1,1,1), (1,1,1,1,1,1), (1,1,1,1,1,1)),
        ((0,1,1,1,1,1), (0,1,1,1,1,1), (0,0,1,1,1,1)),
    ),
    (
        ((1,1,1,1,1,1), (1,1,1,1,1,1), (1,1,1,1,1,1)),
        ((1,1,0,0,0,0), (1,1,0,0,0,0), (1,0,0,0,0,0)),
    ),
    (
        ((1,1,1,1,1,1), (1,1,1,1,1,1), (1,1,1,1,1,1)),
        ((0,0,0,0,0,0), (1,1,0,0,0,0), (1,1,1,1,0,0)),
    ),
    (
        ((1,1,1,1,1,1), (0,1,1,1,1,0), (0,0,0,0,0,0)),
        ((1,1,1,1,0,0), (1,1,0,0,0,0), (0,0,0,0,0,0)),
    ),
    (
        ((1,1,1,1,1,1), (0,1,1,1,1,0), (0,0,0,0,0,0)),
        ((0,0,0,0,0,0), (0,0,0,0,0,0), (0,0,0,0,0,0)),
    ),
    (
        ((1,1,1,1,1,0), (1,1,1,1,1,0), (1,1,1,1,0,0)),
        ((0,0,0,0,0,0), (0,0,0,0,0,0), (1,0,0,0,0,0)),
    ),
    (
        ((1,1,1,1,0,0), (1,1,1,1,1,0), (1,1,1,1,1,0)),
        ((0,0,1,1,1,1), (0,0,0,0,1,1), (0,0,0,0,0,0)),
    ),
    (
        ((0,0,0,0,0,0), (0,0,0,0,1,1), (0,0,1,1,1,1)),
        ((0,0,0,0,0,0), (0,0,0,0,0,0), (0,0,0,0,0,0)),
    ),
    (
        ((0,0,1,1,1,1), (0,0,0,0,1,1), (0,0,0,0,0,0)),
        ((0,0,0,0,0,0), (0,0,0,0,0,0), (0,0,0,0,0,1)),
    ),
    (
        ((0,0,0,0,1,1), (0,0,0,0,1,1), (0,0,0,0,0,1)),
        ((0,0,0,0,0,0), (0,0,0,0,0,0), (0,0,0,0,0,0)),
    ),
    (
        ((0,0,0,0,0,1), (0,0,0,0,1,1), (0,0,0,0,1,1)),
        ((0,0,0,0,0,0), (0,0,0,0,0,0), (0,0,0,0,0,1)),
    ),
    (
        ((0,0,0,0,0,1), (0,0,0,0,0,0), (0,0,0,0,0,0)),
        ((0,0,0,0,0,0), (0,0,0,0,0,0), (0,0,0,0,0,0)),
    ),
]

Solutions

John Bohannon’s solution is hinomaru.py
Steve Witham's solution is an IPython notebook

If you have a solution you'd like to share see the Solutions page for instructions.