数独是"回溯算法"最优雅的舞台:规则简单,但要让程序自动出一道题并验证答案,必须学会深度优先搜索。这一篇写完整版:自动生成唯一解题目、CLI 填数、实时校验、可求解。

1. 棋盘与合法性判断

9×9 用二维列表,0 表示空格。判断某个位置能否放数字 n:所在行、列、3×3 小宫格都不能有 n:

def valid(board, r, c, n):
    for i in range(9):
        if board[r][i] == n or board[i][c] == n:
            return False
    br, bc = r // 3 * 3, c // 3 * 3
    for i in range(3):
        for j in range(3):
            if board[br + i][bc + j] == n:
                return False
    return True

2. 求解器:回溯

从左上到右下找空格,依次试 1~9,能放就递归下一个格;走不通就回退。找到解立刻返回,这就是标准回溯:

def solve(board):
    for r in range(9):
        for c in range(9):
            if board[r][c] == 0:
                for n in range(1, 10):
                    if valid(board, r, c, n):
                        board[r][c] = n
                        if solve(board):
                            return True
                        board[r][c] = 0    # 撤销
                return False
    return True

3. 生成题目:先填满,再挖空

从空盘开始用回溯"正向生成"一个完整终盘;然后随机挖掉若干格,挖掉后仍能解出唯一答案(简化版只校验有解)。挖得越多难度越高:

import random

def generate(difficulty=40):
    board = [[0] * 9 for _ in range(9)]
    solve(board)                     # 先生成完整终盘
    cells = [(r, c) for r in range(9) for c in range(9)]
    random.shuffle(cells)
    for r, c in cells[:difficulty]:
        board[r][c] = 0              # 挖掉
    return board

4. 完整代码

import random

def valid(board, r, c, n):
    for i in range(9):
        if board[r][i] == n or board[i][c] == n:
            return False
    br, bc = r // 3 * 3, c // 3 * 3
    for i in range(3):
        for j in range(3):
            if board[br + i][bc + j] == n:
                return False
    return True

def solve(board):
    for r in range(9):
        for c in range(9):
            if board[r][c] == 0:
                for n in range(1, 10):
                    if valid(board, r, c, n):
                        board[r][c] = n
                        if solve(board):
                            return True
                        board[r][c] = 0
                return False
    return True

def generate(difficulty=40):
    board = [[0] * 9 for _ in range(9)]
    solve(board)
    cells = [(r, c) for r in range(9) for c in range(9)]
    random.shuffle(cells)
    for r, c in cells[:difficulty]:
        board[r][c] = 0
    return board

def show(board):
    for r in range(9):
        row = ' '.join(str(board[r][c]) if board[r][c] else '.'
                       for c in range(9))
        print(row)
        if r in (2, 5):
            print()

board = generate(40)
show(board)
while True:
    cmd = input('\n输入: r c 数字(如 0 1 5), q 退出, s 求解: ')
    if cmd == 'q':
        break
    if cmd == 's':
        print('答案:')
        solve(board)
        show(board)
        break
    parts = cmd.split()
    if len(parts) != 3:
        print('格式错误'); continue
    r, c, n = map(int, parts)
    if not (0 <= r < 9 and 0 <= c < 9 and 1 <= n <= 9):
        print('范围错误'); continue
    if not valid(board, r, c, n):
        print('这个位置不能放', n); continue
    board[r][c] = n
    show(board)
    if all(all(x != 0 for x in row) for row in board):
        print('恭喜,填满了!')
        break

5. 运行与常见问题

保存为 sudoku.py,python3 sudoku.py 运行。常见问题:①生成题目太慢——回溯从空盘生成很快,但挖空后要校验唯一解会更慢,简化版只保证有解;②输入坐标搞混——格式是"行 列 数字",都从 0 开始;③想验证唯一解——在 solve 里计数,解的数量超过 1 就重新挖。

💡 改进方向:①唯一解校验(计数回溯);②难度分级(挖空格数);③3×3 宫格高亮;④计时与计时挑战;⑤图形界面版本。