Pattern visualizer
Rat in a Maze
Four-directional movement means the rat can wander back toward cells it already stood on, so a plain grid walk can loop forever. Marking the current cell visited before stepping to a neighbor, and unmarking it the moment the recursion returns, blocks that cycle on the current branch while still letting a different branch pass through the same cell later. Moves are tried in a fixed alphabetical order (D, L, R, U) so the collected paths come out in a defined order. Reaching (n-1, n-1) records a path but does not stop the search — every other untried direction, at every depth, still gets explored. Animated on: n = 3, maze = [[1,0,0],[1,1,0],[1,1,1]]. Find every path from (0,0) to (n-1,n-1) moving D/L/R/U through open (1) cells, never revisiting a cell on the same path. Answer: ["DDRR","DRDR"]..
Path backtracking with a visited set, moves tried in D, L, R, U order
n = 3. (0, 0) is open, so the rat starts there. Directions are tried in alphabetical order D, L, R, U; a move is legal only if it stays in bounds, the cell is open (1) and not already on the current path.
1FUNCTION solveMaze(maze)2 out <- EMPTY LIST3 path <- EMPTY LIST4 FUNCTION place(r, c)5 IF (r, c) = (n - 1, n - 1)6 APPEND JOIN(path) TO out7 RETURN8 FOR EACH (dir, dr, dc) IN [D, L, R, U]9 IF NOT INBOUNDS(r+dr, c+dc) OR maze[r+dr][c+dc] = 0 OR visited[r+dr][c+dc]10 CONTINUE11 MARK visited[r+dr][c+dc], APPEND dir TO path12 place(r+dr, c+dc)13 REMOVE LAST FROM path, UNMARK visited[r+dr][c+dc]14 place(0, 0)15 RETURN out
← / → step · space play · Home restart