c++ - 递归验证函数堆栈溢出

Question

我正在创建一个可创建随机数独表的控制台应用程序。

我在验证表时遇到了问题(除了 3x3 框验证仍然需要工作)并且它工作得很好但是在 x 和 y< 的这么多循环之后 的 9x9 数独表我得到一个堆栈溢出错误。我不确定如何阻止这种情况发生。

这是代码:

int Array[9][9];
int validate(int i, int j, int *number){
  *number = rand() % 9 + 1;
  for (int x = 0; x < 9; x++){ //row validation 
      if (*number == Array[x][j]){
            validate(i,j,number);
      }
  }

  for (int x = 0; x < 9; x++){ //column validation
      if (*number == Array[i][x]){
            validate(i,j,number);
      }
  }

  return *number;
}

void generate(){
  for (int x = 0; x < 9; x++){
     for (int y = 0; y < 9; y++){
         int *number = new int;
         Array[x][y] = validate(x,y,number);
         delete number;
     }
   }
 }


int main(){
  srand((unsigned int)time(NULL));
  generate();
}

我想我要使用动态内存分配，例如 malloc 或 new？但我不确定如何在 validate() 函数中使用它们，这是我收到堆栈溢出错误的地方。

Answer 1

首先，您的代码有几个基本的 C++ 问题:

• 您正在使用指向 int 的指针使用动态分配，其中分配了简单堆栈 int够了
• 您正在使用 rand()来自 th C 库，再加上一个模，resulting in a very poor distribution , 考虑标准 <random> header 。
• 您使用了不必要的全局变量 ( Array )，您应该避免这种情况。

---

现在，您的真正问题是数学。

您正在尝试随机生成一个数独表:这在确定性方式中是不可能的。

解释:

对于 (i, j) in [1-9] x [1-9] :

• 考虑单元格 (i , j) :对于这个单元格，你已经有了 i - 1随机数就行了j - 1列上的数字，所以 (i + j - 2)数。

• 现在如果我们取 i + j = 11 (例如 i = 4, j = 7 )，我们已经在行或列上生成了 9 个随机数。我们遇到 [1 - 9] 中的所有数字的情况行中或列中已经存在(您的代码中没有任何内容阻止它)，使得无法为当前单元格生成数字，因此无限递归(validate 方法永远不会成功)，因此 <强> Stack Overflow .

网上有很多生成数独表的确定性算法，你应该先看看它。

注意:

如果您非常幸运，您的程序可以生成一个有效的数独表。如果是，请考虑玩国家彩票。