home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 16819 < prev    next >
Encoding:
Internet Message Format  |  1992-12-13  |  3.6 KB
  1. Path: sparky!uunet!newsflash.concordia.ca!mizar.cc.umanitoba.ca!access.usask.ca!skorpio!choy
  2. From: choy@skorpio.usask.ca (I am a terminator.)
  3. Newsgroups: sci.math
  4. Subject: Re: Tiling problem
  5. Date: 13 Dec 1992 23:28:29 GMT
  6. Organization: University of Saskatchewan, Saskatoon, Canada
  7. Lines: 133
  8. Sender: choy@skorpio (I am a terminator.)
  9. Distribution: world
  10. Message-ID: <1gggutINN29q@access.usask.ca>
  11. References: <israel.723716857@unixg.ubc.ca> <israel.723837962@unixg.ubc.ca>
  12. NNTP-Posting-Host: skorpio.usask.ca
  13.  
  14. In article <israel.723837962@unixg.ubc.ca>, israel@unixg.ubc.ca (Robert B. Israel) writes:
  15. |> In <rcbaaw.723228012@rwb.urc.tue.nl>, rwb.urc.tue.nl (Angelo
  16. |> Wentzler) writes:
  17. |> 
  18. |> >Given a grid of squares, tile it with black and white tiles and make
  19. |> >the largest possible square so that no square contained in it has four
  20. |> >equally colored corners.
  21. |>
  22. |> >My computer is fairly slow (8MHz), but after only 6 hours of calculation I
  23. |> >came up with an 11x11 square. About 24 hours later I still hadn't found a
  24. |> >12x12 square!! (An abundance of 11x11, though...)
  25. |> >Two days later: still nothing.
  26. |> 
  27. |> On an overnight run with over 1.2 million steps of tabu search, I did
  28. |> find a 13x13 square:
  29. |> 
  30. |> 0001101010110
  31. |> 0101011000011
  32. |> 1100001101110
  33. |> 0110101011000
  34. |> 0101100001101
  35. |> 0000110101011
  36. |> 1011101100001
  37. |> 0110000110111
  38. |> 0011010101100
  39. |> 1010110000110
  40. |> 1000011011101
  41. |> 1101110110000
  42. |> 1011000011010
  43. |> 
  44. |> Since 12x12 only took a few thousand steps, I think this is a good
  45. |> time to quit.
  46. |> -- 
  47. |> Robert Israel                            israel@math.ubc.ca
  48. |> Department of Mathematics             or israel@unixg.ubc.ca
  49. |> University of British Columbia
  50. |> Vancouver, BC, Canada V6T 1Y4
  51.  
  52.  
  53. Would the following be a recursive solution?
  54.  
  55. 0
  56.  
  57. 1
  58.  
  59. Kinda small--let's double the size.
  60.  
  61. 00
  62. 00
  63.  
  64. Um ... no internal squares in these little squares so no 4 colored corners.
  65.  
  66. Doubling again:
  67.  
  68. 0011
  69. 0011
  70. 1100
  71. 1100
  72.  
  73. Now your starting to worry. The internal squares have 4 (colored) corners.
  74. In general, the internal 0 (or the internal 1) has two 0 corners and two
  75. 1 corners. So that's OK.
  76.  
  77. 00110011
  78. 00110011
  79. 11001100
  80. 11001100
  81. 00110011
  82. 00110011
  83. 11001100
  84. 11001100
  85.  
  86. Recursing makes a checkerboard so internal squares have two colors on the
  87. corners.
  88.  
  89. 0011001100110011
  90. 0011001100110011
  91. 1100110011001100
  92. 1100110011001100
  93. 0011001100110011
  94. 0011001100110011
  95. 1100110011001100
  96. 1100110011001100
  97. 0011001100110011
  98. 0011001100110011
  99. 1100110011001100
  100. 1100110011001100
  101. 0011001100110011
  102. 0011001100110011
  103. 1100110011001100
  104. 1100110011001100
  105.  
  106. 00110011001100110011001100110011
  107. 00110011001100110011001100110011
  108. 11001100110011001100110011001100
  109. 11001100110011001100110011001100
  110. 00110011001100110011001100110011
  111. 00110011001100110011001100110011
  112. 11001100110011001100110011001100
  113. 11001100110011001100110011001100
  114. 00110011001100110011001100110011
  115. 00110011001100110011001100110011
  116. 11001100110011001100110011001100
  117. 11001100110011001100110011001100
  118. 00110011001100110011001100110011
  119. 00110011001100110011001100110011
  120. 11001100110011001100110011001100
  121. 11001100110011001100110011001100
  122. 00110011001100110011001100110011
  123. 00110011001100110011001100110011
  124. 11001100110011001100110011001100
  125. 11001100110011001100110011001100
  126. 00110011001100110011001100110011
  127. 00110011001100110011001100110011
  128. 11001100110011001100110011001100
  129. 11001100110011001100110011001100
  130. 00110011001100110011001100110011
  131. 00110011001100110011001100110011
  132. 11001100110011001100110011001100
  133. 11001100110011001100110011001100
  134. 00110011001100110011001100110011
  135. 00110011001100110011001100110011
  136. 11001100110011001100110011001100
  137. 11001100110011001100110011001100
  138.  
  139.  
  140.  
  141. Henry Choy
  142. choy@cs.usask.ca
  143.  
  144. I guess they don't have all 4 sides the same color either.
  145.  
  146. Bummer.
  147.