c - 返回解数的数独求解器

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

main() 和辅助函数如下:

#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 种可能性，您也可以输入第一个网格，如果它不适合。您删除它并尝试第二个。

其中一个需要太合身:)

要了解数独谜题的可能解决方案，需要进行强力计算。