Is there an assumption that this is a square or can it be a rectangle?
ie 4 by 4096 ??
Subject: [QUIZ] Tiling Turmoil (#33)
From: Ruby Quiz <james@grayproductions.net>
Date: Fri, May 20, 2005 8:37 am
To: ruby-talk@ruby-lang.org (ruby-talk ML)
---snip---
···
-------- Original Message --------
The solution for that might look like:
1 1 2 2
1 5 X 2
3 5 5 4
3 3 4 4
As you can see, all squares are completely filled with the exception of the
empty square which was randomly placed.
It may look simple on a 4 by 4 board, but once you get up to a 128 by 128 or
even 4096 by 4096, it becomes more and more obvious that guess and check is just
not going to work.
Is there an assumption that this is a square or can it be a rectangle?
ie 4 by 4096 ??
"You're going to tile L-trominos on a 2**n by 2**n board that is missing a
single square. What's an L-tromino? It's simply a 2 by 2 square with a
corner missing that looks like an L."
Since "n" will be the same, the sides will always have the same length - so
you only have to worry about squares.
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.
Regards.
Adriano.
···
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?
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
