数独生成器导致随机无限循环 [C]

Question

我正在用 C 语言制作一个数独生成器，但是当我启动程序时它会随机进入无限循环。有时它打印所有行，有时只打印一行，等等……等等。（见下图）这是代码有什么问题？

#include <string.h>
#include <stdlib.h>
#include "sudoku.h"
#include <stdio.h>
#include <time.h>

int dimension = 9;

int main(int argc, char** argv){
  int dimension = 9;
  int j ,k,i ;
  int ** sudo =  malloc(sizeof(*sudo)*dimension);
  for ( j = 0; j< dimension; j++){
    sudo[j] =  malloc(sizeof(int)*dimension);
  }
    riempiSudoku(sudo);
  return 0;

void riempiSudoku(int** sudo){  //fill sudoku
  int j,i,k,f;
  int len; 
  //srand ( time(NULL));
  int ran;
  for (i=0;i<dimension;i++){
    for(j=0;j<dimension;j++){
      if(!thereisNumber(sudo, i,j)){
    printf("\nNon ci sono numeri\n");//no solution, stop the program
    exit(0);
      }
      printf("%d ", sudo[i][j]);
    }
    printf("\n");
  }
}


int checkRow(int** sudo, int row, int value){ //check if the number is in the row
  int i;
  for (i = 0; i<dimension; i++){
    if (sudo[row][i] == value)
      return 1;
  }
  return 0;
}

int checkCol(int** sudo, int col, int value){//check if the number is in the col
  int i;
  for (i = 0; i<dimension; i++){
    if (sudo[i][col] == value)
      return 1;
  }
  return 0;

}


int checkSquare(int** sudo, int row, int col, int value){
  int i, j;
  for(i= (row/3)*3; i<(row/3)*3 +3; i++){
    for(j=(col/3)*3; j<(col/3)*3 +3; j++){
      if(sudo[i][j] == value)
    return 1;
    }
  }
  return 0;

}
int thereisNumber(int** sudo, int i,int j){
  int options[dimension];
  int len;
  for (len=0; len<dimension; len++)
    options[len] = len + 1;             // populate the array with 1..9
  while (len) {
    int ran = rand() % len;         // select an index into the list
    int digit = options[ran];      // get the number from the available list
    if (checkSquare(sudo,i,j,digit) || checkRow(sudo,i,digit) || checkCol(sudo,j,digit))
        options[ran] = options[--len];  // remove digit from list
    else{
      sudo[i][j]= digit;
      return len>0;
    }
  }
  return 0; //thereisNumber(sudo,i,j-1);
}

这些是截图 http://imgur.com/lQpFOPf 这是gdb的结果 http://imgur.com/qp8omko

Answer 1

当没有可能的解决方案时，您的程序陷入僵局 - 正如@BLUEPIXY 所评论的。

但是你的程序检测不到，它一直在尝试更多的随机数。我建议使用与卡片一起使用的 Fisher-Yates shuffle 之类的东西，将不成功的候选人从可能性数组中移除。

int options[dimension];
int len;
for (len=0; len<dimension; len++)
    options[len] = len + 1;             // populate the array with 1..9
while (len) {
    int ran = rand() % len;             // select an index into the list
    int digit = options[ran];           // get the number from the available list
    if (checkSquare(sudo,i,j,digit) || checkRow(sudo,i,digit) || checkCol(sudo,j,digit))
        options[ran] = options[--len];  // remove digit from list
    else break;
}
return len > 0;                         // 0 if failed to find digit

如果该功能不成功，您需要能够"undo" 号码放置的历史记录。那是你的下一个任务！

EDIT 而不是 "undo" 函数，在每个数字位置您都可以实现我展示的 "array of possibilities"。解决方案比你想象的要复杂，可能需要递归解决。

数独生成器导致随机无限循环 [C]

Sudoku generator causes random endless loop [C]

c

sudoku

infinite-loop