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

(In reply to Solution by Penny)

Apparently the next size square that allows half the cells to be X's is 12x12:

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

Where there are 72 X's arranged symmetrically.

DECLARE SUB place (r!, c!)
CLEAR , , 25000
DIM SHARED sz, sCt
sz = 12

DIM SHARED b(sz, sz)

CLS
place 1, 1

SUB place (r, c)
  IF r = 1 THEN
    FOR v = 0 TO 1
     b(r, c) = v
     cp = c + 1: rp = r
     IF cp > sz THEN rp = rp + 1: cp = 1
     place rp, cp
    NEXT v
  ELSEIF r = sz THEN
    pCt = 0
    rm = r - 2
    IF rm > 0 THEN pCt = pCt + b(rm, c)
    cm = c - 1
    IF cm > 0 THEN pCt = pCt + b(r - 1, cm)
    cp = c + 1
    IF cp <= sz THEN pCt = pCt + b(r - 1, cp)
    pCt = pCt + b(r - 1, c)
    b(r, c) = 1 - (pCt MOD 2)
    cm = c - 1
    IF cm > 1 THEN tot = b(r, cm - 1):  ELSE tot = 0
    IF cm > 0 THEN tot = tot + b(r, cm) + b(r - 1, cm)
    tot = tot + b(r, c)
    IF c = 1 OR tot MOD 2 = 1 THEN
      cp = c + 1: rp = r
      IF cp > sz THEN rp = rp + 1: cp = 1
      IF rp > sz THEN
       tot = b(r - 1, c) + b(r, c - 1) + b(r, c)
       IF tot MOD 2 = 1 THEN
         bPerRow = INT(80 / (sz + 3))
         dispRow = sCt \ bPerRow
         dispCol = sCt MOD bPerRow
         dispRow = dispRow * (sz + 3)
         dispCol = dispCol * (sz + 3) + 1
         xCt = 0
         FOR i = 1 TO sz
         LOCATE dispRow + i, dispCol
         FOR j = 1 TO sz
          IF b(i, j) THEN PRINT "X"; : xCt = xCt + 1:  ELSE PRINT ".";
         NEXT
         NEXT
         LOCATE dispRow + i, dispCol
         PRINT xCt;
         sCt = sCt + 1
       END IF
      ELSE
       place rp, cp
      END IF
    END IF
  ELSE
    pCt = 0
    rm = r - 2
    IF rm > 0 THEN pCt = pCt + b(rm, c)
    cm = c - 1
    IF cm > 0 THEN pCt = pCt + b(r - 1, cm)
    cp = c + 1
    IF cp <= sz THEN pCt = pCt + b(r - 1, cp)
    pCt = pCt + b(r - 1, c)
    b(r, c) = 1 - (pCt MOD 2)
    cp = c + 1: rp = r
    IF cp > sz THEN rp = rp + 1: cp = 1
    place rp, cp
  END IF
END SUB

 

Posted by Charlie on 2007-11-01 14:20:25