c++ - 递归回溯数独求解器问题，c++

Question

这是我第一次在低级课程中将递归作为作业处理。我浏览了互联网，似乎找不到任何人使用与我想出的方法类似的方法（这可能说明了为什么这不起作用）。该错误是一个分段错误std::__copy_move...，我假设它是 c++ STL 中的某些内容。任何人，我的代码如下：

bool sudoku::valid(int x, int y, int value)
{
    if (x < 0) {cerr << "No valid values exist./n";}

    if (binary_search(row(x).begin(), row(x).end(), value))
        {return false;}                 //if found in row x, exit, otherwise:
    else if (binary_search(col(y).begin(), col(y).end(), value))
        {return false;}                 //if found in col y, exit, otherwise:
    else if (binary_search(box((x/3), (y/3)).begin(), box((x/3), (y/3)).end(), value))
        {return false;}                 //if found in box x,y, exit, otherwise:
    else
        {return true;}                  //the value is valid at this index
}

int sudoku::setval(int x, int y, int val)
{
    if (y < 0 && x > 0) {x--; y = 9;}   //if y gets decremented past 0 go to previous row.
    if (y > 8) {y %= 9; x++;}           //if y get incremented past 8 go to next row.

    if (x == 9) {return 0;}             //base case, puzzle done.
    else {
        if (valid(x,y,val)){            //if the input is valid
            matrix[x][y] = val;         //set the element equal to val
            setval(x,y++,val);          //go to next element
        }
        else {
            setval(x,y,val++);          //otherwise increment val
            if(val > 9) {val = value(x,y--); setval(x,y--,val++); }
        }                               //if val gets above 9, set val to prev element,  
    }                                   //and increment the last element until valid and start over
}

一段时间以来，我一直在试图解决这个问题，但我似乎无法弄清楚出了什么问题。任何建议都非常感谢！:)

score 1 · Accepted Answer

Without more information, it's impossible to tell. Things like the data structures involved, and what row and col return, for example. Still, there are a number of obvious problems:

In sudoku::valid, you check for what is apparently an error condition (x < 0), but you don't return; you still continue your tests, using the negative value of x.
Also in sudoku:valid: do row and col really return references to sorted values? If the values aren't sorted, then binary_search will have undefined behavior (and if they are, the names are somewhat misleading). And if they return values (copies of something), rather than a reference to the same object, then the begin() and end() functions will refer to different objects—again, undefined behavior.
Finally, I don't see any backtracking in your algorithm, and I don't see how it progresses to a solution.

FWIW: when I wrote something similar, I used a simple array of 81 elements for the board, then created static arrays which mapped the index (0–80) to the appropriate row, column and box. And for each of the nine rows, columns and boxes, I kept a set of used values (a bitmap); this made checking for legality very trivial, and it meant that I could increment to the next square to test just by incrementing the index. The resulting code was extremely simple.

Independently of the data representation used, you'll need: some "global" (probably a member of sudoku) means of knowing whether you've found the solution or not; a loop somewhere trying each of the nine possible values for a square (stopping when the solution has been found), and the recursion. If you're not using a simple array for the board, as I did, I'd suggest a class or a struct for the index, with a function which takes care of the incrementation once and for all.

score 1 · Accepted Answer

sudoku::setval应该返回 anint但至少有两条路径它根本不返回任何内容。您应该弄清楚它需要在其他路径中返回什么，否则您将获得随机的未定义行为。

score 0 · Accepted Answer

以下所有内容均适用于 Unix 而不是 Windows。

std::__copy_move...STL 没问题。但是 STL 本身不会做任何事情，您的代码中的某些函数调用会使用错误的参数或处于错误的状态来调用它。你需要弄清楚这一点。

如果您有来自 teh seg-fault 的核心转储，那么只需执行 a pstack <core file name>，您将看到崩溃的完整调用堆栈。然后只需查看代码的哪一部分参与其中并从那里开始调试（添加跟踪/couts/...）。

通常你会得到这个具有可读性好的名称的核心文件，但如果你不这样做，你可以使用nmor c++filtetc 来分解名称。

最后，pstack它只是一个小型命令行实用程序，您始终可以将二进制文件（生成核心）和核心文件加载到调试器（如gdb、Sun Studio或 IDE 中内置的调试器）中，并查看相同的内容以及许多其他内容信息和选项。

高温高压

score 0 · Accepted Answer

如果您以递归方式多次输入函数，则可能（并且将会）发生分段错误。我注意到导致它的一种情况。但我很确定还有更多。

提示：用你的话写出任何函数的目的——如果写得太复杂——函数可能应该被拆分......

score 0 · Accepted Answer

看起来你的算法有点“蛮力”。对于约束满足问题 (CSP)，这通常不是一个好的策略。不久前我写了一个数独求解器（希望我还有源代码，那是在我发现 github 之前），我能找到的最快的算法是模拟退火：

http://en.wikipedia.org/wiki/Simulated_annealing

这是概率性的，但对于这个问题 IIRC，它通常比其他方法快几个数量级。

！

c++ - 递归回溯数独求解器问题，c++

5 回答 5

Related

Reference