There are 10 coins laid out on a table in a straight line
* * * * * * * * * *
1 2 3 4 5 6 7 8 9 10
The goal is to get 5 stacks of 2 coins each in only 5 jumps.
A coin must jump over exactly 2 other coins and land on a third.
Coins may jump in either direction.
Example:
Jump 1: Jump coin 10 on top of coin 7.
Jump 2: Jump coin 8 on top of coin 6. This is possible since coin 7 and 10 now form a stack of two coins.
To eliminate mirror image solutions, the following list shows only those whose first "from" move is from positions 1 through 5. In each pair the "from" is shown first and then the "to":
4 1 6 9 8 3 2 5 7 10
4 1 6 9 8 3 2 5 10 7
4 1 6 9 8 3 5 2 7 10
4 1 6 9 8 3 5 2 10 7
4 1 6 9 8 3 7 10 2 5
4 1 6 9 8 3 7 10 5 2
4 1 6 9 8 3 10 7 2 5
4 1 6 9 8 3 10 7 5 2
4 1 7 3 5 9 2 6 8 10
4 1 7 3 5 9 2 6 10 8
4 1 7 3 5 9 6 2 8 10
4 1 7 3 5 9 6 2 10 8
4 1 7 3 5 9 8 10 2 6
4 1 7 3 5 9 8 10 6 2
4 1 7 3 5 9 10 8 2 6
4 1 7 3 5 9 10 8 6 2
5 2 7 10 3 8 1 4 6 9
5 2 7 10 3 8 1 4 9 6
5 2 7 10 3 8 4 1 6 9
5 2 7 10 3 8 4 1 9 6
5 2 7 10 3 8 6 9 1 4
5 2 7 10 3 8 6 9 4 1
5 2 7 10 3 8 9 6 1 4
5 2 7 10 3 8 9 6 4 1
Of these 24, there are actually only 3 basic solutions, starting
4 1 6 9 8 3
4 1 7 3 5 9
5 2 7 10 3 8
as the remaining two moves are actually no different within each of these families--just a different order.
DECLARE SUB move (mNum!)
DIM SHARED histA(5), histB(5)
DIM SHARED board(10)
DIM SHARED solCt
FOR i = 1 TO 10: board(i) = 1: NEXT
move 1
PRINT solCt
SUB move (mNum)
IF mNum = 1 THEN top = 5: ELSE top = 10
FOR i = 1 TO top
IF board(i) = 1 THEN
ct = 0
FOR j = i - 1 TO 1 STEP -1
IF ct = 2 AND board(j) = 1 THEN
GOSUB playIt
EXIT FOR
END IF
ct = ct + board(j)
NEXT
ct = 0
FOR j = i + 1 TO 10
IF ct = 2 AND board(j) = 1 THEN
GOSUB playIt
EXIT FOR
END IF
ct = ct + board(j)
NEXT
END IF
NEXT i
EXIT SUB
playIt:
histA(mNum) = i: histB(mNum) = j
board(i) = 0: board(j) = 2
IF mNum = 5 THEN
FOR st = 1 TO 5
PRINT histA(st); histB(st),
NEXT
solCt = solCt + 1
ELSE
move mNum + 1
END IF
board(i) = 1: board(j) = 1
RETURN
END SUB
|
|
Posted by Charlie
on 2004-10-20 02:49:03 |
exhaustive search
