使用「消去法」解數獨 - 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 SparseMatrix:
    '''
    The sparse matrix is constructed by the horizontal and vertical 
    doubly linked lists. 

    Where the linked list is used to visit or iterate a row or a 
    column. For example, if a value on the (r, c) place of the 
    Sudoku board is decided, we need to eliminate the same values 
    from the possible digit sets on the r-th row or the c-th column.
    
    In order to locate the cell quickly, cell_dict is supported to 
    get the target cell. And the "doubly" linked list is used to 
    support the quick deletion in O(1).
    '''
    
    class Cell:
        '''
        The cell is an element of the sparse matrix.
        '''
        def __init__(self, row, col, value = None):
            '''
            The value is located at (row, col), and the base index is 0.
            '''
            self.row = row
            self.col = col
            self.value = value
            
            self.left = None
            self.right = None
            self.up = None
            self.down = None
        # end-of-def
        
        def __repr__(self):
            return '[{}][{}]={}'.format(self.row, self.col, self.value)
        # end-of-def
    # end-of-def
    
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        
        self.cell_dict = dict()
        self.row_heads = [None] * rows
        self.col_heads = [None] * cols
    # end-of-def
    
    def get_cell(self, row, col) -> Cell:
        return self.cell_dict.get((row, col))
    # end-of-def
    
    def set_cell(self, row, col, value) -> Cell:
        cell = SparseMatrix.Cell(row, col, value)
        
        # registers to the cell_dict
        key = (row, col)
        self.cell_dict[key] = cell
        
        # registers to the horizontal linked list
        head = self.row_heads[row]
        if not head:
            # be the head
            self.row_heads[row] = cell
        else:
            if col < head.col:
                # before the head
                cell.right = head
                head.left = cell
                self.row_heads[row] = head
            else:
                # behind the head
                ptr = head.right
                pre = head
                while ptr != None:
                    if ptr.col < cell.col:
                        pre = ptr
                        ptr = ptr.right
                    else:
                        break
                    # end-of-if
                # end-of-while
                
                if not ptr:
                    # pre < cell (tail)
                    pre.right = cell
                    cell.left = pre
                else:
                    # pre < cell < ptr
                    pre.right = cell
                    cell.left = pre
                    cell.right = ptr
                    ptr.left = cell
                # end-of-if
            # end-of-if
        # end-of-if
        
        # registers to the vertical linked list
        head = self.col_heads[col]
        if not head:
            # be the head
            self.col_heads[col] = cell
        else:
            if row < head.row:
                # before the head
                cell.down = head
                head.up = cell
                self.col_heads[col] = head
            else:
                ptr = head.down
                pre = head
                while ptr != None:
                    if ptr.row < cell.row:
                        pre = ptr
                        ptr = ptr.down
                    else:
                        break
                    # end-of-if
                # end-of-while
                
                if not ptr:
                    # pre < cell (tail)
                    pre.down = cell
                    cell.up = pre
                else:
                    # pre < cell < ptr
                    pre.down = cell
                    cell.up = pre
                    cell.down = ptr
                    ptr.up = cell
                # end-of-if
            # end-of-if
        # end-of-if
        return cell
    # end-of-def
    
    def delete_cell(self, row, col):
        key = (row, col)
        cell = self.cell_dict.get(key)
        
        # deletes the cell from the horizontal linked list
        if cell.left == None:
            # the cell is the head
            self.row_heads[row] = cell.right
        else:
            # the cell is behine the head
            cell.left.right = cell.right
        # end-of-if
        
        if cell.right != None:
            cell.right.left = cell.left
        # end-of-if
        
        # deletes the cell from the vertical linked list
        if cell.up == None:
            # the cell is the head
            self.col_heads[col] = cell.down
        else:
            # the cell is behine the head
            cell.up.down = cell.down
        # end-of-if
        
        if cell.down != None:
            cell.down.up = cell.up
        # end-of-if
        
        # deletes the cell from the celll_dict
        del self.cell_dict[key]
        del cell
    # end-of-if
    
    def move_next_from(self, row = 0, col = 0) -> Cell:
        key = (row, col)
        cell = self.cell_dict.get(key)
        
        # for the first cell and the last one
        if cell == None:
            if row == 0 and col == 0:
                for r in range(0, self.rows):
                    if self.row_heads[r] != None:
                        return self.row_heads[r]
                    # end-of-if
                # end-of-for
            # end-of-if
            return None # cannot find the next cell
        # end-of-if
        
        # finds the next cell from the current row
        if cell.right != None:
            return cell.right
        # end-of-if
        
        # finds the next cell from the next row
        for r in range(row + 1, self.rows):
            if self.row_heads[r] != None:
                return self.row_heads[r]
            # end-of-if
        # end-of-for
        
        return None # cannot find the next cell
    # end-of-if
    
    def get_row_cell_list(self, row):
        cell_list = list()
        ptr = self.row_heads[row]
        
        while ptr != None:
            cell_list.append(ptr)
            ptr = ptr.right
        # end-of-while
        return cell_list
    # end-of-def
    
    def get_col_cell_list(self, col):
        cell_list = list()
        ptr = self.col_heads[col]
        
        while ptr != None:
            cell_list.append(ptr)
            ptr = ptr.down
        # end-of-while
        return cell_list
    # end-of-def
    
    def get_block_cell_list(self, row, col):
        cell_list = list()
        block_row = (row // 3) * 3
        block_col = (col // 3) * 3
        next_block_row = block_row + 3
        next_block_col = block_col + 3
        
        for r in range(block_row, next_block_row):
            for c in range(block_col, next_block_col):
                
                # gets the 1st cell from the block
                cell = self.cell_dict.get((r, c))
                if not cell:
                    continue
                else:
                    cell_list.append(cell)
                # end-of-if
                
                # moves to the next cell (on the same row)
                if cell.right != None: 
                    cell = cell.right
                else:
                    break
                # end-of-if
                
                # gets the 2nd cell
                if cell.col < next_block_col: 
                    cell_list.append(cell)
                else:
                    break
                # end-of-if
                
                # moves to the next cell (on the same row)
                if cell.right != None: 
                    cell = cell.right
                else:
                    break
                # end-of-if
                
                # gets the 3rd cell
                if cell.col < next_block_col: 
                    cell_list.append(cell)
                else:
                    break
                # end-of-if
            # end-of-for 
        # end-of-for
        return cell_list
    # end-of-if
    
    def get_cell_list_by_row(self):
        cell_list = list()
        
        for row in range(self.rows):
            ptr = self.row_heads[row]
            while ptr != None:
                cell_list.append(ptr)
                ptr = ptr.right
            # end-of-while
        # end-of-for
        return cell_list
    # end-of-def
    
    def get_cell_list_by_col(self):
        cell_list = list()
        
        for col in range(self.cols):
            ptr = self.col_heads[col]
            while ptr != None:
                cell_list.append(ptr)
                ptr = ptr.down
            # end-of-while
        # end-of-for
        return cell_list
    # end-of-def
        
    def __repr__(self):
        s = ''
        for cell in self.get_cell_list_by_row():
            s += str(cell) + '\n'
        # end-of-for
        return s
    # end-of-if
    
    def debug_rows(self):
        print('\n--- debug_rows ---')
        for row in range(self.rows):
            ptr = self.row_heads[row]
            print(' - row_heads[{}]:'.format(row))
            while ptr != None:
                print('   {} <- ({}) -> {}'.format(
                    ptr.left, ptr, ptr.right))
                ptr = ptr.right
            # end-of-while
            print()
        # end-of-for
    # end-of-def
    
    def debug_cols(self):
        print('\n--- debug_cols ---')
        for col in range(self.cols):
            ptr = self.col_heads[col]
            print(' - col_heads[{}]:'.format(col))
            while ptr != None:
                print('   {} <- ({}) -> {}'.format(
                    ptr.up, ptr, ptr.down))
                ptr = ptr.down
            # end-of-while
            print()
        # end-of-for
    # end-of-def
# end-of-class



class Eliminator(SudokuSolver):
    '''
    Implements the elimination method for Sudoku.
    '''
    def __init__(self, board):
        super(Eliminator, self).__init__(board)
        
        empty_cell_list = self.init_states_and_get_empty_cell_list(board)
        
        # used to list possible ditigts for empty cells
        self.empty_cell_table = SparseMatrix(9, 9)
        
        for row, col, digit_set in empty_cell_list:
            self.empty_cell_table.set_cell(row, col, digit_set)
        # end-of-for
    # end-of-def
    
    def run(self):
        count = 1
        while count > 0:
            count = self.eliminate_impossible_digits()
            #print('After deleting impossible digits:', count)
            #print(e)
        # end-of-while
    # end-of-def
    
    def eliminate_impossible_digits(self) -> int:
        '''
        If a cell has only one possible, then just fill-in it.
        
        Output:
            - the number of cells which have only one possible
        '''
        row = col = 0
        cell = self.empty_cell_table.move_next_from(row, col)
        deleted_cell_list = list()
        
        while cell != None:
            digit_set = cell.value
            row = cell.row
            col = cell.col
            
            # prints the current cell
            # print('({}, {}) = {}'.format(row, col, digit_set))
            
            # moves to the next cell before deleting the cell
            cell = self.empty_cell_table.move_next_from(row, col)
            
            if len(digit_set) == 1:
                # prints the deletion info of the current cell
                # print('delete [{}][{}] = {}'.format(row, col, digit_set))
                
                digit = digit_set.pop()
                deleted_cell_list.append((row, col, digit))
                
                if self.set_cell(row, col, digit) == False:
                    return -1
                # end-of-if
                self.empty_cell_table.delete_cell(row, col)
            # end-of-if
        # end-of-while
        
        # removes other impossible digits
        for row, col, digit in deleted_cell_list:
            
            row_cell_list = self.empty_cell_table.get_row_cell_list(row)
            for cell in row_cell_list:
                digit_set = cell.value
                if digit in digit_set:
                    digit_set.remove(digit)
                # end-of-if
            # end-of-for
            
            col_cell_list = self.empty_cell_table.get_col_cell_list(col)
            for cell in col_cell_list:
                digit_set = cell.value
                if digit in digit_set:
                    digit_set.remove(digit)
                # end-of-if
            # end-of-for
            
            block_cell_list = self.empty_cell_table.get_block_cell_list(row, col)
            for cell in block_cell_list:
                digit_set = cell.value
                if digit in digit_set:
                    digit_set.remove(digit)
                # end-of-if
            # end-of-for
        # end-of-for
        
        return len(deleted_cell_list)
    # end-of-def
    
    def fill_in_once_digit_if_possible(self) -> int:
        # for example
        #  [1][1]={8, 1, 3, 4, 5}
        #  [1][2]={1, 3, 5}
        #  [1][4]={3, 5}
        #  [1][6]={8, 1, 4}
        #  [1][7]={8, 1, 3, 5}
        #  [1][8]={3, 4, 5, 9}
        # We can make sure that board[1][8] must be 9
        
        def fill_digits(cell_list):
            digit2cell_dict = dict()
            
            # visits each digit in the cell list
            for cell in cell_list:
                for digit in cell.value:
                    exist_cell = digit2cell_dict.get(digit)
                    if not exist_cell:
                        digit2cell_dict[digit] = cell
                    else:
                        # more than once -> impossible
                        digit2cell_dict[digit] = -1
                    # end-of-if
                # end-of-if
            # end-of-for
            
            for digit, cell in digit2cell_dict.items():
                if cell != -1:
                    print('>> [{}][{}]={}'.format(cell.row, cell.col, digit))
                    self.set_cell(cell.row, cell.col, digit)
                    cell.value.remove(digit)
                # end-of-if
            # end-of-for
        # end-of-def
        
        mat = self.empty_cell_table
        for idx in range(9):
            # for each row and column
            fill_digits(mat.get_row_cell_list(idx))
            fill_digits(mat.get_col_cell_list(idx))
            
            # the left-top cell of the idx-th block
            cell_offset_idx = idx * 3
            cell_row = (cell_offset_idx // 9) * 3
            cell_col = cell_offset_idx % 9
            fill_digits(mat.get_block_cell_list(cell_row, cell_col))
        # end-of-for
    # 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 = Eliminator(board)
    print(e)
    e.run()
    print(e)
# end-of-def

main()