带Forward Checking的回溯法C++数独求解器故障求助

我正在开发一款优化的数独求解器，核心基于回溯法（backtracking）并加入前瞻检查（Forward Checking）优化：为每个单元格存储可填入数字的Domain（值域）。在尝试向单元格填入数字并回溯前，会检查所有相关单元格是否存在冲突，以此减少回溯次数。但当前C++代码无法正常工作，运行后数独盘面与初始状态一致，未得到预期的求解结果。

问题代码 #

#include <iostream>
#include <bitset>
#include <array>
using namespace std;

#define n 9

void print_board(int board[n][n]);
bool solve(array<bitset<n>, n * n> &domains, int board[n][n], int i = 0, int j = 0);
void initialize_domains(array<bitset<n>, n * n> &domains, int board[n][n]);
bool update_domains(array<bitset<n>, n * n> &domains, int board[n][n], int i, int j, int k);

std::bitset<n> reverse_bits(const std::bitset<n> &bitset)
{
    std::bitset<n> reversed;

    for (int i = 0; i < n; ++i)
    {
        reversed[i] = bitset[n - 1 - i]; // Sets the i-th bit in reversed to the (N-1-i)-th bit in bitset
    }

    return reversed;
}

void printDomains(const std::array<std::bitset<n>, n * n> &domains)
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            std::cout << "Domain for cell (" << i << ", " << j << "): " << reverse_bits(domains[i * n + j]) << std::endl;
        }
    }
}

int main() // main function handles the flow of the program
{
    int board[n][n] = {// definition of the initial board
                       {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}};

    std::array<std::bitset<n>, n * n> domains;

    initialize_domains(domains, board);
    print_board(board);
    solve(domains, board);
    cout << "\n";
    print_board(board);
}

void print_board(int board[n][n]) // displays the Sudoku board
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cout << board[i][j] << " ";
        }
        cout << "\n";
    }
}

// starting from the cell of a cell, update the domains of the influenced cells
bool update_domains(std::array<std::bitset<n>, n * n> &domains, int board[n][n], int i, int j, int k)
{
    for (int a = 0; a < n; ++a)
    {
        domains[i * n + a].set(k - 1); // row
        domains[j + n * a].set(k - 1); // column

        // If it's no longer possible to place a number in the cell
        if (domains[i * n + a].all() && board[i][a] == 0)
            return false;
        if (domains[j + n * a].all() && board[a][j] == 0)
            return false;
    }

    for (int row = (i / 3) * 3; row < ((i / 3) * 3) + 3; ++row)
    {
        for (int col = (j / 3) * 3; col < ((j / 3) * 3) + 3; ++col)
        {

            domains[row * n + col].set(k - 1); // subgrid

            if (domains[row * n + col].all() && board[row][col] == 0)
                return false;
        }
    }

    return true;
}

// 0 = possible to place the number
// 1 = not possible to place the number
void initialize_domains(array<bitset<n>, n * n> &domains, int board[n][n])
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (board[i][j] != 0)
                update_domains(domains, board, i, j, board[i][j]);
        }
    }
}

// i specifies the row
// j specifies the column
bool solve(array<bitset<n>, n * n> &domains, int board[n][n], int i, int j) // responsible for solving the Sudoku using brute-force backtracking
{
    if (i == n) // if all rows and thus all columns are successfully filled, the Sudoku is solved
        return true;
    if (j == n) // if the column index exceeds the dimension, the first cell of the next row must be considered
        return solve(domains, board, i + 1, 0);
    if (board[i][j] != 0) // if there is no empty cell at the current position, move to the next position
        return solve(domains, board, i, j + 1);

    for (int k = 1; k <= n; ++k) // all valid numbers from 1-9 are tried linearly
    {
        if (domains[i * n + j].test(k - 1)) // if the number is not in the domain of the current cell, it can be skipped
            continue;

        array<bitset<n>, n * n> pre_updated_domain = domains;

        if (update_domains(domains, board, i, j, k)) // no conflict
        {
            board[i][j] = k; // the supposedly valid number is tried

            if (solve(domains, board, i, j + 1)) // if no further conflicts arise, this is the correct solution
                return true;

            board[i][j] = 0;
        }

        // if the number leads to a conflict (in an influenced cell, no number can be placed anymore), it will not be used
        domains = pre_updated_domain;
    }

    return false; // if none of the n numbers is valid, a conflict has occurred
}

当前输出 #

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 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

问题原因与修复 #

1. 核心错误：当前单元格的Domain检查逻辑错误 #

在update_domains函数中，尝试向单元格(i,j)填入数字k时，会将该单元格的k-1位设为1（标记为不可填），但此时board[i][j]仍为0（尚未填入数字），触发了domain全1且单元格为空的判断，导致函数返回false，直接跳过了合法的数字填入操作。

2. 辅助优化：Domain初始化显式重置 #

虽然std::bitset默认构造为全0，但显式重置所有Domain为全0，可避免编译器差异导致的初始状态异常。

修复后的代码片段 #

修改update_domains函数

bool update_domains(std::array<std::bitset<n>, n * n> &domains, int board[n][n], int i, int j, int k)
{
    for (int a = 0; a < n; ++a)
    {
        // 处理行，跳过当前单元格
        if (a != j) {
            domains[i * n + a].set(k - 1);
            if (domains[i * n + a].all() && board[i][a] == 0)
                return false;
        }
        // 处理列，跳过当前单元格，修正索引写法提升可读性
        if (a != i) {
            domains[a * n + j].set(k - 1);
            if (domains[a * n + j].all() && board[a][j] == 0)
                return false;
        }
    }

    for (int row = (i / 3) * 3; row < ((i / 3) * 3) + 3; ++row)
    {
        for (int col = (j / 3) * 3; col < ((j / 3) * 3) + 3; ++col)
        {
            // 处理宫，跳过当前单元格
            if (row != i || col != j) {
                domains[row * n + col].set(k - 1);
                if (domains[row * n + col].all() && board[row][col] == 0)
                    return false;
            }
        }
    }

    return true;
}

修改initialize_domains函数

void initialize_domains(array<bitset<n>, n * n> &domains, int board[n][n])
{
    // 显式初始化所有Domain为全0（所有数字可填）
    for (auto &domain : domains) {
        domain.reset();
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (board[i][j] != 0)
                update_domains(domains, board, i, j, board[i][j]);
        }
    }
}

修复后，代码即可正常运行并输出预期的数独解。

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