
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...
There's a QT implementation named hexalate : http://gottcod…
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
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.
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
My Prolog solver finds only two solutions, one of which is the one pictured.
http://telegra…
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