Adriano Ferreira wrote:

> On 5/20/05, Jason Bailey <azrael / demonlords.net> wrote:
> 
>>Is there an assumption that this is a square or can it be a rectangle?
>>
>>ie 4 by 4096 ??
> 
> 
> The man said "on a 2**n by 2**n board". This assumption guarantees the
> board   has at least a number of squares (2**(2n)-1) which is multiple
> of 3 (proof left to the interested reader). Probably it also
> guarantees that the L-trominos (with 3 squares) can be fitted into the
> board. The situation is different with rectangles: for example, a 4 by
> 8 board has 31 squares which are not divisible by 3. So you can't fill
> it with L-trominos without leaving a blank square.
> 

OTOH, the "canonical" solution of this problem should (with minor
modification) work for a 2**n by 2**m board whenever n + m is even
(i.e. whenever the number of empty squares is divisible by 3).

Michael


-- 
Michael Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: michael.ulm / isis-papyrus.com
Visit our Website: www.isis-papyrus.com