Skip to content

Latest commit

 

History

History
161 lines (120 loc) · 5.04 KB

37.sudoku_solver.md

File metadata and controls

161 lines (120 loc) · 5.04 KB
Raw
  1. Sudoku Solver

困难

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

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  • Each of the digits 1-9 must occur exactly once in each row.
  • Each of the digits 1-9 must occur exactly once in each column.
  • Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
  • The '.' character indicates empty cells.

Example 1:

Input: board = [["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"]]

Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

Explanation: The input board is shown above and the only valid solution is shown below:

Constraints:

board.length == 9
board[i].length == 9
board[i][j] is a digit or '.'.
It is guaranteed that the input board has only one solution.

相关企业

  • 微软 Microsoft|9
  • 亚马逊 Amazon|9
  • 苹果 Apple|6
  • 谷歌 Google|5
  • 优步 Uber|3
  • Facebook|2

相关标签

  • Array
  • Backtracking
  • Matrix

相似题目

  • Valid Sudoku 中等
  • Unique Paths III 困难

idea

对于这道题目来说，我们要明确几点

  • 目标(base case) ：填满每个格子。
  • 选择列表(choice list)：每个空的格子可以填入1-9这九个数字。
  • 约束条件(constrain)：1-9在每一行、每一列和每个3x3的大格中都只能出现一次。
  • 选择路径(path)：由于我们是inplace操作，board就存储了已经做过的选择。

我们在这里设置backtrack函数的返回类型为bool，这样一来，当程序找到可行解后就能终止递归。

复杂度分析

时间复杂度：

时间复杂度是常数。由于数独的大小是固定的，因此没有 N 变量来衡量。上限是(9!)^9 。

对第一行来说，第一个格子不会超过9种情况，

第二个格子不会超过8种...

所以第一行不会超过9!个情况。

那么所有行不会超过(9!)^2

空间复杂度：

数独大小固定，空间用来存储数独，行，列和子方块的结构，每个有 81 个元素。

Write this skeleton firstly then add detials

def dfs(self, board, rowi, colj):
        if self.isCompletedSudoku(board):
            return True
            
        for add_number in range(1, 10):
            if not self.isValidNewStep(board, str(add_number), rowi, colj):
                continue
            board[rowi][colj] = str(add_number)
            if self.dfs(board, rowi, colj+1):
                return True
            board[rowi][colj] = "."
        return False

下面是完整版：

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.dfs(board, 0, 0)

    def dfs(self, board, rowi, colj):
        if self.isCompletedSudoku(board):
            return True
        if colj == 9:
            rowi += 1
            colj = 0
        if rowi == 9:
            return True

        if board[rowi][colj] != ".":
            return self.dfs(board, rowi, colj+1)
        for add_number in range(1, 10):
            if not self.isValidNewStep(board, str(add_number), rowi, colj):
                continue
            board[rowi][colj] = str(add_number)
            if self.dfs(board, rowi, colj+1):
                return True
            board[rowi][colj] = "."
        return False
        
    def isCompletedSudoku(self, board):
        for rowi in range(9):
            for colj in range(9):
                if board[rowi][colj] == ".":
                    return False
        return True

    def isValidNewStep(self, board, new_number, rowi, colj):
        for i in range(9): 
            # check all cells in same row
            if board[rowi][i] == new_number:
                return False
            # check all cells in same col
            if board[i][colj] == new_number:
                return False
        # check all cells in same 9-cells-small-sudoku
        nineCellSudoku_rowi = rowi // 3
        nineCellSudoku_colj = colj // 3
        for i in range(3):
            for j in range(3):
                if board[nineCellSudoku_rowi * 3 + i][nineCellSudoku_colj * 3 + j] == new_number:
                    return False
        return True