sudoku_backtracking.py

import re

import numpy as np


box_slices = {
    0: slice(0, 3),
    1: slice(0, 3),
    2: slice(0, 3),
}


def load_grids(fname, grid_number=None):
    """
    fname : str
        Filename to Project Euler Sudoku grids
    grid_name : int
        Zero-based grid to return. If none, returns a list of them all.
    """
    with open(fname) as fin:
        if grid_number is not None:
            # 10 newlines + len of grid name and len of grid
            grid_size = 7 + 9 ** 2 + 10
            fin.seek(grid_number * grid_size)
            fin.seek(8)  # seek to next line where grid starts
            # + 9 for newlines
            return fin.read(9 ** 2 + 9)
        return re.split(r"Grid \d\d\n", fin.read())[1:]


def parse_grid(grid):
    return (
        np.array([int(s) for line in grid.split() for s in line]).reshape(9, 9)
    )


def check_constraint(grid, index, value):
    if value in set(grid[index[0]]):
        return False
    if value in set(grid[:, index[1]]):
        return False
    grid_box = np.lib.stride_tricks.sliding_window_view(
        grid, [3, 3])[::3, ::3, :, :][(index[0] // 3, index[1] // 3)].flatten()
    if value in set(grid_box):
        return False
    return True


def naive_backtrack(grid):
    if np.all(grid > 0):
        return True

    for index, value in np.ndenumerate(grid):
        if value == 0:
            print(index, value)
            break
    else:
        return True

    for fill_value in range(1, 10):
        if check_constraint(grid, index, fill_value):
            grid[index] = fill_value

            if naive_backtrack(grid):
                return True

            grid[index] = 0

    return False


def constrain(grid, pencil_marks):
    # WIP: use same binary cube to keep track of pencil marks
    # not completed
    for index, value in np.ndenumerate(grid):
        if pencil_marks[index].sum() == 1 and value == 0:
            # go ahead and fill the grid
            grid[index] = np.where(pencil_marks[index]) + 1

        # eliminate possibilities from rows
        # the 1: removes the 0 counts and makes the indexing zero-based
        row_constraint = np.where(np.bincount(grid[index[0]])[1:])[0]
        col_constraint = np.where(np.bincount(grid[:, index[1]])[1:])[0]
        grid_constraint = np.where(np.bincount(
            grid[box_slices[index[0] // 3],
                 box_slices[index[1] // 3]].flatten())[1:]
        )

        pencil_marks[index[0], index[1], row_constraint] = 0
        pencil_marks[index[0], index[1], col_constraint] = 0
        pencil_marks[index[0], index[1], grid_constraint] = 0


if __name__ == "__main__":
    grids = load_grids("./p096_sudoku.txt")
    grid = load_grids("./p096_sudoku.txt", 0)

    constrainable_grid = np.array([
        [5, 3, 0, 0, 7, 0, 0, 0, 0],
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
        [0, 9, 8, 0, 0, 0, 0, 6, 0],
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
        [0, 0, 0, 0, 8, 0, 0, 7, 9],
    ])

    assert grid == grids[0]

    grid = parse_grid(grid)

    naive_backtrack(constrainable_grid)