LeetCode Python - 37.解数独

本文主要是介绍LeetCode Python - 37.解数独，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

题目

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

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

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

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

提示：

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

---

答案

class Solution(object):def solveSudoku(self, board):""":type board: List[List[str]]:rtype: None Do not return anything, modify board in-place instead."""empty = []for i in range(9):for j in range(9):if board[i][j] == '.':empty.append(9 * i + j)self.solve(board, empty)def solve(self, board, empty):if len(empty) == 0:return Truefirst_value = empty[-1]row, col = first_value / 9, first_value % 9for k in range(1, 10):if self.is_safe(board, row, col, str(k)):board[row][col] = str(k)empty.pop()if self.solve(board, empty):return Trueboard[row][col] = '.'empty.append(first_value)return Falsedef is_safe(self, board, row, col, ch):for k in range(9):if board[k][col] == ch:return Falseif board[row][k] == ch:return Falsestart_row, start_col = 3 * (row / 3), 3 * (col / 3)for i in range(start_row, start_row + 3):for j in range(start_col, start_col + 3):if board[i][j] == ch:return Falsereturn True

---

运行结果

这篇关于LeetCode Python - 37.解数独的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---