algorithm - 数独板检查算法 - 除了重复之外还有什么要检查的吗？

Question

我做了一个算法来检查棋盘是否非法，它检查行、列和扇区中的重复项，它对重复项很有效，但经过几场比赛后我得到了以下棋盘:

没有解决方案(没有 B5 和 A7 的候选项)但没有重复项。我们是否总是需要检查是否没有候选人以及检查重复项？还有什么要检查的吗？

Answer 1

只需检查重复项就可以让您证明明显的非法填充案例。

恐怕你必须尝试解决数独板才能证明部分填充是合法的，即有解决方案。找到一个解决方案就足够了，但可能还有其他解决方案。找到所有解决方案并不难。

对于您提供的情况来说，证明没有解决方案很容易，一步就会导致失败(单元格 A7 的所有可能解决方案都会产生重复)，但在一般情况下可能会更复杂，因为它需要多个步骤。

蛮力方法(例如尝试每个空方 block 的所有可能性并递归)具有可怕的复杂性。您可以在 Internet 上找到快捷方式并使用您自己的代码进行研究。

编辑:如有疑问，请尝试暴力破解!数独在一般情况下可能是 NP-Complete，但在实践中它似乎并没有显着发散。我反射(reflection)了上面的初步分析，并决定尝试一下蛮力。我写了一个小程序来解决命令行上给出的数独问题。即使在我的旧 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 使程序查找所有解决方案并打印找到的总数。正如预期的那样，时间随着空单元格的数量呈指数增长。但只有当董事会还不到半满并且有很多解决方案时，它们才会变得重要。