A B C D E F G H I J K L M N O P Q R S

In this maze the exits/entrances are the triple coloured bars, green, yellow and magenta. Your path is defined by the sequence of those colours; ie, if you start at the top you may only enter a cell in the order of the cyclic sequence of G-Y-M (or the reverse order if you begin from below).

The object is to complete this maze, visiting each cell at least once. While there is more than one route, the shortest routes are 31 and 34 letters. What are those routes?

Note: This has been modelled on the contribution of Chris Lusby Taylor at http://www.mathpuzzle.com/ , 26 Jul 2009.

The DATA statements, whose strings are stored in the room$ array, describe each room with a lower case letter representing each exit color, each followed by an upper case letter signifying where that exit leads. The recursive subroutine "move" builds on roomList$ to provide the sequence of rooms entered. An X at the end indicates the exit from the maze.

DECLARE SUB move ()
CLEAR , , 25000
CLS
DATA yByEmD,gCgFgEyA,gBmFyG
DATA mAgEyIgH,yAgByFmJyIgD,gBmCmGyKyJyE,yCgLgKmF
DATA gDmImM,yDyEgJyNmMmH,mEyFgKyOyNgI,yFgGyLyPmOgJ,gGmPyK
DATA mHmIgNyQ,yIyJyOmRmQgM,yJmKgPmSyRyNyJ,yKmLmSgO
DATA yMmNgR,mNyOySgXgQ,mOmPyR

DIM SHARED cSeq$, room$(19), roomList$, currSeq, sct

cSeq$ = "gym"

FOR i = 1 TO 19
 READ room$(i)
NEXT

roomList$ = "B": currSeq = 1

move

PRINT sct

END

SUB move
 IF RIGHT$(roomList$, 1) = "X" THEN
   good = 1
   FOR i = 1 TO 19
    IF INSTR(roomList$, MID$("ABCDEFGHIJKLMNOPQRS", i, 1)) = 0 THEN good = 0
   NEXT
   IF good THEN
    PRINT roomList$; LEN(roomList$) - 1
    sct = sct + 1
   END IF
   EXIT SUB
 END IF
 IF INSTR(roomList$, RIGHT$(roomList$, 2)) < LEN(roomList$) - 1 THEN EXIT SUB
 IF LEN(roomList$) > 36 THEN EXIT SUB
 sb = INSTR("ABCDEFGHIJKLMNOPQRSTUVWXYZ", RIGHT$(roomList$, 1))
 guide$ = room$(sb)
 seek$ = MID$(cSeq$, currSeq, 1)
 ix = 1
 DO
  ix = INSTR(ix, guide$, seek$)
  IF ix = 0 THEN EXIT DO

  roomList$ = roomList$ + MID$(guide$, ix + 1, 1)
  currSeq = currSeq + 1: IF currSeq > 3 THEN currSeq = currSeq - 3
  move
  currSeq = currSeq - 1: IF currSeq < 1 THEN currSeq = currSeq + 3
  roomList$ = LEFT$(roomList$, LEN(roomList$) - 1)

  ix = ix + 1
 LOOP
END SUB

The above program finds three solutions:

BFEJKFGKPLGCFBADEIHDIMNOKJNQRSPONRX 34
BFEJKPLGCFBADEIHDIMNOKJNQRSPONRX 31
BEFGKPLGCFBADEIHDIMNOKJNQRSPONRX 31
 3

 
However, if we remove the line 

 IF INSTR(roomList$, RIGHT$(roomList$, 2)) < LEN(roomList$) - 1 THEN EXIT SUB

that prevents going through the same portal more than once in the same direction, then we get many more (60 -- i.e., 57 more) solutions that are just as short:

BCGFBADEADEIHDIMNOKJFGKLPONQRSPONRX 34
BCGFBADEFGKLPOJEDIHDIMNOKJNQRSPONRX 34
BCGFBADEFGKLPONRQMHDIMNOKJNQRSPONRX 34
BCGFBADEFGKLPONQRSPOJEDIHDIMNOKJNRX 34
BCGFBADEFGKLPONQRSPONRQMHDIMNOKJNRX 34
BCGFBADEFGKLPONQRSPOJEDIHDIMNOKJNRX 34
BCGFBADEFGKLPOJEDIHDIMNOKJNQRSPONRX 34
BCGFBADEIMNIHDIMNOKJFGKLPONQRSPONRX 34
BCGFBADEIHDIMNIMNOKJFGKLPONQRSPONRX 34
BCGFBADEIHDIMNJEBADEFGKLPONQRSPONRX 34
BCGFBADEIHDIMNOKJFGKFGKLPONQRSPONRX 34
BCGFBADEIHDIMNOKJFGKLPONQRSPONRX 31
BCGFBADEIHDIMNOKJOKJFGKLPONQRSPONRX 34
BCGFBADEIHDIHDIMNOKJFGKLPONQRSPONRX 34
BFJEDIHDIMNOKGCFBADEFGKLPONQRSPONRX 34
BFJEDIHDIMNOKJFCBADEFGKLPONQRSPONRX 34
BFEJKFCBADEIHDIMNOKJFGKLPONQRSPONRX 34
BFEJKFGKPLGCFBADEIHDIMNOKJNQRSPONRX 34
BFEJKPLGCFBADEADEIHDIMNOKJNQRSPONRX 34
BFEJKPLGCFBADEIMNIHDIMNOKJNQRSPONRX 34
BFEJKPLGCFBADEIHDIMNIMNOKJNQRSPONRX 34
BFEJKPLGCFBADEIHDIMNOKJOKJNQRSPONRX 34
BFEJKPLGCFBADEIHDIMNOKJNQRSPONRX 31
BFEJKPLGCFBADEIHDIHDIMNOKJNQRSPONRX 34
BFEJIEJKPLGCFBADEIHDIMNOKJNQRSPONRX 34
BEADEFCBADEIHDIMNOKJFGKLPONQRSPONRX 34
BEADEFGKPLGCFBADEIHDIMNOKJNQRSPONRX 34
BEADEIHDIMNOKJFCBADEFGKLPONQRSPONRX 34
BEFCBADEADEIHDIMNOKJFGKLPONQRSPONRX 34
BEFCBADEFGKLPOJEDIHDIMNOKJNQRSPONRX 34
BEFCBADEFGKLPONRQMHDIMNOKJNQRSPONRX 34
BEFCBADEFGKLPONQRSPOJEDIHDIMNOKJNRX 34
BEFCBADEFGKLPONQRSPONRQMHDIMNOKJNRX 34
BEFCBADEFGKLPONQRSPOJEDIHDIMNOKJNRX 34
BEFCBADEFGKLPOJEDIHDIMNOKJNQRSPONRX 34
BEFCBADEIMNIHDIMNOKJFGKLPONQRSPONRX 34
BEFCBADEIHDIMNIMNOKJFGKLPONQRSPONRX 34
BEFCBADEIHDIMNJEBADEFGKLPONQRSPONRX 34
BEFCBADEIHDIMNOKJFGKFGKLPONQRSPONRX 34
BEFCBADEIHDIMNOKJFGKLPONQRSPONRX 31
BEFCBADEIHDIMNOKJOKJFGKLPONQRSPONRX 34
BEFCBADEIHDIHDIMNOKJFGKLPONQRSPONRX 34
BEFGKFCBADEIHDIMNOKJFGKLPONQRSPONRX 34
BEFGKFGKPLGCFBADEIHDIMNOKJNQRSPONRX 34
BEFGKPLGCFBADEADEIHDIMNOKJNQRSPONRX 34
BEFGKPLGCFBADEIMNIHDIMNOKJNQRSPONRX 34
BEFGKPLGCFBADEIHDIMNIMNOKJNQRSPONRX 34
BEFGKPLGCFBADEIHDIMNOKJOKJNQRSPONRX 34
BEFGKPLGCFBADEIHDIMNOKJNQRSPONRX 31
BEFGKPLGCFBADEIHDIHDIMNOKJNQRSPONRX 34
BEIMNIHDIMNOKJFCBADEFGKLPONQRSPONRX 34
BEIHDIMNIMNOKJFCBADEFGKLPONQRSPONRX 34
BEIHDIMNJEBADEFCBADEFGKLPONQRSPONRX 34
BEIHDIMNOKJFCBADEADEFGKLPONQRSPONRX 34
BEIHDIMNOKJFCBADEFGKFGKLPONQRSPONRX 34
BEIHDIMNOKJFCBADEFGKLPONQRSPONRX 31
BEIHDIMNOKJFGKFCBADEFGKLPONQRSPONRX 34
BEIHDIMNOKJOKGCFBADEFGKLPONQRSPONRX 34
BEIHDIMNOKJOKJFCBADEFGKLPONQRSPONRX 34
BEIHDIHDIMNOKJFCBADEFGKLPONQRSPONRX 34
 60
 

Posted by Charlie on 2009-08-13 18:45:26