老鼠走迷宮

November 29, 2021

老鼠走迷宮是遞迴求解的基本題型,例如,在二維陣列中使用 2 表示迷宮牆壁,1 表示老鼠的行走路徑,以程式求出由入口至出口的一條路徑;進一步地,若入口至出口路徑可能不只一條,列出全部路。

想知道怎麼隨機生成迷宮嗎?你可以參考〈玩轉 p5.js〉中的迷宮說明。

解法思路

老鼠的走法有上、左、下、右四個方向,每前進一格後,選一個未造訪方向進行遞迴,無法前進時退回,選擇下個未造訪方向進行遞迴,每次遞迴亦是依序測試四個方向,直到走到出口為止。

Procedure GO(maze[])
    VISIT(maze, START_I, START_J, END_I, END_J)
    
Procedure VISIT(maze[], i, j, end_i, end_j)
    IF maze[i][j] == 0
        maze[i][j] = 1
        IF maze[end_i][end_j] == 0
           IF !(VISIT(maze, i, j + 1, end_i, end_j) OR 
                VISIT(maze, i + 1, j, end_i, end_j) OR
                VISIT(maze, i, j - 1, end_i, end_j) OR 
                VISIT(maze, i - 1, j, end_i, end_j))
               maze[i][j] = 0
    RETURN maze[end_i][end_j] == 1

求全部路徑的話,只要在老鼠走至出口時顯示經過的路徑,然後退回重新選擇下個方向遞迴就可以了:

Procedure GO(maze[])
    VISIT(maze, START_I, START_J, END_I, END_J)
    
Procedure VISIT(maze[], i, j, end_i, end_j)
    IF maze[i][j] == 0
        maze[i][j] = 1
        IF maze[end_i][end_j] == 1
            PRINT maze
        ELSE
            VISIT(maze, i, j + 1, end_i, end_j)
            VISIT(maze, i + 1, j, end_i, end_j)
            VISIT(maze, i, j - 1, end_i, end_j)
            VISIT(maze, i - 1, j, end_i, end_j)
        maze[i][j] = 0

程式實作:單一路徑

#include <stdlib.h>
#define SIZE 7

typedef struct {
    int x; 
    int y;
} Point;

Point pt(int, int);
int visit(int[][SIZE], Point, Point);
void print(int[][SIZE]);

int main(void) { 
    int maze[SIZE][SIZE] = {{2, 2, 2, 2, 2, 2, 2}, 
                            {2, 0, 0, 0, 0, 0, 2}, 
                            {2, 0, 2, 0, 2, 0, 2}, 
                            {2, 0, 0, 2, 0, 2, 2}, 
                            {2, 2, 0, 2, 0, 2, 2}, 
                            {2, 0, 0, 0, 0, 0, 2}, 
                            {2, 2, 2, 2, 2, 2, 2}}; 

    if(!visit(maze, pt(1, 1), pt(5, 5))) {
        printf("\n沒有找到出口!\n"); 
    }
    print(maze);
    
    return 0; 
}

Point pt(int x, int y) {
    Point p = {x, y};
    return p;
}

int visit(int maze[][SIZE], Point start, Point end) {
    if(!maze[start.x][start.y]) {
         maze[start.x][start.y] = 1;
         if(!maze[end.x][end.y] && 
            !(visit(maze, pt(start.x, start.y + 1), end) || 
              visit(maze, pt(start.x + 1, start.y), end) ||
              visit(maze, pt(start.x, start.y - 1), end) || 
              visit(maze, pt(start.x - 1, start.y), end))) {
                 maze[start.x][start.y] = 0;
         }
    }
    return maze[end.x][end.y];
    
}

void print(int maze[][SIZE]) {
    int i, j;
    for(i = 0; i < SIZE; i++) { 
        for(j = 0; j < SIZE; j++) switch(maze[i][j]) {
            case 0 : printf("  "); break;
            case 1 : printf("◇"); break;
            case 2 : printf("█"); 
        }
        printf("\n"); 
    }     
}
import static java.lang.System.out;

class Point {
    final int x;
    final int y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Mouse {
    public static int[][] go(int[][] maze, Point start, Point end) {
        visit(maze, start, end);
        return maze;
    }
    
    public static boolean visit(int[][] maze, Point pt, Point end) {
        if(isVisitable(maze, pt)) {
            maze[pt.x][pt.y] = 1;
            if(!isEnd(maze, end) && !tryOneOut(maze, pt, end)) {
                maze[pt.x][pt.y] = 0;
            }
        }
        return isEnd(maze, end);
    }

    public static boolean isVisitable(int[][] maze, Point pt) {
        return maze[pt.x][pt.y] == 0;
    }
    
    public static boolean isEnd(int[][] maze, Point end) {
        return maze[end.x][end.y] == 1;
    }
    
    public static boolean tryOneOut(int[][] maze, Point pt, Point end) {
        return visit(maze, new Point(pt.x, pt.y + 1), end) ||
               visit(maze, new Point(pt.x + 1, pt.y), end) ||
               visit(maze, new Point(pt.x, pt.y - 1), end) ||
               visit(maze, new Point(pt.x - 1, pt.y), end);
    }
    
    public static void main(String[] args) {
        int[][] maze = new int[][]{{2, 2, 2, 2, 2, 2, 2}, 
                                   {2, 0, 0, 0, 0, 0, 2}, 
                                   {2, 0, 2, 0, 2, 0, 2}, 
                                   {2, 0, 0, 2, 0, 2, 2}, 
                                   {2, 2, 0, 2, 0, 2, 2}, 
                                   {2, 0, 0, 0, 0, 0, 2}, 
                                   {2, 2, 2, 2, 2, 2, 2}};
                                   
        for(int[] row : Mouse.go(maze, new Point(1, 1), new Point(5, 5))) {
            for(int block : row) switch(block) {
                case 0: out.print("  "); break;
                case 1: out.print("◇"); break;
                case 2: out.print("█");
            }
            out.println();
        }
        out.println(Mouse.isEnd(maze, new Point(5, 5)) 
                    ? "找到出口" : "沒有找到出口!");
    }
} 
class Mouse:
    @staticmethod
    def go(maze, start, end):
        route = []
        Mouse.visit(maze, start, end, route)
        return route
    
    @staticmethod
    def visit(maze, pt, end, route):
        if Mouse.isVisitable(maze, pt, route):
            route.append(pt)
            if not Mouse.isEnd(route, end) and \
               not Mouse.tryOneOut(maze, pt, end, route):
                route.pop()
        return Mouse.isEnd(route, end)
    
    @staticmethod
    def isVisitable(maze, pt, route):
        return maze[pt[0]][pt[1]] == 0 and pt not in route
        
    @staticmethod
    def isEnd(route, end):
        return end in route
        
    @staticmethod
    def tryOneOut(maze, pt, end, route):
        return Mouse.visit(maze, (pt[0], pt[1] + 1), end, route) or \
               Mouse.visit(maze, (pt[0] + 1, pt[1]), end, route) or \
               Mouse.visit(maze, (pt[0], pt[1] - 1), end, route) or \
               Mouse.visit(maze, (pt[0] - 1, pt[1]), end, route)
               
maze = [[2, 2, 2, 2, 2, 2, 2],
        [2, 0, 0, 0, 0, 0, 2],
        [2, 0, 2, 0, 2, 0, 2],
        [2, 0, 0, 2, 0, 2, 2],
        [2, 2, 0, 2, 0, 2, 2],
        [2, 0, 0, 0, 0, 0, 2],
        [2, 2, 2, 2, 2, 2, 2]]
        
for pt in Mouse.go(maze, (1, 1), (5, 5)):
    maze[pt[0]][pt[1]] = 1

if maze[5][5] == 0:
    print("找不到出口")

for row in maze:
    for block in row:
        {
            0 : lambda: print("  ", end=""),
            1 : lambda: print("◇", end=""),
            2 : lambda: print("█",end=""),
        }[block]()
    print()
case class Point(x: Int, y: Int)

object Mouse {
    def go(maze: List[List[Int]], start: Point, end: Point) = {
        visit(maze, start, end, Nil)
    }
    
    def visit(maze: List[List[Int]], pt: Point, 
              end: Point, route: List[Point]): List[Point] = {
        if(isVisitable(maze, pt, route)) {
            if(isEnd(pt, end)) end::route 
            else tryOneOut(maze, pt, end, pt::route)
        } else Nil
    }
    
    def isVisitable(maze: List[List[Int]], pt: Point, route: List[Point]) = {
        maze(pt.x)(pt.y) == 0 && !route.contains(pt)
    }
    
    def isEnd(pt: Point, end: Point) = pt == end
    
    def tryOneOut(maze: List[List[Int]], pt: Point, 
                  end: Point, route: List[Point]) = {
        or(visit(maze, Point(pt.x, pt.y + 1), end, route)) { 
            or(visit(maze, Point(pt.x + 1, pt.y), end, route)) {
                or(visit(maze, Point(pt.x, pt.y - 1), end, route)) {
                    visit(maze, Point(pt.x - 1, pt.y), end, route)
                }
            }
        }
    }
    
    def or(expr1: => List[Point])(expr2: => List[Point]) = {
        val route = expr1
        if(route == Nil) expr2 else route    
    }
}

val maze = List(
               List(2, 2, 2, 2, 2, 2, 2), 
               List(2, 0, 0, 0, 0, 0, 2), 
               List(2, 0, 2, 0, 2, 0, 2), 
               List(2, 0, 0, 2, 0, 2, 2), 
               List(2, 2, 0, 2, 0, 2, 2), 
               List(2, 0, 0, 0, 0, 0, 2), 
               List(2, 2, 2, 2, 2, 2, 2)
           )

val route = Mouse.go(maze, Point(1, 1), Point(5, 5))

if(!route.contains(Point(5, 5))) {
    println("找不到出口")
}

for(i <- 0 until maze.length) {
    for(j <- 0 until maze(i).length) {
        if(route.contains(Point(i, j))) {
            print("◇")
        } else {
            maze(i)(j) match {
                case 0 => print("  ")
                case 2 => print("█")
            }
        }
    }
    println()
}
# encoding: UTF-8
class Mouse
    def self.go(maze, start, goal)
        route = []
        visit(maze, start, goal, route)
        route
    end
    
    def self.visit(maze, pt, goal, route)
        if isVisitable(maze, pt, route)
            route << pt
            if not isGoal(route, goal) and 
               not tryOneOut(maze, pt, goal, route)
                route.pop
            end
        end
        isGoal(route, goal)
    end
    
    def self.isVisitable(maze, pt, route)
        maze[pt[:x]][pt[:y]] == 0 and not route.include? pt
    end
   
    def self.isGoal(route, goal)
        route.include? goal
    end
    
    def self.tryOneOut(maze, pt, goal, route)
        visit(maze, {x: pt[:x], y: pt[:y] + 1}, goal, route) or
        visit(maze, {x: pt[:x] + 1, y: pt[:y]}, goal, route) or
        visit(maze, {x: pt[:x], y: pt[:y] - 1}, goal, route) or
        visit(maze, {x: pt[:x] - 1, y: pt[:y]}, goal, route)
    end
end

maze = [
          [2, 2, 2, 2, 2, 2, 2],
          [2, 0, 0, 0, 0, 0, 2],
          [2, 0, 2, 0, 2, 0, 2],
          [2, 0, 0, 2, 0, 2, 2],
          [2, 2, 0, 2, 0, 2, 2],
          [2, 0, 0, 0, 0, 0, 2],
          [2, 2, 2, 2, 2, 2, 2]
       ]
       
Mouse.go(maze, {x: 1, y: 1}, {x: 5, y: 5}).each do |pt|
    maze[pt[:x]][pt[:y]] = 1
end

if maze[5][5] == 0
    puts "找不到出口"
end

maze.each do |row|
    row.each do |block|
        case block
            when 0 then print "  "
            when 1 then print "◇"
            when 2 then print "█"
        end
    end
    puts
var mouse = function() {

    function visit(maze, pt, end) {
        if(isVisitable(maze, pt)) {
            maze[pt.x][pt.y] = 1;
            if(!isEnd(maze, end) && !tryOneOut(maze, pt, end)) {
                maze[pt.x][pt.y] = 0;
            }
        }
        return isEnd(maze, end);
    }
    
    function isVisitable(maze, pt) {
        return maze[pt.x][pt.y] === 0;
    }
    
    function isEnd(maze, end) {
        return maze[end.x][end.y] === 1;
    }
    
    function tryOneOut(maze, pt, end) {
        return visit(maze, {x: pt.x, y: pt.y + 1}, end) ||
               visit(maze, {x: pt.x + 1, y: pt.y}, end) ||
               visit(maze, {x: pt.x, y: pt.y - 1}, end) ||
               visit(maze, {x: pt.x - 1, y: pt.y}, end);
    }
    
    return function(maze, start, end) {
        visit(maze, start, end);
        return maze;
    };
    
}();

var maze = mouse([[2, 2, 2, 2, 2, 2, 2],
                  [2, 0, 0, 0, 0, 0, 2],
                  [2, 0, 2, 0, 2, 0, 2],
                  [2, 0, 0, 2, 0, 2, 2],
                  [2, 2, 0, 2, 0, 2, 2],
                  [2, 0, 0, 0, 0, 0, 2],
                  [2, 2, 2, 2, 2, 2, 2]],
                  {x: 1, y: 1}, {x: 5, y: 5});

var layout = '';
maze.forEach(function(row) {
    row.forEach(function(block) {
        switch(block) {
            case 0: layout += '  '; break;
            case 1: layout += '◇'; break;
            case 2: layout += '█';
        }
    });
    layout += '\n';
});
print(layout);
mouse maze start end = visit maze start end []
    where visit maze pt end route = if isVisitable maze pt route then 
                                        if isEnd pt end then end:route 
                                        else tryOneOut maze pt end (pt:route)
                                    else []
                                    
          isVisitable maze pt route = 
              maze !! fst pt !! snd pt == 0 && not (pt `elem` route)
              
          isEnd pt end = pt == end
          
          tryOneOut maze pt end route = 
              visit maze (fst pt, snd pt + 1) end route `or'`
              visit maze (fst pt + 1, snd pt) end route `or'`
              visit maze (fst pt, snd pt - 1) end route `or'`
              visit maze (fst pt - 1, snd pt) end route
              
          or' expr1 expr2 = if route == [] then expr2 else route
              where route = expr1
    
main = sequence [putStrLn row | row <- toSymbol maze \$ mouse maze start end]
    where maze = [
              [2, 2, 2, 2, 2, 2, 2],
              [2, 0, 0, 0, 0, 0, 2],
              [2, 0, 2, 0, 2, 0, 2],
              [2, 0, 0, 2, 0, 2, 2],
              [2, 2, 0, 2, 0, 2, 2],
              [2, 0, 0, 0, 0, 0, 2],
              [2, 2, 2, 2, 2, 2, 2]]

          start = (1, 1)
          end = (5, 5)

          width = length maze
          height = length \$ maze !! 0

          toSymbol maze route = [[if (i, j) `elem` route then 'M' 
                                  else case (maze !! i !! j) of 
                                           0 -> ' '
                                           2 -> 'X' | j <- [0..height - 1]
                                 ] | i <- [0..width - 1]]
contains(Pt, [Pt|_]).
contains(Pt, [_|T]) :- contains(Pt, T).

elem(Maze, [Px, Py], N) :- 
    nth0(Py, Maze, Row), nth0(Px, Row, N).

visitable(Maze, Route, Pt) :- 
    elem(Maze, Pt, 0), not(contains(Pt, Route)).

finish(Pt, Pt, Route, [Pt|Route]).

workaround(Maze, End, Route, Pt, Solution) :- 
    down(Maze, End, Route, Pt, Solution); 
    right(Maze, End, Route, Pt, Solution);
    up(Maze, End, Route, Pt, Solution); 
    left(Maze, End, Route, Pt, Solution).

down(Maze, End, Route, [Px, Py], Solution) :- 
    Npy is Py + 1, 
    find(Maze, End, Route, [Px, Npy], Solution).
    
right(Maze, End, Route, [Px, Py], Solution) :- 
    Npx is Px + 1, 
    find(Maze, End, Route, [Npx, Py], Solution).
    
up(Maze, End, Route, [Px, Py], Solution) :- 
    Npy is Py - 1, 
    find(Maze, End, Route, [Px, Npy], Solution).
    
left(Maze, End, Route, [Px, Py], Solution) :- 
    Npx is Px - 1,
    find(Maze, End, Route, [Npx, Py], Solution).

tryMore(Maze, End, Route, Pt, Solution) :- 
    workaround(Maze, End, [Pt|Route], Pt, Solution).

finish_or_tryMore(Maze, End, Route, Pt, Solution) :- 
    finish(End, Pt, Route, Solution); tryMore(Maze, End, Route, Pt, Solution).

find(Maze, End, Route, Pt, Solution) :- 
    visitable(Maze, Route, Pt), finish_or_tryMore(Maze, End, Route, Pt, Solution).

printMaze(_, X, Y, Solution) :- contains([X, Y], Solution), write("◇").
printMaze(0, _, _, _) :- write("  ").
printMaze(2, _, _, _) :- write("█").

printNext(T, Solution, X, Y) :- NX is X + 1, printRow(T, Solution, NX, Y).

printRow([], _, _, _) :- nl.
printRow([H|T], Solution, X, Y) :- printMaze(H, X, Y, Solution), printNext(T, Solution, X, Y).
    
printIt([Row|Rows], Solution, Y) :-
    printRow(Row, Solution, 0, Y), NY is Y + 1, printIt(Rows, Solution, NY).
    
printIt([], _, _) :- nl.

main(_) :-
    Maze = [
            [2, 2, 2, 2, 2, 2, 2],
            [2, 0, 0, 0, 0, 0, 2],
            [2, 0, 2, 0, 2, 0, 2],
            [2, 0, 0, 2, 0, 2, 2],
            [2, 2, 0, 2, 0, 2, 2],
            [2, 0, 0, 0, 0, 0, 2],
            [2, 2, 2, 2, 2, 2, 2]
         ],
    find(Maze,
         [5, 5],
         [],
         [1, 1],
         Solution
    ), 
    printIt(Maze, Solution, 0).
# 我寫的玩具語言 https://github.com/JustinSDK/toy_lang

def pt(x, y) {
    return new Object([['x', x], ['y', y]])
}

class Maze {
    def init(raw) {
        this.raw = raw
    }
 
    def get(x, y) {
        return this.raw.get(x).get(y)
    }

    def set(x, y, v) {
        this.raw.get(x).set(y, v)
    }

    def visit(st, ed) {
        if not this.get(st.x, st.y) {
            this.set(st.x, st.y, 1)
            if not this.get(ed.x, ed.y) and not this.tryOneOut(st, ed) {
                this.set(st.x, st.y, 0)
            }
        }
        return this.get(ed.x, ed.y)
    }
    
    def tryOneOut(st, ed) {
        (return this.visit(pt(st.x, st.y + 1), ed) or 
                this.visit(pt(st.x + 1, st.y), ed) or 
                this.visit(pt(st.x, st.y - 1), ed) or 
                this.visit(pt(st.x - 1, st.y), ed))

    }

    def printSymbol(i, j) {
        switch this.get(i, j) {
            case 0 
                print('  ')
            case 1
                print('++')
            case 2
                print('██') 
        }
    }

    def printRow(i) {
        (iterate(0, this.raw.get(i).length())
              .forEach(j -> this.printSymbol(i, j)))
        println()
    }

    def print() {
        iterate(0, this.raw.length()).forEach(this.printRow)
    }
}

(maze = new Maze([
    [2, 2, 2, 2, 2, 2, 2],
    [2, 0, 0, 0, 0, 0, 2],
    [2, 0, 2, 0, 2, 0, 2],
    [2, 0, 0, 2, 0, 2, 2],
    [2, 2, 0, 2, 0, 2, 2],
    [2, 0, 0, 0, 0, 0, 2],
    [2, 2, 2, 2, 2, 2, 2]
]))

if not maze.visit(pt(1, 1), pt(5, 5)) {
    println('沒有找到出口!')
}

maze.print()

程式實作:全部路徑

#include <stdio.h>
#include <stdlib.h>
#define SIZE 9

typedef struct {
    int x; 
    int y;
} Point;

Point pt(int, int);
void visit(int[][SIZE], Point, Point, void (*)(int[][SIZE]));
void print(int[][SIZE]);

int main(void) { 
    int maze[SIZE][SIZE] = {{2, 2, 2, 2, 2, 2, 2, 2, 2},
                            {2, 0, 0, 0, 0, 0, 0, 0, 2},
                            {2, 0, 2, 2, 0, 2, 2, 0, 2},
                            {2, 0, 2, 0, 0, 2, 0, 0, 2},
                            {2, 0, 2, 0, 2, 0, 2, 0, 2},
                            {2, 0, 0, 0, 0, 0, 2, 0, 2},
                            {2, 2, 0, 2, 2, 0, 2, 2, 2},
                            {2, 0, 0, 0, 0, 0, 0, 0, 2},
                            {2, 2, 2, 2, 2, 2, 2, 2, 2}}; 

    visit(maze, pt(1, 1), pt(7, 7), print);

    return 0; 
}

Point pt(int x, int y) {
    Point p = {x, y};
    return p;
}

void visit(int maze[][SIZE], Point start, 
           Point end, void (*take)(int[][SIZE])) {
    if(!maze[start.x][start.y]) {
         maze[start.x][start.y] = 1;
         if(maze[end.x][end.y]) {
             take(maze);
         }
         else {
             visit(maze, pt(start.x, start.y + 1), end, take);
             visit(maze, pt(start.x + 1, start.y), end, take);
             visit(maze, pt(start.x, start.y - 1), end, take);
             visit(maze, pt(start.x - 1, start.y), end, take);
         }
         maze[start.x][start.y] = 0;
    }
}

void print(int maze[][SIZE]) {
    int i, j;
    for(i = 0; i < SIZE; i++) { 
        for(j = 0; j < SIZE; j++) switch(maze[i][j]) {
            case 0 : printf("  "); break;
            case 1 : printf("◇"); break;
            case 2 : printf("█"); 
        }
        printf("\n"); 
    }     
}
import static java.lang.System.out;

class Point {
    final int x;
    final int y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

interface Boss {
    void take(int[][] maze);
}

public class Mouse {    
    public static void visit(int[][] maze, Point pt, Point end, Boss boss) {
        if(isVisitable(maze, pt)) {
            maze[pt.x][pt.y] = 1;
            if(isEnd(maze, end)) {
                boss.take(maze);
            } else {
                visit(maze, new Point(pt.x, pt.y + 1), end, boss);
                visit(maze, new Point(pt.x + 1, pt.y), end, boss);
                visit(maze, new Point(pt.x, pt.y - 1), end, boss);
                visit(maze, new Point(pt.x - 1, pt.y), end, boss);
            }
            maze[pt.x][pt.y] = 0;
        }
    }

    private static boolean isVisitable(int[][] maze, Point pt) {
        return maze[pt.x][pt.y] == 0;
    }
    
    public static boolean isEnd(int[][] maze, Point end) {
        return maze[end.x][end.y] == 1;
    }
    
    public static void main(String[] args) {
    
        Mouse.visit(new int[][] {
        
            {2, 2, 2, 2, 2, 2, 2, 2, 2},
            {2, 0, 0, 0, 0, 0, 0, 0, 2},
            {2, 0, 2, 2, 0, 2, 2, 0, 2},
            {2, 0, 2, 0, 0, 2, 0, 0, 2},
            {2, 0, 2, 0, 2, 0, 2, 0, 2},
            {2, 0, 0, 0, 0, 0, 2, 0, 2},
            {2, 2, 0, 2, 2, 0, 2, 2, 2},
            {2, 0, 0, 0, 0, 0, 0, 0, 2},
            {2, 2, 2, 2, 2, 2, 2, 2, 2}},
                        
            new Point(1, 1), new Point(7, 7), 

            // JDK8 Lambda
            maze -> {
                for(int[] row : maze) {
                    for(int block : row) switch(block) {
                        case 0: out.print("  "); break;
                        case 1: out.print("◇"); break;
                        case 2: out.print("█");
                    }
                    out.println();
                }
            }
        );
    }
} 
class Mouse:
    @staticmethod
    def go(maze, start, end, take):
        Mouse.visit(maze, start, end, [], take)
    
    @staticmethod
    def visit(maze, pt, end, route, take):
        if Mouse.isVisitable(maze, pt, route):
            route.append(pt)
            if Mouse.isEnd(route, end):
                take(maze, route)
            else:
                Mouse.visit(maze, (pt[0], pt[1] + 1), end, route, take)
                Mouse.visit(maze, (pt[0] + 1, pt[1]), end, route, take)
                Mouse.visit(maze, (pt[0], pt[1] - 1), end, route, take)
                Mouse.visit(maze, (pt[0] - 1, pt[1]), end, route, take)
            route.pop()
    
    @staticmethod
    def isVisitable(maze, pt, route):
        return maze[pt[0]][pt[1]] == 0 and pt not in route
        
    @staticmethod
    def isEnd(route, end):
        return end in route

def console(maze, route):
    for i in range(len(maze)):
        for j in range(len(maze[i])):
            if (i, j) in route:
                print("◇", end="")
            else:
                {
                    0 : lambda: print("  ", end=""),
                    2 : lambda: print("█",end="")
                }[maze[i][j]]()
        print()
   
Mouse.go([
           [2, 2, 2, 2, 2, 2, 2, 2, 2],
           [2, 0, 0, 0, 0, 0, 0, 0, 2],
           [2, 0, 2, 2, 0, 2, 2, 0, 2],
           [2, 0, 2, 0, 0, 2, 0, 0, 2],
           [2, 0, 2, 0, 2, 0, 2, 0, 2],
           [2, 0, 0, 0, 0, 0, 2, 0, 2],
           [2, 2, 0, 2, 2, 0, 2, 2, 2],
           [2, 0, 0, 0, 0, 0, 0, 0, 2],
           [2, 2, 2, 2, 2, 2, 2, 2, 2]
         ], (1, 1), (7, 7), console)
case class Point(x: Int, y: Int)

object Mouse {
    def go(maze: List[List[Int]], start: Point, end: Point) = {
        visit(maze, start, end, Nil)
    }
    
    def visit(maze: List[List[Int]], pt: Point, 
              end: Point, route: List[Point]): List[List[Point]] = {
        if(isVisitable(maze, pt, route)) {
            if(isEnd(pt, end)) {
                (end::route)::Nil 
            } else {
                visit(maze, Point(pt.x, pt.y + 1), end, pt::route) ++
                visit(maze, Point(pt.x + 1, pt.y), end, pt::route) ++
                visit(maze, Point(pt.x, pt.y - 1), end, pt::route) ++
                visit(maze, Point(pt.x - 1, pt.y), end, pt::route)
            }
        } else {
            Nil
        }
    }
    
    def isVisitable(maze: List[List[Int]], pt: Point, route: List[Point]) = {
        maze(pt.x)(pt.y) == 0 && !route.contains(pt)
    }
    
    def isEnd(pt: Point, end: Point) = {
        pt == end
    }
}

val maze = List(
                List(2, 2, 2, 2, 2, 2, 2, 2, 2),
                List(2, 0, 0, 0, 0, 0, 0, 0, 2),
                List(2, 0, 2, 2, 0, 2, 2, 0, 2),
                List(2, 0, 2, 0, 0, 2, 0, 0, 2),
                List(2, 0, 2, 0, 2, 0, 2, 0, 2),
                List(2, 0, 0, 0, 0, 0, 2, 0, 2),
                List(2, 2, 0, 2, 2, 0, 2, 2, 2),
                List(2, 0, 0, 0, 0, 0, 0, 0, 2),
                List(2, 2, 2, 2, 2, 2, 2, 2, 2)
            )

val allRoute = Mouse.go(maze, Point(1, 1), Point(7, 7))

allRoute.foreach( route =>
    for(i <- 0 until maze.length) {
        for(j <- 0 until maze(i).length) {
            if(route.contains(Point(i, j))) {
                print("◇")
            } else {
                maze(i)(j) match {
                    case 0 => print("  ")
                    case 2 => print("█")
                }
            }
        }
        println()
    }
)
# encoding: UTF-8
class Mouse
    def self.go(maze, start, goal)
        visit(maze, start, goal, [], ->(m, r) { yield(m, r) })
    end
    
    def self.visit(maze, pt, goal, route, take)
        if isVisitable(maze, pt, route)
            route << pt
            if isGoal(route, goal)
                take.call(maze, route)
            else
                visit(maze, {x: pt[:x], y: pt[:y] + 1}, goal, route, take)
                visit(maze, {x: pt[:x] + 1, y: pt[:y]}, goal, route, take)
                visit(maze, {x: pt[:x], y: pt[:y] - 1}, goal, route, take)
                visit(maze, {x: pt[:x] - 1, y: pt[:y]}, goal, route, take)
            end
            route.pop
        end
    end
    
    def self.isVisitable(maze, pt, route)
        maze[pt[:x]][pt[:y]] == 0 and not route.include? pt
    end
   
    def self.isGoal(route, goal)
        route.include? goal
    end
end

maze = [
           [2, 2, 2, 2, 2, 2, 2, 2, 2],
           [2, 0, 0, 0, 0, 0, 0, 0, 2],
           [2, 0, 2, 2, 0, 2, 2, 0, 2],
           [2, 0, 2, 0, 0, 2, 0, 0, 2],
           [2, 0, 2, 0, 2, 0, 2, 0, 2],
           [2, 0, 0, 0, 0, 0, 2, 0, 2],
           [2, 2, 0, 2, 2, 0, 2, 2, 2],
           [2, 0, 0, 0, 0, 0, 0, 0, 2],
           [2, 2, 2, 2, 2, 2, 2, 2, 2]
       ]

Mouse.go(maze, {x: 1, y: 1}, {x: 7, y: 7}) do |maze, route|
    0.upto(maze.size - 1) do |i|
        0.upto(maze[i].size - 1) do |j|
            if route.include?({x: i, y: j})
                print "◇"
            else
                case maze[i][j]
                    when 0 then print "  "
                    when 2 then print "█"
                end
            end
        end
        puts
    end
end
var mouse = function() {
    function isVisitable(maze, pt) {
        return maze[pt.x][pt.y] === 0;
    }
    
    function isEnd(maze, end) {
        return maze[end.x][end.y] === 1;
    }
    
    return function visit(maze, pt, end, take) {
        if(isVisitable(maze, pt)) {
            maze[pt.x][pt.y] = 1;
            if(isEnd(maze, end)) {
                take(maze);
            }
            else {
                visit(maze, {x: pt.x, y: pt.y + 1}, end, take);
                visit(maze, {x: pt.x + 1, y: pt.y}, end, take);
                visit(maze, {x: pt.x, y: pt.y - 1}, end, take);
                visit(maze, {x: pt.x - 1, y: pt.y}, end, take);
            }
            maze[pt.x][pt.y] = 0;
        }
    };
}();

mouse([[2, 2, 2, 2, 2, 2, 2, 2, 2],
       [2, 0, 0, 0, 0, 0, 0, 0, 2],
       [2, 0, 2, 2, 0, 2, 2, 0, 2],
       [2, 0, 2, 0, 0, 2, 0, 0, 2],
       [2, 0, 2, 0, 2, 0, 2, 0, 2],
       [2, 0, 0, 0, 0, 0, 2, 0, 2],
       [2, 2, 0, 2, 2, 0, 2, 2, 2],
       [2, 0, 0, 0, 0, 0, 0, 0, 2],
       [2, 2, 2, 2, 2, 2, 2, 2, 2]],
      {x: 1, y: 1}, {x: 7, y: 7},
      function(maze) {
          var layout = '';
          maze.forEach(function(row) {
              row.forEach(function(block) {
                  switch(block) {
                      case 0: layout += '  '; break;
                      case 1: layout += '◇'; break;
                      case 2: layout += '█';
                  }
             });
             layout += '\n';
          });
          print(layout);
      });
mouse maze start end = visit maze start end []
    where visit maze pt end route = 
              if isVisitable maze pt route then 
                  if isEnd pt end then (end:route):[]
                  else visit maze (fst pt, snd pt + 1) end (pt:route) ++
                       visit maze (fst pt + 1, snd pt) end (pt:route) ++
                       visit maze (fst pt, snd pt - 1) end (pt:route) ++
                       visit maze (fst pt - 1, snd pt) end (pt:route)
              else []
                                    
          isVisitable maze pt route = 
              maze !! fst pt !! snd pt == 0 && not (pt `elem` route)
              
          isEnd pt end = pt == end
          
         
main = sequence[
          sequence [putStrLn row | row <- toSymbol maze route] 
          | route <- mouse maze start end]
          
    where maze = [[2, 2, 2, 2, 2, 2, 2, 2, 2],
                  [2, 0, 0, 0, 0, 0, 0, 0, 2],
                  [2, 0, 2, 2, 0, 2, 2, 0, 2],
                  [2, 0, 2, 0, 0, 2, 0, 0, 2],
                  [2, 0, 2, 0, 2, 0, 2, 0, 2],
                  [2, 0, 0, 0, 0, 0, 2, 0, 2],
                  [2, 2, 0, 2, 2, 0, 2, 2, 2],
                  [2, 0, 0, 0, 0, 0, 0, 0, 2],
                  [2, 2, 2, 2, 2, 2, 2, 2, 2]]
              
          start = (1, 1)
          end = (7, 7)
          
          width = length maze
          height = length \$ maze !! 0
          
          toSymbol maze route = [[if (i, j) `elem` route then 'M' 
                                  else case (maze !! i !! j) of 
                                           0 -> ' '
                                           2 -> 'X' | j <- [0..height - 1]
                                 ] | i <- [0..width - 1]]
contains(Pt, [Pt|_]).
contains(Pt, [_|T]) :- contains(Pt, T).

elem(Maze, [Px, Py], N) :- 
    nth0(Py, Maze, Row), nth0(Px, Row, N).

visitable(Maze, Route, Pt) :- 
    elem(Maze, Pt, 0), not(contains(Pt, Route)).

finish(Pt, Pt, Route, [Pt|Route]).

workaround(Maze, End, Route, Pt, Solution) :- 
    down(Maze, End, Route, Pt, Solution); 
    right(Maze, End, Route, Pt, Solution);
    up(Maze, End, Route, Pt, Solution); 
    left(Maze, End, Route, Pt, Solution).

down(Maze, End, Route, [Px, Py], Solution) :- 
    Npy is Py + 1, 
    find(Maze, End, Route, [Px, Npy], Solution).
    
right(Maze, End, Route, [Px, Py], Solution) :- 
    Npx is Px + 1, 
    find(Maze, End, Route, [Npx, Py], Solution).
    
up(Maze, End, Route, [Px, Py], Solution) :- 
    Npy is Py - 1, 
    find(Maze, End, Route, [Px, Npy], Solution).
    
left(Maze, End, Route, [Px, Py], Solution) :- 
    Npx is Px - 1,
    find(Maze, End, Route, [Npx, Py], Solution).

tryMore(Maze, End, Route, Pt, Solution) :- 
    workaround(Maze, End, [Pt|Route], Pt, Solution).

finish_or_tryMore(Maze, End, Route, Pt, Solution) :- 
    finish(End, Pt, Route, Solution); tryMore(Maze, End, Route, Pt, Solution).

find(Maze, End, Route, Pt, Solution) :- 
    visitable(Maze, Route, Pt), finish_or_tryMore(Maze, End, Route, Pt, Solution).

printMaze(_, X, Y, Solution) :- contains([X, Y], Solution), write("◇").
printMaze(0, _, _, _) :- write("  ").
printMaze(2, _, _, _) :- write("█").

printNext(T, Solution, X, Y) :- NX is X + 1, printRow(T, Solution, NX, Y).

printRow([], _, _, _) :- nl.
printRow([H|T], Solution, X, Y) :- printMaze(H, X, Y, Solution), printNext(T, Solution, X, Y).
    
printIt([Row|Rows], Solution, Y) :-
    printRow(Row, Solution, 0, Y), NY is Y + 1, printIt(Rows, Solution, NY).
    
printIt([], _, _) :- nl.

printAll(_, []) :- nl, nl.
printAll(Maze, [H|T]) :- printIt(Maze, H, 0), printAll(Maze, T).

main(_) :-
    Maze =  [[2, 2, 2, 2, 2, 2, 2, 2, 2],
             [2, 0, 0, 0, 0, 0, 0, 0, 2],
             [2, 0, 2, 2, 0, 2, 2, 0, 2],
             [2, 0, 2, 0, 0, 2, 0, 0, 2],
             [2, 0, 2, 0, 2, 0, 2, 0, 2],
             [2, 0, 0, 0, 0, 0, 2, 0, 2],
             [2, 2, 0, 2, 2, 0, 2, 2, 2],
             [2, 0, 0, 0, 0, 0, 0, 0, 2],
             [2, 2, 2, 2, 2, 2, 2, 2, 2]],
    findall(Solution, find(Maze,
         [7, 7],
         [],
         [1, 1],
         Solution
    ), Solutions), 
    printAll(Maze, Solutions).
# 我寫的玩具語言 https://github.com/JustinSDK/toy_lang

def pt(x, y) {
    return new Object([['x', x], ['y', y]])
}

class Maze {
    def init(raw) {
        this.raw = raw
    }
 
    def get(x, y) {
        return this.raw.get(x).get(y)
    }

    def set(x, y, v) {
        this.raw.get(x).set(y, v)
    }

    def goalOrTry(st, ed) {
        if this.get(ed.x, ed.y) {
            this.print()
        }
        else {
            this.visit(pt(st.x, st.y + 1), ed)
            this.visit(pt(st.x + 1, st.y), ed) 
            this.visit(pt(st.x, st.y - 1), ed) 
            this.visit(pt(st.x - 1, st.y), ed)
        }
    }

    def visit(st, ed) {
        if not this.get(st.x, st.y) {
            this.set(st.x, st.y, 1)
            this.goalOrTry(st, ed)
            this.set(st.x, st.y, 0)
        }
    }

    def printSymbol(i, j) {
        switch this.get(i, j) {
            case 0 
                print('  ')
            case 1
                print('++')
            case 2
                print('██') 
        }
    }

    def printRow(i) {
        (iterate(0, this.raw.get(i).length())
              .forEach(j -> this.printSymbol(i, j)))
        println()
    }

    def print() {
        iterate(0, this.raw.length()).forEach(this.printRow)
    }
}

(maze = new Maze([
           [2, 2, 2, 2, 2, 2, 2, 2, 2],
           [2, 0, 0, 0, 0, 0, 0, 0, 2],
           [2, 0, 2, 2, 0, 2, 2, 0, 2],
           [2, 0, 2, 0, 0, 2, 0, 0, 2],
           [2, 0, 2, 0, 2, 0, 2, 0, 2],
           [2, 0, 0, 0, 0, 0, 2, 0, 2],
           [2, 2, 0, 2, 2, 0, 2, 2, 2],
           [2, 0, 0, 0, 0, 0, 0, 0, 2],
           [2, 2, 2, 2, 2, 2, 2, 2, 2]
         ]))

maze.visit(pt(1, 1), pt(7, 7))