Problem of the Month (September 2006)

In the 2002 World Puzzle Championship, there was a puzzle in the form of a rectangular grid containing several 1×1 and 2×2 squares. The puzzle was to find the unique path from the top left to the bottom right of the grid that intersected each 2×2 square in exactly one square and didn't pass through any of the dark 1×1 squares. Can you solve this puzzle?

Although not a terribly hard puzzle, it got me (as a puzzle designer) thinking about how hard it was to produce such a puzzle without those pesky dark squares. In particular, given a polyomino P, and a non-negative integer n no greater than the area of P, what is the smallest rectangular puzzle containing some non-overlapping copies of P that has a unique path connecting opposite corners that intersects each copy of P in exactly n squares? We do not allow the path to start or end inside a copy of P.

What are the answers for the tetrominoes? Can you prove that many of the cases, especially with large n, are impossible? What about larger polyominoes? Is there a solution for every polyomino and n=1? Can you classify the polyominoes that have solutions where n is equal to the area of the polyomino? Can you classify the polyominoes that fail to have solutions for n=0?

ANSWERS

Sam Collins wrote a C++ program to solve the World Championship puzzle:

Here are the smallest known solutions for polyominoes of area 5 or less.

Small Polyominoes

P \ n	0	1	2	3


			(George Sicherman)

Tetrominoes

P \ n	0	1	2	3	4
				?

				?

			?	?

Pentominoes

0	1	2	3	4
				?
			?	?
			(George Sicherman)	(George Sicherman)
		(George Sicherman)	?	?
			(George Sicherman)	?
(Sune Kristian Jakobsen)		(George Sicherman)	?	?
			?	?
			(George Sicherman)	?
			?	?
	(George Sicherman)	?	?	?
				?
(Sune Kristian Jakobsen)		(George Sicherman)	?	?

Hexominoes:

All of the hexominoes have puzzles for n=0 using either 1 or 2 copies of P. Sune Kristian Jakobsen found the last case. They also all have solutions for n=1 using 1 or 2 copies of P. Most of them have solutions for n=2, but I couldn't find solutions for one of them. Gabriele Carelli found one of these. I found 14 hexominoes that needed more than 2 copies of P. In 2011, George Sicherman found one more. Can you improve any of them?

(George Sicherman)
(George Sicherman)

(George Sicherman)

Heptominoes:

Sune Kristian Jakobsen found there are 9 heptominoes that need more than 2 copies of P, and 2 that have no solutions for n=0. Here are the smallest known solutions. Can you improve any of them?

(Sune Kristian Jakobsen)
(George Sicherman)

(Sune Kristian Jakobsen)
(Sune Kristian Jakobsen)
(George Sicherman)

(George Sicherman)
(George Sicherman)

George Sicherman found that for n=1, all the heptominoes have solutions with no more than 3 tiles. For n=2, he found solutions for most of them, except for these:

Octominoes:

George Sicherman looked at octominoes for n=0, and found 8 that apparently need 6 copies, shown below. Can you improve any of these?

(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)
(George Sicherman)

(George Sicherman)
(George Sicherman)

Here is the list of unsolved octominoes for n=0:

Sune Kristian Jakobsen found that this polyomino had no unique paths for any value of n.

We can also ask: what is the smallest puzzle for each polyomino that has a unique solution for two different values of n? The smallest-known solutions are shown below.

Unique Solutions for Multiple Values of n

polyomino	n=0 and n=1 solutions	n=1 and n=2 solutions

polyomino n=0 and n=1 solutions n=1 and n=2 solutions
?

?

polyomino n=0 and n=1 solutions n=1 and n=2 solutions

(George Sicherman)

(George Sicherman)

(George Sicherman)

(George Sicherman)

(George Sicherman) ?
?

(George Sicherman) ?

(George Sicherman)
?

(George Sicherman)
(George Sicherman)