标签: sudoku

有多少可能的独特方式来产生数独谜？我只想到两种可能的方法1)采取一个解决的数独谜题并洗牌行和列2)生成一个随机数并检查它是否违反任何数独约束,重复直至数字不违反每个方格的任何数独约束(理论上可能,但通常会导致死锁)

还有其他方法吗？

我正在寻求实现一个非常简单的算法,该算法使用强力反向跟踪来解决数独网格.我现在面临的问题是,我在执行中,我有两个实例变量Sudoku称为类row和col,对应于空单元格的行和列在代表数独网格二维数组.

当我的solve()方法执行时,它首先检查是否没有任何空单元格,在这种情况下拼图已经完成.否则,同一方法将空单元格的行和列分配给实例变量row和包含网格col的Sudoku对象.之后,for循环验证通过方法调用可以在该空单元格中放置哪个数字isSafe(int n)(此方法检查是否满足拼图的约束,我可以保证它完美地运行).因此,该isSafe()方法在空单元格中放置一个数字,然后solve()在该Sudoku对象上再次对该方法进行递归调用.

如果我们遇到了无法满足的约束,那么我们将a重新分配0给最后一个row并且col填充了.这就是问题所在!由于程序不断更新row和col变量,因此每次递归调用都会丢失旧实例.我一直在试图弄清楚如何存储这些值,以便程序可以在回溯时撤消操作.我想过互推col及row到堆栈,但我真的不知道该去哪里.

有人能告诉我解决这个问题的简单方法是什么？我不包括整个班级,如果你觉得它有用,请告诉我,我会发布.

class Sudoku {
    int SIZE, N, row, col;
    int Grid[][];    

    public boolean solve() {
        if (!this.findNextZero()) return true;

        for (int num = 1; num <= 9; num++) {
            if (isSafe(num)) {
                this.Grid[this.row][this.col] = num;

                if (this.solve()) return true;

                this.Grid[this.row][this.col] …

这是Pramp的问题。我需要确定数独功能是否可解决（与LEETcode问题不同，我只需要查看电路板是否有效）。

下面是我使用递归的JavaScript代码。我遵循Pramp上建议的逻辑，即创建一个辅助函数getCandidates（）来查找可以进入空白空间的所有候选编号。然后，在实际的sudokuSolve（）函数中，找到候选集最小的空白空间，将这些候选内容输入空白空间，然后尝试使用递归求解电路板。如果可行，则该板是可解决的。

我的代码每次都是正确的，我找不到问题。我已经研究了互联网上提出的其他类似问题，但大多数问题都是为数独板找到确切的解决方案或生成数独板。我只需要查看一块木板是否可解决。如果可以的话，请告诉我我的代码哪里有错，我将非常感谢。

无论测试案例是什么，我现在每次都得到“ true” ...对于提供的这个测试案例，答案应该为false。

const test02 = [
  ['.', '8', '9', '.', '4', '.', '6', '.', '5'],
  ['.', '7', '.', '.', '.', '8', '.', '4', '1'],
  ['5', '6', '.', '9', '.', '.', '.', '.', '8'],
  ['.', '.', '.', '7', '.', '5', '.', '9', '.'],
  ['.', '9', '.', '4', '.', '1', '.', '5', '.'],
  ['.', '3', '.', '9', '.', '6', '.', '1', '.'],
  ['8', '.', '.', '.', '.', '.', '.', '.', '7'],
  ['.', '2', '.', '8', '.', '.', '.', …

根据上图中的坐标，我希望能够计算出所选单元格属于哪个以红色突出显示的“正方形”。

我正在解决一个数独难题，并​​且可以访问每个正方形的宽度以及单元格所在的行/列。

我在计算单元格所属的正方形的“编号”时遇到困难（它们从 1 开始，从左到右、从上到下递增），因此上面的正方形的编号为：

1|2
3|4

我该如何计算呢？任何建议，将不胜感激。要么是 Java 特定的方法，要么只是一个算法就可以了:)

我正在尝试编写一个算法,用Java或Javascript创建一个合法的数独板.既不工作,也不完全确定原因.

从本质上讲,两个程序中的问题是x或y的增加量超过它应该增加(跳过正方形).我不能为我的生活弄清楚这是怎么回事.如果需要,我可以提供完成JS解决方案的HTML.

我最好的猜测是它与我如何使用递归创建堆栈有关,但据我所知,它应该工作.在我的旧代码中有一个不正确的for循环,我知道这一点.我粘贴了一个旧版本,现在已经修好了.

Java的:

import java.util.*;

public class SudokuGenerator
{
//credit:cachao
//http://stackoverflow.com/questions/9959172/recursive-solution-to-sudoku-generator
public static final int BOARD_WIDTH = 9;
public static final int BOARD_HEIGHT = 9;

public SudokuGenerator() {
    board = new int[BOARD_WIDTH][BOARD_HEIGHT];
}
//Recursive method that attempts to place every number in a square
public int[][] nextBoard()
{
    nextBoard(0,0);
    return board;
}

public void nextBoard(int x, int y)
{
    int nextX = x;
    int nextY = y;
    //int[] toCheck = Collections.shuffle(Arrays.asList({1,2,3,4,5,6,7,8,9}));
    int[] toCheck = {1,2,3,4,5,6,7,8,9};
    Collections.shuffle(Arrays.asList(toCheck));

    for(int …

所以,我已经完成了对数独谜题生成的一些阅读.据我所知,具有所需难度的数独谜题的标准方法是生成谜题,然后对其进行评分,并重复直到您具有可接受的评级之一.这可以通过使用一些更复杂的解决模式(XY翼,箭鱼等)生成回溯来改进,但这不是我想要在这里做的.

我想做的,但一直无法找到任何真正的资源,是从"难度值"生成一个谜题(0-1.0值,0是最简单的,1.0是最难的).

例如,我想创建一个中等难度的谜题,因此选择值.675.现在使用该值我希望能够产生一个中等难度的谜题.

有人知道这样的事吗？或者也许有类似方法的东西？

如果Sudoku难题有一个独特的解决方案,那么它是最小的(也称为不可简化的),但删除任何数字都会产生一个包含多个解决方案的难题.换句话说,每个数字都是确定解决方案所必需的.

我有一个基本算法来生成最小的Sudokus:

• 生成完整的拼图.
• 以随机顺序访问每个单元格.对于每个访问过的小区
  • 暂时删除它的数字
  • 使用递归回溯算法解决两次拼图.一个求解器以正向顺序尝试数字1-9,另一个以相反的顺序尝试.从某种意义上说,求解器遍历包含所有可能配置的搜索树,但来自相对的两端.这意味着如果拼图具有独特的解决方案,这两个解决方案将匹配.
  • 如果拼图有独特的解决方案,请永久删除数字; 否则,把它放回去.

这种方法可以保证产生最小的拼图,但它很慢(我的电脑上100毫秒,智能手机上几秒钟).我想减少解决方案的数量,但我能想到的所有显而易见的方法都是不正确的.例如:

• 添加数字而不是删除它们. 这样做的好处是,由于最小的谜题需要至少17个填充数字,前17个数字保证不具有独特的解决方案,减少了解决的数量.不幸的是,由于以随机顺序访问单元格,因此在"锁定"唯一解决方案的一个重要数字之前将添加许多不必要的数字.例如,如果添加的前9个单元格都在同一列中,则存在大量冗余信息.
• 如果没有其他数字可以替换当前数字,请将其保留并且不解决难题.因为检查展示位置是否合法是比解决拼图两倍快几千倍,这可能会节省大量时间.但是,仅仅因为没有其他合法数字现在并不意味着一旦我们删除其他数字就不会有.
• 由于我们生成了原始解决方案,因此只针对每个单元解决一次,看它是否与原始单元匹配.这不起作用,因为原始解决方案可能位于搜索树中可能解决方案的任何位置.例如,如果原始解决方案靠近树的"左"侧,并且我们从左侧开始搜索,我们将错过树右侧的解决方案.

我还想优化求解算法本身.困难的部分是确定解决方案是否是唯一的.我可以进行微观优化,例如为每个单元格创建一个合法位置的位掩码,如这篇精彩的帖子所述.然而,诸如Dancing Links或模拟退火之类的更高级算法并不是为了确定唯一性而设计的,而只是为了找到任何解决方案.

如何优化我的最小数独生成器？

我的数独求解方法存在问题.该计划的工作方式如下; 当电路板启动时,它是空的,用户在电路板上添加了几个数字,然后点击一个Solve按钮,程序试图解决它.如果我将相同的数字放在同一行中,一切正常.因此,如果用户添加1,1,0,0 ... 0.在拼图中它无法解决它,因为它的两个1彼此相邻并且将继续尝试找到一个沉闷,即使它是无法解决的难题.但是,如果它们都是0(空),它将立即解决它,就像Id在左上角放置1和2一样.如果我只是在其中放入一些随机数将检测到它无法解决(或者如果它是一个有效的谜题将解决它)

我正在考虑说什么theNumber == (row, col) equals thenNumber == (row+1, col),它应该return false是因为它是一个重复的数字.

这是我试图在solve方法中添加的代码,显然没有成功.

if ((puzzle.getNum(row, col) == a) == (puzzle.getNum(row + 1, col) == a)) {
   return false;
}

非常感谢帮助

我正在尝试生成一个完整的(即每个单元格中填充一个数字)类似Sudoku的板.这是与sudokus无关的其他东西,所以我对达到可以解决的白色方块或与sudokus有关的任何东西都不感兴趣.不知道你是否知道我的意思.

我在java中完成了这个:

private int sudokuNumberSelector(int x, int y, int[][] sudoku) {


    boolean valid = true;
    String validNumbers = new String();
    int[] aValidNumbers;
    int squarexstart = 0;
    int squareystart = 0;
    int b = 0;                          // For random numbers
    Random randnum = new Random();
    randnum.setSeed(new Date().getTime());

    // Check numbers one by one
    for(int n = 1; n < 10; n++) {

        valid = true;

        // Check column
        for(int i = 0; i < 9; i++) {
            if(sudoku[i][y] == n) {
                valid …

我查看了手册和文档,但仍然不明白.我正在尝试实现一个数独解决方案,在写出游戏的所有其他规则后,我根据老师的指示添加了标签(Board).

但是我仍然没有得到它的工作原理或它正在做什么.不应该有其他约束(我有检查说数字必须是1..9,行必须全部不同,等等)给我自己的答案？