今天看到一个挺有意思的网友吐槽：刚入职一周的同事提交了一个新增2万行、删减1.4万行的代码，要求做Code Review。
结果他表示：“我真的头大，不想review了！”作为一个程序员，我不得不说，这种事情真的很让人头疼。
首先，2万行的新增代码，基本可以理解为“半个新模块”了。如果没有明确的文档或注释，review的时候几乎就是在“盲人摸象”。哪怕代码写得再好，能不能理解、能不能维护，都是问题。
而删减1.4万行代码更让人抓狂，删掉的部分会不会影响到其他功能？哪些是冗余的，哪些是意外删除的？这些都需要小心谨慎地检查。
我深知新人刚入职的时候，有时候就是会“过度热情”，要不然怎么在上班的第一周就提交如此“大作”呢？如果是我，会建议同事们给新人更多指导，尽量避免这种一刀切式的提交。
对新人来说，代码质量比数量重要，逐步积累经验更能提高工作效率。
你们怎么看呢？
算法题：解数独
今天我们来聊聊解数独的算法，作为程序员，数独这类题目你可能已经见怪不怪了，但如果你真的用程序来解它，那就有些意思了。
数独问题的核心就是在一个 9x9 的网格中填充数字，规则很简单：每一行、每一列以及每个 3x3 的子宫格都必须包含 1 到 9 的数字，而且不能重复。听起来简单，但你要用程序去解，难度可就大了。别着急，咱们一步步来。
首先，我知道你脑海中可能会出现“暴力破解”这个词。嗯，确实，这是最直接的一种方法，就是通过遍历每一个空格，试着填入每个数字，直到所有规则都满足为止。但这种方法效率低，尤其是在数据量较大的时候，性能会很差。所以，今天咱们要讲的，是一种更加高效的回溯算法。
回溯算法怎么理解呢？可以这么想：每次填数字的时候，咱们会考虑当前数字是否符合规则，如果不符合，直接回退，换一个数字继续尝试。这就像你在解谜游戏时，推倒一块拼图发现不对劲时，再去试其他拼法一样，直到拼图完美符合。
现在，我们开始动手了。先来看一下数独的解法：
def solve_sudoku(board):
def is_valid(board, row, col, num):
# 检查行
for i in range(9):
if board[row][i] == num:
return False
# 检查列
for i in range(9):
if board[i][col] == num:
return False
# 检查3x3子宫格
start_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] == num:
return False
return True
def solve(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0: # 找到一个空格
for num in range(1, 10):
if is_valid(board, i, j, num): # 如果数字符合规则
board[i][j] = num # 填入数字
if solve(board): # 递归继续填
return True
board[i][j] = 0 # 如果填错了，就回退
return False # 如果所有数字都试过了，返回False
return True # 如果整个板子都填满了，返回True
solve(board)
return board
这段代码首先定义了一个 is_valid 函数，用来判断某个数字能否放在某个位置上。它分别检查了数字是否已经在当前行、列或3x3子宫格中出现。如果没有出现，就说明这个数字可以填上。接着在 solve 函数中，我们遍历每一个空格，尝试填入数字 1 到 9，并递归调用 solve 继续尝试。如果发现填入某个数字后无法继续填下去，就回退，换一个数字。
其实，回溯算法最大的特点就是不断尝试和回退。它的效率虽然比暴力破解强，但当数据量增大时，还是会遇到一些性能瓶颈。毕竟，9x9的数独虽然不是特别大，但算法的执行过程其实是有很多可能的分支。
不过，别急！我们可以对回溯做一些优化。比如，如果我们使用“最小候选数策略”，即优先填充空格数最少的单元格，这样可以在某些情况下更早地找出错误并回退，从而减少不必要的递归。可以通过预处理来统计每个空格可填的数字数量。
这里有个优化后的代码示例：
def solve_sudoku(board):
def is_valid(board, row, col, num):
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
start_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] == num:
return False
return True
def find_empty(board):
empty_cells = []
for i in range(9):
for j in range(9):
if board[i][j] == 0:
empty_cells.append((i, j))
return empty_cells
def solve(board):
empty_cells = find_empty(board)
if not empty_cells:
return True
# 优先选择最少候选数的空格
i, j = min(empty_cells, key=lambda cell: len(get_candidates(board, *cell)))
for num in range(1, 10):
if is_valid(board, i, j, num):
board[i][j] = num
if solve(board):
return True
board[i][j] = 0
return False
def get_candidates(board, row, col):
candidates = set(range(1, 10))
for i in range(9):
candidates.discard(board[row][i])
candidates.discard(board[i][col])
start_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):
candidates.discard(board[i][j])
return candidates
solve(board)
return board
这里我们在 solve 函数中加入了一个 find_empty 函数，它会先找到所有空格，并通过 min 函数结合 get_candidates 来选择可选数字最少的空格。这样，在大多数情况下可以有效减少回溯的深度。
数独问题看似简单，但要做到高效解决其实不容易。回溯算法已经是目前为止比较高效的解法了，当然如果你需要更高效的算法（比如在更大的棋盘上），那就得用到更多高级的优化技巧啦。
不过，今天就先聊到这里。希望你对解数独的算法有了更深的理解，动手试试吧！
对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。
虎哥作为一名老码农，整理了全网最全《python高级架构师资料合集》。
