You are given a board 5x5 and 24 square pieces (1x1), one of them with a cross (+) and all the others 23 with a straight line on it (25 such pieces would cover the entire board).
(1) (23)
+-------+ +-------+
| _|_ | | _____ |
| | | | |
+-------+ +-------+Place the cross-piece in the upper left corner of the board.Your task is to find
"how to put the others 23 pieces," leaving the bottom right corner free, so that once this is made,
by only sliding the pieces, you can bring the cross-piece from the upper left corner to the right bottom corner (that is "free" initially).
"How to put the other 23 pieces" means what must be the orientation of the line on each one, horizontal or vertical, since those placed with the line horizontal-oriented
can only slide horizontally - to the right and to the left,- and those placed with the line vertical-oriented
can only slide vertically - up and down. Obviously, sliding is limited by the edges of the board.
The cross-piece is the only one that can slide horizontally and vertically.
The way I approaced it was to start with the + piece and the empty space in their proper positions, while leaving the other pieces indeterminate. As each piece gets used, its orientation is determined from then on.
The following program does that, systematically trying each possible move from a given state. When it reaches an impasse (or has traced 40 steps) it backtracks and continues with the next move from whatever level it can. The indeterminate states are marked by a ?, vertical movers by a | and horizontal movers by a -. An "impasse" means that any legal move from there results in a combination of + position and blank position that was arrived at before in the same solution chain.
DECLARE SUB move ()
CLEAR , , 10000
DIM SHARED board$(5, 5)
DIM SHARED rboard$(5, 5)
DIM SHARED origRow(5, 5)
DIM SHARED origCol(5, 5)
DIM SHARED hadState(625)
DIM SHARED blRow, blCol, plusRow, plusCol, lvl, h$
OPEN "crosbrd2.txt" FOR OUTPUT AS #2
FOR r = 1 TO 5
FOR c = 1 TO 5
board$(r, c) = "?"
origRow(r, c) = r
origCol(r, c) = c
NEXT
NEXT
board$(1, 1) = "+"
board$(5, 5) = "O"
blRow = 5: blCol = 5
plusRow = 1: plusCol = 1
CLS
state = (5 - 1) * 125 + (5 - 1) * 25 + (1 - 1) * 5 + 1 - 1
hadState(state) = 1
move
SUB move
lvl = lvl + 1
FOR i = 1 TO 4
a$ = MID$("udlr", i, 1)
SELECT CASE LCASE$(a$)
CASE "d"
r = blRow - 1: c = blCol
CASE "u"
r = blRow + 1: c = blCol
CASE "l"
r = blRow: c = blCol + 1
CASE "r"
r = blRow: c = blCol - 1
END SELECT
IF r < 1 OR r > 5 OR c < 1 OR c > 5 THEN
REM
ELSEIF (a$ = "u" OR a$ = "d") AND board$(r, c) = "-" OR (a$ = "l" OR a$ = "r") AND board$(r, c) = "|" THEN
REM
ELSE
pb$ = board$(r, c)
IF pb$ = "+" THEN
pr = blRow: pc = blCol
ELSE
pr = plusRow: pc = plusCol
END IF
newstate = (r - 1) * 125 + (c - 1) * 25 + (pr - 1) * 5 + pc - 1
IF hadState(newstate) = 0 THEN
' PRINT lvl; newstate
hadState(newstate) = 1
IF board$(r, c) = "?" THEN
IF a$ = "u" OR a$ = "d" THEN board$(r, c) = "|"
IF a$ = "l" OR a$ = "r" THEN board$(r, c) = "-"
END IF
SWAP board$(r, c), board$(blRow, blCol)
SWAP origRow(r, c), origRow(blRow, blCol)
SWAP origCol(r, c), origCol(blRow, blCol)
saveBlRow = blRow: saveBlCol = blCol
blRow = r: blCol = c
h$ = h$ + a$
IF pb$ = "+" THEN plusRow = saveBlRow: plusCol = saveBlCol
IF pb$ = "+" AND saveBlRow = 5 AND saveBlCol = 5 THEN
FOR rw = 1 TO 5
FOR cl = 1 TO 5
ro = origRow(rw, cl)
co = origCol(rw, cl)
rboard$(ro, co) = board$(rw, cl)
NEXT
NEXT
PRINT
PRINT #2,
FOR rw = 1 TO 5
FOR cl = 1 TO 5
PRINT rboard$(rw, cl);
PRINT #2, rboard$(rw, cl);
NEXT
PRINT
PRINT #2,
NEXT
PRINT h$
PRINT #2, h$
ELSE
IF lvl < 40 THEN
move
END IF
END IF
h$ = LEFT$(h$, LEN(h$) - 1)
blRow = saveBlRow: blCol = saveBlCol
SWAP board$(r, c), board$(blRow, blCol)
SWAP origRow(r, c), origRow(blRow, blCol)
SWAP origCol(r, c), origCol(blRow, blCol)
board$(r, c) = pb$
IF pb$ = "+" THEN plusRow = r: plusCol = c
hadState(newstate) = 0
END IF
END IF
NEXT
lvl = lvl - 1
END SUB
The shortest solution it finds is:
+-???
||-??
-||-?
?-|-|
??-|O
drurdrdrddluruldluruldluruldlur
where some pieces have never moved and so are still indeterminate--they could be oriented either way. The moves to solve this are marked below it, representing down, right, up and left. These are the motions of the piece being moved, not of the empty square.
Here's this solution worked out, with the 0 representing the empty spot (read left to right then go to the next row):
+-??? +-??? +-??? +-???
||-?? ||-?? ||-?? ||-??
-||-? -||-? -||-? -||-?
?-|-| ?-|-O ?-|O- ?-||-
??-|O ??-|| ??-|| ??-O|
+-??? +-??? +-??? +-???
||-?? ||-?? ||-?? ||-??
-||-? -||-? -||-? -O|-?
?-||- ?-O|- ?O-|- ?|-|-
??O-| ??|-| ??|-| ??|-|
+-??? +-??? O-??? -O???
||-?? O|-?? +|-?? +|-??
O-|-? |-|-? |-|-? |-|-?
?|-|- ?|-|- ?|-|- ?|-|-
??|-| ??|-| ??|-| ??|-|
-|??? -|??? -|??? -|???
+O-?? O+-?? |+-?? |+-??
|-|-? |-|-? O-|-? -O|-?
?|-|- ?|-|- ?|-|- ?|-|-
??|-| ??|-| ??|-| ??|-|
-|??? -|??? -|??? -|???
|O-?? |-O?? |-|?? |-|??
-+|-? -+|-? -+O-? -O+-?
?|-|- ?|-|- ?|-|- ?|-|-
??|-| ??|-| ??|-| ??|-|
-|??? -|??? -|??? -|???
|-|?? |-|?? |-|?? |-|??
-|+-? -|+-? -|O-? -|-O?
?O-|- ?-O|- ?-+|- ?-+|-
??|-| ??|-| ??|-| ??|-|
-|??? -|??? -|??? -|???
|-|?? |-|?? |-|?? |-|??
-|-|? -|-|? -|-|? -|-|?
?-+O- ?-O+- ?-|+- ?-|+-
??|-| ??|-| ??O-| ??-O|
-|??? -|??? -|??? -|???
|-|?? |-|?? |-|?? |-|??
-|-|? -|-|? -|-|? -|-|?
?-|O- ?-|-O ?-|-| ?-|-|
??-+| ??-+| ??-+O ??-O+
The program found 1707 basic solutions (this one plus 1706 others). Each of course has variations, as each of the ?'s can be replaced by either a vertical or horizontal line. Also, I chose only those solutions starting with a d move. Each such has a reflection that starts with an r move. Also, the program limited its search to paths of 40 or fewer moves. All the solutions have at least one spot which does not move and therefore is indeterminate.
A different solution, chosen in the middle of the file at random:
+-|--
||-?|
-||-|
?||-|
?--|O
drurrddrddluruldluruulddddlluururuldlur
|
|
Posted by Charlie
on 2005-09-30 21:08:44 |
solution -- computer assisted
