16x16数独求解器逻辑错误排查求助（附C++代码）

正在开发16x16数独求解器，此前完成的9x9版本运行良好。采用消元+猜测的策略，但当前C++代码存在逻辑错误，无法得到正确结果。作为编程入门学生，希望得到易懂的帮助。以下是代码、测试输入及输出：

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <set>

using namespace std;

const int N = 16;
array<array<int, N>, N> board;
array<array<set<int>, N>, N> possibilities;
vector<pair<int, int>> guesses;

void eliminate_possibilities();

int char_to_int(char c) {
    if (c >= '0' && c <= '9') {
        return c - '0';
    } else if (c >= 'A' && c <= 'F') {
        return c - 'A' + 10;
    } else {
        return 0;
    }
}

char int_to_char(int i) {
    if (i >= 0 && i <= 9) {
        return '0' + i;
    } else if (i >= 10 && i <= 15) {
        return 'A' + i - 10;
    } else {
        return '0';
    }
}

bool solve() {
    int min_possibilities = N + 1;
    pair<int, int> next_cell = {-1, -1};
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] != 0) {
                continue;
            }
            if (possibilities[i][j].size() < min_possibilities) {
                min_possibilities = possibilities[i][j].size();
                next_cell = {i, j};
            }
        }
    }
    if (next_cell.first == -1 && next_cell.second == -1) {
        return true;
    }
    int row = next_cell.first;
    int col = next_cell.second;
    for (int val : possibilities[row][col]) {
        board[row][col] = val;
        guesses.emplace_back(row, col);
        eliminate_possibilities();
        if (solve()) {
            return true;
        }
        board[row][col] = 0;
        guesses.pop_back();
    }
    return false;
}

void eliminate_possibilities() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] != 0) {
                continue;
            }
            set<int> &p = possibilities[i][j];
            p.clear();
            for (int val = 1; val <= N; val++) {
                bool valid = true;
                for (int k = 0; k < N; k++) {
                    if (board[i][k] == val || board[k][j] == val) {
                        valid = false;
                        break;
                    }
                }
                int boxRowStart = (i / 4) * 4;
                int boxColStart = (j / 4) * 4;
                for (int r = boxRowStart; r < boxRowStart + 4; r++) {
                    for (int c = boxColStart; c < boxColStart + 4; c++) {
                        if (board[r][c] == val) {
                            valid = false;
                            break;
                        }
                    }
                }
                if (valid) {
                    p.insert(val);
                }
            }
        }
    }
}

void print_board() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << int_to_char(board[i][j]) << " ";
        }
        cout << endl;
    }
}

int main() {
    srand(time(0));
    char c;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> c;
            board[i][j] = char_to_int(c);
        }
    }

    eliminate_possibilities();
    if (!solve()) {
        cout << "No Solution" << endl;
    } else {
        print_board();
    }

    return 0;
}

测试输入与输出 #

测试用例1

输入

C 0 8 9 0 6 F 0 4 0 0 B E 0 D 1
0 0 5 0 0 8 0 0 0 D 0 G B 0 0 3
B 0 0 0 0 0 0 0 0 0 0 5 4 8 0 0
0 0 6 0 0 0 A G 0 0 0 0 0 0 0 9
0 5 0 0 C 9 0 0 0 F 0 8 A 4 0 0
0 0 F 4 8 D 0 0 0 0 G E C 0 0 5
A G 0 8 0 0 6 E 0 4 0 0 0 0 9 0
6 0 0 E 0 G 4 0 3 5 B 9 D 0 1 0
0 9 0 0 0 0 0 0 C 0 0 0 0 1 E 6
0 0 E 0 0 0 0 0 0 9 0 0 G 0 F 0
0 0 B 0 A 0 G 0 0 7 8 0 0 0 C D
0 0 0 D 0 B C 0 0 0 0 F 8 3 5 0
8 B 0 A 0 C 2 0 0 0 6 0 0 7 4 0
E 0 D F G 0 8 0 B 0 0 0 0 9 0 0
0 0 0 0 F 0 B 0 0 E 0 0 6 0 0 0
0 7 4 6 1 A D 0 0 C 0 0 F 0 0 0

预期输出

C A 8 9 2 6 F 5 4 3 7 B E G D 1
1 F 5 2 4 8 E 7 9 D A G B C 6 3
B E G 7 D 3 9 C 1 6 2 5 4 8 A F
4 D 6 3 B 1 A G E 8 F C 2 5 7 9
D 5 7 B C 9 3 2 6 F 1 8 A 4 G E
9 3 F 4 8 D 1 B 7 A G E C 6 2 5
A G 1 8 5 F 6 E D 4 C 2 3 B 9 7
6 2 C E 7 G 4 A 3 5 B 9 D F 1 8
F 9 A G 3 2 5 8 C B D 4 7 1 E 6
5 8 E C 6 4 7 D 2 9 3 1 G A F B
3 4 B 1 A E G F 5 7 8 6 9 2 C D
7 6 2 D 9 B C 1 A G E F 8 3 5 4
8 B 9 A E C 2 3 F 1 6 D 5 7 4 G
E C D F G 5 8 6 B 2 4 7 1 9 3 A
2 1 3 5 F 7 B 4 G E 9 A 6 D 8 C
G 7 4 6 1 A D 9 8 C 5 3 F E B 2

实际输出

C A 8 9 2 6 F 5 4 3 7 B E 0 D 1
1 F 5 2 4 8 E 7 9 D A 0 B C 6 3
B E 0 7 D 3 9 C 1 6 2 5 4 8 A F
4 D 6 3 B 1 A 0 E 8 F C 2 5 7 9
D 5 7 B C 9 3 2 6 F 1 8 A 4 0 E
9 3 F 4 8 D 1 B 7 A 0 E C 6 2 5
A 0 1 8 5 F 6 E D 4 C 2 3 B 9 7
6 2 C E 7 0 4 A 3 5 B 9 D F 1 8
F 9 A 0 3 2 5 8 C B D 4 7 1 E 6
5 8 E C 6 4 7 D 2 9 3 1 0 A F B
3 4 B 1 A E 0 F 5 7 8 6 9 2 C D
7 6 2 D 9 B C 1 A 0 E F 8 3 5 4
8 B 9 A E C 2 3 F 1 6 D 5 7 4 0
E C D F 0 5 8 6 B 2 4 7 1 9 3 A
2 1 3 5 F 7 B 4 0 E 9 A 6 D 8 C
0 7 4 6 1 A D 9 8 C 5 3 F E B 2

测试用例2

输入

0 0 0 0 7 0 0 0 0 0 0 0 0 E 0 2
7 0 B 0 0 0 0 0 A 0 2 D 0 F 0 5
1 0 G E 3 B 2 0 5 0 0 0 0 0 0 D
0 2 0 5 0 0 0 0 0 0 7 0 0 8 B 0
2 0 0 0 0 0 G 0 0 6 0 0 0 0 0 0
0 B 1 C E 0 0 0 8 0 5 7 0 A 0 0
F 0 0 G 0 0 0 0 1 0 9 2 0 0 6 4
0 0 5 0 2 0 0 7 0 0 0 4 8 1 0 B
0 0 4 0 0 0 0 8 0 A 0 B C 0 0 1
0 0 8 6 0 E 0 3 D 0 0 0 0 9 0 0
0 0 D F B G 5 4 0 0 3 0 0 0 0 A
0 G 0 9 C 0 0 0 0 0 0 6 B 0 8 0
0 0 0 D 6 0 0 0 0 1 F G 0 0 7 0
E 0 0 A 0 C B 0 9 0 0 0 0 5 0 0
0 0 3 0 5 0 0 0 0 B 0 0 D 0 E 0
0 0 0 0 0 1 0 G 3 E C 0 A 0 0 0

预期输出

D A F 8 7 9 4 5 B C 6 1 G E 3 2
7 9 B 4 G 8 E C A 3 2 D 6 F 1 5
1 C G E 3 B 2 6 5 9 8 F 7 4 A D
3 2 6 5 F A D 1 G 4 7 E 9 8 B C
2 8 9 7 1 4 G A C 6 B 3 F D 5 E
4 B 1 C E 6 3 D 8 F 5 7 2 A 9 G
F E A G 8 5 C B 1 D 9 2 3 7 6 4
6 D 5 3 2 F 9 7 E G A 4 8 1 C B
5 3 4 2 9 7 6 8 F A E B C G D 1
B 7 8 6 A E 1 3 D 2 G C 5 9 4 F
C 1 D F B G 5 4 7 8 3 9 E 6 2 A
A G E 9 C D F 2 4 5 1 6 B 3 8 7
8 5 C D 6 3 A E 2 1 F G 4 B 7 9
E 6 2 A 4 C B F 9 7 D 8 1 5 G 3
G F 3 1 5 2 7 9 6 B 4 A D C E 8
9 4 7 B D 1 8 G 3 E C 5 A 2 F 6

实际输出

"No Solution"

猜测问题可能出在猜值选择或终止条件上，期待回复，谢谢！

内容的提问来源于stack exchange，提问作者Joash Paul