再帰的バックトラッキングによる迷路生成（Python版）

@hextomino さんの「[再帰的バックトラッキングによる迷路生成](https://qiita.com/hextomino/items/d0bda1bf3bc62ec60f9c)」のコードのクラス構成を見直し、Pythonで書いてみました。

```py
import time
import random
import tkinter as tk


class Wall:

    def __init__(self):
        self.top = self.bottom = self.left = self.right = True


class Cell:
    SIZE = 40

    def __init__(self, x: int, y: int) -> None:
        self.x = x
        self.y = y
        self.wall = Wall()
        self.visited = False

    def knock_through(self, neighbor: "Cell") -> None:
        """neighbor（上下左右のいずれか）との間の壁をなくす"""
        match (self.x - neighbor.x, self.y - neighbor.y):
            case (0, 1):
                self.wall.top = neighbor.wall.bottom = False
            case (0, -1):
                self.wall.bottom = neighbor.wall.top = False
            case (1, 0):
                self.wall.left = neighbor.wall.right = False
            case (-1, 0):
                self.wall.right = neighbor.wall.left = False

    def draw(self, canvas: tk.Canvas, color: str="pink") -> None:
        """canvasに背景色colorで描画する"""
        x1, y1 = self.x * self.SIZE, self.y * self.SIZE
        x2, y2 = x1 + self.SIZE, y1 + self.SIZE
        if self.visited:
            canvas.create_rectangle(x1, y1, x2, y2, fill=color, outline=color)
        if self.wall.top:
            canvas.create_line(x1, y1, x2, y1)
        if self.wall.bottom:
            canvas.create_line(x1, y2, x2, y2)
        if self.wall.left:
            canvas.create_line(x1, y1, x1, y2)
        if self.wall.right:
            canvas.create_line(x2, y1, x2, y2)


class Maze:
    ROWS = 20
    COLS = 20
    YS = range(ROWS)
    XS = range(COLS)

    def __init__(self, canvas: tk.Canvas) -> None:
        self.canvas = canvas
        self.cells = [[Cell(x, y) for x in self.XS] for y in self.YS]
        self.tracking = [self.cells[self.ROWS//2][self.COLS//2]]

    def make(self, animation: bool=True, interval: int=50):
        """再帰的バックトラッキングによる迷路生成"""
        while self.tracking:
            cell = self.tracking[-1]
            cell.visited = True
            x, y = cell.x, cell.y
            neighbors = [self.cells[ny][nx]
                         for nx, ny in ((x-1, y), (x+1, y), (x, y-1), (x, y+1))
                         if nx in self.XS and ny in self.YS
                         if not self.cells[ny][nx].visited]
            if neighbors:
                neighbor = random.choice(neighbors)
                cell.knock_through(neighbor)
                self.tracking.append(neighbor)
                if animation:
                    self.canvas.after(interval, self.make)
                    break
            else:
                del self.tracking[-1]
        if animation:
            self.draw()

    def draw(self) -> None:
        """描画する"""
        self.canvas.delete("all")
        for rows in self.cells:
            for cell in rows:
                cell.draw(self.canvas, "cyan" if cell in self.tracking else "pink")


def main() -> None:
    root = tk.Tk()
    root.title("Maze")
    canvas = tk.Canvas(root,
                       width=Maze.COLS*Cell.SIZE,
                       height=Maze.ROWS*Cell.SIZE,
                       bg="white")
    canvas.pack()
    maze = Maze(canvas)
    maze.make()
    maze.draw()
    root.mainloop()


main()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29070/6fa0c38a-5e40-4a52-acd7-4b11c5bab75e.png)