Problem statement

https://leetcode.com/problems/sudoku-solver/

Solution

The idea here is to use dfs(board, empty, rows, cols, boxes) function, where:

  1. board is current board we have.
  2. empty is list of empty cells.
  3. rows is defaultict, where for each of 9 rows we have set of values we have in this row, similar logic for cols and boxes.

What we do in our dfs backtracking algorithm is to choose any empty cell, and then try to put some number in this cell from the numbers we did not have on the same row, column or box, and run dfs with new arguments:

  1. We look at row[r], cols[c] and boxes[3*(r//3)+c//3], and remove this elements from set("123456789")
  2. Make board[r][c] = k.
  3. Add k to corresponding row, column and box.
  4. Run dfs recursively and if we found solution, return True.
  5. Delete k from corresponding row, column and box.

Complexity

Time complexity of one dfs step is O(1), because we actually need to check row, column and box. However it is difficult to estimate overall complexity of algorithm - I think it is exponential at least. Space complexity is O(1).

Code

class Solution:    
    def solveSudoku(self, board):
        def dfs(board, empty, rows, cols, boxes):
            if not empty: return True
            r, c = empty[-1]
            for k in set("123456789") - (rows[r]|cols[c]|boxes[3*(r//3)+c//3]):
                board[r][c] = k
                for dic in [rows[r], cols[c], boxes[3*(r//3)+c//3]]:
                    dic.add(k)
                if dfs(board, empty[:-1], rows, cols, boxes): return True
                board[r][c] = '.'
                for dic in [rows[r], cols[c], boxes[3*(r//3)+c//3]]:
                    dic.remove(k)

            return False
        
        cols, rows, boxes, empty = defaultdict(set), defaultdict(set), defaultdict(set), []
        for r, c in product(range(9), range(9)):
            if board[r][c] == ".":
                empty.append((r,c))
            else:
                for dic in [rows[r], cols[c], boxes[3*(r//3)+c//3]]:
                    dic.add(board[r][c])
               
        dfs(board, empty, rows, cols, boxes)