Sunday Times Teaser 2650 – Squares of Oblongs

by Des MacHale

I gave a set of nine rectangular cards of dimensions 1×2, 2×3, 3×4, 4×5, 5×6, 6×7, 7×8, 8×9 and 9×10 to each of two friends.

I asked each of them to arrange some of their cards to form a complete square and it turned out that those they made were the smallest and the largest that were possible.

What, in increasing order, were the sizes of all the unused cards?

This weeks teaser is a more difficult one to program than is usual and involves finding ways of arranging a number of rectangles to cover a square area.

This is an ‘exact cover’ problem for which there are, fortunately, a number of Python based solvers.

There is an interesting article on Donald Knuth’s ‘Dancing Links’ algorithm for solving exact cover problems here: http://www.ams.org/samplings/feature-column/fcarc-kanoodle.

I am using an exact cover solver coded in Python by David Goodger, for which I provide a copy here: http://cgi.gladman.plus.com/wp/wp-content/uploads/exact_cover.py.

Here is my solution using this solver