返回解決方案數量的數獨求解器

Question

我使用基本的回溯算法制作了一個數獨求解器。 即使有很多優化要完成，它的工作還算不錯。

我嘗試修改我的代碼，以返回給定數獨網格的解決方案總數。爲了做到這一點，我簡單地改變了求解函數，把所有可能性加起來，而不是停在一個可能性上。

但是我只拿到1或0

下面是基本求解代碼：

int  check_row(char **tab, int y, int n) 
{ 
    int i; 

    i = 0; 
    while (i < 9) 
    { 
     if (tab[y][i] == n + '0') 
      return (0); 
     i++; 
    } 
    return (1); 
} 

int  check_column(char **tab, int x, int n) 
{ 
    int j; 

    j = 0; 
    while (j < 9) 
    { 
     if (tab[j][x] == n + '0') 
      return (0); 
     j++; 
    } 
    return (1); 
} 

int  check_square(char **tab, int x, int y, int n) 
{ 
    int i; 
    int j; 

    i = (x/3) * 3; 
    while (i < (x/3) * 3 + 3) 
    { 
     j = (y/3) * 3; 
     while (j < (y/3) * 3 + 3) 
     { 
      if (tab[j][i] == n + '0') 
       return (0); 
      j++; 
     } 
     i++; 
    } 
    return (1); 
} 

int  solve(char **tab, int x, int y) 
{ 
    int n; 

    if (y >= 9 || x >= 9) 
     return (1); 
    if (tab[y][x] == '.') 
    { 
     n = 1; 
     while (n < 10) 
     { 
      if (check_row(tab, y, n) && check_column(tab, x, n) 
       && check_square(tab, x, y, n)) 
      { 
       tab[y][x] = n + '0'; 
       if (solve(tab, (x + 1) % 9, y + ((x + 1)/9))) 
        return (1); 
      } 
      n++; 
     } 
     tab[y][x] = '.'; 
     return (0); 
    } 
    else 
     return (solve(tab, (x + 1) % 9, y + ((x + 1)/9))); 
} 

這裏是修改後的功能應該算解決方案：

int  solve_count(char **tab, int x, int y) 
{ 
    int n; 
    int count; 
    count = 0; 
    if (y >= 9 || x >= 9) 
     return (1); 
    if (tab[y][x] == '.') 

    { 

     n = 1; 
     while (n < 10) 
     { 
      if (check_row(tab, y, n) && check_column(tab, x, n) 
       && check_square(tab, x, y, n)) 
      { 
       tab[y][x] = n + '0'; 
       count += solve_count(tab, (x + 1) % 9, y + ((x + 1)/9)); 
      } 
      n++; 
     } 
     tab[y][x] = '.'; 
    return (count); 


    } 
    else 
     return (solve_count(tab, (x + 1) % 9, y + ((x + 1)/9))); 
} 

主要功能和幫助功能如下：

#include <unistd.h> 

int  solve(char **tab, int x, int y); 
int  solve_count(char **tab, int x, int y); 
void ft_putchar(char c) 
{ 
    write(1, &c, 1); 
} 

void ft_putstr(char *str) 
{ 
    int i; 

    i = 0; 
    while (*(str + i) != '\0') 
    { 
     ft_putchar(*(str + i)); 
     i++; 
    } 
} 

void ft_putnbr(int n) 
{ 
    int  i; 
    int  vect[20]; 
    long nb; 

    nb = n; 
    i = -1; 
    if (nb < 0) 
    { 
     ft_putchar('-'); 
     nb = -nb; 
    } 
    if (nb == 0) 
     ft_putchar('0'); 
    while (nb > 0) 
    { 
     i++; 
     vect[i] = nb % 10; 
     nb = nb/10; 
    } 
    while (i > -1) 
    { 
     ft_putchar('0' + vect[i]); 
     i--; 
    } 
} 

int  ft_check_input(int argc, char **argv) 
{ 
    int i; 
    int j; 

    i = 1; 
    j = 0; 
    if (argc != 10) 
     return (1); 
    while (i < argc) 
    { 
     while (argv[i][j]) 
      j++; 
     if (j != 9) 
      return (1); 
     j = 0; 
     while (argv[i][j] == '.' || (argv[i][j] > '0' && argv[i][j] <= '9')) 
      j++; 
     if (j != 9) 
      return (1); 
     j = 0; 
     i++; 
    } 
    if (i != 10) 
     return (1); 
    else 
     return (0); 
} 

void ft_print_sudoku(char **tab) 
{ 
    int i; 
    int j; 

    i = 1; 
    j = 0; 
    while (i < 10) 
    { 
     while (j < 9) 
     { 
      ft_putchar(tab[i][j]); 
      if (j < 8) 
       ft_putchar(' '); 
      j++; 
     } 
     ft_putchar('\n'); 
     j = 0; 
     i++; 
    } 
} 

int  main(int argc, char **argv) 
{ 
    if (ft_check_input(argc, argv)) 
     ft_putstr("Error: not a good sudoku\n"); 
    else 
    { 
     if (solve(argv + 1, 0, 0)) 
     { 
      ft_print_sudoku(argv); 
      ft_putnbr(solve_count(argv + 1, 0, 0)); 
     } 
     else 
      ft_putstr("Error: no solution\n"); 
    } 
    return (0); 
} 

要獲得解決方案的編號爲空的數獨，你會跑（指空項目「」）：

./sudoku "........." "........." "........." "........." "........." "........." "........." "........." "........." 

它運行，但仍處於第一個找到的解決辦法停止，返回1 我錯過了什麼？我現在一直在撓頭。

最後我想通過添加隨機數來創建一個網格，直到只有一個解決方案。

Answer 1

我這樣做是很久以前的樂趣...

我做了什麼，以解決最困難的問題是返回每個廣場，所有可能的數字

再消滅每一個可能的一個數字每個網格一個...

所以，即使你得到9個可能性，你輸入第一個網格，如果它不適合。你刪除它並嘗試第二個。

其中一人需要太合身了:)

要懂得可以到soduku謎可能的解決方案存在，將採取強力計算。