java - 计算给定数独谜题的解数？

Question

我正在开发一个基于网络的数独游戏，允许用户定制自己的数独板。我需要一种方法来告诉用户他组装的电路板有多少种可能的解决方案。数独具有唯一解的最少条目数是 17。我需要找到条目数小于 17 的解数。

这是我的方法:

public long numberOfSolutions (Board myBoard) {
    this.board = myBoard;
    this.tempBoard = new Board();
    long num = 0;

    tempBoard.copy(board);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board.getCell(i,j).equals(0)) {
                for(int k=1;k<10;k++){
                    board.setCell(i, j, k, true);
                    if(isCorrect() && solvable()){
                        num++;
                    }
                    board.copy(tempBoard);
                }
            }
        }
    }
    return num;
}

基本上，对于每个空单元格，我都会插入 1-9 之间的数字，并尝试解决每个数字的游戏问题。如果成功增加解决方案的数量。但这并没有让我得到所有可能组合的数量，而是每个单元格可以插入的数字的总和。

有什么方法可以计算吗？

Answer 1

答案是(可能):不要那样做。

数独解法是NP-complete , 所以解决一个可能需要一段时间，更不用说计算解决方案的数量了。

即使您尝试计算计数，它也可能非常大。一个什么都没有的数独板上有 6,670,903,752,021,072,936,960答案。