标签: sudoku

我正在做一个有趣的项目:使用OpenCV从输入图像中解决数独(如Google护目镜等).我完成了任务,但最后我发现了一个问题,我来到这里.

我使用OpenCV 2.3.1的Python API进行编程.

以下是我的所作所为:

1. 阅读图片
2. 找到轮廓
3. 选择具有最大面积的那个(并且也有点等于正方形).

4. 找到角点.

   例如,如下:

   

   (请注意,绿线正确地与Sudoku的真实边界重合,因此可以正确扭曲数独.查看下一张图片)

5. 将图像扭曲成完美的正方形

   例如:

   

6. 执行OCR(我使用我在OpenCV-Python中的简单数字识别OCR中给出的方法)

而且方法效果很好.

问题:

看看这个图像.

在此图像上执行第4步,结果如下:

绘制的红线是原始轮廓,它是数独边界的真实轮廓.

绘制的绿线是近似轮廓,它将是扭曲图像的轮廓.

当然,在数独的上边缘绿线和红线之间存在差异.因此,在翘曲时,我没有得到数独的原始边界.

我的问题 :

如何在数独的正确边界上扭曲图像,即红线,或者如何消除红线和绿线之间的差异？在OpenCV中有没有这方法？

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

有没有人知道一个简单的算法来检查数独配置是否有效？我提出的最简单的算法是(对于一个大小为n的板)Pseudocode

for each row
  for each number k in 1..n
    if k is not in the row (using another for-loop)
      return not-a-solution

..do the same for each column

但我确信必须有一个更好的(在更优雅的意义上)解决方案.效率非常不重要.

我正在用Java编写一个用于9x9网格的数独求解器.

我有方法:

• 打印网格

• 用给定的值初始化电路板

• 测试冲突(如果相同的数字在同一行或3x3子网格中)

• 一种逐个放置数字的方法,这需要最多的工作.

在我详细介绍该方法之前,请记住我必须使用递归来解决它,以及回溯(在这里观看applet作为示例http://www.heimetli.ch/ffh/simplifiedsudoku.html)

此外,我正在通过垂直向下移动来解决这个数独,从左上角开始,到第一列,然后到第二列,等等.

到目前为止,我有以下内容:

public boolean placeNumber(int column){

    if (column == SUDOKU_SIZE){  // we have went through all the columns, game is over

        return true;

    }

    else
    {
        int row=0;  //takes you to the top of the row each time

        while (row < SUDOKU_SIZE)    loops through the column downwards, one by one
        {

            if (puzzle[row][column]==0){  //skips any entries already in there (the given values)

                puzzle[row][column]=1;   //starts with one

                while(conflictsTest(row,column)){   //conflictsTest is the method …

我一直在研究数独求解器,我现在的求解器使用回溯算法,但它仍然需要很长时间.

我希望在大多数情况下将其降低到不到一秒钟.因此,我决定使用跳舞链接算法重写它,理解它是更好的强力方法之一,特别是对于诸如Sudoku Puzzle之类的约束问题.

我试图阅读Wiki和Knuth的论文,但是它们都难以理解并且非常冗长.

我还阅读了Sudopedia的版本,似乎一旦它进入数独的实现,它就太抽象了.

有人可以尝试解释Dancing Links算法,而不是根据其推导而是实现吗？(以Sudoku为例非常棒)

谢谢!

过去几天我一直在尝试从图片中获取数独网格，并且一直在努力获取网格的较小方块。我正在处理下面的图片。我认为用精明的过滤器处理图像会正常工作，但它没有，我无法获得每个正方形的每个轮廓。然后我将自适应阈值、otsu 和经典阈值化进行测试，但每次似乎都无法捕捉到每个小方块。

最终目标是获取包含数字的单元格，并使用 pytorch 识别数字，所以我真的很想拥有一些干净的数字图像，这样识别就不会出错:)

有没有人知道如何实现这一目标？非常感谢！:D

我正在阅读这里发布的一个问题:C#中的数独算法

其中一个解决方案是这段代码.

public static bool IsValid(int[] values) {
        int flag = 0;
        foreach (int value in values) {
                if (value != 0) {
                        int bit = 1 << value;
                        if ((flag & bit) != 0) return false;
                        flag |= bit;
                }
        }
        return true;
}

这个想法是它将检测值数组中的重复项; 但是我不知道有多少我不知所措.谁可以给我解释一下这个？

编辑:谢谢大家.这么多很棒的答案,我不知道如何选择一个.它现在非常有意义.

我有一个家庭作业来编写一个多线程的数独求解器,它找到给定谜题的所有解决方案.我以前写过一个非常快速的单线程回溯数独求解器,所以我不需要任何帮助解决数独问题.

我的问题可能与不真正的并发性有关,但我不知道这个问题如何从多线程中受益.我不明白如何在不保留拼图的多个副本的情况下同时找到同一问题的不同解决方案.鉴于这种假设(请证明它是错误的),我没有看到多线程解决方案如何比单线程更有效.

我很感激,如果有人能给我一些算法的开始建议(请,没有代码......)

我忘了提到,要使用的线程数被指定为程序的参数,所以据我所知,它与任何方式的拼图状态无关......

此外,可能没有一个独特的解决方案 - 有效的输入可能是一个完全空的板.我必须报告min(1000, number of solutions)并显示其中一个(如果存在)

我正在用Javascript编写一个有趣的数独游戏.
一切都很好,每次都用一个解决方案完全生成电路板.

我唯一的问题是,这就是让我从公开发布我的项目的原因
是我不知道如何评估我的电路板的难度等级.我在任何地方都看过,
发布在论坛上等等.我不想自己编写算法,这不是这个项目的重点,
除此之外,它们对我来说太复杂了,因为我不是数学家.

我唯一接近的是这个网站,它通过JS进行评分,
但问题是,代码是用一种糟糕的无证,非常特别的方式编写的,
因此无法借用......

我会谈到这一点 -
任何人都可以请我指向一个提供Sudoku评级/评级源代码的地方吗？

谢谢

更新22.6.11:
这是我的数独游戏,我已经实现了自己的评分系统,它依赖
于基本的人工逻辑解决技术,所以请查看它.

介绍

有效的数独网格填充数字1到9,在9,行或列的每个子块中没有数字出现多次.如果您不熟悉这个流行的谜题,请阅读本文以获取更多详细信息.

挑战

挑战是编写最短的程序来验证可能未满的Sudoku网格.

输入将是一行9行,每行9个字符,代表网格.空单元格将由a表示..您的输出应该是Valid网格有效,否则输出Invalid.

例

输入

123...789
...456...
456...123
789...456
...123...
564...897
...231...
897...564
...564...

产量

Valid

输入

123456789
987654321
123456789
123456789
987654321
123456789
123456789
987654321
123456789

产量

Invalid

代码高尔夫规则

请以解决此问题的任何语言发布您的最短代码.输入和输出可以通过stdin和stdout或您选择的其他文件来处理.

获胜者将是在发布此问题之前存在实现的语言中最短的解决方案(按字节数).因此,虽然您可以自由地使用您刚刚编写的语言来提交一个0字节的解决方案,但它不会计算,您可能会得到downvotes.