如何使用独特的解决方案生成数独板

Question

如何使用独特的解决方案生成数独板？我想的是初始化一个随机板然后删除一些数字.但我的问题是如何保持解决方案的独特性？

Answer 1

这是我自己的SuDoKu程序的方式:

1. 从一个完整有效的电路板(填充81个数字)开始.

2. 列出所有81个单元格位置并随机随机播放.

3. 只要列表不为空,请从列表中取出下一个位置,然后从相关单元格中删除该编号.

4. 使用快速回溯求解器测试唯一性.理论上,我的解算器能够计算所有解决方案,但是为了测试唯一性,它会在找到多个解决方案时立即停止.

5. 如果当前电路板仍然只有一个解决方案,请转到步骤3)并重复.

6. 如果当前电路板有多个解决方案,请撤消上次移除(步骤3),然后从列表中的下一个位置继续执行步骤3

7. 当您测试了所有81个位置时停止.

这不仅为您提供了独特的电路板,而且还为您提供了无法在不破坏解决方案独特性的情况下再删除任何数字的电路板.

当然,这只是算法的后半部分.前半部分是首先找到一个完整有效的板(随机填充!)它的工作方式非常相似,但"在另一个方向":

1. 从空板开始.

2. 在其中一个空闲单元格中添加一个随机数(随机选择该单元格,并根据SuDoKu规则从该单元格的有效数字列表中随机选择该数字).

3. 使用回溯解算器检查当前板是否至少有一个有效的解决方案.如果不是,请撤消步骤2并重复另一个数字和单元格.请注意,此步骤可能会自行生成完整的有效板,但这些板并非随机.

4. 重复直到电路板完全充满数字.

Answer 2

简单:

1. 使用高效的回溯算法找到所有解决方案.
2. 如果只有一个解决方案,那么你就完成了.否则,如果您有多个解决方案,请找到大多数解决方案不同的位置.在此位置添加号码.
3. 转到1.

我怀疑你能找到比这更快的解决方案.

Answer 3

你可以作弊.从现有的数独板开始,然后可以解决它.

您可以将三个3x3块的任意行与任何其他行交换.您可以将三个3x3块的任何列与另一列交换.在每个块行或块列中,您可以交换单行和单列.最后,您可以对数字进行置换,因此只要整个板上的排列一致,填充位置就会有不同的数字.

这些变化都不会使可解决的电路板无法解决.

Answer 4

这样您就可以生成任何可能的数独板以及任何其他 nxn 数独板

至于这个算法的效率如何，在java中生成一百万个板需要3.6秒，在golang中需要3.5秒

1. 找到任何填满的数独板。（使用琐碎的不会影响最终结果）

int[][] board = new int[][] {
                {1,2,3,  4,5,6,  7,8,9},
                {4,5,6,  7,8,9,  1,2,3},
                {7,8,9,  1,2,3,  4,5,6},

                {2,3,1,  5,6,4,  8,9,7},
                {5,6,4,  8,9,7,  2,3,1},
                {8,9,7,  2,3,1,  5,6,4},

                {3,1,2,  6,4,5,  9,7,8},
                {6,4,5,  9,7,8,  3,1,2},
                {9,7,8,  3,1,2,  6,4,5}
        };

2. 对于从 1 到 9（例如 num）的每个数字（即 1、2、3、5、6、7、8、9），从 [1 到 9] 范围内随机取一个数字，遍历棋盘，将 num 与您的值交换随机数。

void shuffleNumbers() {
        for (int i = 0; i < 9; i++) {
            int ranNum = random.nextInt(9);
            swapNumbers(i, ranNum);
        }
    }

private void swapNumbers(int n1, int n2) {
    for (int y = 0; y<9; y++) {
        for (int x = 0; x<9; x++) {
            if (board[x][y] == n1) {
                board[x][y] = n2;
            } else if (board[x][y] == n2) {
                board[x][y] = n1;
            }
        }
    }
}

3. 现在洗牌。取出第一组 3 行，将它们打乱，然后对所有行执行此操作。（在 9 X 9 数独中），为第二组和第三组执行此操作。

void shuffleRows() {
        int blockNumber;

        for (int i = 0; i < 9; i++) {
            int ranNum = random.nextInt(3);
            blockNumber = i / 3;
            swapRows(i, blockNumber * 3 + ranNum);
        }
    }

void swapRows(int r1, int r2) {
        int[] row = board[r1];
        board[r1] = board[r2];
        board[r2] = row;
    }

4. 交换列，再次取出 3 列的块，将它们打乱，并对所有 3 个块执行此操作

void shuffleCols() {
        int blockNumber;

        for (int i = 0; i < 9; i++) {
            int ranNum = random.nextInt(3);
            blockNumber = i / 3;
            swapCols(i, blockNumber * 3 + ranNum);
        }
    }
void swapCols(int c1, int c2) {
        int colVal;
        for (int i = 0; i < 9; i++){
            colVal = board[i][c1];
            board[i][c1] = board[i][c2];
            board[i][c2] = colVal;
        }
    }

5. 交换行块本身（即 3X9 块）

void shuffle3X3Rows() {

        for (int i = 0; i < 3; i++) {
            int ranNum = random.nextInt(3);
            swap3X3Rows(i, ranNum);
        }
    }

void swap3X3Rows(int r1, int r2) {
        for (int i = 0; i < 3; i++) {
            swapRows(r1 * 3 + i, r2 * 3 + i);
        }
    }

6. 对列执行相同操作，按块交换

void shuffle3X3Cols() {

        for (int i = 0; i < 3; i++) {
            int ranNum = random.nextInt(3);
            swap3X3Cols(i, ranNum);
        }
    }
private void swap3X3Cols(int c1, int c2) {
        for (int i = 0; i < 3; i++) {
            swapCols(c1 * 3 + i, c2 * 3 + i);
        }
    }

现在你已经完成了，你的棋盘应该是一个有效的数独棋盘

要生成具有隐藏值的棋盘，可以使用回溯数独算法来完成，该算法尝试从棋盘中删除一个元素，直到您拥有一个可解的棋盘，删除直到它变得不可解，即使您只删除一个元素。

如果你想按难度对最终生成的棋盘进行分类，只需在逐个删除元素的同时计算棋盘中还剩下多少个数字即可。数字越少，解决起来就越困难

数独中最少可能的提示可以是 17 个，但所有可能的数独板不一定能简化为 17 个提示数独

Answer 5

除非P = NP,否则没有多项式时间算法可以用一个解决方案生成一般的数独问题.

在他的硕士论文中,Takayuki Yato定义了另一个解决方案问题(ASP),其目标是,在给出问题和解决方案的情况下,找到针对该问题的不同解决方案或表明不存在问题.Yato然后定义了ASP完整性,难以找到另一个解决方案的问题,并表明Sudoku是ASP完成的.由于他也证明ASP完全性意味着NP硬度,这意味着如果你允许任意大小的数独板,没有多项式时间算法来检查你生成的拼图是否有一个独特的解决方案(除非P = NP).

抱歉,破坏了快速算法的希望!

Answer 6

解决方案分为2部分：
A.生成6000亿的数字模式
B.生成掩码模式 ~7e23组合

A）对于数字图案可产生具有独特的组合的最快方式NO时间花费在回溯或测试

步骤 1. 选择一个已经存在的矩阵，我选择了下面的矩阵，因为它可以由人类轻松制作，无需计算设备或求解器的任何帮助：

第一行是升序数字
第二行也是升序但从4开始滚动
第三行也是升序但从7开始滚动
第4、5、6行：用顶部替换三个单元格列右列 - 2 5 8 并在最后一列的 3x3 单元格内滚动
第 7,8,9 行：将三个单元格列替换为右上角的列 - 3 6 9 并在最后一列的 3x3 单元格内滚动

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5

步骤 2. 打乱数字并替换所有其他单元格
步骤 3. 随机重新排列列 1,2 和 3
步骤 4. 随机重新排列列 4,5 和列 6
步骤 5. 随机重新排列列 7,8 和 9
第 6 步。在它们自身内部随机重新排列第 1,2 和 3 行
第 7 步。在它们自身内部随机重新排列第 4,5 和 6 行
第 8 步。在它们自身内部随机重新排列第 7,8 和 9 行
第 9 步。在 3 个列组中随机重新排列大小为 9x3
步骤 10. 随机重新排列为大小为 3x9 的3 行组

瞧...

5 8 3 1 6 4 9 7 2
7 2 9 3 5 8 1 4 6
1 4 6 2 7 9 3 8 5
8 5 2 6 9 1 4 3 7
3 1 7 4 2 5 8 6 9
6 9 4 8 7 2 5 1
4 6 5 9 1 3 7 2 8
2 3 1 7 8 6 5 9 4
9 7 8 5 4 2 6 1 3

B ) 对于掩蔽模式，我们需要有一个求解器算法。由于我们已经有一个非常独特的数字网格（也已解决！），这为我们使用求解器提供了更快的性能

步骤 1：从 81 个随机位置中选择 15 个开始。
步骤 2：与求解器检查是否有唯一解
步骤 3：如果解不唯一，则选择附加位置。迭代第 2 步和第 3 步，直到找到唯一的解决方案

这应该为您提供非常独特且快速的数独板。