The diagram shows a restricted chess board with three black knights and three white knights. Your goal is to move the pieces so that the same squares are occupied but the colors are reversed. Your first move must use a black piece.

Pieces may move only as a normal chess knight, from one corner of a 2×3 rectangle to the opposite corner. No more than one piece may occupy a single square at a time. No piece may move onto a darkened square. No other rules of chess apply.

One turn is a sequence of moves made by a single piece. Find a solution with the minimum number of turns.

(In reply to One computer solution by Charlie)

The program is:

DECLARE SUB move (round&)
DECLARE FUNCTION codeMove& (sendRow&, sendCol&, recRow&, recCol&)
DECLARE FUNCTION codePos& ()
DEFLNG A-Z
CLEAR , , 8500

DIM SHARED board(5, 5), emptyR(3), emptyC(3), goal, turn
DIM SHARED mHist(100), pHist(100)   'move history and position history
CLS
OPEN "kngtmove.txt" FOR OUTPUT AS #2

DATA 10,1,10,10,10
DATA 10,0,10,2,2
DATA 10,10,0,10,10
DATA 1,1,10,0,10
DATA 10,10,10,2,10
FOR r = 1 TO 5
 FOR c = 1 TO 5
  READ board(r, c)
  IF board(r, c) = 1 OR board(r, c) = 2 THEN
    board(r, c) = 3 - board(r, c)
  END IF
 NEXT
NEXT

goal = codePos

FOR r = 1 TO 5
 FOR c = 1 TO 5
  IF board(r, c) = 1 OR board(r, c) = 2 THEN
    board(r, c) = 3 - board(r, c)
  END IF
 NEXT
NEXT

turn = 1
emptyR(1) = 2: emptyC(1) = 2
emptyR(2) = 3: emptyC(2) = 3
emptyR(3) = 4: emptyC(3) = 4

move 1

CLOSE

FUNCTION codeMove (sendRow, sendCol, recRow, recCol)
 codeMove = 1000 * sendRow + 100 * sendCol + 10 * recRow + recCol
END FUNCTION

FUNCTION codePos
 codePos = ((((((((board(1, 2) * 3 + board(2, 2)) * 3 + board(2, 4)) * 3 + board(2, 5)) * 3 + board(3, 3)) * 3 + board(4, 1)) * 3 + board(4, 2)) * 3 + board(4, 4)) * 3 + board(5, 4))
END FUNCTION

SUB move (round)
 pHist(round) = codePos
 FOR e = 1 TO 3
  r = emptyR(e): c = emptyC(e)
  sendR = r - 2: sendC = c - 1
  GOSUB trySend
  r = emptyR(e): c = emptyC(e)
  sendR = r - 2: sendC = c + 1
  GOSUB trySend
  r = emptyR(e): c = emptyC(e)
  sendR = r - 1: sendC = c - 2
  GOSUB trySend
  r = emptyR(e): c = emptyC(e)
  sendR = r - 1: sendC = c + 2
  GOSUB trySend
  r = emptyR(e): c = emptyC(e)
  sendR = r + 2: sendC = c - 1
  GOSUB trySend
  r = emptyR(e): c = emptyC(e)
  sendR = r + 2: sendC = c + 1
  GOSUB trySend
  r = emptyR(e): c = emptyC(e)
  sendR = r + 1: sendC = c - 2
  GOSUB trySend
  r = emptyR(e): c = emptyC(e)
  sendR = r + 1: sendC = c + 2
  GOSUB trySend
 NEXT
 EXIT SUB

trySend:
 IF sendR >= 1 AND sendR <= 5 AND sendC >= 1 AND sendC <= 5 THEN
   allowSame = 0
   mCode = codeMove(sendR, sendC, r, c)
   IF round > 1 THEN
    IF mCode \ 100 = mHist(round - 1) MOD 100 THEN
      allowSame = 1
    END IF
   END IF
   IF board(sendR, sendC) = turn OR allowSame = 1 THEN
     SWAP board(sendR, sendC), board(r, c)
   
     good = 1
     pCode = codePos
     FOR pn = 1 TO round - 1
       IF pCode = pHist(pn) THEN good = 0: EXIT FOR
     NEXT
     IF good THEN
      IF round > 2 THEN
        IF mHist(round - 2) = mCode \ 100 + 100 * (mCode MOD 100) THEN
          good = 0
        END IF
      END IF
      IF round > 1 THEN
        IF mHist(round - 1) = mCode \ 100 + 100 * (mCode MOD 100) THEN
          good = 0
        END IF
      END IF
      IF good THEN
        mHist(round) = mCode
        IF pCode = goal THEN
         FOR i = 1 TO round
           PRINT mHist(i);
           mh$ = LTRIM$(STR$(mHist(i)))
           mh$ = MID$(mh$, 2, 1) + MID$(mh$, 1, 1) + MID$(mh$, 4, 1) + MID$(mh$, 3, 1)
           FOR j = 1 TO LEN(mh$)
             IF j MOD 2 THEN
              PRINT #2, MID$("ABCDE", VAL(MID$(mh$, j, 1)), 1);
             ELSE
              PRINT #2, MID$(mh$, j, 1);
             END IF
           NEXT
           PRINT #2,
         NEXT
         PRINT "---": PRINT
         PRINT #2, "---"
        ELSE
         IF round < 33 THEN
          emptyR(e) = sendR: emptyC(e) = sendC

          IF allowSame = 0 THEN turn = 3 - turn
          move round + 1
          IF allowSame = 0 THEN turn = 3 - turn

          emptyR(e) = r: emptyC(e) = c
          ELSE
      '   FOR i = 1 TO round
      '     PRINT mHist(i), pHist(i)
      '   NEXT
      '   PRINT
      '   DO: LOOP UNTIL INKEY$ > ""
         END IF
        END IF
      END IF
     END IF
   
     SWAP board(sendR, sendC), board(r, c)
   END IF
 END IF
 RETURN
END SUB

(but I've added hyphens to the text of the file for readability in the previous post.)

Posted by Charlie on 2004-12-10 21:25:24