使用「暴力法」解數獨 - tsungjung411/python-study GitHub Wiki

class SudokuSolver:
    '''
    Implements common methods.
    '''
    
    def __init__(self, board):
        self.int_board = [[0] * 9 for _ in range(9)]
        
        # -----------------------------------------------
        # for the tables below, 
        # we ignores the digit 0 of the digit list [0~9]
        # -----------------------------------------------
        # horizontal states: [row_index][1~9]
        self.row_states = [[False] * 10 for _ in range(9)]

        # vertical states: [col_index][1~9]
        self.col_states = [[False] * 10 for _ in range(9)]

        # block states: [block_row_index][block_col_index][1~9]
        self.block_states = [
            [
                [False] * 10 for _ in range(3) # for cols
            ] for _ in range(3) # for rows
        ]
    # end-of-def
    
    def init_states_and_get_empty_cell_list(self, board):
        empty_cell_list = list()
        
        # (1) collects the empty cells
        # (2) marks the states of the non-empty cells as occupied
        for row in range(9):
            for col in range(9):
                if board[row][col] == '.':
                    digit_set = set()
                    cell = (row, col, digit_set)
                    empty_cell_list.append(cell)
                else:
                    digit = int(board[row][col])
                    self.set_cell(row, col, digit)
                # end-of-if
            # end-of-for
        # end-of-for
        
        for row, col, digit_set in empty_cell_list:
            for digit in range(1, 10):
                if self.is_accepted(row, col, digit):
                    digit_set.add(digit)
                # end-of-if
            # end-of-for
            
            # shows possible digits for empty celss
            #print('[{}][{}]={}'.format(row, col, digit_set))
        # end-of-for
        
        return empty_cell_list
    # end-of-def
    
    def is_accepted(self, row, col, digit):
        '''
        Indicates where the digit on the board (row, col) is accepted.
        '''
        if self.row_states[row][digit]:
            return False
        elif self.col_states[col][digit]:
            return False
        else:
            block_row = row // 3
            block_col = col // 3
            if self.block_states[block_row][block_col][digit]:
                return False
            # end-of-if
        # end-of-if
        return True
    # end-of-def
    
    def set_cell(self, row, col, digit):
        self.int_board[row][col] = digit
        self.row_states[row][digit] = True
        self.col_states[col][digit] = True
        self.block_states[row//3][col//3][digit] = True
    # end-of-def
    
    def unset_cell(self, row, col, digit):
        self.int_board[row][col] = 0
        self.row_states[row][digit] = False
        self.col_states[col][digit] = False
        self.block_states[row//3][col//3][digit] = False
    # end-of-def
    
    def __repr__(self):
        s = '-' * 13 + '\n'
        for r in range(9):
            s += '|'
            for c in range(9):
                digit = self.int_board[r][c]
                s += str(digit) if digit != 0 else ' '
                if c == 2 or c == 5 or c == 8:
                    s += '|'
                # end-of-if
            # end-of-for
            s += '\n'
            
            if r == 2 or r == 5 or r == 8:
                s += '-' * 13 + '\n'
            # end-of-if
        # end-of-for
        return s
    # end-of-def
# end-of-class



class BruteForce(SudokuSolver):
    '''
    Implements the brute-force method for Sudoku.
    '''
    def __init__(self, board):
        super(BruteForce, self).__init__(board)
        
        self.empty_cell_list = self.init_states_and_get_empty_cell_list(board)
        self.empty_cell_list.sort(
            key = lambda cell : len(cell[2]) * 100 + cell[0] * 10 + cell[1])
    # end-of-def
    
    def run(self):
        self.found = False
        self._traversal(0)
    # end-of-def
    
    def _traversal(self, idx):
        if idx == len(self.empty_cell_list):
            self.found = True
            return True
        # end-of-if
        
        #print(self)
        row, col, digit_set = self.empty_cell_list[idx]
       
        for digit in digit_set:
            if self.is_accepted(row, col, digit):
                self.set_cell(row, col, digit)
                
                # fills-in the next digit
                self._traversal(idx + 1)
                if not self.found:
                    self.unset_cell(row, col, digit)
                # end-of-if
            # end-of-if
        # end-of-for
        return False
    # end-of-def
# end-of-class



def main():
    board1 = [
        ["5","3",".",".","7",".",".",".","."],
        ["6",".",".","1","9","5",".",".","."],
        [".","9","8",".",".",".",".","6","."],
        ["8",".",".",".","6",".",".",".","3"],
        ["4",".",".","8",".","3",".",".","1"],
        ["7",".",".",".","2",".",".",".","6"],
        [".","6",".",".",".",".","2","8","."],
        [".",".",".","4","1","9",".",".","5"],
        [".",".",".",".","8",".",".","7","9"]]

    board2 = [
        [".",".","9","7","4","8",".",".","."],
        ["7",".",".",".",".",".",".",".","."],
        [".","2",".","1",".","9",".",".","."],
        [".",".","7",".",".",".","2","4","."],
        [".","6","4",".","1",".","5","9","."],
        [".","9","8",".",".",".","3",".","."],
        [".",".",".","8",".","3",".","2","."],
        [".",".",".",".",".",".",".",".","6"],
        [".",".",".","2","7","5","9",".","."]]
    
    board = board1
    e = BruteForce(board)
    print(e)
    e.run()
    print(e)
# end-of-def

main()