Giant's Causeway puzzleGiant's Causeway puzzle

12 January, 2015
Six Comments

https://d1icoid1cnixnp.cloudfront.net/yadt/blog.Image/image/original/23.jpeg

Over Christmas I found the above puzzle at my parent's house. I don't know if it has a name but it seemed apt to name it after The Giant's Causeway.

The idea is that you swap and/or rotate the outer tiles until the colours at the edges match. The center tile is fixed, or at least I assume it is as the wooden edges are deliberately less rounded.

Of course, solving it manually would be boring so here's a dumb brute force solution. I actually admire how inefficient and stupid it is...

import itertools

class Tile(list):
    def __getitem__(self, x):
        return super(Tile, self).__getitem__(x % len(self))

    def rotate(self, x):
        return Tile(self[x:] + self[:x])

COLOURS = ('YELLOW', 'WHITE', 'BLACK', 'RED', 'GREEN', 'BLUE')
YELLOW, WHITE, BLACK, RED, GREEN, BLUE = range(len(COLOURS))

TILES = (
    Tile((WHITE, YELLOW, RED, BLUE, BLACK, GREEN)),
    Tile((RED, BLUE, BLACK, YELLOW, GREEN, WHITE)),
    Tile((WHITE, BLACK, YELLOW, GREEN, BLUE, RED)),
    Tile((WHITE, BLUE, GREEN, YELLOW, BLACK, RED)),
    Tile((GREEN, BLUE, BLACK, YELLOW, RED, WHITE)),
    Tile((RED, YELLOW, GREEN, BLACK, BLUE, WHITE)),
)

CENTER = Tile((WHITE, BLACK, RED, GREEN, BLUE, YELLOW))

def pairwise(it):
    a, b = itertools.tee(it)

    next(b, None)

    return itertools.izip(a, b)

def validate(xs):
    for idx, x in enumerate(xs):
        if x[idx + 3] != CENTER[idx]:
            raise ValueError("Tile does not match center")

    for idx, (a, b) in enumerate(pairwise(xs)):
        if a[idx + 2] != b[idx + 5]:
            raise ValueError("Tile does not match previous anticlockwise tile")

    return xs

def find_solution():
    # For all possible tile permutations..
    for xs in itertools.permutations(TILES):

        # ... try all possible rotations
        for ys in itertools.product(range(len(COLOURS)), repeat=len(COLOURS)):
            try:
                return validate([x.rotate(y) for x, y in zip(xs, ys)])
            except ValueError:
                pass

    raise ValueError("Could not find a solution.")

for x in find_solution():
    print ', '.join(COLOURS[y] for y in x)

This prints (after 5 minutes!):

$ python giants.py
GREEN, BLUE, RED, WHITE, BLACK, YELLOW
WHITE, BLUE, GREEN, YELLOW, BLACK, RED
YELLOW, GREEN, BLACK, BLUE, WHITE, RED
GREEN, WHITE, YELLOW, RED, BLUE, BLACK
RED, BLUE, BLACK, YELLOW, GREEN, WHITE
BLUE, BLACK, YELLOW, RED, WHITE, GREEN
python giants.py  269.08s user 0.02s system 99% cpu 4:29.36 total

UPDATE: Seems like this puzzle is called "Circus Seven". Now to dust off my Prolog...

Posted 12 January, 2015

Hacks, Misc

Comments (6)

Landry

There's a QT implementation named hexalate : http://gottcod…

Jan. 12, 2015, 6:21 p.m. #

Hakan Kjellerstrand

Hi Chris.

Another name of the problem is Drive Ya Nuts. Here are three Constraint Programming models which solve the problem (not exactly the same as your what I can see) in some tenth of a second:

- MiniZinc: http://hakank.…
- Gecode: http://hakank.…
- Picat: Gecode: http://hakank.…

Best,

Hakan

Jan. 12, 2015, 10:57 p.m. #

Alan Eliasen

Nice! I've written a solver for that too. I've owned it as a puzzle by Hasbro called "Drive Ya Nuts," which I owned for about 35 years without solving manually; I finally decided to write a solver for it a couple years ago. Here are links and a slightly wordy solution in my programming language "Frink":

http://futureb…

It solves (after testing all possibilities) in about 2.5 seconds. It gets some speed by bailing out of each arrangement as early as possible when it determines that two nuts don't match.

Frink documentation:
http://futureb…

P.S. This site won't let you submit replies unless I'm sending a referer header. People shouldn't send referer headers for privacy reasons. That would be a good thing to fix.

Jan. 12, 2015, 11:15 p.m. #

lamby

(Re. referer headers, that's to provide strict CRSF checking over SSL... but I take your point)

Ivan

Really nice post!

In case you're not really going to do a version in Prolog, here's one by me:

https://llaisd…

Solves more or less straightaway. I don't know if there's a bug in my code, but it finds twelve solutions.

Best wishes

Ivan

Jan. 13, 2015, 9:45 a.m. #

Toby

My Prolog solver finds only two solutions, one of which is the one pictured.

http://telegra…

Feb. 13, 2016, 5:21 a.m. #

Robert Smith

Here is my solution in Lisp. As can be seen by the algorithm analysis at the top of the linked file, this solution is somewhat overkill, but it is very efficient (in both relative and absolute terms): https://bitbuc…

My solver excludes rotationally symmetric solutions. Those can be trivially generated from any individual solution.

Very little data is allocated and very little data is moved around.

Here's example output for your problem above:

> (mapc #'pretty-print-solution (mapc #'validate (time (find-solutions))))
Timing the evaluation of (FIND-SOLUTIONS)
Tried 104 piece placements. Found 2 solutions.

User time = 0.000
System time = 0.000
Elapsed time = 0.000
Allocation = 4288 bytes
0 Page faults

Center : BLACK, RED, GREEN, BLUE, YELLOW, WHITE
Top Left : BLUE, GREEN, YELLOW, BLACK, RED, WHITE
Top Right : GREEN, BLACK, BLUE, WHITE, RED, YELLOW
Right : WHITE, YELLOW, RED, BLUE, BLACK, GREEN
Bottom Right: BLUE, BLACK, YELLOW, RED, WHITE, GREEN
Bottom Left : BLACK, YELLOW, GREEN, WHITE, RED, BLUE
Left : BLUE, RED, WHITE, BLACK, YELLOW, GREEN

Center : BLACK, RED, GREEN, BLUE, YELLOW, WHITE
Top Left : BLUE, GREEN, YELLOW, BLACK, RED, WHITE
Top Right : GREEN, BLACK, BLUE, WHITE, RED, YELLOW
Right : WHITE, YELLOW, RED, BLUE, BLACK, GREEN
Bottom Right: BLUE, BLACK, YELLOW, GREEN, WHITE, RED
Bottom Left : BLACK, YELLOW, RED, WHITE, GREEN, BLUE
Left : BLUE, RED, WHITE, BLACK, YELLOW, GREEN

Feb. 13, 2016, 9:01 a.m. #