迷路最短経路を無限(かもしれない)リストを使って

maze-problem-stream.py

# https://yosh.hateblo.jp/entries/2010/01/19#p1
# http://okajima.air-nifty.com/b/2010/01/post-abc6.html

from dataclasses import dataclass
from typing import NamedTuple, TextIO
from io import StringIO
from collections import deque

class Point(NamedTuple):
    x: int
    y: int


class Edge(NamedTuple):
    head: Point
    tail: Point


def neighbours(point: Point) -> list[Point]:
    x, y = point
    return [Point(x, y - 1), Point(x, y + 1), Point(x - 1, y), Point(x + 1, y)]


@dataclass
class Board:
    blanks: set[Point]
    start: Point
    goal: Point
    points: list[list[str]]


class PathStream:
    def __init__(self, board: Board) -> None:
        self.unvisited = board.blanks | {board.goal}
        self.q = deque([[board.start]])

    def __iter__(self) -> 'PathStream':
        return self

    def __next__(self) -> Point:
        path = self.q.popleft()
        for neighbour in neighbours(path[-1]):
            if neighbour in self.unvisited:
                self.unvisited.remove(neighbour)
                self.q.append(path + [neighbour])
        return path


def find_path(board: Board) -> list[Point]:
    for path in PathStream(board):
        if path[-1] == board.goal:
            return path


def load_board(f: TextIO):
    blanks = set()
    start = Point(-1, -1)
    goal = Point(-1, -1)
    points = []
    for y, line in enumerate(f):
        for x, ch in enumerate(line):
            if ch == ' ':
                blanks.add(Point(x, y))
            if ch == 'S':
                start = Point(x, y)
            if ch == 'G':
                goal = Point(x, y)
        points.append(list(line.rstrip('\n')))
    return Board(blanks, start, goal, points)


def main():
    board_str = '''\
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************'''
    board = load_board(StringIO(board_str))
    path = find_path(board)

    for point in path[1:-1]:
        board.points[point.y][point.x] = '$'
    for line in board.points:
        print(''.join(line))

if __name__ == '__main__':
    main()

無限リストを使わない版
https://gist.github.com/gyu-don/4923c31eed49e89aaf1dda6501d9c5cd

形式的な証明ではないが、pathの長さが非減少であるのはコードから明らか。
もしゴールに到達する経路がなければ、全ての可能なpathを列挙し終わった後で、キューから引けるものがなくなってエラーが出る。

訪問していない点のみを訪問するようにしなければ、計算が終わらなかった(時間がかかるだけでいずれ停止するとは思うが未検証)