; This program attempts to find the exit of a maze. If a path to exit is found, ; it stores a 1 in x4000, otherwise, it stores a 0 in x4000. .ORIG x3000 LD R6, STACK ; compute the address of the starting point LEA R0, MAZE LD R1, START_IDX ADD R0, R0, R1 JSR FIND_EXIT STI R1, OUTPUT HALT STACK .FILL xFE00 OUTPUT .FILL x4000 START_IDX .FILL #9 ; the index of the starting location in the maze ; Read comments above definition of MAZE for details ; Recursive subroutine that determines if there is a path from current cell ; to the exit point. ; input: R0, current cell address ; output: R1, Yes (1) or No (0) FIND_EXIT ; save modified registers into the stack. ADD R6, R6, #-1 STR R2, R6, #0 ADD R6, R6, #-1 STR R3, R6, #0 ADD R6, R6, #-1 STR R7, R6, #0 ; Move cell address to R3, since we need to use R0 ; as the input to recursive subroutine calls. ADD R3, R0, #0 ; Put breadcrumb in the current cell. LDR R2, R0, #0 LD R7, BREADCRUMB ADD R2, R2, R7 STR R2, R0, #0 ; If the exit is in this cell, return yes LD R7, EXIT_MASK AND R7, R2, R7 BRnp DONE_YES ; check the north cell for a path to exit CHECK_NORTH LD R7, NORTH_MASK AND R7, R2, R7 BRz CHECK_EAST ; If the way to north is blocked, check east LDR R7, R3, #-6 BRn CHECK_EAST ; If there is breadcrumb in the north cell, check east ADD R0, R3, #-6 JSR FIND_EXIT ; Recursively check the north cell ADD R1, R1, #0 BRp DONE_YES ; If a path from north cell is found, return yes ; check the north cell for a path to exit CHECK_EAST LD R7, EAST_MASK AND R7, R2, R7 BRz CHECK_WEST ; If the way to east is blocked, check west LDR R7, R3, #1 BRn CHECK_WEST ; If there is breadcrumb in the east cell, check west ADD R0, R3, #1 JSR FIND_EXIT ; Recursively check the east cell ADD R1, R1, #0 BRp DONE_YES ; If a path from east cell is found, return yes ; check the west cell for a path to exit CHECK_WEST LD R7, WEST_MASK AND R7, R2, R7 BRz CHECK_SOUTH ; If the way to west is blocked, check south LDR R7, R3, #-1 BRn CHECK_SOUTH ; If there is breadcrumb in the west cell, check south ADD R0, R3, #-1 JSR FIND_EXIT ; Recursively check the west cell ADD R1, R1, #0 BRp DONE_YES ; If a path from west cell is found, return yes ; check the south cell for a path to exit CHECK_SOUTH LD R7, SOUTH_MASK AND R7, R2, R7 BRz DONE_NO ; If the way to south is blocked, return no LDR R7, R3, #6 BRn DONE_NO ; If there is breadcrumb in the south cell, return no ADD R0, R3, #6 JSR FIND_EXIT ; Recursively check the south cell ADD R1, R1, #0 BRp DONE_YES ; If a path from south cell is found, return yes DONE_NO AND R1, R1, #0 BR RESTORE DONE_YES AND R1, R1, #0 ADD R1, R1, #1 RESTORE ADD R0, R3, #0 ; restore R0 from R3 ; restore the rest of the modified registers from the stack. LDR R7, R6, #0 ADD R6, R6, #1 LDR R3, R6, #0 ADD R6, R6, #1 LDR R2, R6, #0 ADD R6, R6, #1 RET BREADCRUMB .FILL x8000 EXIT_MASK .FILL x0010 NORTH_MASK .FILL x0001 EAST_MASK .FILL x0002 WEST_MASK .FILL x0004 SOUTH_MASK .FILL x0008 ; The data structure initialized below represents the 6x6 maze shown in the ; comments. Each location in memory stores information relevant for one cell. ; Bits 0, 1, 2, and 3 in each words are set to 1 if path towards north, east, ; west, and south exists. Bit 4 is set if the cell is an exit point. bit 15 ; is initialized to zero and is used as a placeholder for breadcrumbs needed ; by the recursive algorithm. ; _ _ _ _ _ _ ; |_|_ _ |_| | ; | | |_|S|_| | ; | | _ | | ; |_ _|_| | |_| ; | | _ _|_|_| ; |_|E|_ _ _ _| ; The maze is stored in row major-order, meaning that the cells corresponding ; to each row are stored in sequential order. ; first row : indices 0 to 5 MAZE .FILL x0000 .FILL x0002 .FILL x0006 .FILL x000C .FILL x0000 .FILL x0008 ; second row : indices 6 to 11 .FILL x0008 .FILL x0008 .FILL x0000 .FILL x0009 .FILL x0000 .FILL x0009 ; third row : indices 12 to 17 .FILL x0009 .FILL x000B .FILL x0006 .FILL x000F .FILL x000C .FILL x0009 ; fourth row : indices 18 to 23 .FILL x0003 .FILL x0005 .FILL x0000 .FILL x0009 .FILL x0009 .FILL x0001 ; fifth row : indices 24 to 29 .FILL x0008 .FILL x000A .FILL x0006 .FILL x0005 .FILL x0001 .FILL x0000 ; sixth row : indices 30 to 35 .FILL x0001 .FILL x0019 .FILL x0002 .FILL x0006 .FILL x0006 .FILL x0004 .END