【Python】回溯之解数独

解数独需要两个前置知识：

• 回溯算法原理
• 校验数独是否合法

回溯算法基础理论：

# 回溯算法
# - 都可以抽象为树形结构，最重要的就是剪枝
# - 一般来说回溯算法是没有返回值的。
# - 函数名叫：backtracking or backtrack

def backtracking():
  if 终止条件:
      收集结果
      return 
  for 集合元素：
      处理节点
      递归函数
      回溯操作
  return xxx

校验数独是否合法：

36. 有效的数独

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

解法1（暴力解法）

思路：

• 直接对行和列循环，进行遍历，如果当前位置不为空
  • 判断行内是否重复
  • 判断列内是否重复
  • 判断9方格里是否重复（(row // 3) * 3 计算从行开始）
• 全部结束后返回true

暴力循环行和列和九方格进行判断，时间较慢，空间占用少

from typing import List

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for x in range(9):
            for y in range(9):
                if board[x][y] != '.':
                    for i in range(9):  # 判断行里是否重复
                        if i == y: continue
                        if board[x][i] == board[x][y]:
                            return False
                    for j in range(9):  # 判断列里是否重复
                        if j == x: continue
                        if board[j][y] == board[x][y]:
                            return False
                    startRow = (x // 3) * 3
                    startcol = (y // 3) * 3
                    for i in range(startRow,startRow + 3):  # 判断9方格里是否重复
                        for j in range(startcol,startcol + 3):
                            if i == x and j == y: continue
                            if board[i][j] == board[x][y]:
                                return False
        return True

解法2（哈希法）

思路：

• 构建三个列表，里面都包含了9个字典，每个字典用于存储该行（列、九宫格）的数字
• 直接对行和列循环，进行遍历，如果当前位置不为空
  • 判断行内是否重复
  • 判断列内是否重复
  • 判断9方格里是否重复（(row // 3) * 3 计算从行开始）
• return True

采用构建字典的方式，避免了暴力循环，时间更快了，空间占用也不多

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [{} for _ in range(9)]
        col = [{} for _ in range(9)]
        nine = [{} for _ in range(9)]
        for i in range(9):
            for j in range(9):
                tmp = board[i][j]
                if tmp == ".":
                    continue
                if tmp in row[i]:
                    return False
                if tmp in col[j]:
                    return False
                if tmp in nine[(j // 3) * 3 + (i // 3)]:
                    return False
                row[i][tmp] = None
                col[j][tmp] = None
                nine[(j // 3) * 3 + (i // 3)][tmp] = None
        return True

好了，现在开始解决解数组的问题

37. 解数独

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

思路：

• 首先确定采用递归算法
• 确定回溯函数：
  • 递归返回值：False -> 需要进行回溯， True -> 不需要回溯，
  • 遍历每个数，将1~9逐个放入空位置，放入以后，校验当前数独表是否合法，如不合法，则进行回溯，撤销当前放入的数。
    • 每放置一个数，都需要进行递归，因为，根据递归结果来确定是否需要回溯
    • ！！！important -> 当九个数都放完了，但是都不合法，则回溯。
  • 所有的回溯函数都没有出错，说明九宫格填完了

**为什么不能传入row和col的参数，填完的行和列不再进入递归？

因为行、列数不是递增关系，遍历完一行（列）后又变为1**

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def backtracking(board):
            for i in range(9):  #遍历行
                for j in range(9):  #遍历列
                    if board[i][j] != ".":  continue
                    for k in range(1,10):  #(i, j) 这个位置放k是否合法
                        if isValid(i, j, k, board):
                            board[i][j] = str(k)  #放置k
                            if backtracking(board): return True  #如果找到合适一组立刻返回
                            board[i][j] = "."  #回溯，撤销k
                    return False  #9个数都试完了，都不行，那么就返回false
            return True  #遍历完没有返回false，说明找到了合适棋盘位置了
        
        def isValid(row, col, val, board):
            for i in range(9):  #判断行里是否重复
                if board[row][i] == str(val):
                    return False
            for j in range(9):  #判断列里是否重复
                if board[j][col] == str(val):
                    return False
            startRow = (row // 3) * 3
            startcol = (col // 3) * 3
            for i in range(startRow,startRow + 3):  #判断9方格里是否重复
                for j in range(startcol,startcol + 3):
                    if board[i][j] == str(val):
                        return False
            return True
        
        backtracking(board)