Easy to understand - Text Book solution - Algorithm Design Manual :-)


  • 0
    S

    Nothing fancy - no bitsets, no claim of 0ms etc. But sticking to the basics of backtracking and other tricks given in Algorithm Design Manual. The code is my own implemented in python but complies Skiena's backtracking template -

    class Solution(object):
        def solveSudoku(self, board):
            """
            :type board: List[List[str]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
    
            def possible_values(board, m, n, row, col):
                # get possible value for given cell
                candidates = {str(x) for x in range(1, 10)}
                for j in range(n):
                    if board[row][j] in candidates:
                        candidates.remove(board[row][j])
    
                for i in range(m):
                    if board[i][col] in candidates:
                        candidates.remove(board[i][col])
    
                top, left = (m // 3 * (row // 3), n // 3 * (col // 3))
                for i in range(top, top + 3):
                    for j in range(left, left + 3):
                        if board[i][j] in candidates:
                            candidates.remove(board[i][j])
                return candidates
    
            def get_most_constrained(board, m, n):
                most_constrained_possible = {}
                maxlen = float('inf')
                most_constrained = (None, None)
                for i in range(m):
                    for j in range(n):
                        if board[i][j] == '.':
                            ijpossible = possible_values(board, m, n, i, j)
                            if len(ijpossible) < maxlen:
                                maxlen = len(ijpossible)
                                most_constrained_possible = ijpossible
                                most_constrained = (i, j)
                # if maxlen is zero solution is not possible
                return most_constrained, most_constrained_possible
    
            def make_move(board, i, j, value):
                board[i][j] = value
    
            def unmake_move(board, i, j):
                board[i][j] = '.'
    
            if board:
                self.finished = False
                xboard = list(map(list, board))
                m = len(xboard)    # expected 9
                n = len(xboard[0]) # expected 9
                open_cells = len([(i, j) for i in range(m) for j in range(n) if board[i][j] == '.'])
    
                def is_solution(open_cells):
                    return open_cells == 0
    
                def process_solution():
                    self.finished = True
    
                def construct_candidates(xboard, m, n):
                    return get_most_constrained(xboard, m, n)
    
                def backtrack(xboard, m, n, open_cells):
                    if is_solution(open_cells):
                        process_solution()
                    else:
                        (x, y), candidates = construct_candidates(xboard, m, n)
                        open_cells -= 1
                        for candidate in candidates:
                            make_move(xboard, x, y, candidate)
                            backtrack(xboard, m, n, open_cells)
                            if self.finished == True:
                                break
                            unmake_move(xboard, x, y)
                        open_cells += 1
    
                backtrack(xboard, m, n, open_cells)
                for i,row in enumerate(xboard):
                    board[i] = ''.join(row)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.