All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Knight Moves (Posted on 2004-12-10)
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.

 No Solution Yet Submitted by DJ Rating: 3.1250 (8 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 re: One computer solution | Comment 4 of 10 |
(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
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

 Search: Search body:
Forums (0)