Python 实现数独求解算法详解

南乔

发布时间：2026-10-13| 2人浏览过

原创

本文介绍如何使用 Python 编写程序自动求解数独。通过将数独转换为矩阵，利用递归和回溯算法，依次寻找空白格并尝试填入符合行列及九宫格规则的数字。文章包含从数据预处理到核心求解逻辑的完整代码示例，帮助开发者理解算法实现细节。

数独规则与背景

芬兰数学家因卡拉耗时三个月设计的数独，被公认为目前世界上难度最高的谜题之一。标准数独由 9 行 9 列共 81 个格子组成，并细分为 9 个 3x3 的九宫格。其核心规则简单明确：在空格中填入 1 至 9 之间的任意数字，确保每一行、每一列以及每一个九宫格内的数字均不重复。

数独通常被视为一种益智娱乐，许多人虽知晓其规则却未深入钻研。此前，因学生安装了 Ubuntu 18.04 系统并预装了数独游戏，这激发了作者展示 Python 编程能力的想法。为了演示如何利用 Python 解决此类问题，特此整理出相关的实现思路与代码。

Python 求解算法实现

第一步是将待求解的数独题目转换为 Python 可处理的矩阵数据结构。


m = [
 [6, 0, 0, 1, 0, 0, 7, 0, 8],
 [0, 0, 0, 8, 0, 0, 2, 0, 0],
 [2, 3, 8, 0, 5, 0, 1, 0, 0],
 [0, 0, 0, 0, 4, 0, 0, 9, 2],
 [0, 0, 4, 3, 0, 8, 6, 0, 0],
 [3, 7, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 3, 0, 7, 0, 5, 2, 6],
 [0, 0, 2, 0, 0, 4, 0, 0, 0],
 [9, 0, 7, 0, 0, 6, 0, 0, 4]
]

具体操作十分直观：将数独中所有需要填写的空白格，在矩阵中统一用数字 0 进行占位表示。

第二步是定位矩阵中第一个值为 0 的空白格，并获取其所在的坐标位置。


def start_pos(m:"数独矩阵"):
 """ 功能：返回第一个空白格的位置坐标"""
 for x in range(9):
  for y in range(9):
   if m[x][y] == 0:
    return x, y
 return False, False # 若数独已完成，则返回 False, False

通过遍历 Python 矩阵，查找第一个元素为 0 的位置，并返回该位置的行号和列号坐标。

第三步是确定当前空白格之后的下一个空白格位置，以便进行后续的递归处理。


def get_next(m:"数独矩阵", x:"空白格行数", y:"空白格列数"):
 """ 功能：获得下一个空白格在数独中的坐标。  
 """
 for next_y in range(y+1, 9): # 下一个空白格和当前格在一行的情况
  if m[x][next_y] == 0:
   return x, next_y
 for next_x in range(x+1, 9): # 下一个空白格和当前格不在一行的情况
  for next_y in range(0, 9):
   if m[next_x][next_y] == 0:
    return next_x, next_y
 return -1, -1    # 若不存在下一个空白格，则返回 -1，-1

在获取当前空白格坐标后，需进一步查找矩阵中下一个值为 0 的元素坐标。具体逻辑详见代码注释部分。

第四步是筛选出当前空白格可填入的有效数字集合。


def value(m:"数独矩阵", x:"空白格行数", y:"空白格列数"):
 """ 功能：返回符合"每个横排和竖排以及
    九宫格内无相同数字"这个条件的有效值。
 """ 
 i, j = x//3, y//3
 grid = [m[i*3+r][j*3+c] for r in range(3) for c in range(3)]
 v = set([x for x in range(1,10)]) - set(grid) - set(m[x]) - \
  set(list(zip(*m))[y])
 return list(v)

虽然每个空格理论上可填 1 至 9 的任意数字，但必须严格遵守数独规则：同一行、同一列及所在九宫格内不得出现重复数字。代码中的 grid 变量用于标识当前格子所属的九宫格范围。v 变量通过集合运算，从 1 至 9 的全集中剔除当前行、当前列及当前九宫格内已存在的数字，剩余的数字即为当前空格符合条件的候选值集合。

第五步是利用递归算法尝试求解整个数独盘面。


def try_sudoku(m:"数独矩阵", x:"空白格行数", y:"空白格列数"):
 """ 功能：试着填写数独 """
 for v in value(m, x, y):
  m[x][y] = v
  next_x, next_y = get_next(m, x, y)
  if next_y == -1: # 如果无下一个空白格
   return True
  else:
   end = try_sudoku(m, next_x, next_y) # 递归
   if end: # 数独解完之后，此处的 end 会是 True
    return True
   m[x][y] = 0 # 在递归的过程中，如果数独没有解开，
      # 则回溯到上一个空白格

递归过程的具体实现与边界条件处理详见代码中的详细注释。

完整代码示例

以下是完整的 Python 求解代码展示。


import random 
import sys 
sys.setrecursionlimit(100000) # 发现python默认的递归深度是很有限的
        #（默认是1000），因此当递归深度超过999的
        # 样子，就会引发这样的一个异常。


def get_next(m:"数独矩阵", x:"空白格行数", y:"空白格列数"):
 """ 功能：获得下一个空白格在数独中的坐标。  
 """
 for next_y in range(y+1, 9): # 下一个空白格和当前格在一行的情况
  if m[x][next_y] == 0:
   return x, next_y
 for next_x in range(x+1, 9): # 下一个空白格和当前格不在一行的情况
  for next_y in range(0, 9):
   if m[next_x][next_y] == 0:
    return next_x, next_y
 return -1, -1    # 若不存在下一个空白格，则返回 -1，-1
  
def value(m:"数独矩阵", x:"空白格行数", y:"空白格列数"):
 """ 功能：返回符合"每个横排和竖排以及
    九宫格内无相同数字"这个条件的有效值。
 """ 
 i, j = x//3, y//3
 grid = [m[i*3+r][j*3+c] for r in range(3) for c in range(3)]
 v = set([x for x in range(1,10)]) - set(grid) - set(m[x]) - \
  set(list(zip(*m))[y]) 
 return list(v)

def start_pos(m:"数独矩阵"):
 """ 功能：返回第一个空白格的位置坐标"""
 for x in range(9):
  for y in range(9):
   if m[x][y] == 0:
    return x, y
 return False, False # 若数独已完成，则返回 False, False

def try_sudoku(m:"数独矩阵", x:"空白格行数", y:"空白格列数"):
 """ 功能：试着填写数独 """
 for v in value(m, x, y):
  m[x][y] = v
  next_x, next_y = get_next(m, x, y)
  if next_y == -1: # 如果无下一个空白格
   return True
  else:
   end = try_sudoku(m, next_x, next_y) # 递归
   if end:
    return True
   m[x][y] = 0 # 在递归的过程中，如果数独没有解开，
      # 则回溯到上一个空白格

def sudoku(m):  
 x, y = start_pos(m)
 try_sudoku(m, x, y)
 print(m)  
 
  

     
if __name__ == "__main__":
 m = [
  [6, 0, 0, 1, 0, 0, 7, 0, 8],
  [0, 0, 0, 8, 0, 0, 2, 0, 0],
  [2, 3, 8, 0, 5, 0, 1, 0, 0],
  [0, 0, 0, 0, 4, 0, 0, 9, 2],
  [0, 0, 4, 3, 0, 8, 6, 0, 0],
  [3, 7, 0, 0, 1, 0, 0, 0, 0],
  [0, 0, 3, 0, 7, 0, 5, 2, 6],
  [0, 0, 2, 0, 0, 4, 0, 0, 0],
  [9, 0, 7, 0, 0, 6, 0, 0, 4]
 ]

 sudoku(m)
 
""" 数独结果如下：
[
 [6, 9, 5, 1, 2, 3, 7, 4, 8], 
 [7, 4, 1, 8, 6, 9, 2, 5, 3], 
 [2, 3, 8, 4, 5, 7, 1, 6, 9], 
 [8, 1, 6, 7, 4, 5, 3, 9, 2], 
 [5, 2, 4, 3, 9, 8, 6, 7, 1], 
 [3, 7, 9, 6, 1, 2, 4, 8, 5], 
 [4, 8, 3, 9, 7, 1, 5, 2, 6], 
 [1, 6, 2, 5, 8, 4, 9, 3, 7], 
 [9, 5, 7, 2, 3, 6, 8, 1, 4]
]
"""

以上就是利用 Python 解决数独问题的全部内容，希望能为读者的学习提供参考，欢迎继续支持本站获取更多技术分享。