Echo chess generator

gen.py

import sys
import random
from itertools import chain
from dataclasses import dataclass

@dataclass(eq=True, frozen=True)
class P:
    rank: int
    file: int

    def __repr__(self):
        return f'{chr(96 + self.rank)}{self.file}'

    def __add__(self, other):
        return self.__class__(self.rank + other.rank, self.file + other.file)

@dataclass
class Bounds:
    width: int
    height: int

    def __contains__(self, p):
        return 1 <= p.rank <= self.width and 1 <= p.file <= self.height

class King:
    def __repr__(self):
        return "K"

    def moves(self):
        yield from [(False, True, P(0, 1)), (False, True, P(1, 0)), (False, True, P(-1, 0)), (False, True, P(0, -1)), (False, True, P(1, 1)), (False, True, P(-1, -1)), (False, True, P(-1, 1)), (False, True, P(1, -1))]

class Pawn:
    def __repr__(self):
        return "P"

    def moves(self):
        yield from [(False, False, P(0, 1)), (True, True, P(-1, 1)), (True, True, P(1, 1))]

class Knight:
    def __repr__(self):
        return "N"

    def moves(self):
        yield from [(False, True, P(-2, -1)), (False, True, P(-2, 1)), (False, True, P(-1, -2)), (False, True, P(-1, 2)), (False, True, P(1, -2)), (False, True, P(1, 2)), (False, True, P(2, -1)), (False, True, P(2, 1))]

pieces = [Pawn(), Knight(), King()]

def reachable(piece, bounds, source):
    history = set([source])
    def go(u):
        for (final, capture, n) in piece.moves():
            v = u + n
            if v not in history and v in bounds:
                history.add(v)
                if capture:
                    yield v
                if not final:
                    yield from go(v)
    yield from go(source)

def dijkstra(piece, bounds, source, target):
    dist = {}
    prev = {}
    dist[source] = 0

    q = set([source])
    history = set()
    while len(q) > 0:
        u = min(q, key=lambda p: dist[p])
        q.remove(u)
        history.add(u)

        for (final, capture, n) in piece.moves():
            v = u + n
            if v not in history and v in bounds:
                if not final:
                    q.add(v)
                if (alt := dist[u] + 1) < dist.get(v, float('Inf')):
                    dist[v] = alt
                    prev[v] = u
    path = []
    u = target
    while prev.get(u, None):
        path.insert(0, u)
        u = prev[u]
    path.insert(0, source)
    return path

def generate(bounds, source, piece):
    explored = set([source])
    board = {}

    u = source
    while True:
        board[u] = piece
        r = list(reachable(piece, bounds, u))
        random.shuffle(r)
        for v in r:
            if v not in explored:
                moves = dijkstra(piece, bounds, u, v)
                piece = random.choice(pieces)
                explored.update(moves)
                u = moves[-1]
                break
        else:
            break
    return board

print(generate(Bounds(4, 4), P(1, 1), Knight()))