Place eight 'A's and eight 'B's in a 4x4 grid such that each 'A' is orthogonally bordered by 1 or 3 'A's and each 'B' is orthogonally bordered by 0, 2, or 4 'B's.

Can a 6x6 grid be filled with 18 'A's and 18 'B's in this manner?

Note: 'orthogonally' means horizontally or vertically

(In reply to solution of first part by Robby Goetschalckx)

DECLARE FUNCTION count! (r!, c!, p!)
DECLARE SUB place (r!, c!)
CLEAR , , 44444
DIM SHARED sz

sz = 4

DIM SHARED g(sz + 1, sz + 1), noRem(1)
CLS
FOR r = 0 TO sz + 1 STEP sz + 1
  FOR c = 0 TO sz + 1
    g(r, c) = -1
    g(c, r) = -1
  NEXT
NEXT

noRem(0) = sz * sz / 2: noRem(1) = sz * sz / 2

place 1, 1

END

FUNCTION count (r, c, pc)
 p = g(r, c)
 ct = (g(r - 1, c) = p) + (g(r, c - 1) = p) + (g(r, c + 1) = p) + (g(r + 1, c) = p)
 count = ABS(ct)
END FUNCTION

SUB place (r, c)
 FOR pc = 0 TO 1
  IF noRem(pc) > 0 THEN
    good = 1
    g(r, c) = pc
    noRem(pc) = noRem(pc) - 1
    IF r > 1 THEN
     n = count(r - 1, c, pc)
     IF n MOD 2 = g(r - 1, c) THEN good = 0
    END IF
    IF r = sz AND c > 1 THEN
     n = count(r, c - 1, pc)
     IF n MOD 2 = g(r, c - 1) THEN good = 0
    END IF
    IF r = sz AND c = sz THEN
      n = count(r, c, pc)
      IF n MOD 2 = g(r, c) THEN good = 0
      IF good THEN
        FOR row = 1 TO sz
         FOR col = 1 TO sz
          PRINT g(row, col);
         NEXT
         PRINT
        NEXT
      END IF
    ELSE
     IF good THEN
      cl = c + 1: rw = r
      IF cl > sz THEN
        rw = rw + 1: cl = 1
      END IF
      place rw, cl
     END IF
    END IF
    noRem(pc) = noRem(pc) + 1
  END IF
 NEXT
END SUB

finds

 1  0  0  1
 0  1  1  0
 0  1  1  0
 1  0  0  1
 
 with 0's representing A's and 1's representing B's.
 
 When sz is set to 6 it finds no solutions.

Posted by Charlie on 2007-08-08 11:48:06