From: choy@skorpio.usask.ca (I am a terminator.)
Newsgroups: sci.math
Subject: Re: Tiling problem
Date: 13 Dec 1992 23:28:29 GMT
Organization: University of Saskatchewan, Saskatoon, Canada
Distribution: world
NNTP-Posting-Host: skorpio.usask.ca

In article <israel.723837962@unixg.ubc.ca>, israel@unixg.ubc.ca (Robert B. Israel) writes:
|> In <rcbaaw.723228012@rwb.urc.tue.nl>, rwb.urc.tue.nl (Angelo
|> Wentzler) writes:
|> 
|> >Given a grid of squares, tile it with black and white tiles and make
|> >the largest possible square so that no square contained in it has four
|> >equally colored corners.
|>
|> >My computer is fairly slow (8MHz), but after only 6 hours of calculation I
|> >came up with an 11x11 square. About 24 hours later I still hadn't found a
|> >12x12 square!! (An abundance of 11x11, though...)
|> >Two days later: still nothing.
|> 
|> On an overnight run with over 1.2 million steps of tabu search, I did
|> find a 13x13 square:
|> 
|> 0001101010110
|> 0101011000011
|> 1100001101110
|> 0110101011000
|> 0101100001101
|> 0000110101011
|> 1011101100001
|> 0110000110111
|> 0011010101100
|> 1010110000110
|> 1000011011101
|> 1101110110000
|> 1011000011010
|> 
|> Since 12x12 only took a few thousand steps, I think this is a good
|> time to quit.
|> -- 
|> Robert Israel                            israel@math.ubc.ca
|> Department of Mathematics             or israel@unixg.ubc.ca
|> University of British Columbia
|> Vancouver, BC, Canada V6T 1Y4


Would the following be a recursive solution?

0

1

Kinda small--let's double the size.

00
00

Um ... no internal squares in these little squares so no 4 colored corners.

Doubling again:

0011
0011
1100
1100

Now your starting to worry. The internal squares have 4 (colored) corners.
In general, the internal 0 (or the internal 1) has two 0 corners and two
1 corners. So that's OK.

00110011
00110011
11001100
11001100
00110011
00110011
11001100
11001100

Recursing makes a checkerboard so internal squares have two colors on the
corners.

0011001100110011
0011001100110011
1100110011001100
1100110011001100
0011001100110011
0011001100110011
1100110011001100
1100110011001100
0011001100110011
0011001100110011
1100110011001100
1100110011001100
0011001100110011
0011001100110011
1100110011001100
1100110011001100

00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100
00110011001100110011001100110011
00110011001100110011001100110011
11001100110011001100110011001100
11001100110011001100110011001100



Henry Choy
choy@cs.usask.ca

I guess they don't have all 4 sides the same color either.

Bummer.