sudokusolver.py

#!/usr/bin/python

import pprint
import functools
import itertools
import re
import time
import copy

SUBSQUARE_SIZE = 3
SUDOKU_SIZE = SUBSQUARE_SIZE * SUBSQUARE_SIZE
ALL_SET = set(list(range(1, SUDOKU_SIZE+1)))
ZERO_SET = set([])

def dbg_print(*args, **kwargs):
    return
    print(*args, **kwargs)

class SudokuCell(set):
    def __init__(self, *args, **kwargs):
        if(len(args) == 1):
            super().__init__(args[0])
        else:
            super().__init__(ALL_SET)
            self._board = args[0]
            self._ri = args[1]
            self._ci = args[2]

    def __int__(self):
        return self._ri * SUDOKU_SIZE + self._ci

    def __hash__(self):
        return hash(self.__int__())

    def __deepcopy__(self, memo):
        dup = type(self)(self)
        memo[id(self)] = dup
        dup._ri = self._ri
        dup._ci = self._ci
        dup._board = copy.deepcopy(self._board, memo)
        return dup

    @property
    def ri(self):
        return self._ri

    @property
    def ci(self):
        return self._ci

    @property
    def sqi(self):
        if "_sqi" not in self.__dict__:
            self._sqi = (self.ri//SUBSQUARE_SIZE) * SUBSQUARE_SIZE + (self.ci//SUBSQUARE_SIZE)
        return self._sqi

    @property
    def row(self):
        return self._board.row(self.ri)

    @property
    def col(self):
        return self._board.col(self.ci)

    @property
    def sq(self):
        return self._board.sq(self.sqi)

    def digest(self):
        return sum(self)

    def solv_2_cross(self,n):
            pass

    def uniq_solver(func):
        def wrapper(self, *args, **kwargs):
            orig = set(self)
            ret = func(self, *args, **kwargs)
            len_new = len(self)
            if orig != self:
                #if(self._board.is_original()):
                #    self._board.print_text()
                dbg_print(f"cell ({self.ri},{self.ci}) updated {orig} to {set(self)}")
            assert len_new
            if len_new == 1:
                for cell in filter(lambda c: self <= c, itertools.chain(self.row, self.col, self.sq)):
                    if id(cell) != id(self):
                        dbg_print(f"target ({cell.ri} {cell.ci}) {cell}")
                        assert cell != self
                        cell -= self
            return ret
        return wrapper

    @uniq_solver
    def __iand__(self,target):
        return super().__iand__(target)

    @uniq_solver
    def __isub__(self,target):
        return super().__isub__(target)

class SudokuChunk(frozenset):
    @property
    def remain(self):
        remain = set(ALL_SET)
        for cell in self:
            if len(cell) == 1:
                remain -= cell
        return remain

    def solv_n(self, n):
        ret = False
        for tpl in itertools.combinations(self.remain, n):
            tpl_set = set(tpl)
            found = set(filter(lambda cell: cell <= tpl_set, self))
            if len(found) == len(tpl):
                for cell in self - found:
                    if not cell.isdisjoint(tpl_set):
                        dbg_print(f"1 ({cell.ri},{cell.ci}) {cell} {tpl_set}")
                        cell -= tpl_set
                        ret = True
            found = set(filter(lambda cell: not cell.isdisjoint(tpl_set), self))
            if len(found) == len(tpl):
                for cell in found:
                    if not cell <= tpl_set:
                        dbg_print(f"2 ({cell.ri},{cell.ci}) {cell} {tpl_set}")
                        cell &= tpl_set
                        ret = True
        return ret

class SudokuSubSquare(SudokuChunk):
    def row(self, i):
        return self.rows[i]

    def col(self, i):
        return self.cols[i]

    @property
    def rows(self):
        if "_rows" not in self.__dict__:
            self._rows = set(map(lambda cell: cell.row, self))
        return self._rows

    @property
    def cols(self):
        if "_cols" not in self.__dict__:
            self._cols = set(map(lambda cell: cell.col, self))
        return self._cols

    def solv_n(self, n):
        def _solv_sq(c1, c2):
            for tpl in itertools.combinations(c1.remain, n):
                tpl_set = set(tpl)
                found = set(filter(lambda cell: not cell.isdisjoint(tpl_set), c1))
                if len(found) and found <= c2:
                    for cell in c2 - found:
                        dbg_print(f"3 ({cell.ri},{cell.ci}) {cell} {tpl_set}")
                        cell -= tpl_set
                        ret = True

        ret = super().solv_n(n)
        if n < 4:
            for chunk in itertools.chain(self.rows, self.cols):
                _solv_sq(self, chunk)
                _solv_sq(chunk, self)
        return ret

class SudokuBoard(list):
    def __init__(self, exam):
        assert isinstance(exam, str)
        exam = re.sub(r'\D','',exam)
        assert len(exam) == SUDOKU_SIZE * SUDOKU_SIZE
        print(exam)
        self.exam = exam
        super().__init__()
        self._original = id(self)
        for i in range(SUDOKU_SIZE * SUDOKU_SIZE):
            self.append(SudokuCell(self, i//SUDOKU_SIZE, i%SUDOKU_SIZE))
        for i, s in enumerate(exam):
            if int(s) != 0:
                self[i] &= set([int(s)])

    def row(self, i):
        return self.rows[i]

    def col(self, i):
        return self.cols[i]

    def sq(self,i):
        return self.sqs[i]

    def is_original(self):
        if "_original" not in self.__dict__:
            return False
        return self._original == id(self)

    @property
    def rows(self):
        if "_rows" not in self.__dict__:
            self._rows = list(map(lambda i: SudokuChunk(filter(lambda cell: cell.ri == i, self)), range(SUDOKU_SIZE)))
        return self._rows

    @property
    def cols(self):
        if "_cols" not in self.__dict__:
            self._cols = list(map(lambda i: SudokuChunk(filter(lambda cell: cell.ci == i, self)), range(SUDOKU_SIZE)))
        return self._cols

    @property
    def sqs(self):
        if "_sqs" not in self.__dict__:
            self._sqs = list(map(lambda i: SudokuSubSquare(filter(lambda cell: cell.sqi == i, self)), range(SUDOKU_SIZE)))
        return self._sqs


    def digest(self):
        return sum(map(lambda cell:cell.digest(), self))

    def solv_n(self, n):
        ret = False
        for chunk in itertools.chain(self.rows, self.cols, self.sqs):
            ret |= chunk.solv_n(n)
        return ret

    def _solv_chain(self, idx, num):
        dbg_print(f"_solv_chain {self[idx]}")
        self[idx] -= set([num])
        self.solv()

    def solv_chain(self):
        for i in ALL_SET:
            for chunk in itertools.chain(self.rows, self.cols, self.sqs):
                found_cells = list(filter(lambda cell: set({i}) <= cell, chunk))
                if len(found_cells) == 2:
                    for cell in found_cells:
                        #print("enter chain")
                        board_new = copy.deepcopy(self)
                        try:
                            board_new._solv_chain(int(cell), i)
                        except:
                            dbg_print("except")
                            cell &= set([i])
                            return
                        else:
                            if board_new.digest() == sum(range(1, SUDOKU_SIZE+1))*SUDOKU_SIZE:
                                dbg_print("dekite shimatta")
                                for dst in self:
                                    dst &= board_new[int(dst)]
                                return
                        finally:
                            pass
                            #print("leave chain")

    def print(self):
        for ri in range(SUDOKU_SIZE):
            for nr in range(1, SUDOKU_SIZE, SUBSQUARE_SIZE):
                for ci in range(SUDOKU_SIZE):
                    cell = self[ri * SUDOKU_SIZE + ci]
                    for n in range(nr, nr+SUBSQUARE_SIZE):
                        if n in cell:
                            print(n, end="")
                        else:
                            print(" ", end="")
                    if (ci+1) % SUBSQUARE_SIZE:
                        print(" ", end="")
                    else:
                        print("|", end="")
                print("\n", end="")
            if (ri+1) % SUBSQUARE_SIZE:
                print("\n", end="")
            else:
                print("--- --- --- --- --- --- --- --- ---")

    def print_text(self):
        for cell in self:
            if len(cell) != 1:
                print("0", end="")
            else:
                print(next(iter(cell)), end="")
        print("")

    def solv(self):
        digest = self.digest()
        while digest > sum(range(1, SUDOKU_SIZE+1))*SUDOKU_SIZE:
            for n in range(1,SUDOKU_SIZE):
                self.solv_n(n)
            new_digest = self.digest()
            if new_digest == digest:
                self.solv_chain()
                new_digest = self.digest()
                if new_digest == digest:
                    dbg_print(f"give up")
                    dbg_print(f"digest: {digest}")
                    return
            digest = new_digest
        assert digest == sum(range(1, SUDOKU_SIZE+1))*SUDOKU_SIZE

sudoku = """
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
"""

board = SudokuBoard(sudoku)
board.print()
board.solv()
print(f"digest: {board.digest()}")
board.print()
board.print_text()