Leetcode37. 解独数

一、题目描述：

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

• 数字 1-9 在每一行只能出现一次。
• 数字 1-9 在每一列只能出现一次。
• 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

1. 示例 1：
   • 输入：

     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"]]
     

   • 输出：

     [["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"]]
     

   • 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

• 提示：
  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字（1-9）或者 ‘.’
  • 题目数据 保证 输入数独仅有一个解

二、解决思路和代码

1. 解决思路

• 分析：借助Leetcode36题中，解独数的思路和递归方法来解这道题
  • step1: 在初始状态下，统计 每一行、每一列、每个 3x3 宫内 已经出现的数字。
    • 例如，实例1中：
      • row[0] = [5, 3, 7], row[0]表示第0行中已有的数字
      • col[0] = [5, 6, 8, 4, 7], col[0]表示第0列中已有的数字
      • x33[0] = [5, 3, 6, 9, 8], x33[0]表示第0个 3x3 宫中已有的数字
      • …
  • step2: 开始解独数。
    • (1) 确定board中，所有元素为’.‘的候选数字。循环遍历board，当第i行，第j列 board[i][j]=’.'时，根据 row[i],col[j],x33[i//3*3+j//3] 统计的已出现的数字，确定候选数字。
      • 例如，实例1中，第0行，第2列
        • row[0] = [5, 3, 7]
        • col[2] = [8]
        • x33[0//3*3+2//3] = x33[0] = [5, 3, 6, 9, 8]
      • 那么 board[0][2] 的候选数字有：[1, 2, 4]。统计board中所有元素为 ‘.’ 的候选数字，使用temp记录，temp = {(0,2):[1, 2, 4], …}
    • (2) 确定 temp 中每个 key=(i,j) 位置的元素。这里使用递归的思路：递归跳出的条件是 len(temp)=0
      • 例如，实例1中，第0行，第2列
        • 当$board[0][2]=1$，那我们就回到了step1，继续 确定候选数字，解独数
          • 如果 len(temp)=0，那么$board[0][2]=1$的解是正确的
          • 如果 len(temp)>0，那么$board[0][2]=1$的解是错误的。令$board[0][2]=2$，继续循环，直到遍历完[1, 2, 4]所有的数字。一定会找到解，因为题目数据保证输入数独仅有一个解

2. 代码

from typing import *
class Solution:def getUnused(self, board):row = {0:[],1:[],2:[],3:[],4:[],5:[],6:[],7:[],8:[]}col = {0:[],1:[],2:[],3:[],4:[],5:[],6:[],7:[],8:[]}x33 = {0:[],1:[],2:[],3:[],4:[],5:[],6:[],7:[],8:[]}for i in range(len(board)):for j in range(len(board[0])):if board[i][j]=='.': continuerow[i].append(board[i][j])col[j].append(board[i][j])x33[i//3*3+j//3].append(board[i][j])all = {'1','2','3','4','5','6','7','8','9'}temp = {}for i in range(len(board)):for j in range(len(board[0])):if board[i][j]=='.':   temp[(i,j)] = all-set(row[i]+col[j]+x33[i//3*3+j//3])# tempSort = dict(sorted(temp.items(), key=lambda k: len(k[1])) )return tempSortdef backtracking(self, board, temp):for key,vals in temp.items():i, j = keyfor val in list(vals):board[i][j] = valtemp = self.getUnused(board)if self.backtracking(board, temp): return Trueboard[i][j] = '.'return Falsereturn Truedef solveSudoku(self, board: List[List[str]]) -> None:tempSort = self.getUnused(board)        self.backtracking(board, tempSort)return