perplexus.info :: Logic : On a Grid 2

On a Grid 2 (Posted on 2007-08-29)

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.4000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

Some comments

| Comment 10 of 11 |

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 (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info