第十四届蓝桥杯青少组C++国赛[2023.5.28]第二部分编程题（4、 数独填数）

参考程序：

#include <bits/stdc++.h>
using namespace std;char board[9][9];// 检查在 (r,c) 填 num 是否有效
bool isValid(int r, int c, char num) {for (int i = 0; i < 9; ++i) {if (board[r][i] == num) return false;      // 同行if (board[i][c] == num) return false;      // 同列int br = (r/3)*3 + i/3;int bc = (c/3)*3 + i%3;if (board[br][bc] == num) return false;   // 同 3x3 宫}return true;
}// 回溯 DFS 填数
bool dfs(int r, int c) {if (r == 9) return true; // 已填完所有行，成功if (board[r][c] != '.') {// 已有数字，移动到下一个格子if (c == 8) return dfs(r+1, 0);else return dfs(r, c+1);}for (char num = '1'; num <= '9'; ++num) {if (isValid(r, c, num)) {board[r][c] = num;if (c == 8) {if (dfs(r+1, 0)) return true;} else {if (dfs(r, c+1)) return true;}board[r][c] = '.'; // 回溯}}return false; // 无可行数字，回溯
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);// 输入 9 行for (int i = 0; i < 9; ++i) {string line;cin >> line;for (int j = 0; j < 9; ++j) board[i][j] = line[j];}dfs(0, 0); // 从左上角开始填数// 输出结果for (int i = 0; i < 9; ++i) {for (int j = 0; j < 9; ++j) cout << board[i][j];cout << '\n';}return 0;
}

参考程序2：

#include <bits/stdc++.h>
using namespace std;char board[9][9];
int rowMask[9], colMask[9], boxMask[9];
vector<pair<int,int>> empties;inline int boxIndex(int r, int c) {return (r/3)*3 + (c/3);
}bool dfs() {// 找还未填且候选数最少的空格（启发式）int bestIdx = -1;int bestCount = 10;int bestMask = 0;for (int k = 0; k < (int)empties.size(); ++k) {int r = empties[k].first;int c = empties[k].second;if (board[r][c] != '.') continue; // 已被填过int mask = ~(rowMask[r] | colMask[c] | boxMask[boxIndex(r,c)]) & 0x1FF; // 9位掩码int cnt = __builtin_popcount(mask);if (cnt == 0) return false; // 无候选 -> 这条路失败，回溯if (cnt < bestCount) {bestCount = cnt;bestIdx = k;bestMask = mask;if (cnt == 1) break; // 已经是最优（1）可直接尝试}}if (bestIdx == -1) {// 没有空格，解出return true;}int r = empties[bestIdx].first;int c = empties[bestIdx].second;int b = boxIndex(r,c);// 依次尝试 bestMask 中的每个候选数字（低位表示数字1）int mask = bestMask;while (mask) {int bit = mask & -mask; // 取最低位 2^dint d = __builtin_ctz(bit); // d in [0..8], 对应数字 (d+1)mask ^= bit;// 放置 d+1board[r][c] = char('1' + d);rowMask[r] |= (1 << d);colMask[c] |= (1 << d);boxMask[b] |= (1 << d);if (dfs()) return true;// 撤销board[r][c] = '.';rowMask[r] &= ~(1 << d);colMask[c] &= ~(1 << d);boxMask[b] &= ~(1 << d);}return false;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);// 读取 9 行，每行可能含空格，保留数字或 '.' 字符直至获得 9 个有效字符for (int i = 0; i < 9; ++i) {string line;if (!getline(cin, line)) return 0; // 非法输入或 EOFstring filtered;for (char ch : line) {if (ch == '.' || (ch >= '1' && ch <= '9')) filtered.push_back(ch);if (filtered.size() == 9) break;}// 若本行过滤后不足9个字符，继续读接下来的行拼满（提高对不规范输入的容错）while (filtered.size() < 9) {string extra;if (!getline(cin, extra)) break;for (char ch : extra) {if (ch == '.' || (ch >= '1' && ch <= '9')) filtered.push_back(ch);if (filtered.size() == 9) break;}}if (filtered.size() != 9) {// 如果输入仍然异常，填充 '.' 保证程序不会越界（实际题目不会出现）filtered.resize(9, '.');}for (int j = 0; j < 9; ++j) board[i][j] = filtered[j];}// 初始化掩码与空格列表fill(begin(rowMask), end(rowMask), 0);fill(begin(colMask), end(colMask), 0);fill(begin(boxMask), end(boxMask), 0);empties.clear();for (int i = 0; i < 9; ++i) {for (int j = 0; j < 9; ++j) {char ch = board[i][j];if (ch >= '1' && ch <= '9') {int d = ch - '1';int b = boxIndex(i,j);rowMask[i] |= (1 << d);colMask[j] |= (1 << d);boxMask[b] |= (1 << d);} else {board[i][j] = '.';empties.emplace_back(i,j);}}}bool ok = dfs();if (!ok) {// 按题意不会发生（保证有效且唯一），但安全处理cout << "No solution\n";return 0;}// 输出结果：9 行，每行 9 个数字，无空格for (int i = 0; i < 9; ++i) {for (int j = 0; j < 9; ++j) cout << board[i][j];cout << '\n';}return 0;
}