目录

一、题目内容

二、解题思路

三、代码

一、题目内容

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

二、解题思路

DFS+回溯

row存储每行使用的数字

col存储每列使用的数字

block存储每个小方块使用的数字

三、代码

  

   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def solveSudoku(self, board: list) -> None:
     
    
   

    

     

    
    

     
 """
     
    
   

    

     

    
    

     

       Do not return anything, modify board in-place instead.
     
    
   

    

     

    
    

     

       """
     
    
   

    

     

    
    

     

       row = [[0 for _ in range(9)] for _ in range(9)]
     
    
   

    

     

    
    

     

       col = [[0 for _ in range(9)] for _ in range(9)]
     
    
   

    

     

    
    

     

       block = [[0 for _ in range(9)] for _ in range(9)]
     
    
   

    

     

    
    

     
 # print(row)
     
    
   

    

     

    
    

     
 # print(col)
     
    
   

    

     

    
    

     
 # print(block)
     
    
   

    

     

    
    

     
 for i in range(9):
     
    
   

    

     

    
    

     
 for j in range(9):
     
    
   

    

     

    
    

     
 if board[i][j] != '.':
     
    
   

    

     

    
    

     

       num = ord(board[i][j]) - ord('1')
     
    
   

    

     

    
    

     

       row[i][num] = True
     
    
   

    

     

    
    

     

       col[j][num] = True
     
    
   

    

     

    
    

     

       block[i // 3 * 3 + j // 3][num] = True
     
    
   

    

     

    
    

     
 def print_board():
     
    
   

    

     

    
    

     
 for i in range(9):
     
    
   

    

     

    
    

     

       print(board[i])
     
    
   

    

     

    
    

     

       print('\n')
     
    
   

    

     

    
    

     
 def dfs(i, j):
     
    
   

    

     

    
    

     
 while board[i][j] != '.':
     
    
   

    

     

    
    

     

       j += 1
     
    
   

    

     

    
    

     
 if j > 8:
     
    
   

    

     

    
    

     

       j = 0
     
    
   

    

     

    
    

     

       i += 1
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 if i > 8:
     
    
   

    

     

    
    

     
 return True
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 for num in range(9):
     
    
   

    

     

    
    

     

       blockindex = i // 3 * 3 + j // 3
     
    
   

    

     

    
    

     
 if not row[i][num] and not col[j][num] and not block[blockindex][num]:
     
    
   

    

     

    
    

     

       board[i][j] = str(1 + num)
     
    
   

    

     

    
    

     

       row[i][num] = True
     
    
   

    

     

    
    

     

       col[j][num] = True
     
    
   

    

     

    
    

     

       block[blockindex][num] = True
     
    
   

    

     

    
    

     
 # print_board()
     
    
   

    

     

    
    

     
 if dfs(i, j):
     
    
   

    

     

    
    

     
 return True
     
    
   

    

     

    
    

     
 else:
     
    
   

    

     

    
    

     

       board[i][j] = '.'
     
    
   

    

     

    
    

     

       row[i][num] = False
     
    
   

    

     

    
    

     

       col[j][num] = False
     
    
   

    

     

    
    

     

       block[blockindex][num] = False
     
    
   

    

     

    
    

     
 # print_board()
     
    
   

    

     

    
    

     
 return False
     
    
   

    

     

    
    

     

       dfs(0, 0)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

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

    

     

    
    

     
 # print(str(1 + 8))
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       s.solveSudoku(board)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/108595823