Recreating Peter Norvig's Sudoku solver from memory

sudoku.py

"""
I've always found Peter Norvig's Python solver for Sudoku at https://norvig.com/sudoku.html very elegant.
It had been a few years since I visited the page and I decided I would try to recreate it from memory.
I got pretty close!

The major difference is that my solution is missing one of the two propagation strategies.
Search works without it so I thought Norvig's solution might not use it.
Turns out I was wrong and it did have it.

Another difference is that Norvig's code is much better documented at the page https://norvig.com/sudoku.html .
So if you have trouble understanding the code below, be sure to visit the original.
"""

def _run_examples():
    # From https://en.wikipedia.org/wiki/Sudoku
    problem_1 = """
    53_ _7_ ___
    6__ 195 ___
    _98 ___ _6_

    8__ _6_ __3
    4__ 8_3 __1
    7__ _2_ __6

    _6_ ___ 28_
    ___ 419 __5
    ___ _8_ _79
    """

    # From https://www.youtube.com/watch?v=EciHY-dxIIE
    problem_2 = """
    _21 __4 98_
    4__ __2 _6_
    __5 _3_ 2__

    ___ __7 ___
    _5_ _1_ _9_
    ___ 2__ ___

    __4 _2_ 1__
    _9_ 8__ __7
    _16 9__ 83_
    """

    print(Sudoku.from_str(problem_1).solve())
    print()
    print()
    print(Sudoku.from_str(problem_2).solve())


def _str_product(a_str, b_str):
    return {a + b for a in a_str for b in b_str}


def _chunk(str, chunk_length):
    return [str[i:i+chunk_length] for i in range(0, len(str), chunk_length)]


NUMBERS = set("123456789")
X_COORDS = "123456789"
Y_COORDS = "ABCDEFGHI"
ALL_COORDS = _str_product(Y_COORDS, X_COORDS)
ROWS = [_str_product(y, X_COORDS) for y in Y_COORDS]
COLUMNS = [_str_product(Y_COORDS, x) for x in X_COORDS]
BOXES = [
    _str_product(y_chunk, x_chunk)
    for y_chunk in _chunk(Y_COORDS, 3)
    for x_chunk in _chunk(X_COORDS, 3)
]

# Each cell belongs to one row, one column and one box.
SETS = {
    coord: [set for set in (ROWS + COLUMNS + BOXES) if coord in set]
    for coord in ALL_COORDS
}


class NoSolutionError(Exception):
    def __init__(self, sudoku):
        self.sudoku = sudoku


class Sudoku:
    def __init__(self, copy=None):
        if copy is None:
            self._available = {
                loc: NUMBERS.copy()
                for loc in ALL_COORDS
            }
        else:
            self._available = copy._available.copy()

    def __getitem__(self, coord):
        if len(self._available[coord]) == 1:
            number, = self._available[coord]
            return number
        else:
            return None

    def __setitem__(self, coord, number):
        self._constrain(coord, {number})

    def _constrain(self, coord, constraint):
        old = self._available[coord]
        new = old & constraint
        self._available[coord] = new

        if len(new) == 0:
            raise NoSolutionError(self)
        elif old != new and len(new) == 1:
            for set in SETS[coord]:
                for c in set - {coord}:
                    self._constrain(c, NUMBERS - new)

    def solve(self):
        for coord in ALL_COORDS:
            if len(self._available[coord]) == 0:
                raise NoSolutionError(self)
            elif len(self._available[coord]) > 1:
                return self._try_each_number(coord)

        # For each coordinate only one choice, so this is the solution
        return self

    def _try_each_number(self, coord):
        for number in self._available[coord]:
            try:
                sudoku = Sudoku(self)
                sudoku[coord] = number
                return sudoku.solve()
            except NoSolutionError:
                continue
        raise NoSolutionError(self)

    @classmethod
    def from_str(cls, board_str):
        sudoku = cls()
        row_strs = [r.strip()
                    for r in board_str.replace(" ", "").strip().split("\n")
                    if r.strip() != ""]
        assert [len(r) for r in row_strs] == [9] * 9, str(row_strs)

        for y, row in zip(Y_COORDS, row_strs):
            for x, number in zip(X_COORDS, row):
                assert number in NUMBERS | set("_")
                if number != "_":
                    sudoku[y+x] = number
        return sudoku

    def __str__(self):
        return "\n\n".join(
            "\n".join(
                " ".join(
                    "".join(
                        self[y + x] or '_' for x in x_chunk
                    ) for x_chunk in _chunk(X_COORDS, 3)
                ) for y in y_chunk
            ) for y_chunk in _chunk(Y_COORDS, 3)
        )


if __name__ == "__main__":
    _run_examples()