标签: sudoku

.

概述,样本

大家好,

我已经创建了一个基本的数独求解器,可以很快地解决大多数问题.我仍然需要做很多工作才能解决最棘手的问题,但我想首先尝试实现一个基本的JFrame GUI.

我过去曾使用过互联网小程序,但从未使用过JFrame.

我想创建类似于下图的内容(对于初学者):

-------------------------------------------------------------------------------------------------
! Sudoku Solver 1.0                                                                      - [] X !
-------------------------------------------------------------------------------------------------
!  _____________ _____________ _____________         _____________ _____________ _____________  !
! |  _   _   _  |  _   _   _  |  _   _   _  |       |  _   _   _  |  _   _   _  |  _   _   _  | !
! | !5! !_! !_! | !_! !_! !_! | !6! !_! !1! |       | !5! !7! !2! | !4! !9! !3! | !6! !8! !1! | …

是否有算法或方法我可以获得数独游戏的初始状态数独游戏.最好能否具有不同难度？

我希望为我的Sudoku Solver优化我的回溯算法.

它现在做了什么:

递归求解器函数采用具有各种给定值的数独谜题.

我将遍历拼图中的所有空槽,寻找可能性最小的槽,并获取值列表.

从值列表中,我将通过将列表中的一个值放入插槽中来循环遍历它,并递归地求解它,直到填满整个网格.

对于一些难题,这种实现仍然需要非常长的时间,我希望进一步优化这一点.有没有人有任何想法我怎么能够进一步优化这个？

如果您有兴趣,这是我的Java代码.

public int[][] Solve(int[][] slots) {
    // recursive solve v2 : optimization revision

    int[] least = new int[3];
    least[2] = Integer.MAX_VALUE;
    PuzzleGenerator value_generator = new PuzzleGenerator();
    LinkedList<Integer> least_values = null;

    // 1: find a slot with the least possible solutions
    // 2: recursively solve.

    // 1 - scour through all slots.
    int i = 0;
    int j = 0;
    while (i < 9) {
        j = 0;
        while (j < 9) {
            if …

我想在python中编写一个代码来解决数独谜题.你们对这个目的的好算法有什么想法吗？我在网上读了一个关于算法的地方,通过用所有可能的数字填充整个框来解决它,然后将已知值插入相应的框中.从已知值的行和列表中删除已知值.如果你们知道更好的话算法比这个请帮我写一个.另外,我很困惑,我应该如何读取用户的已知值.通过控制台逐个输入值非常困难.除了使用gui之外,还有什么简单的方法吗？

我是一个控制台数独求解器,其主要目标是原始速度.

我现在有一个ManagerThread,它启动WorkerThreads来计算每个单元格的neibhbors.因此,现在为每个单元启动一个WorkerThread.如何重新使用已完成其工作的现有线程？

线程池模式似乎是解决方案,但我不明白如何防止线程在其工作完成后死亡.

ps:我不希望这个特定任务获得太多性能,只是想在将多线程应用到更复杂的代码部分之前尝试多线程的工作原理.

谢谢

我的逻辑解算算法存在问题.它很好地解决了大量提示的谜题,它只有少于45条线索的谜题.

这是解决的算法.Immutable是一个布尔值,用于确定是否可以更改该值.cell [row] [col] .possibleValues是名为SudokuCell的类中的LinkedList,用于存储该网格元素可能存在的值.grid.sGrid是拼图的主要int [] []数组.removeFromCells()是一种从网格的行,列和象限中删除值的方法.该代码进一步提供.

第二个for循环仅用于检查单个解决方案.我决定避免递归,因为我真的无法理解它.这种方法现在似乎运作良好.

public boolean solve(){

    for(int i = 0; i < 81; i++){
        for(int row = 0; row < 9; row++){
            for(int col = 0; col < 9; col++){
                if(!immutable[row][col]){
                    if(cell[row][col].getSize() == 1){
                        int value = cell[row][col].possibleValues.get(0);
                        grid.sGrid[row][col] = value;
                        immutable[row][col] = true;
                        removeFromCells(row, col, value);
                    }
                }
            }
        }
    }


    int i = 0;
    for(int row = 0; row < 9; row++){
        for(int col = 0; col < 9; col++){
            if(grid.sGrid[row][col] == 0){ …

有没有算法解决任何传统的数独谜题,没有猜测？

在这里猜测意味着尝试一个候选人并看看它有多远,如果发现与猜测的矛盾,回溯到猜测步骤并尝试另一个候选人; 当所有候选人都没有成功时,请回溯到上一个猜测步骤(如果有的话;否则拼图证明无效.)等等.

编辑1:谢谢你的回复.

传统的数独意味着81-box数独,没有任何其他限制.让我们说我们知道解决方案是独一无二的,是否有任何算法可以保证在没有回溯的情况下解决它？回溯是一种通用工具,我没有任何问题,但是,使用通用工具来解决数独游戏会降低解密(手动或通过计算机)数独谜题的价值和乐趣.

一个人如何解决所谓的"世界上最难的数独",他需要猜测吗？

我听说一些研究人员意外发现他们的算法可以解决所有数据分析.这是真的,他们也必须猜测吗？

首先,我将说明这是一项大学任务,所以我不是要求别人为我编写代码,我只需要指向正确的方向.:)

好的,所以我需要编写一个算法来解决任意大小的任何(可解决的)数独板.我已经编写了一个递归功能,可以快速解决任何9x9电路板(约1ms),但是当我做大型电路板(16x16)很难解决时,它会挣扎......我已经进行了一次20分钟的测试,它可以'似乎解决了它.它可以解决简单的16x16谜题甚至是一个空白的16x16板,所以我不认为这是问题的维度..它更可能是我认为的问题算法.

无论如何,这是我的程序的基本逻辑..

• 我有一个3D矢量,存储我每个方格的可能值
• 当一个值放在一个正方形中时,它将从它所在的周围正方形,行和列的可能值中删除

然后我的解决功能基本上是:

bool solve() {

    if (there are no unfilled squares)
        return true

    if (the board is unsolvable - there are empty squares that have no possible values)
        return false

    while (there are empty squares)
    {
        int squaresFilled = fillSquaresWithOnlyOneChoice(); //this method updates the possible results vector whenever it fills a square

        if (squaresFilled == 0)
            break;
    }

    //exhausted all of the 'easy' squares (squares with only one possible choice), need to make a guess

    while …

两天前，我收到了一个我试图用 Python 3 解决的数独问题。我被告知确实存在一个解决方案，但我不确定是否存在多个解决方案。

问题如下： 一个 9x9 的数独网格是完全空的。然而，它确实包含彩色框，并且在这些框内，数字的总和必须是平方数。除此之外，正常的数独规则适用。

这里的问题不是解决数独谜题，而是生成一个满足彩色框规则的可行谜题。

我的策略

使用 numpy 数组，我将网格划分为 81 个索引，这些索引可以重新排列为 9x9 网格。

import numpy as np
print(np.array([i for i in range(81)]).reshape((9, 9)))

->
[[ 0  1  2  3  4  5  6  7  8]
 [ 9 10 11 12 13 14 15 16 17]
 [18 19 20 21 22 23 24 25 26]
 [27 28 29 30 31 32 33 34 35]
 [36 37 38 39 …

我正在寻找"你如何找到它",因为我不知道如何找到我的程序的算法复杂性.

我用java编写了一个数独求解器,没有效率(我想尝试让它递归工作,我成功了!)

一些背景:

我的策略采用回溯来确定,对于给定的数独谜题,谜题是否只有一个独特的解决方案.所以我基本上阅读了一个给定的谜题并解决它.一旦我找到了一个解决方案,我不一定完成,需要继续探索进一步的解决方案.最后,三种可能的结果之一发生:难题根本无法解决,拼图有独特的解决方案,或者拼图有多种解决方案.

我的程序从一个文件中读取拼图坐标,该文件对于每个给定的数字有一行,包括行,列和数字.根据我自己的惯例,7的左上角正方形写为007.

执行:

我从文件中加载值,并将它们存储在二维数组中,然后沿阵列向下,直到找到空白(未填充的值),并将其设置为1.并检查是否有任何冲突(值是否为i输入有效或无效).如果是,我转到下一个值.如果不是,我将值递增1,直到找到一个有效的数字,或者如果它们都不起作用(1到9),我返回1步到我调整的最后一个值,然后递增该值(使用递归) ).当所有81个元素都被填满时,我完成了解决,没有冲突.如果找到任何解决方案,我将它们打印到终端.否则,如果我尝试在我最初修改的FIRST元素上"返回一步",则意味着没有解决方案.

我的程序如何算法复杂度？我认为它可能是线性的[O(n)],但我多次访问该数组,所以我不确定:(

任何帮助表示赞赏