0037._Sudoku_Solver.md

37. Sudoku Solver

难度: Hard

刷题内容

原题连接

• https://leetcode.com/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 the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.


A sudoku puzzle...


...and its solution numbers marked in red.

Note:

The given board contain only digits 1-9 and the character '.'.
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9x9.

解题方案

思路 1 - 时间复杂度: O(9 ^ count('.'))- 空间复杂度: O(1)******

经典backtrack

对于每一个为'.'的点都从1试到9，如果valid就继续往下走，不valid立马backtrack

class Solution:
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        self.backtrack(board)
        
    def backtrack(self, board):
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for c in '123456789':
                        if self.isPointValid(board, i, j, c):
                            board[i][j] = c
                            if self.backtrack(board): 
                                return True
                            else:
                                board[i][j] = '.' # backtrack
                    return False
        return True
    
    def isPointValid(self, board, x, y, c):
        for i in range(9):
            if board[i][y] == c: # check col
                return False
            if board[x][i] == c: # check row
                return False
            if board[3*(x//3)+i//3][3*(y//3)+i%3] == c: # check 3 * 3 block
                return False
        return True