sudoku.py

from collections import deque
from itertools import cycle, chain, zip_longest
from pprint import pprint
from random import random, randint, sample, shuffle


class Sudoku:
    def __init__(self, grid):
        self.grid = grid

    @classmethod
    def from_seed(cls, seed):
        seed = deque(seed)
        grid = []

        for _ in range(3):
            for _ in range(3):
                grid.append(tuple(seed))
                seed.rotate(3)
            seed.rotate(1)

        return cls(grid)

    @classmethod
    def random_grid(cls):
        seed = list(range(1, 10))
        shuffle(seed)
        seed = deque(seed)

        grid = []

        # Initialize valid grid
        for _ in range(3):
            for _ in range(3):
                grid.append(tuple(seed))
                seed.rotate(3)
            seed.rotate(1)
        
        for i in range(5 + randint(0, 5)):
            # in-group inter-row shuffling
            for g in range(0, 9, 3):
                if random() < .5:
                    r1 = g + randint(0, 2)
                    r2 = g + (r1 + randint(1, 2)) % 3
                    grid[r1], grid[r2] = grid[r2], grid[r1]

            # inter-group shuffling
            if random() < .5:
                g1 = randint(0, 2) * 3
                g2 = (g1 + randint(1, 2) * 3) % 9
                for r in range(3):
                    grid[g1 + r], grid[g2 + r] = grid[g2 + r], grid[g1 + r]

            # transpose grid
            grid = list(zip(*grid))

        return cls([list(line) for line in grid])

    def copy(self):
        return type(self)([line.copy() for line in self.grid])

    def validate(self):
        def isvalid(line):
            x = tuple(filter(bool, line))
            return len(x) == len(set(x))

        for rowno, row in enumerate(self.grid):
            assert isvalid(row), f"row {rowno} is broken: {row}"

        for colno, col in enumerate(list(zip(*self.grid))):
            assert isvalid(col), f"col {colno} is broken: {col}"

        for group in [[self.grid[grow+row][gcol+col]
                       for col in range(3)
                       for row in range(3)]
                      for gcol in range(0, 9, 3)
                      for grow in range(0, 9, 3)]:
            assert isvalid(group), f"group {grow}:{gcol} is broken: {group}"

    def complexify(self):
        for (col, row) in chain.from_iterable(zip(*[
            iter(sample([
                (gcol + drow, grow + dcol)
                for drow in range(3)
                for dcol in range(3)
            ], 9))
            for grow in range(0, 9, 3)
            for gcol in range(0, 9, 3)
        ])):
            value = self.grid[row][col]
            self.grid[row][col] = 0
            if not self.is_solvable():
                self.grid[row][col] = value

    def iscomplete(self):
        return all(map(all, self.grid))

    def _get_possible_values(self, row, col):
        grow = row // 3 * 3
        gcol = col // 3 * 3
        return (
            set(range(1, 10))
            - {self.grid[row][x] for x in range(9)}
            - {self.grid[y][col] for y in range(9)}
            - {self.grid[grow+drow][gcol+dcol]
               for dcol in range(3)
               for drow in range(3)
            }
        )

    def get_hint(self, verbose=False):
        for row in range(9):
            for col in range(9):
                if not self.grid[row][col]:
                    if len(ps := self._get_possible_values(row, col)) == 1:
                        return row, col, ps.pop()

    def solve(self, verbose=False):
        while not self.iscomplete():
            hint = self.get_hint(verbose)
            if not hint:
                raise RuntimeError("Cannot solve further")
            if verbose:
                print(f"Found {hint[2]} at ({hint[1]},{hint[0]})")
            self.grid[hint[0]][hint[1]] = hint[2]

    def is_solvable(self):
        copy = self.copy()
        while not copy.iscomplete():
            hint = copy.get_hint()
            if not hint:
                return False
            copy.grid[hint[0]][hint[1]] = hint[2]

        return True

    def freeze(self):
        return "".join(map(str, chain.from_iterable(self.grid)))

    @classmethod
    def restore(cls, freeze):
        return cls([
            list(map(int, freeze[n:n+9]))
            for n in range(0, 81, 9)
        ])

    def __hash__(self):
        return hash(tuple(chain.from_iterable(self.grid)))

    def __str__(self):
        nstr = lambda n: " " if not n else str(n)
        return (
            "╔═╤═╤═╦═╤═╤═╦═╤═╤═╗\n%s%s" % ( 
            "╠═╪═╪═╬═╪═╪═╬═╪═╪═╣\n".join([
            "╟─┼─┼─╫─┼─┼─╫─┼─┼─╢\n".join([
                    "║%s║\n" % "║".join([
                        "│".join(map(nstr, line[j:j+3]))
                        for j in range(0, 9, 3)
                    ])
                    for line in self.grid[i:i+3]
                ])
                for i in range(0, 9, 3)
            ]),
            "╚═╧═╧═╩═╧═╧═╩═╧═╧═╝")
        )


def ():
    s1 = Sudoku.from_seed([1,2,3,4,5,6,7,8,9])
    s2 = Sudoku.from_seed([5,6,7,8,9,1,2,3,4])
    s3 = Sudoku.from_seed([4,5,6,7,8,9,1,2,3])
    s4 = Sudoku.from_seed([6,7,8,9,1,2,3,4,5])
    s5 = Sudoku.from_seed([9,1,2,3,4,5,6,7,8])


if __name__ == '__main__':
    import sys
    if len(sys.argv) > 1:
        su = Sudoku.restore("".join([
            "0" if s == " " else s
            for s in " ".join(sys.argv[1:])
            if s == " " or s.isdigit()
        ]))
        su.validate()
        resp = input("So far so good, [s]olve, [h]int, [q]uit ? ").casefold().strip()
        if resp == 'h':
            row, col, val = su.get_hint()
            print(f"row {row+1} col {col+1} is a {val}")
        elif resp == 's':
            su.solve()
            print(su)
    else:
        su = Sudoku.random_grid()
        su.complexify()
        print(su.freeze())
        print(su)