+---+---+---+---+               +---+---+---+---+
|   | 5 | 5 |   |               |   | 6 |   | 6 |
+---+---+---+---+               +---+---+---+---+
| 5 |   |   | 5 |               | 6 |   |   |   |
+---+---+---+---+               +---+---+---+---+
| 5 |   |   | 5 |               |   |   |   | 6 |  
+---+---+---+---+               +---+---+---+---+
|   | 5 | 5 |   |               | 6 |   | 6 |   | 
+---+---+---+---+               +---+---+---+---+ 
                               

                  +---+---+---+---+            
                  |   |   |   |   |             
                  +---+---+---+---+            
                  |   |   |   |   |           
                  +---+---+---+---+           
                  |   |   |   |   |          
                  +---+---+---+---+            
                  |   |   |   |   |          
                  +---+---+---+---+ 

1. Each watchman looks in all directions on a square board (horizontal, vertical and both diagonals).
2. A watchman can see beyond another watchman.
3. On the left board, each watchman has five vacant cells under his gaze.
4. On the right board, each watchman can see six empty cells.

What is the maximum number of watchmen that can be placed so that each sees seven empty cells?

There are two basic solutions, each with six watchmen:

 +---+---+---+---+    +---+---+---+---+           
 |   |   | 7 |   |    |   |   | 7 |   |            
 +---+---+---+---+    +---+---+---+---+           
 | 7 |   | 7 |   |    |   |   | 7 |   |          
 +---+---+---+---+    +---+---+---+---+          
 |   | 7 | 7 |   |    |   |   | 7 | 7 |         
 +---+---+---+---+    +---+---+---+---+           
 |   | 7 |   |   |    | 7 | 7 |   |   |         
 +---+---+---+---+    +---+---+---+---+ 

 
These and their reflections and rotations were found by:

DECLARE SUB addOn (lvl!)
DIM SHARED grid(4, 4), n, hist(10), solCt

CLS

FOR n = 9 TO 6 STEP -1
  addOn 1
NEXT

SUB addOn (lvl)
  IF lvl = 1 THEN
    FOR linear = 0 TO 16 - n
      row = linear \ 4 + 1
      col = linear MOD 4 + 1
      grid(row, col) = 1
      hist(1) = linear
      addOn lvl + 1
      grid(row, col) = 0
    NEXT linear
  ELSE
    FOR linear = hist(lvl - 1) + 1 TO 15 - n + lvl
      hist(lvl) = linear
      row = linear \ 4 + 1
      col = linear MOD 4 + 1
      grid(row, col) = 1
    
      IF lvl = n THEN
        good = 1
        FOR mv = 1 TO lvl
          ct = 0
          linear1 = hist(mv)
          r0 = linear1 \ 4 + 1
          c0 = linear1 MOD 4 + 1
          FOR i = 1 TO 4
             IF grid(r0, i) = 0 THEN ct = ct + 1
             IF grid(i, c0) = 0 THEN ct = ct + 1
             r1 = r0 - c0 + i
             IF r1 > 0 AND r1 < 5 THEN IF grid(r1, i) = 0 THEN ct = ct + 1
             r1 = r0 + c0 - i
             IF r1 > 0 AND r1 < 5 THEN IF grid(r1, i) = 0 THEN ct = ct + 1
          NEXT i
          IF ct <> 7 THEN good = 0: EXIT FOR
        NEXT mv
        IF good THEN
          prow = 6 * (solCt \ 8) + 1
          pcol = 9 * (solCt MOD 8)

          FOR r1 = 1 TO 4
          FOR c1 = 1 TO 4
            LOCATE prow + r1, pcol + 2 * c1
            PRINT grid(r1, c1);
          NEXT
          NEXT

          solCt = solCt + 1
        END IF
      ELSE
        addOn lvl + 1
      END IF
    
      grid(row, col) = 0
    NEXT linear
  END IF
END SUB

yielding

  1 1 0 0  1 0 0 0  0 1 0 0  0 1 0 0  0 1 0 0  0 1 0 0  0 1 0 0  0 0 1 1
  0 0 1 1  1 0 0 0  0 1 1 1  0 1 1 0  0 1 0 1  0 1 0 0  0 0 1 1  1 1 0 0
  0 0 1 0  0 1 1 1  1 0 0 0  1 0 1 0  0 1 1 0  1 1 0 0  1 1 1 0  0 1 0 0
  0 0 1 0  0 1 0 0  1 0 0 0  0 0 1 0  0 0 1 0  0 0 1 1  0 0 0 0  0 1 0 0

  0 0 1 0  0 0 1 0  0 0 1 0  0 0 1 0  0 0 1 0  0 0 0 1  0 0 0 0  0 0 0 0
  1 1 1 0  1 1 0 0  1 0 1 0  0 1 1 0  0 0 1 0  0 0 0 1  1 1 1 0  0 1 1 1
  0 0 0 1  0 1 1 1  0 1 1 0  0 1 0 1  0 0 1 1  1 1 1 0  0 0 1 1  1 1 0 0
  0 0 0 1  0 0 0 0  0 1 0 0  0 1 0 0  1 1 0 0  0 0 1 0  0 1 0 0  0 0 1 0

Posted by Charlie on 2013-07-22 13:31:34