From - Tue Feb 23 11:07:38 1999 From: Jim Ferry Newsgroups: rec.puzzles Subject: "Square-free" chessboards Date: Sun, 21 Feb 1999 17:09:26 -0600 Organization: Center for Simulation of Advanced Rockets Lines: 112 Message-ID: <36D09226.2A9D@delete_this_field.uiuc.edu> This post addresses the question of how to place black and white pawns on a chessboard such that no squares have four pawns of the same color as vertices. It turns out a 6x6 board is the largest for which this is possible. The question was raised by Doodoo: > Suppose that all 64 squares of my chessboard are occupied by a pawn > each. > > Q1) How many different squares are there if squares are formed by > having a pawn at each corner? > > Q2) Suppose the pawns can be of different colours, but no square > can have 4 corners of the same colour. How many different > colours are needed? BillRyan22 showed that the answer to Q1 is 336. NickGard and Ilan Mayer found 3-color solutions to Q2. The present post indicates this is minimal. Here are the number of solutions for an n x n board: 1x1: 1 Class, 2 Boards 2x2: 3 Classes, 14 Boards 3x3: 20 Classes, 248 Boards 4x4: 332 Classes, 5006 Boards 5x5: 447 Classes, 7120 Boards 6x6: 5 Classes, 56 Boards 7x7: 0 Classes, 0 Boards We count both the number of solutions (boards) and the number of symmetry classes under the problem's 16-fold symmetry group (the D4 group of the board X swapping colors). The 5 6x6 classes (56 boards) can be represented thusly: 010a01 111100 d01001 10010b 001111 10c010 where a, b, c and d aren't all the same. a 1 0 d b = 0 0 and 1 1 give inequivalent 4-fold-symmetric solutions; c 1 0 1 1 1 1 0 , 1 1 and 1 0 give inequivalent non-symmetric solutions, 0 0 1 one of which was found by NickGard, who wrote: > ABAAAB > BBBBAA > AABAAB > BAABAA > AABBBB > BABABA If we relax the problem to only restrict squares aligned with the chess board, the numbers are: 1x1: 1 Class, 2 Boards 2x2: 3 Classes, 14 Boards 3x3: 24 Classes, 276 Boards 4x4: 727 Classes, 10980 Boards 5x5: 48974 Classes, 781712 Boards The second column can be found at Sloane's sequence site: http://www.research.att.com/~njas/sequences/ %I A018803 %S A018803 2,14,276,10980,781712,58339148,3066831440 %N A018803 Ways to color cells of nxn square with 2 colors so that no subsquare of side >1 has all corners same color. %O A018803 1,1 %K A018803 nonn,fini %A A018803 David W. Wilson (wilson@ctron.com) More data (since the program outputs it anyway): Strict case (oblique squares restricted): 1x2: 2 Classes, 4 Boards 2x3: 11 Classes, 50 Boards 3x4: 173 Classes, 1236 Boards 4x5: 2346 Classes, 18282 Boards 5x6: 731 Classes, 5684 Boards 6x7: 0 Classes, 0 Boards Loose case: 1x2: 2 Classes, 4 Boards 2x3: 11 Classes, 50 Boards 3x4: 209 Classes, 1498 Boards 4x5: 10796 Classes, 85138 Boards 5x6: 871724 Classes, 6965108 Boards The program I used for this was adapted from a polyomino code: it represents colors as bits, so can't easily be generalized to handle more than two colors. | Jim Ferry | Center for Simulation | +------------------------------------+ of Advanced Rockets | | http://www.uiuc.edu/ph/www/jferry/ +------------------------+ | jferry@expunge_this_field.uiuc.edu | University of Illinois |