솔루션 수를 반환하는 스도쿠 솔버

Question

기본 백 트랙킹 알고리즘을 사용하여 스도쿠 솔버를 만들었습니다. 많은 최적화가 이루어져야 합리적으로 잘 작동합니다.

주어진 스도쿠 격자에 대한 전체 솔루션 수를 반환하기 위해 코드를 수정하려고했습니다. 이렇게하기 위해 나는 간단히 해결 기능을 변경하여 하나에 멈추지 않고 모든 가능성을 추가했습니다.

그러나 나는 단지 1 얻거나 여기

0 기본적인 해석 코드입니다 :

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))); 
} 

: 여기

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))); 
} 

그리고 것은 솔루션을 계산해야 수정 된 기능입니다 다음

주() 및 헬퍼 기능은 다음

#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 퍼즐 가능한 솔루션은 그 무력 계산을 할 존재 수있는 방법을 알려면 :

에 맞게 너무 필요합니다.