You are given 21 3x1 rectangular pieces to cover an 8x8 chessboard. Since the board has 64 squares, which square on the chessboard must you cut out so that the 21 given pieces exactly cover the remaining 63 squares? Or it is impossible, no matter which square you remove?

(In reply to Count the Ways by Charlie)

The program (similar to that for Count the Ways):

DECLARE SUB place ()
CLEAR , , 25000
DIM SHARED sz, numb, solCt, lvl, vCt, hCt
sz = 8: numb = INT(sz * sz / 3)
DIM SHARED board$(sz, sz)

CLS

OPEN "trominos.txt" FOR OUTPUT AS #2
place
CLOSE

PRINT solCt

OPEN "trominos.txt" FOR INPUT AS #1
OPEN "tromino2.txt" FOR OUTPUT AS #2

FOR major = 0 TO 17
  REDIM b$(10, sz)
  FOR minor = 1 TO 10
    FOR row = 1 TO 8
     IF EOF(1) = 0 THEN
      LINE INPUT #1, l$
      b$(minor, row) = l$
     END IF
    NEXT
    IF EOF(1) = 0 THEN LINE INPUT #1, l$
  NEXT
  FOR row = 1 TO 8
    FOR minor = 1 TO 10
      PRINT #2, b$(minor, row); " ";
    NEXT
    PRINT #2,
  NEXT
  PRINT #2,
NEXT

CLOSE

SUB place
 lvl = lvl + 1
 ltr$ = MID$("abcdefghijklmnopqrstuvwxyz", lvl, 1)
 found = 0
 FOR i = 1 TO sz
 FOR j = 1 TO sz
   IF i <> 3 OR j <> 3 THEN
   IF LTRIM$(board$(i, j)) = "" THEN
      rw = i: cl = j
      found = 1
      EXIT FOR
   END IF
   END IF
 NEXT
 IF found THEN EXIT FOR
 NEXT
 IF found = 0 THEN
   solCt = solCt + 1
   FOR i = 1 TO sz
     FOR j = 1 TO sz
       PRINT #2, LEFT$(board$(i, j) + " ", 1);
     NEXT
     PRINT #2,
   NEXT
   PRINT #2,
'  DO: a$ = INKEY$: LOOP UNTIL a$ > ""
 ELSE
   ' horiz
   IF cl < sz - 1 THEN
   IF board$(rw, cl + 1) = "" AND board$(rw, cl + 2) = "" THEN

    board$(rw, cl) = ltr$
    board$(rw, cl + 1) = ltr$
    board$(rw, cl + 2) = ltr$
    hCt = hCt + 1

    place

    hCt = hCt - 1
    board$(rw, cl) = ""
    board$(rw, cl + 1) = ""
    board$(rw, cl + 2) = ""

   END IF
   END IF
   ' vert
   IF lvl > 1 THEN
   IF rw < sz - 1 THEN
   IF board$(rw + 1, cl) = "" AND board$(rw + 2, cl) = "" THEN

    board$(rw, cl) = ltr$
    board$(rw + 1, cl) = ltr$
    board$(rw + 2, cl) = ltr$
    vCt = vCt + 1

    place

    vCt = vCt - 1
    board$(rw, cl) = ""
    board$(rw + 1, cl) = ""
    board$(rw + 2, cl) = ""

   END IF
   END IF
   END IF
 END IF
 lvl = lvl - 1
END SUB

 

Posted by Charlie on 2005-11-13 19:22:35