利用豆包辅助编写数独隐式唯一数填充c程序

在查看程宁先生的SQL中间过程时，发现他一轮迭代填充的唯一数要比我自己的程序多很多，以下面数据为例

id | iteration | puzzle | result
——+———–+———–+———–
1001 | 0 | …….1.+| 000000010+
| | 4……..+| 400000000+
| | .2…….+| 020000000+
| | ….5.4.7+| 000050407+
| | ..8…3..+| 008000300+
| | ..1.9….+| 001090000+
| | 3..4..2..+| 300400200+
| | .5.1…..+| 050100000+
| | …8.6… | 000806000
1001 | 1 | …….1.+| 000000010+
| | 4……..+| 400000000+
| | .2…….+| 020000000+
| | ….5.4.7+| 000051407+ <—
| | ..8…3..+| 008000301+ <—
| | ..1.9….+| 001090000+
| | 3..4..2..+| 300475200+ <—
| | .5.1…..+| 050100000+
| | …8.6… | 000806100 <—

填充了5个唯一数，而我的唯一数程序只找到1个。 请教程宁先生，他说他让AI实现了显式和隐式唯一数，我查了资料。看了隐性唯一数的定义，终于明白了，某数某宫group by后count(*)=1就是此数在此宫候选数出现了一次 。行、列隐式唯一数同理。我的唯一数程序只实现了显式的。 明白了原理，就让豆包辅助编写程序

还有一种“隐性唯一数” (Hidden Single) 是指一个单元格里有多个候选数（例如：{1, 7, 8}），但其中一个候选数（例如 ‘1’）在该宫的其他任何笔记中都没有出现。比如在这个宫里，我们可以看到以下已填入的数字和笔记： 已填数字： 5 (R1C7), 6 (R2C7), 2 (R2C8)。 笔记 (候选数)：R1C8 = {3, 4, 9}R1C9 = {3, 4, 9}R2C9 = {3, 4, 7, 8}R3C7 = {1, 7, 8} （我们需要关注的单元格）R3C8 = {7, 8, 9}R3C9 = {7, 8, 9} 第一步：扫描笔记寻找特定数字 与其盯着单个单元格看，不如扫描整个宫来寻找特定的数字。让我们来寻找数字 1。 R1C8？没有 ‘1’。 R1C9？没有 ‘1’。 R2C9？没有 ‘1’。 R3C7？是的，它有一个 ‘1’。 R3C8？没有 ‘1’。 R3C9？没有 ‘1’。 第二步：找到解 数字 1 作为候选数，在整个 3×3 宫中仅出现在一个单元格中：单元格 R3C7。 尽管 R3C7 也包含了 7 和 8 的笔记，但它是这个宫里数字 1 唯一可能的容身之处。因此，R3C7 必须是 1。实现这种算法的函数，不做别的。 它输出如下代码

// 检查并填充宫(Box)中的隐性唯一数
int fill_hidden_single_in_boxes() {
int filled_count = 0;

// 遍历所有9个3×3宫
for (int box_row = 0; box_row < SIZE; box_row += 3) {
for (int box_col = 0; box_col < SIZE; box_col += 3) {

// 对每个数字1-9检查是否是该宫的隐性唯一数
for (int num = 1; num <= SIZE; num++) {
int found_row = –1;
int found_col = –1;
int count = 0;

// 遍历当前宫的所有格子
for (int r = box_row; r < box_row + 3; r++) {
for (int c = box_col; c < box_col + 3; c++) {
// 跳过已填充的格子
if (sudoku[r][c].value != 0) {
continue;
}

// 计算当前格子的候选数掩码
uint16_t mask = get_candidate_mask(r, c);
// 检查该数字是否是当前格子的候选数
if (mask & (1 << (num – 1))) {
found_row = r;
found_col = c;
count++;

// 超过1个格子有该候选数，无需继续检查
if (count > 1) {
break;
}
}
}
if (count > 1) {
break;
}
}

// 该数字在当前宫中仅出现在一个空位的候选数中（隐性唯一）
if (count == 1) {
sudoku[found_row][found_col].value = num;
sudoku[found_row][found_col].candidates = 0;
filled_count++;
// 填充后立即更新，避免重复处理
printf("填充宫隐性唯一数: 位置(%d,%d) = %d\\n", found_row+1, found_col+1, num);
}
}
}
}

return filled_count;
}

// 检查并填充行中的隐性唯一数
int fill_hidden_single_in_rows() {
int filled_count = 0;

// 遍历所有9行
for (int row = 0; row < SIZE; row++) {
// 对每个数字1-9检查是否是该行的隐性唯一数
for (int num = 1; num <= SIZE; num++) {
int found_col = –1;
int count = 0;

// 遍历当前行的所有格子
for (int col = 0; col < SIZE; col++) {
// 跳过已填充的格子
if (sudoku[row][col].value != 0) {
continue;
}

// 计算当前格子的候选数掩码
uint16_t mask = get_candidate_mask(row, col);
// 检查该数字是否是当前格子的候选数
if (mask & (1 << (num – 1))) {
found_col = col;
count++;

// 超过1个格子有该候选数，无需继续检查
if (count > 1) {
break;
}
}
}

// 该数字在当前行中仅出现在一个空位的候选数中（隐性唯一）
if (count == 1) {
sudoku[row][found_col].value = num;
sudoku[row][found_col].candidates = 0;
filled_count++;
printf("填充行隐性唯一数: 位置(%d,%d) = %d\\n", row+1, found_col+1, num);
}
}
}

return filled_count;
}

// 检查并填充列中的隐性唯一数
int fill_hidden_single_in_cols() {
int filled_count = 0;

// 遍历所有9列
for (int col = 0; col < SIZE; col++) {
// 对每个数字1-9检查是否是该列的隐性唯一数
for (int num = 1; num <= SIZE; num++) {
int found_row = –1;
int count = 0;

// 遍历当前列的所有格子
for (int row = 0; row < SIZE; row++) {
// 跳过已填充的格子
if (sudoku[row][col].value != 0) {
continue;
}

// 计算当前格子的候选数掩码
uint16_t mask = get_candidate_mask(row, col);
// 检查该数字是否是当前格子的候选数
if (mask & (1 << (num – 1))) {
found_row = row;
count++;

// 超过1个格子有该候选数，无需继续检查
if (count > 1) {
break;
}
}
}

// 该数字在当前列中仅出现在一个空位的候选数中（隐性唯一）
if (count == 1) {
sudoku[found_row][col].value = num;
sudoku[found_row][col].candidates = 0;
filled_count++;
printf("填充列隐性唯一数: 位置(%d,%d) = %d\\n", found_row+1, col+1, num);
}
}
}

return filled_count;
}

// 综合填充所有隐性唯一数（宫+行+列），迭代直到无新填充
int fill_hidden_singles() {
int total_filled = 0;
int has_change;

// 循环直到一轮遍历中没有填充任何隐性唯一数
do {
has_change = 0;

int filled_box = fill_hidden_single_in_boxes();
int filled_row = fill_hidden_single_in_rows();
int filled_col = fill_hidden_single_in_cols();

int current_filled = filled_box + filled_row + filled_col;
if (current_filled > 0) {
has_change = 1;
total_filled += current_filled;
}

} while (has_change);

return total_filled;
}

并告知了调用位置。 集成到原有流程 在原有fill_unique_candidates之后调用该函数，形成完整的预处理流程：

// 第一步：填充唯一候选数（显性唯一）
fill_unique_candidates();
// 第二步：填充隐性唯一数
fill_hidden_singles();
// 第三步：DFS求解剩余部分
if (!is_sudoku_complete()) {
solve_sudoku_dfs();
}

合并后的代码编译执行

gcc cand.c -o cand -O3
root@66d4e20ec1d7:/par/1224/0112# ./cand
000000003001005600090040070000009050700000008050402000080020090003500100600000000
填充宫隐性唯一数: 位置(5,5) = 5
000000003001005600090040070000009050700050008050402000080020090003500100600000000,59
000000010400000000020000000000050407008000300001090000300400200050100000000806000
填充宫隐性唯一数: 位置(5,9) = 1
填充宫隐性唯一数: 位置(7,6) = 5
填充宫隐性唯一数: 位置(8,6) = 9
填充宫隐性唯一数: 位置(9,7) = 1
填充行隐性唯一数: 位置(4,6) = 1
…
填充列隐性唯一数: 位置(1,3) = 3
693784512487512936125963874932651487568247391741398625319475268856129743274836159,0
总计处理数独数量：2
完全解决的数独数量：1

17个已知数的难题有很多可以只用两种唯一数解决。

time ./cand < sudoku17.txt >17out.txt
总计处理数独数量：49151
完全解决的数独数量：17376

real0m6.511s
user0m6.468s
sys0m0.032s

从解决问题的数量时间来说，已经超过了MRV+DFS的效率。