c++ - C++ 使用列表解决数独问题

Question

我正在尝试用 C++ 制作数独求解器。我想从 [9] 到 [9] 保留一个数组（显然）。我现在正在想办法跟踪可能的值。我考虑了数组中每个条目的列表。所以这个列表最初的数字是 1 到 9，每次迭代我都可以去掉一些值。

现在我的问题是，我可以为 2D 数组中的每个条目分配一个列表吗？如果可以的话怎么办？还有其他/更好的选择吗？

我是一名初级程序员，这基本上是我在 C++ 中的第一个项目。提前致谢！

Answer 1

您始终可以将数独视为 3D 数组，使您的 3D 维度存储可能的值，主要是：

// set "1" in cell's which index corespond to a possible value for the Sudoku cell
for (int x = 0; x < 9; x++)
    for (int y = 0; y < 9; y++)
        for (int i = 1; i < 10; i++)
            arr[x][y][i] = 1;

并arr[x][y][0]包含您的数独的价值。

例如，删除“5”的值作为单元格的可能性，[x][y]只需更改arr[x][y][5] = 0

Answer 2

好吧，您可以通过以下方式创建一组集合

std::array<std::set<int>,81> possibleValues;

例如。您可以通过编写以所有可能性填充此数组

const auto allPossible = std::set<int>{ 0, 1, 2, 3, 4, 5, 6, 7, 8 };
std::fill( std::begin(possibleValues), std::end(possibleValues), 
    allPossible );

如果您使用的是现代 C++11 编译器。这是您可以设置/清除和测试每个条目的方式：

possibleValues[x+9*y].insert( n ); // sets that n is possible at (x,y).
possibleValues[x+9*y].erase( n ); // clears the possibility of having n at (x,y).
possibleValues[x+9*y].count( n ) != 0 // tells, if n is possible at (x,y).

如果性能是一个问题，您可能希望使用位操作而不是（相对）重量级std::set操作。在这种情况下使用

std::array<short, 81> possibleValues;
std::fill( begin(possibleValues), end(possibleValues), (1<<10)-1 );

当且仅当，在这种情况下，所有索引都从 0 开始，该值才n可能用于 field 。(x,y)possibleValues[x+9*y] & (1<<n) != 0

Answer 3

一个简单的解决方案是为每个方格使用一组一位标志，例如

uint16_t board[9][9]; // 16 x 1 bit flags for each square where 9 bits are used
                      // to represent possible values for the square

然后您可以使用按位运算符来设置/清除/测试每个位，例如

board[i][j] |= (1 << n);  // set bit n at board position i, j

board[i][j] &= ~(1 << n); // clear bit n at board position i, j

test = (board[i][j] & (1 << n)) != 0; // test bit n at board position i, j