1

为了学习使用递归，我正在尝试制作数独求解器。我似乎已经让大部分代码一起工作得很好，但是当我运行程序时，我收到一个 Windows 错误，告诉我程序已经停止工作。调试表明存在分段错误，我在其他地方看到这可能是由太多递归引起的。我知道这是一种蛮力方法，但同样，我更担心让它发挥作用而不是速度。我该怎么做才能将其修复到工作水平？

struct Playing_grid {
    //Value of cell
    int number;
    //wether the number was a clue or not
    bool fixed;
}
grid[9][9];

    void recursiveTest(int row, int column, int testing)
    {
    //first, check to make sure it's not fixed
        if(grid[row][column].fixed == false)
        {
            if((checkRow(testing, row) | checkColumn(testing, column) | checkBox(testing,boxNumber(row,column)) | (testing > 9)) == 0)
            {
                grid[row][column].number = testing;
                moveForward(row,column,testing);
                recursiveTest(row, column, testing);
            }
            else if(testing < 9)
            {
                testing ++;
                recursiveTest(row, column, testing);
            }
            else if(testing == 9)
            {
                while(testing == 9)
               {
                moveBack(row,column,testing);
                while(grid[row][column].fixed == true)
                {
                    {
                        moveBack(row,column,test);
                    }
                }
                testing = grid[row][column].number;
                recursiveTest(row,column,testing);
               }
            }
        }
        else
        {
            moveForward(row,column,testing);
            recursiveTest(row,column,testing);
        }
    }



     void moveForward(int& row, int& column, int& test)
{
    if(column < 8)
    {
        column ++;
    }
    else if((column == 8) & (row != 8))
    {
        column = 0;
        row ++;
    }
    else if((column == 8) & (row == 8))
    {
        finishProgram();
    }
    test = 1;
}

    void moveBack(int& row, int& column, int& test)
    {
        grid[row][column].number = 0;
        if(column > 0)
            {
                column --;
            }
        else if((column == 0) & (row > -1))
            {
                column = 8;
                row --;
            }
        else
        {
            cout << "This puzzle is unsolveable!" << endl;
        }
        test++;
    }

我试图包括所有相关的部分。我基本上创建了一个 9x9 矩阵，此时它填充了 81 个值，其中空槽写为 0。确认测试值在行、列和框中有效后，它填充该值并移动到下一个空间。每当它运行到 9 并且没有可能的值时，它就会返回到前一个值并遍历那个值。

为了不覆盖已知值，递归函数每次都会检查 grid[row][column].fixed 的值是否为假。

我将不胜感激有关清理，浓缩等方面的任何见解。在此先感谢！

编辑：要退出递归循环，当调用函数向前移动时，如果它已到达最后一个单元格，则完成（保存+输出）解决方案。代码已被调整以反映这一点。

4

1 回答 1

0

我通常会尝试修复你的代码，但我认为在这种情况下它存在根本缺陷，你需要回到绘图板上。

作为一般规则，像这样的递归函数的伪代码是

For each possible (immediate) move
  Perform that move
  Check for win state, if so store/output it and return true.
  Call this function. If it returns true then a win state has been found so return true 
  Otherwise unperform the move
Having tried every move without finding a win state, return false.
于 2012-07-25T00:18:21.753 回答