C++ - 解决数独游戏

Question

我是 C++ 的新手，必须做家庭作业 (sudoku)。我遇到了一个问题。

问题是实现一个解决数独的搜索功能。

说明:为了找到解决方案，递归搜索的使用如下。假设有一个尚未分配带有数字 (d1....dn) (n > 1) 的字段。然后我们首先尝试将字段分配给 d1，进行传播，然后继续搜索递归地。可能发生的是传播导致失败(一个字段变成空的)。在这种情况下，搜索会失败，需要为其中一个尝试不同的数字田野。由于搜索是递归的，因此最后考虑的字段的下一个数字被试过了。如果没有数字导致解决方案，则搜索再次失败。这在turn 将导致尝试与前一个字段不同的数字，依此类推。

在通过分配字段来尝试数字 d 之前它，你必须创建一个新的板作为当前板的拷贝(使用复制构造函数并使用 new 从堆中分配板)。仅有的然后在拷贝上执行分配。如果递归调用搜索返回不成功，可以为下一个数字创建一个新的板尝试过。

我试过:

// Search for a solution, returns NULL if no solution found
Board* Board::search(void) {
    // create a copy of the cur. board
    Board *copyBoard = new Board(*this);
    Board b = *copyBoard;

    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){

              //  if the field has not been assigned, assign it with a digit 
            if(!b.fs[i][j].assigned()){
                digit d = 1;

                     // try another digit if failed to assign (1 to 9)
                while (d <=9 && b.assign(i, j, d) == false){
                        d++;


                      // if no digit matches, here is the problem, how to 
                      // get back to the previous field and try another digit?
                      // and return null if there's no pervious field 
                if(d == 10){
                      ...
                    return NULL;
                }
            }
        }
    }
    return copyBoard;
 }

另一个问题是递归调用用在什么地方？有小费吗？谢谢!

完整的说明可以在这里找到:http://www.kth.se/polopoly_fs/1.136980!/Menu/general/column-content/attachment/2-2.pdf

代码:http://www.kth.se/polopoly_fs/1.136981!/Menu/general/column-content/attachment/2-2.zip

Answer 1

您的代码中没有递归。您不能只访问每个字段一次并尝试为其分配一个值。问题是您可能能够将 5 分配给字段 (3,4) 并且可能只有当您到达字段 (6,4) 时才发现 (3 , 4).最终你需要退出递归，直到你回到 (3,4) 并在那里尝试另一个值。

使用递归，您可能不会使用嵌套的 for 循环来访问字段，而是通过递归调用访问下一个字段。您要么设法到达最后一个字段，要么尝试所有可能性，然后离开该功能以返回到您访问的上一个字段。

---

旁注:绝对不要为此任务分配动态内存:

//Board *copyBoard = new Board(*this);
Board copyBoard(*this); //if you need a copy in the first place