Re: The square tiling problem

From: <wh_at_icparc.ic.ac.uk>
Date: Thu 14 Oct 2004 08:52:26 PM GMT
Message-ID: <20041014205226.GA17978@tempest.icparc.ic.ac.uk>
On Thu, Oct 14, 2004 at 02:57:37PM -0300, christian wrote:
>  The square tiling problem is about how to cover a square with square
>  tiles of given sizes.
> 
>  For a square of size 19 and tiles of sizes
>  [10,9,7,6,4,4,3,3,3,3,3,2,2,2,1,1,1,1,1,1] one of the answers is
> 
>  Xs = [1, 1, 10, 11, 11, 15, 17, 17, 17, 17, 17, 10, 12, 14, 16, 16, 19, 19, 19, ...]
> Ys = [1, 11, 11, 1, 7, 7, 1, 4, 11, 14, 17, 18, 18, 18, 18, 19, 7, 8, 9, ...]
> 
> How i should interpret this result? I imagine X,Y are coordinates and i
> plote them but couldn't find a pattern.

Xs and Ys give the coordinates of one corner of each square (which corner it
is depends on what direction your coordinate axes go in - I've assumed the
axes go right and down, so the coordinates are for the top left corner).  So
the square of size 10 goes at (1,1), the square of size 9 goes at (1,11),
etc.  Here are the first 9 squares plotted, you get the idea:

                     1 1 1 1 1 1 1 1 1 1
   1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
 1 1-----------------+ 4---------+ 7---+
 2 |                 | |         | |   |
 3 |                 | |         | +---+
 4 |                 | |         | 8---+
 5 |                 | |         | |   |
 6 |                 | +---------+ +---+
 7 |                 | 5-----+ 6-----+  
 8 |                 | |     | |     |  
 9 |                 | |     | |     |  
10 +-----------------+ +-----+ +-----+  
11 2---------------+ 3-----------+ 9---+
12 |               | |           | |   |
13 |               | |           | +---+
14 |               | |           |      
15 |               | |           |      
16 |               | |           |      
17 |               | +-----------+      
18 |               |                    
19 +---------------+                    

Cheers,
Warwick
Received on Thu Oct 14 21:55:17 2004

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:31 PM GMT GMT