6 September, 2003: Tri for help

[ Home page | Web log ]

As a rule, logic puzzles really irritate me (you might have detected that from previous comments, I suppose). But I recently saw one which intrigued me (partly because I was offered cash money for solving it by somebody who'd managed to throw out the instructions...):

Logic puzzle

The puzzle consists of 16 triangular tiles which fit into a triangular recess in a piece of wood; the side of the recess is four times the length of the side of each triangular tile. Each edge of each tile is marked with a spot of paint which is either red, green, blue, white, yellow or black; along each side of the triangular recess are four paint spots chosen from same colours.

The problem is to arrange the tiles such that any two adjacent paint spots (lying on either side of the edge of a tile) are the same colour. (The photograph above shows the unsolved puzzle....)

This puzzle has a very large number of possible states. In particular, there are 16! (about 2.110**13) ways to arrange the tiles, and three possible rotations of each tile in each position, giving 3**16 2.110**13 or about 8.610**16 combinations. This is A Lot.

Obviously you can cut down on the possibilities by starting at a corner, where there is more than one constraint on which tiles can be used, but even so, solving the thing by hand would be a monumental pain in the arse.

(Incidentally, it's worth pointing out that no effort at all is required to make the puzzle-- you just paint the little dots on in place, making sure they match up as they should.)

I quickly became bored and wrote a computer program to solve it--

Logic puzzle solution

-- which performs an exhaustive search, starting from the bottom-left tile and working left and up until it completes the board. Producing the solution above required 37,293 separate tests (checking whether a given tile in a given orientation would fit in a given location). Sober, awake and enthusiastic, you might be able to do one test every second -- but after ten hours you might not be performing so quickly or so accurately.

So is there a trick which makes this problem manageable, or is it just stupidly difficult? Answers on a postcard much appreciated.

Copyright (c) 2003 Chris Lightfoot; available under a Creative Commons License.