数独棋盘检查算法 - 除了重复以外还有其他需要检查的吗？

Question

数独棋盘检查算法 - 除了重复以外还有其他需要检查的吗？

algorithmsudoku

3

我制作了一个算法来检查棋盘是否合法，它会检查每行、每列和每个区域中是否有重复项。对于重复项，它运行良好，但是在几局游戏后，我遇到了以下棋盘： enter image description here

这个棋盘没有解决方案（B5和A7没有候选数字），但是没有重复项。我们是否总是需要在检查重复项的同时检查是否存在候选数字？还有其他需要检查的内容吗？

- shinzou

这个案例很容易检查，只需为所有空单元格的候选项创建一个位掩码，如果它们中的任何一个为空，则为无效棋盘。然而，棋盘无效可能还有其他原因。 - harold

@哈罗德，还有其他原因吗？ - shinzou

很多。例如，想象一行中有3个空单元格（由于其余部分的配置），每个单元格只有可能是{1, 2}。但是3个单元格中的两个可能性意味着1个单元格永远无法获得任何值。这实际上也很容易检测到，但也有一些难以检测的原因。 - harold

只是一点小提示：数独问题是NP难问题（当你将其推广到任意边长的正方形时）。 - G. Bach

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- chqrlie · Accepted Answer

只要检查重复项，就能证明非法填充的明显情况。

很遗憾，你必须尝试解决数独棋盘，才能证明部分填充的合法性，也就是有解。找到一个解足以，但可能还有其他解。找到所有解并不更难。

对于您提供的情况，证明没有解很容易（单个步骤导致失败，A7单元格的所有可能解产生重复），但在一般情况下可能更复杂，因为需要多个步骤。

采用蛮力方法，如为每个空方格尝试每种可能性并进行递归，其复杂度极高。您可以在互联网上找到快捷方法，并使用自己的代码进行研究。

编辑：如果不确定，请尝试蛮力！在一般情况下，数独可能是NP-Complete问题，但实际上它似乎并不会发散太多。我反思了我以上的初步分析，决定尝试蛮力。我编写了一个小程序来解决在命令行中给出的数独。即使在我的老MacBook Air上，它也可以在几毫秒内解决我尝试的所有问题。

再次编辑：我用更好的算法更新了代码，并且速度接近快了80倍。

以下是代码：

/* Generic Sudoku solver by Charles Gordon */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifndef GEN
#define GEN   3
#endif
#define SIZE  (GEN*GEN)

typedef unsigned char u8_t;
typedef unsigned long long llu_t;

static int print_count = 0, print_solutions = 1;

/* utility arrays to dispatch cell number to signature arrays */
static int rowsig[SIZE * SIZE], colsig[SIZE * SIZE], regsig[SIZE * SIZE];

static void sigcell_init() {
    for (int i = 0, row = 0; row < SIZE; row++) {
        for (int col = 0; col < SIZE; col++, i++) {
            rowsig[i] = row;
            colsig[i] = SIZE + col;
            regsig[i] = SIZE + SIZE + (row / GEN) * GEN + (col / GEN);
        }
    }
}

static void print_board(const int *board, const char *header) {
    printf("%s:\n", header);
    for (int i = 0, row = 0; row < SIZE; row++) {
        for (int col = 0; col < SIZE; col++, i++)
            printf("%*.0d", 2 + (SIZE > 9) + (SIZE > 99), board[i]);
        putchar('\n');
    }
}

static int validate_board(const int *board, u8_t sigs[3 * SIZE][SIZE]) {
    memset(sigs, 0, 3 * SIZE * SIZE * sizeof(sigs[0][0]));
    for (int i = 0; i < SIZE * SIZE; i++) {
        int val = board[i];
        if (val == 0)
            continue;
        if (val < 0 || val > SIZE)
            return 2;  /* found invalid value */
        val -= 1;
        if (sigs[rowsig[i]][val] | sigs[colsig[i]][val] | sigs[regsig[i]][val])
            return 1;  /* found duplicate */
        sigs[rowsig[i]][val] = sigs[colsig[i]][val] = sigs[regsig[i]][val] = 1;
    }
    return 0;  /* board is valid */
}

static llu_t try_board(int *board, u8_t sigs[3 * SIZE][SIZE], int *empty, int emp) {
    llu_t count, total = 0;
    int n, cell;
    u8_t *rowsigp, *colsigp, *regsigp;

    if (emp == 0) {
        if (print_solutions)
            print_board(board, "found a board solution");
        return 1;
    }

    cell = *empty; /* next cell to try and populate */
    rowsigp = sigs[rowsig[cell]];
    colsigp = sigs[colsig[cell]];
    regsigp = sigs[regsig[cell]];
    for (n = 0; n < SIZE; n++) {
        /* check if value is possible */
        if ((rowsigp[n] | colsigp[n] | regsigp[n]) == 0) {
            rowsigp[n] = colsigp[n] = regsigp[n] = 1;
            board[cell] = n + 1;
            if ((count = try_board(board, sigs, empty + 1, emp - 1)) > 0) {
                total += count;
                if (!print_count)
                    break;
            }
            rowsigp[n] = colsigp[n] = regsigp[n] = 0;
            board[cell] = 0;
        }
    }
    return total;
}

int main(int argc, char *argv[]) {
    int board[SIZE * SIZE];   /* board values: empty=0 */
    u8_t sigs[3 * SIZE][SIZE];  /* signatures for row, col and regions */
    int empty[SIZE * SIZE];   /* list of empty cells */
    int i, n;
    llu_t count = 0;

    sigcell_init();

    /* initialize board */
    for (i = 1, n = 0; i < argc; i++) {
        if (!strcmp(argv[i], "-a")) {
            print_count = 1;
            print_solutions = 0;
            continue;
        }
        if (n < SIZE * SIZE)
            board[n++] = atoi(argv[i]);
    }
    while (n < SIZE * SIZE)
        board[n++] = 0;

    print_board(board, "initial board");

    if (validate_board(board, sigs)) {
        printf("board is invalid\n");
        return 1;
    }
    /* compute list of empty cells */
    for (i = n = 0; i < SIZE * SIZE; i++) {
        if (board[i] == 0)
            empty[n++] = i;
    }
    if ((count = try_board(board, sigs, empty, n)) == 0) {
        printf("board does not have solutions\n");
        return 1;
    }
    if (print_count) {
        printf("total board solutions: %llu\n", count);
    }
    return 0;
}

传递一个命令行选项-a，使程序查找所有解并打印总数。如预期的那样，随着空单元格数量的增加，计时呈指数级增长。但只有当棋盘填充不到一半且有许多解决方案时，计时才变得显著。