用C++解决数独问题（附代码）

用户11952558

发布于 2026-01-09 14:05:57

1540

下面，我们将使用DFS（深度优先搜索）、回溯算法和剪枝等，将你小学时的“拦路虎”——数独斩落马下。

前言

数独是一种经典的数字逻辑游戏，它不仅能够锻炼思维能力，还是学习算法设计的绝佳案例。

数独规则：由9x9个空格组成，分为9个3x3的小方格。

每一行、每一列和每个3x3的小方格中，数字1到9只能出现一次

只能使用数字1到9。

算法基础概念

1. DFS（深度优先搜索）

DFS 是一种用于遍历或搜索树或图的算法。它的核心思想是"一条路走到黑"：

从根节点开始，沿着某条路径尽可能深地搜索
当到达叶子节点或无法继续时，回溯到上一个分叉点
选择另一条路径继续搜索

在数独中的应用：将每个空位看作决策点，先地尝试所有可能的数字。

2. 回溯算法

回溯算法 是DFS的一种特定形式，主要用于解决约束满足问题：

系统性搜索：尝试所有可能的候选解
剪枝：在发现当前路径不可能得到解时立即放弃
撤销操作：在回退时恢复状态

在数独中的应用：将每个空位看作决策点，先地尝试所有可能的数字

3. 剪枝

剪枝是优化搜索过程的关键技术，目的是避免无效的搜索路径：

可行性剪枝：当前选择明显违反约束条件时立即停止
最优性剪枝：在优化问题中，当前路径已不可能优于已知最优解时停止

数据结构设计

int a[10][10];          // 数独棋盘
bool row[10][10];       // 行约束：row[i][k]表示第i行是否有数字k
bool col[10][10];       // 列约束：col[j][k]表示第j列是否有数字k  
bool ge[10][10][10];    // 九宫格约束：ge[x][y][k]表示第(x,y)个九宫格是否有数字k

int a[10][10]; 数独棋盘
bool row[10][10]; 行约束：row[i][k]表示第i行是否有数字k
bool col[10][10]; 列约束：col[j][k]表示第j列是否有数字k
bool ge[10][10][10]; 九宫格约束：ge[x][y][k]表示第(x,y)个九宫格是否有数字k

核心算法：带剪枝的回溯

bool dfs(int i, int j) {
    // 边界检查：移动到下一行或下一列
    if (i == 9) {
        j++;
        i = 0;
    }
    if (j == 9) return true;  // 成功填充所有格子
    
    // 剪枝：如果当前格子已有数字，直接跳过
    if (a[i][j]) return dfs(i + 1, j);
    
    // 尝试所有可能的数字
    for (int k = 1; k <= 9; k++) {
        // 重要剪枝：检查数字k是否满足所有约束
        if (row[i][k] || col[j][k] || ge[i/3][j/3][k])
            continue;  // 不满足约束，跳过
        
        // 做出选择
        row[i][k] = col[j][k] = ge[i/3][j/3][k] = true;
        a[i][j] = k;
        
        // 递归深入
        if (dfs(i + 1, j)) {
            return true;  // 找到解
        }
        
        // 回溯：撤销选择
        row[i][k] = col[j][k] = ge[i/3][j/3][k] = false;
        a[i][j] = 0;
    }
    
    return false;  // 当前路径无解
}

边界检察

if (i == 9) 
{
    j++;
    i = 0;
}
if (j == 9) 
return true;

当i=9时，表示当前行已填满，移动到下一行
当j=9时，表示所有格子已填充，成功返回

剪枝：跳过已有数字的格子：

if (a[i][j]) 
return dfs(i + 1, j);

如果当前格子已有数字，直接跳过

尝试所有可能的数字：

从1到9尝试每个数字
检查数字是否满足约束（行、列、3x3宫格）
如果满足，标记为已使用，填充到格子
递归深入尝试下一个格子
如果递归成功，返回true
如果递归失败，回溯（撤销选择）

完整代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
using namespace std;

int _size;
int a[10][10];//数独
bool row[10][10];//行
bool col[10][10];//列
bool ge[10][10][10];//小方格
int r;


bool dfs(int i, int j)
{
	if (i == 9)
	{
		j++; i = 0;
	}
	if (j == 9)return true;
	if (a[i][j])return dfs(i + 1, j);
	for (int k = 1; k <= 9; k++)
	{
		if (row[i][k] || col[j][k] || ge[i / 3][j / 3][k])continue;
		row[i][k] = col[j][k] = ge[i / 3][j / 3][k] = true;
		a[i][j] = k;
		if (dfs(i + 1, j))
		{
			return true;
		}
		row[i][k] = col[j][k] = ge[i / 3][j / 3][k] = false;
		a[i][j] = 0;
	}
	return false;
}


int main()
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cin >> a[i][j];
			int x = a[i][j];
			if (x) 
			{
				row[i][x] = true;
				col[j][x] = true;
				ge[i / 3][j / 3][x] = true;
			}
		}
	}
	dfs(0, 0);
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

算法分析

时间复杂度

最坏情况：O(9^(n))，其中n为空位数
实际运行：通过剪枝大幅优化，通常能在毫秒级解决标准数独

空间复杂度

O(1)，使用固定大小的数组

关键优化点

快速约束检查：通过预处理三个标记数组，将约束检查从O(n)降到O(1)
智能回溯：在发现冲突时立即回溯，避免无效搜索
系统搜索顺序：按行优先顺序填充，保证完整性

用例

输入

5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

输出

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9