(Miracle) Sudoku Solver

MiracleBoard.py

from copy import deepcopy
from time import time
from typing import Dict, Optional, Set, Tuple


class Cell:
    def __init__(self):
        self.possibilities: Set[int] = set(range(1, 10))
        self._update()

    def remove(self, num: int):
        self.possibilities.discard(num)
        self._update()

    def set(self, num: int):
        self.possibilities = {num}
        self.possibilities_tuple = (num,)
        self.final = True

    def is_final(self) -> bool:
        return self.final

    def discard(self, num: int):
        self.possibilities.discard(num)
        self._update()

    def get_tuple(self) -> Tuple[int]:
        return tuple(self.possibilities)

    def get_first(self) -> int:
        return self.possibilities_tuple[0]

    def get_string(self) -> str:
        if self.is_final():
            return str(self.possibilities_tuple[0])
        return '.'

    def _update(self):
        self.possibilities_tuple = tuple(self.possibilities)
        self.final = len(self.possibilities_tuple) == 1


Cells = Dict[int, Cell]


class MiracleBoard:
    special_moves = {}
    orthogonal_moves = {}

    def __init__(self):
        self.board: Cells = {}
        for x in range(81):
            self.board[x] = Cell()

    def read_puzzle(self, s: str):
        if len(s) != 81:
            raise Exception('Input size must be 81')

        for i in range(81):
            if s[i] == '.':
                continue
            self.board[i].set(int(s[i]))

    def get_board_string(self) -> str:
        s = ''
        for x in range(81):
            s += str(self.board[x].get_string())
        return s

    def print(self):
        print('-' * 19)
        col_count = 0
        row_count = 0
        for x in range(81):
            if col_count == 0:
                print('|', end='')
            print(self.board[x].get_string(), end='')
            col_count = (col_count + 1) % 9

            if (col_count % 3) == 0:
                print('|', end='')
            else:
                print(' ', end='')

            if col_count == 0:
                print('')
                row_count += 1
                if (row_count % 3) == 0:
                    print('-' * 19)

    def debug(self):
        for x in range(81):
            print(x, self.board[x].possibilities)

    def get_row(self, row: int) -> Cells:
        start_index = row * 9
        return dict((x, self.board[x]) for x in range(start_index, start_index + 9))

    def get_column(self, column: int) -> Cells:
        return dict((x * 9 + column, self.board[x * 9 + column]) for x in range(9))

    def get_block(self, block: int) -> Cells:
        start_index = 27 * (block // 3) + (block % 3) * 3
        return dict((
            (start_index, self.board[start_index]),
            (start_index + 1, self.board[start_index + 1]),
            (start_index + 2, self.board[start_index + 2]),

            (start_index + 9, self.board[start_index + 9]),
            (start_index + 10, self.board[start_index + 10]),
            (start_index + 11, self.board[start_index + 11]),

            (start_index + 18, self.board[start_index + 18]),
            (start_index + 19, self.board[start_index + 19]),
            (start_index + 20, self.board[start_index + 20])
        ))

    def has_won(self) -> bool:
        return all(cell.is_final() for cell in self.board.values()) and self.is_board_valid()

    def is_board_valid(self) -> bool:
        return all(
            MiracleBoard.is_set_valid(self.get_row(i)) and
            MiracleBoard.is_set_valid(self.get_column(i)) and
            MiracleBoard.is_set_valid(self.get_block(i))
            for i in range(9)
        )

    def eliminate_set(self, i: int) -> bool:
        return any((
            MiracleBoard.eliminate_possibilities(self.get_row(i)),
            MiracleBoard.eliminate_possibilities(self.get_column(i)),
            MiracleBoard.eliminate_possibilities(self.get_block(i)),
            MiracleBoard.confirm_single_possibility(self.get_row(i)),
            MiracleBoard.confirm_single_possibility(self.get_column(i)),
            MiracleBoard.confirm_single_possibility(self.get_block(i))
        ))

    def eliminate(self) -> bool:
        return any(self.eliminate_set(i) for i in range(9)) or \
               any(self.eliminate_special_possibilities(i) for i in range(81) if self.board[i].is_final()) or \
               any(self.eliminate_adjacent_nums(i) for i in range(81) if self.board[i].is_final())

    def eliminate_all(self):
        while self.eliminate():
            continue

    def get_first_unresolved(self) -> Optional[Tuple[int, Cell]]:
        for i in range(81):
            if not self.board[i].is_final():
                return i, self.board[i]
        return None

    def bruteforce(self) -> bool:
        unresolved = self.get_first_unresolved()
        if unresolved is None:
            return True

        for value in unresolved[1].possibilities:
            ori = deepcopy(self.board)
            self.board[unresolved[0]].set(value)
            self.eliminate_all()
            self.bruteforce()
            if self.has_won():
                return True
            self.board = ori

        return False

    @staticmethod
    def is_set_valid(cells: Cells) -> bool:
        nums = tuple(cell.get_first() for cell in cells.values() if cell.is_final())
        return len(nums) == len(set(nums))

    @staticmethod
    def eliminate_possibilities(cells: Cells) -> bool:
        to_removes: Tuple[int] = tuple(c.get_first() for c in cells.values() if c.is_final())
        modified = False
        for to_remove in to_removes:
            for cell in cells.values():
                if not cell.is_final() and to_remove in cell.possibilities:
                    cell.discard(to_remove)
                    modified = True
        return modified

    @staticmethod
    def confirm_single_possibility(cells: Cells) -> bool:
        possibilities: Dict[int, int] = {}
        modified = False
        for cell in cells.values():
            for num in cell.possibilities:
                possibilities[num] = possibilities.get(num, 0) + 1

        for num, cells_with_num in possibilities.items():
            if cells_with_num != 1:
                continue
            for cell in cells.values():
                if num in cell.possibilities:
                    if not cell.is_final():
                        modified = True
                    cell.set(num)

        return modified

    def eliminate_special_possibilities(self, i: int) -> bool:
        modified = False
        num = self.board[i].get_first()
        for index in MiracleBoard.get_special_moves(i):
            if not self.board[index].is_final() and num in self.board[index].possibilities:
                self.board[index].discard(num)
                modified = True
        return modified

    def eliminate_adjacent_nums(self, i: int) -> bool:
        modified = False
        num = self.board[i].get_first()
        for index in MiracleBoard.get_orthogonal_moves(i):
            if num - 1 >= 1 and not self.board[index].is_final() and num - 1 in self.board[index].possibilities:
                self.board[index].discard(num - 1)
                modified = True
            if num + 1 <= 9 and not self.board[index].is_final() and num + 1 in self.board[index].possibilities:
                self.board[index].discard(num + 1)
                modified = True
        return modified

    @staticmethod
    def compare_boards(board1: Cells, board2: Cells) -> bool:
        if len(board1) != len(board2):
            return False

        for i in range(len(board1)):
            if board1[i].possibilities != board2[i].possibilities:
                return False

        return True

    @staticmethod
    def get_special_moves(i: int) -> Tuple[int]:
        if i in MiracleBoard.special_moves:
            return MiracleBoard.special_moves[i]

        x, y = MiracleBoard.to_xy(i)
        raw_moves = (
            # knight moves
            (x - 2, y - 1),
            (x - 2, y + 1),
            (x - 1, y - 2),
            (x + 1, y - 2),
            (x - 1, y + 2),
            (x + 1, y + 2),
            (x + 2, y - 1),
            (x + 2, y + 1),

            # king_moves
            (x - 1, y - 1),
            (x - 1, y + 1),
            (x + 1, y - 1),
            (x + 1, y + 1)
        )
        MiracleBoard.special_moves[i] = tuple(MiracleBoard.to_index(x, y) for x, y in raw_moves if 0 <= x <= 8 and
                                              0 <= y <= 8)
        return MiracleBoard.special_moves[i]

    @staticmethod
    def get_orthogonal_moves(i: int) -> Tuple[int]:
        if i in MiracleBoard.orthogonal_moves:
            return MiracleBoard.orthogonal_moves[i]

        x, y = MiracleBoard.to_xy(i)
        raw_moves = (
            (x, y + 1),
            (x, y - 1),
            (x + 1, y),
            (x - 1, y)
        )
        MiracleBoard.orthogonal_moves[i] = tuple(MiracleBoard.to_index(x, y) for x, y in raw_moves if 0 <= x <= 8 and
                                                 0 <= y <= 8)
        return MiracleBoard.orthogonal_moves[i]

    @staticmethod
    def to_xy(i: int) -> Tuple[int, int]:
        return i // 9, i % 9

    @staticmethod
    def to_index(x: int, y: int) -> int:
        return x * 9 + y


if __name__ == '__main__':
    b = MiracleBoard()
    puzzle = '......................................1............2.............................'
    b.read_puzzle(puzzle)
    b.eliminate_all()
    b.bruteforce()
    b.print()

SudokuBoard.py

from copy import deepcopy
from time import time
from typing import Dict, Optional, Set, Tuple


class Cell:
    def __init__(self):
        self.possibilities: Set[int] = set(range(1, 10))
        self._update()

    def remove(self, num: int):
        self.possibilities.discard(num)
        self._update()

    def set(self, num: int):
        self.possibilities = {num}
        self.possibilities_tuple = (num,)
        self.final = True

    def is_final(self) -> bool:
        return self.final

    def discard(self, num: int):
        self.possibilities.discard(num)
        self._update()

    def get_tuple(self) -> Tuple[int]:
        return tuple(self.possibilities)

    def get_first(self) -> int:
        return self.possibilities_tuple[0]

    def get_string(self) -> str:
        if self.is_final():
            return str(self.possibilities_tuple[0])
        return '.'

    def _update(self):
        self.possibilities_tuple = tuple(self.possibilities)
        self.final = len(self.possibilities_tuple) == 1


Cells = Dict[int, Cell]


class SudokuBoard:
    def __init__(self):
        self.board: Cells = {}
        for x in range(81):
            self.board[x] = Cell()

    def read_puzzle(self, s: str):
        if len(s) != 81:
            raise Exception('Input size must be 81')

        for i in range(81):
            if s[i] == '.':
                continue
            self.board[i].set(int(s[i]))

    def get_board_string(self) -> str:
        s = ''
        for x in range(81):
            s += str(self.board[x].get_string())
        return s

    def print(self):
        print('-' * 19)
        col_count = 0
        row_count = 0
        for x in range(81):
            if col_count == 0:
                print('|', end='')
            print(self.board[x].get_string(), end='')
            col_count = (col_count + 1) % 9

            if (col_count % 3) == 0:
                print('|', end='')
            else:
                print(' ', end='')

            if col_count == 0:
                print('')
                row_count += 1
                if (row_count % 3) == 0:
                    print('-' * 19)

    def debug(self):
        for x in range(81):
            print(x, self.board[x].possibilities)

    def get_row(self, row: int) -> Cells:
        start_index = row * 9
        return dict((x, self.board[x]) for x in range(start_index, start_index + 9))

    def get_column(self, column: int) -> Cells:
        return dict((x * 9 + column, self.board[x * 9 + column]) for x in range(9))

    def get_block(self, block: int) -> Cells:
        start_index = 27 * (block // 3) + (block % 3) * 3
        return dict((
            (start_index, self.board[start_index]),
            (start_index + 1, self.board[start_index + 1]),
            (start_index + 2, self.board[start_index + 2]),

            (start_index + 9, self.board[start_index + 9]),
            (start_index + 10, self.board[start_index + 10]),
            (start_index + 11, self.board[start_index + 11]),

            (start_index + 18, self.board[start_index + 18]),
            (start_index + 19, self.board[start_index + 19]),
            (start_index + 20, self.board[start_index + 20])
        ))

    def has_won(self) -> bool:
        return all(cell.is_final() for cell in self.board.values()) and self.is_board_valid()

    def is_board_valid(self) -> bool:
        return all(
            SudokuBoard.is_set_valid(self.get_row(i)) and
            SudokuBoard.is_set_valid(self.get_column(i)) and
            SudokuBoard.is_set_valid(self.get_block(i))
            for i in range(9)
        )

    def eliminate_set(self, i: int) -> bool:
        return any((
            SudokuBoard.eliminate_possibilities(self.get_row(i)),
            SudokuBoard.eliminate_possibilities(self.get_column(i)),
            SudokuBoard.eliminate_possibilities(self.get_block(i)),
            SudokuBoard.confirm_single_possibility(self.get_row(i)),
            SudokuBoard.confirm_single_possibility(self.get_column(i)),
            SudokuBoard.confirm_single_possibility(self.get_block(i))
        ))

    def eliminate(self) -> bool:
        return any(self.eliminate_set(i) for i in range(9))

    def eliminate_all(self):
        while self.eliminate():
            continue

    def get_first_unresolved(self) -> Optional[Tuple[int, Cell]]:
        for i in range(81):
            if not self.board[i].is_final():
                return i, self.board[i]
        return None

    def bruteforce(self) -> bool:
        unresolved = self.get_first_unresolved()
        if unresolved is None:
            return True

        for value in unresolved[1].possibilities:
            ori = deepcopy(self.board)
            self.board[unresolved[0]].set(value)
            self.eliminate_all()
            self.bruteforce()
            if self.has_won():
                return True
            self.board = ori

        return False

    @staticmethod
    def is_set_valid(cells: Cells) -> bool:
        nums = tuple(cell.get_first() for cell in cells.values() if cell.is_final())
        return len(nums) == len(set(nums))

    @staticmethod
    def eliminate_possibilities(cells: Cells) -> bool:
        to_removes: Tuple[int] = tuple(c.get_first() for c in cells.values() if c.is_final())
        modified = False
        for to_remove in to_removes:
            for cell in cells.values():
                if not cell.is_final() and to_remove in cell.possibilities:
                    cell.discard(to_remove)
                    modified = True
        return modified

    @staticmethod
    def confirm_single_possibility(cells: Cells) -> bool:
        possibilities: Dict[int, int] = {}
        modified = False
        for cell in cells.values():
            for num in cell.possibilities:
                possibilities[num] = possibilities.get(num, 0) + 1

        for num, cells_with_num in possibilities.items():
            if cells_with_num != 1:
                continue
            for cell in cells.values():
                if num in cell.possibilities:
                    if not cell.is_final():
                        modified = True
                    cell.set(num)

        return modified

    @staticmethod
    def compare_boards(board1: Cells, board2: Cells) -> bool:
        if len(board1) != len(board2):
            return False

        for i in range(len(board1)):
            if board1[i].possibilities != board2[i].possibilities:
                return False

        return True


if __name__ == '__main__':
    b = SudokuBoard()
    puzzle = '.....6....59.....82....8....45........3........6..3.54...325..6..................'
    puzzle = '8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..'
    print(puzzle)
    b.read_puzzle(puzzle)
    start = time()
    b.eliminate_all()
    b.bruteforce()
    print(time() - start)
    b.print()