### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,123)
- misc (2)
- project euler (2)
- puzzle (31)
- site news (43)
- tantalizer (31)
- teaser (3)

### Site Stats

- 168,355 hits

Programming Enigma Puzzles

4 December 2011

Posted by on **From New Scientist #2819, 2nd July 2011** [link]

The image, above, shows six dominoes forming a rectangle. The dotted line shows how the rectangle can be cut into two rectangles without cutting through a domino.

I started again with a standard set of 28 dominoes and used some of them to make another rectangle. This time it was impossible to find a line that cuts it into two rectangles without cutting a domino.

I then broke up that rectangle, added two further dominoes from the set, and used them all to make a new rectangle. Once again, it was impossible to find a line that cut this into two rectangles without cutting a domino.

How many dominoes did I use in this last rectangle?

[enigma1653]

Advertisements

%d bloggers like this:

This was a fun puzzle to solve programatically. The following Python program uses a recursive algorithm to attempt to fit dominoes into grids of various sizes until it finds an indivisible grid. Then it looks for grids that differ by 4 squares (2 dominoes).

Runtime is 1m52s, although using PyPy gets this down to a more acceptable 10.2s.

Solution:The second rectangle used 27 dominoes.Here is a diagram of the cut-free tiling of the rectangles using 25 and 27 dominoes found by my program:

The following paper on “Fault-free Tilings of Rectangles” [ http://math.ucsd.edu/~ronspubs/81_01_fault_free_tilings.pdf ] establishes the following necessary and sufficient conditions for the existence of a fault-free tiling of a

p×qrectangle:The proof that the 6×6 grid is not fault-free is nice.

This means that all even area grids that have both dimensions greater that 4 have a fault-free tiling, apart from the 6×6 grid.

The following program gives an analytical solution to the puzzle in 40ms, which is much less work than the constructive solution.