c - 生成数独谜题

Question

我正在尝试编写一段代码来为我生成一个有效的数独谜题。

我的算法:

1. 所有字段都以 0 开头
2. 遵守规则，将 1-9 之间的 20 个随机值设置为随机字段
3. 使用回溯算法解决难题

我的问题:

1. 有时它会在 1 秒内生成有效的数独谜题。
2. 有时它无法生成有效的数独，并且会出现错误，但这没关系，因为我可以返回算法中的第 1 步。
3. 有时它无法生成有效的数独，并且会出现错误，但大约需要 2-3 分钟，这是不行的。

我该如何解决我的问题？ 特别是问题3。 我可以只计算秒数吗？如果花费的时间超过 5 秒，则返回算法的第 1 步？

或者谁有更好的主意？

提前致谢。

这是我的代码:

#include <stdio.h>
#include <stdlib.h>

#define N 9
#define UNASSIGNED 0


typedef enum {false, true} bool;
typedef struct { 
    char number;
    bool editable; 
} GRID;

void print_sudoku(GRID **g){
    char row=0, col=0;
    for(row=0; row<N; row++){
        for(col=0; col<N; col++){
            printf("%d ", g[row][col].number);
        }
        printf("\n");
    }
}


GRID ** create_sudoku_grid(){
    char i, row, col;
    GRID **g = (GRID **) malloc(N * sizeof(GRID *));
    for (i=0; i<N; i++) {
        g[i] = (GRID *) malloc(N * sizeof(GRID)); 
    }

    for(row=0; row<N; row++){
        for(col=0; col<N; col++){
            g[row][col].number = UNASSIGNED;
            g[row][col].editable = true;
        }
    }
    return g;
}



bool find_unassigned_field(GRID **g, int *row, int *col){
    for (*row = 0; *row < N; (*row)++) {
        for (*col = 0; *col < N; (*col)++) { 
            if (g[*row][*col].number == UNASSIGNED){
                return true;    
            } 
        }
    }
    return false; 
}

bool validate_row(GRID **g, int row, int num) { 
    for (int col = 0; col < N; col++) {
        if (g[row][col].number == num) {
            return false; 
        }
    }
    return true; 
} 

bool validate_col(GRID **g, int col, int num) { 
    for (int row = 0; row < N; row++) {
        if (g[row][col].number == num) {
            return false; 
        }
    }
    return true; 
} 


bool validate_box(GRID **g, int row, int col, int num) { 
    for (int r = 0; r < 3; r++) {
        for (int c = 0; c < 3; c++) { 
            if (g[r+row][c+col].number == num) {
                return false; 
            }
        }
    }
    return true; 
} 


bool validate_field(GRID **g, int row, int col, int num){
    bool valrow, valcol, valbox, valunassigned;

    valrow = validate_row(g, row, num); 
    valcol = validate_col(g, col, num);
    valbox = validate_box(g, row - row%3 , col - col%3, num);
    valunassigned = g[row][col].number==UNASSIGNED; 
    return (valrow && valcol && valbox && valunassigned);

}


bool generate_sudoku(GRID **g) { 
    int row, col; 

    // If there is no unassigned location, we are done 
    if (!find_unassigned_field(g, &row, &col)) {
        return true; // success! 
    }

    // consider digits 1 to 9 
    for (int num = 1; num <= 9; num++) { 
        // if looks promising 
        if (validate_field(g, row, col, num)) { 
            // make tentative assignment 
            g[row][col].number = num; 

            // return, if success, yay! 
            if (generate_sudoku(g)) {
                return true; 
            }
            // failure, unmake & try again 
            g[row][col].number = UNASSIGNED; 
        } 
    } 
    return false; // this triggers backtracking 
} 

void random_init_grid(GRID **g){
    int row, col, num;
    srand(time(0));

    for(int cntr=0; cntr<20;){
        row = rand() % N;
        col = rand() % N;
        num = rand() % N + 1;
        if(g[row][col].number == UNASSIGNED){
            if(validate_field(g, row, col, num)){
                g[row][col].number = num;
                cntr++;
            }
        }

    }
}

int main(int argc, char *argv[]) {
    GRID **g = create_sudoku_grid();
    random_init_grid(g);

    if(generate_sudoku(g)){
        printf("OK\n\n");
    } else {
        printf("\nNOT OK\n\n");
    }
    print_sudoku(g);
}

Answer 1

Sudoko 是一个计算困难的问题，使用蛮力和无知可能会达到 10^100 的量级。可能需要比 2-3 分钟更长的时间!有时，由于数字布局，它比这更容易。

在一种方法中，您可以计算迭代次数，如果超过则放弃。你的关键部分是你递归调用generate_soduko()的 block ——如果你在这里结束太多次，你就会遇到麻烦。

为此，我改变了你的程序，在其执行时设置一个 1 秒警报，计数器该 block 中的次数；如果警报到期，则打印计数器并退出；如果它最后没有打印计数器以供引用。在我的机器上，1s == 500,000 次迭代。

*** sud.c~  2019-12-06 14:30:21.000000000 -0500
--- sud.c   2019-12-06 14:30:57.000000000 -0500
***************
*** 1,10 ****
  #include <stdio.h>
  #include <stdlib.h>

  #define N 9
  #define UNASSIGNED 0

- 
  typedef enum {false, true} bool;
  typedef struct { 
      char number;
--- 1,21 ----
  #include <stdio.h>
  #include <stdlib.h>
+ #include <signal.h>
+ #include <unistd.h>
+ #include <time.h>
+ 
+ volatile long  counter;
+ void alrm(int signo) {
+   char buf[64];
+   int n;
+   n = sprintf(buf, "failed after %ld iter\n", counter);
+   write(2, buf, n);
+   _exit(1);
+ }

  #define N 9
  #define UNASSIGNED 0

  typedef enum {false, true} bool;
  typedef struct { 
      char number;
***************
*** 106,111 ****
--- 117,123 ----
      for (int num = 1; num <= 9; num++) { 
          // if looks promising 
          if (validate_field(g, row, col, num)) { 
+       counter++;
              // make tentative assignment 
              g[row][col].number = num; 

***************
*** 139,145 ****
  }

  int main(int argc, char *argv[]) {
!     GRID **g = create_sudoku_grid();
      random_init_grid(g);

      if(generate_sudoku(g)){
--- 151,161 ----
  }

  int main(int argc, char *argv[]) {
! 
!     GRID **g;
!   signal(SIGALRM, alrm);
!   alarm(1);
!     g = create_sudoku_grid();
      random_init_grid(g);

      if(generate_sudoku(g)){
***************
*** 148,151 ****
--- 164,168 ----
          printf("\nNOT OK\n\n");
      }
      print_sudoku(g);
+     printf("iter = %ld\n", counter);
  }