Starting from the central cell of this maze (there's a (3) in it), the challenge is to find a path that leads you off the maze, and to a "star" (*).
The number at each cell shows how many steps, in a straight line, you must take. You can travel horizontally, vertically, or diagonally, up or down, left or right.
The computer algorithm is recursive, backing up when all directions lead to a dead end, where a dead end means that either a node is revisited (overall in all solutions) with more steps than it took before, or there is no node in that direction and it is more than one unit away from the digits. So long as viable paths lead from a point all such viable paths are explored. It proceeds rather rapidly, to arrive at a 9-move solution (It was told initially to go no more than 100 levels deep--no more than 100 moves--and its first found solution had 92 steps.)
The 9-step solution, can be described in words. First of all, except for the last step it is all on a diagonal running from upper right to lower left, and exiting by making a right-angled turn at the 4 that's near the lower left end of this diagonal (the 6 that is next to it is on the edge). All the solutions seem to go through that 4.
From the initial 3 go down and to the left to a 4; then down and to the left to the 6; then up and to the right to another 6 and further to the upper right to a 2. Again go up and to the right to a 5 on the edge. From there, down and to the left to a 4, and again down and to the left to another 4. Down and to the left again leads to the magic 4, where a right angled turn in either direction (upper left or lower right) takes you out.
The program, listed below, initially reads in the digits from a file and places them in an array, centering each row on the middle element of the array. When presenting the result it sends an expanded form of the original array to a file, with each single digit preceded by the time at which that node is visited and with a directional indicator next to the original digit showing the direction to the next node in sequence. (That's to make the longer paths more easy to follow.)
DECLARE SUB move (row!, col!)
CLEAR , , 20000
OPEN "startrek.txt" FOR INPUT AS #1
DO
LINE INPUT #1, l$
ct = 0
FOR i = 1 TO LEN(l$)
IF INSTR("0123456789", MID$(l$, i, 1)) THEN ct = ct + 1
NEXT
IF ct > maxCt THEN maxCt = ct
IF ct > 0 THEN lCt = lCt + 1
LOOP UNTIL EOF(1)
CLOSE
PRINT maxCt; lCt
DIM SHARED cell(lCt + 1, maxCt + 1), had(lCt, maxCt), gridSize, lvl
DIM SHARED drH(lCt, maxCt), dcH(lCt, maxCt)
DIM SHARED when(lCt + 1, maxCt + 1), when2(lCt + 1, maxCt + 1), solCt, bestSol
gridSize = maxCt
midPos = INT((maxCt + 1) / 2)
OPEN "startrek.txt" FOR INPUT AS #1
lCt = 0
DO
LINE INPUT #1, l$
ct = 0
FOR i = 1 TO LEN(l$)
IF INSTR("0123456789", MID$(l$, i, 1)) THEN ct = ct + 1
NEXT
IF ct > 0 THEN
lCt = lCt + 1
midCt = INT((ct + 1) / 2)
offSet = midPos - midCt
FOR i = 1 TO LEN(l$)
IF INSTR("0123456789", MID$(l$, i, 1)) THEN
offSet = offSet + 1
cell(lCt, offSet) = VAL(MID$(l$, i, 1))
END IF
NEXT
END IF
LOOP UNTIL EOF(1)
CLOSE
FOR row = 1 TO lCt
FOR col = 1 TO maxCt
PRINT cell(row, col);
NEXT
PRINT
NEXT
had(midPos, midPos) = 1
when(midPos, midPos) = 1
lvl = 1
bestSol = 9999
OPEN "startrk3.txt" FOR OUTPUT AS #2
move midPos, midPos
PRINT solCt, bestSol
CLOSE
END
SUB move (row, col)
stpSize = cell(row, col)
FOR dr = -1 TO 1
FOR dc = -1 TO 1
IF dr OR dc THEN
good = 1
r1 = row + dr * (stpSize - 1): c1 = col + dc * (stpSize - 1)
IF r1 > 0 AND r1 <= gridSize AND c1 > 0 AND c1 <= gridSize THEN
IF cell(r1, c1) THEN
r = row + dr * stpSize: c = col + dc * stpSize
IF cell(r, c) = 0 THEN
when(r, c) = lvl + 1
drH(row, col) = dr
dcH(row, col) = dc
FOR rw = 1 TO gridSize
FOR cl = 1 TO gridSize
IF drH(rw, cl) < 0 AND when(rw, cl) > 0 THEN
SELECT CASE dcH(rw, cl)
CASE -1
PRINT #2, " \ ";
CASE 0
PRINT #2, " ^ ";
CASE 1
PRINT #2, " /";
END SELECT
ELSE
PRINT #2, " ";
END IF
NEXT cl
PRINT #2,
FOR cl = 1 TO gridSize
IF when(rw, cl) > 0 THEN
PRINT USING "##"; when(rw, cl);
COLOR 14: IF cell(rw, cl) = 0 THEN COLOR 9
PRINT USING "#"; cell(rw, cl);
IF drH(rw, cl) = 0 AND dcH(rw, cl) < 0 THEN
PRINT #2, "<";
ELSE
PRINT #2, " ";
END IF
PRINT #2, USING "##"; when(rw, cl);
PRINT #2, USING "#"; cell(rw, cl);
IF drH(rw, cl) = 0 AND dcH(rw, cl) > 0 THEN
PRINT #2, ">";
ELSE
PRINT #2, " ";
END IF
COLOR 7
ELSE
IF cell(rw, cl) THEN
COLOR 14: IF cell(rw, cl) = 0 THEN COLOR 9
PRINT USING " #"; cell(rw, cl);
PRINT #2, USING " # "; cell(rw, cl);
COLOR 7
ELSE
PRINT " ";
PRINT #2, " ";
END IF
END IF
NEXT cl
PRINT #2,
FOR cl = 1 TO gridSize
IF drH(rw, cl) > 0 AND when(rw, cl) > 0 THEN
SELECT CASE dcH(rw, cl)
CASE -1
PRINT #2, " / ";
CASE 0
PRINT #2, " v ";
CASE 1
PRINT #2, " \";
END SELECT
ELSE
PRINT #2, " ";
END IF
NEXT cl
PRINT #2,
PRINT : PRINT
NEXT
solCt = solCt + 1
IF lvl < bestSol THEN bestSol = lvl
when(r, c) = 0
ELSE
IF lvl < 100 AND (had(r, c) = 0 OR when2(r, c) > lvl) THEN
drH(row, col) = dr
dcH(row, col) = dc
lvl = lvl + 1
had(r, c) = 1
when(r, c) = lvl
when2(r, c) = lvl
move r, c
when(r, c) = 0
lvl = lvl - 1
END IF
END IF
END IF
END IF
END IF
NEXT
NEXT
END SUB
|
|
Posted by Charlie
on 2005-09-24 02:29:46 |
computer solution
