All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Logic
On a Grid 2 (Posted on 2007-08-29) Difficulty: 3 of 5
Place eight 'X's on a 4x4 grid so that each 'X' is orthogonally bordered by an even number of 'X's and each empty square is orthogonally bordered by an odd number of 'X's.

Can 18 'X's be placed in a 6x6 grid in this manner?

Note: 'orthogonally' means horizontally or vertically

No Solution Yet Submitted by Brian Smith    
Rating: 4.2500 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts Some comments Comment 10 of 10 |

I had originally thought about this the wrong way, considering, say, C(36,18) = 9,075,135,300 ways of arranging 18 X's on a 6x6 grid, and testing each one for parity constraints.  That's silly.  On a 6x6 grid, there are 2^6 = 64 choices for filling in the top row, and from then on your hand is forced in order to keep up with the parity rule(s). For the last piece placed on the bottom row, a solution is either possible or not. If it is possible, then the number of X's either is or is not 18 (in the 6x6 case), but only 64 grids had to be checked.

By the way, the two parity rules could be simplified into one: any + sign shaped group of five (or portion, around the edges), must have an odd number of X's.

In doing the puzzle this way, what's striking is the large number of arrangements that fit the parity criteria on a 9x9 grid. The below set has been culled to eliminate trivial rotations and reflections, and has been arranged into ascending order of the number of X's. A striking symmetry is seen in one grid with 41 X's (as close as you can get to (9^2)/2):

X X X X . . X X X 
X . . X . . X . X
X X X X . . X . X
. . . . . . X X X
. . . . X . . . .
X X X . . . . . .
X . X . . X X X X
X . X . . X . . X
X X X . . X X X X

All of them are listed below with the number of X's:


. X . . . X . X .
. . . X . . X . .
X . . . . X . X X
. . X . . . . X X
. . . . X . . . .
X X . . . . X . .
X X . X . . . . X
. . X . . X . . .
. X . X . . . X .
 25
X . . X . . . . X 
. . . . . X X . .
. X X . . X X . .
. X X . . . . . X
. . . . X . . . .
X . . . . . X X .
. . X X . . X X .
. . X X . . . . .
X . . . . X . . X
 25
. X X . . . X . . 
. X X . X . . . X
. . . X . . . . .
X . X . X X X X .
. X . . X . . X .
X . X . X X X X .
. . . X . . . . .
. X X . X . . . X
. X X . . . X . .
 31
. X X X . X X X . 
. X . X X X . X .
. X . . . . . X .
. X . . . . . X .
. X . X X X . X .
. X X X . X X X .
. . . . . . . . .
X . . . X . . . X
. . X . . . X . .
 31
. X . . . . X . X 
. . . X X . . X .
X . . X X . X . X
. . . . . X . . .
. X X . X . X X .
. X X X . . X X .
. . X X X . . . .
X X . X X . . . X
X X . . . . X . .
 33
. X X X . . X . . 
. X . X . . . . X
. X . X . X . . .
. X X X X . . X .
. . . X X X . . .
X . X . X X . . X
. X . . . . . . .
X . X X . . X X .
. . X X . . X X .
 33
. X X X . . X X . 
. X . X . . X X .
. X . X . . . . .
. X X X . X . . X
. . . . X . . . .
X . . X . X X X .
. . . . . X . X .
. X X . . X . X .
. X X . . X X X .
 33
. X . . X X . . X 
. . . . X X . . .
X . X . . . . X .
. X . . . . . . .
X . X X X X X . X
. . X . . . X X .
. . X X . X . X X
X . . X X . . . X
. . X . X X X X X
 35
. X X . . X . . X 
. X X . . . . . .
. . . . X . X X .
X . . . . X X X .
. . X X X X X . .
. . X . . X . X X
X . X X X X . X X
. X . . . . X . .
X . X . . X . X .
 35
. X X . X . X . X 
. X X X . X . X .
. . X X . . . . X
X X . . . . X X .
X X X . X . X X X
. X X X . X . X X
X . X X . . . . .
. . . . . . X . .
. X . . X . . . X
 37
. X X X X . . X . 
. X . . X . . . .
. X X X X . X . X
. . . . . X . X .
X . . . X . . . X
. . X . . X X X .
. . . . X X . X X
X X . . X . . . X
X X . . X X X X X
 37
X . . X . . . X X 
. . . . . X . X X
. X X . . . X . .
. X X . X X . X .
. . . X X X . . .
X . X X X . . . X
. X X X . X X . .
X X X . . X X . .
X X . X . . . . X
 37
. X X . . . X X . 
. X X . X . X X .
. . . X . X . . .
X . X . . . X . X
. X . X X X . X .
X . . X . X . . X
. X . X . X . X .
X . X X X X X . X
. . X X . X X . .
 39
. X X . . X . X X 
. X X . . . X X X
. . . . X X X X .
X . . . X . X . X
. . X . X . X . .
. . . X X X X . .
X X X X X . . . X
X . . X . X . . .
X X X X . . . X .
 39
. X X X . . . . X 
. X . X . X X . .
. X . X X X X . .
. X X . . X . . X
. . X X X X X . .
X X . . . X X . .
X X X . X . . . X
. X X X . X . . .
X . X X . . . X .
 39
. X X X . X X . . 
. X . X X X X . X
. X . . . X . X .
. X . . X X . . X
. X . . X . . X .
. X . . X X . . X
. X . . . X . X .
. X . X X X X . X
. X X X . X X . .
 39
. X X X X X . X . 
. X . . . X X . .
. X X . X . X X X
. . X X . . . . X
X X . X X X . X X
X X . . . X X X .
. . . . X . . . X
. . X . . X . X .
X . . . X . X . X
 39
X . . X . X . . X 
. . . . X . . . .
. X X X . X X X .
. X . X . X . X .
. X . X X X . X .
. X X . . . X X .
. . X X . X X . .
X X . X X X . X X
X X . . . . . X X
 39
X . . X . X . X X 
. . . . X . X X X
. X X X . . X X .
. X . X X . . . X
. X . . X . . X .
. X . X X . . . X
. X X X . . X X .
. . . . X . X X X
X . . X . X . X X
 39
X . X . . . X X X 
. X . . X . X . X
X . X . . X X . X
. . . . X X . X X
. X . . X . . X .
. . . . X X . X X
X . X . . X X . X
. X . . X . X . X
X . X . . . X X X
 39
. X . . . . X X X 
. . . X X . X . X
X . . X X X X . X
. . . . X . . X X
. X X X X X X X .
. X . . X . . . X
. X X X X X . X .
. . . . X X X . X
X . . X . X X . .
 41
. X X X . X . . X 
. X . X X . . . .
. X . . X X X X .
. X . X . . . X .
. X X . X . X X .
. . X . . X X . .
X X X . X X . X X
X . . X X . . X X
X X X X . X . . .
 41
. X X X X . . . . 
. X . . X . X X X
. X X X X X X . X
. . . . X . . . X
X . . X X X . . X
. . . X X X . . X
. X . . X . . . X
. . . X X X X . X
X . . X X . X X X
 41
. X X X X X X . X 
. X . . . . X X .
. X X . . X . X X
. . X . . . . . X
X X X . X . X X X
X . . X . X X . .
X X X . . X . X .
. . X X . X . . .
. X . X X X . . X
 41
X . X . . X X . X 
. X . . . X X X .
X . X X . . X X X
. . X X . X . X X
. . . . X . . . .
X X . X . X X . .
X X X . . X X . X
. X X X . . . X .
X . X X . . X . X
 41
X X . . . X . X X 
X X . X . . X X X
. . X . . X X X .
. X . X . X X . X
. . . . X . . . .
X . X X . X . X .
. X X X . . X . .
X X X . . X . X X
X X . X . . . X X
 41
X X X X . . X X X 
X . . X . . X . X
X X X X . . X . X
. . . . . . X X X
. . . . X . . . .
X X X . . . . . .
X . X . . X X X X
X . X . . X . . X
X X X . . X X X X
 41
. X . X X X X . . 
. . X X . . X . X
X X X . X X X X .
X . . . X . X X X
X X . . X . . X X
. X . . X . X . .
X X . . X X . X .
X . . . . X . . .
X X X X X X . . X
 43
. X X . X . . X . 
. X X X . . . . .
. . X X X X X . X
X X . X . . X X .
X X . X X X . X X
. . X . . X . . X
. X . X X X . X X
. . . X . . X X .
X . . X X X X . X
 43
. X X X . . . X X 
. X . X . X . X X
. X . X X . X . .
. X X . X . . X .
. . X . X . X . .
X X X X X X . X X
X . X . X X . X X
X . X . . . X . .
X X X . . X . X .
 43
. X X X X . X . X 
. X . . X X . X .
. X X X . X . . X
. . . X . X . X .
X . X X X X X . X
. X X X . X X . .
X X X . . . . . .
X X . X X . . X X
. . . X X . . X X
 43
. X X X X . X X X 
. X . . X X X . X
. X X X . . . . X
. . . X X . . . X
X . X . X . X . X
. X . . X X . X X
X . X . . X . X .
. . . . X X X X X
. X . . X X . X X
 43
. X . . X . . X X 
. . . . . . . X X
X . X X . X . . .
. X X X X . . . .
X X X X X X X X X
X X X X X . . . X
. X X X . X . X X
X . X . . . X X .
. . X X X X X . X
 45
. X . . X X X . . 
. . . . X . X . X
X . X . X . X X .
. X . X X X . X X
X . . X X X . . X
. X . . X . . X X
X . . X X X . X .
. X . X X X X X X
X . X . X X . X X
 45
. X X X . X . X X 
. X . X X . X X X
. X . . X . X X .
. X . X X X . . X
. X X X X X X X .
. . . X X X . X X
X . X . X . . . X
. X . . X X X X X
X . X . . . . . .
 45
X . X . . X X X X 
. X . . . X . . X
X . X X . X X X X
. . X X X . . . .
. . . X X X . . .
X X X . X X . X X
X . X . . . X X X
X . X . . X X X .
X X X . . X X . X
 45
. X X . X X X X X 
. X X X X . . . X
. . X . . X . X X
X X X X X . X X .
X . X . X . X . X
X . X . X X X . .
X X X X . . . . .
. . X X X . . X X
. X . X X . . X X
 47
. X . X . X X . X 
. . X . X X X X .
X X . . X X X X X
X X X . . X X X X
. X X . X . X X .
X . . X . . . . X
. X X . X X . X .
X X X . X X X . X
X X . X . X X . .
 49
. X X . X . X X X 
. X X X . X X . X
. . X X . X . . X
X X . . X X X . X
X X X X X X X X X
. X . . X X X . .
X X X X . X . X .
X X . X . X . . .
. . . X X X . . X
 49
. X X . X X . X . 
. X X X X X X . .
. . X . X X X X X
X X X . . X X . X
X . . . X . . . X
X X . . . X . . X
. X . X X . . . X
X X X X X X X . X
X X . X X . X X X
 49
. X X X X X . . . 
. X . . . X . X X
. X X . X X X X X
. . X X X X . X .
X X . . X . . X X
X X X X X X . . X
. X . . X X . X X
X X X X . . X X .
X X . X X X X . X
 51
. X X . . . . X X 
. X X . X X . X X
. . . X X X X . .
X . X X X X X X .
. X X X X X X X .
X X X X X X X . .
X X X X X X . X X
. X X X X . . X X
X . X X . X . . .
 53
X . X X . X X X X 
. X X X X X . . X
X X X X . . X X X
X X X . X X X . .
. X . . X . . X .
X X X . X X X . .
X X X X . . X X X
. X X X X X . . X
X . X X . X X X X
 55

 


  Posted by Charlie on 2007-11-02 12:54:33
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information