Leetcode练习(Python)：哈希表类：第37题：解数独：编写一个程序，通过已填充的空格来解决数独问题。 一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9
题目：
解数独：编写一个程序，通过已填充的空格来解决数独问题。 一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。
思路：
这道题太难了，按照自己的思路从昨晚到现在了，实现不了，还是水平不够高吧，后来看了官方的解答，发现自己的思路一开始就设计错了，太难了，理解了一下官方的程序，然后放到这里了，以备继续学习，怀挺！
程序：
from collections import defaultdict
class Solution:
def solveSudoku(self, board):
def could_place(d, row, col):
return not (d in rows[row] or d in columns[col] or \
d in boxes[box_index(row, col)])
def place_number(d, row, col):
rows[row][d] += 1
columns[col][d] += 1
boxes[box_index(row, col)][d] += 1
board[row][col] = str(d)
def remove_number(d, row, col):
del rows[row][d]
del columns[col][d]
del boxes[box_index(row, col)][d]
board[row][col] = '.'
def place_next_numbers(row, col):
if col == N - 1 and row == N - 1:
nonlocal sudoku_solved
sudoku_solved = True
else:
if col == N - 1:
backtrack(row + 1, 0)
else:
backtrack(row, col + 1)
def backtrack(row = 0, col = 0):
if board[row][col] == '.':
for d in range(1, 10):
if could_place(d, row, col):
place_number(d, row, col)
place_next_numbers(row, col)
if not sudoku_solved:
remove_number(d, row, col)
else:
place_next_numbers(row, col)
n = 3
N = n * n
box_index = lambda row, col: (row // n ) * n + col // n
rows = [defaultdict(int) for i in range(N)]
columns = [defaultdict(int) for i in range(N)]
boxes = [defaultdict(int) for i in range(N)]
for i in range(N):
for j in range(N):
if board[i][j] != '.':
d = int(board[i][j])
place_number(d, i, j)
sudoku_solved = False
backtrack()