Sudoku生成器的递归解决方案

Question

我正在尝试编写一个算法,用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 i=0;i<toCheck.length;i++)
    {
        if(legalMove(x, y, toCheck[i]))
        {
            board[x][y] = toCheck[i];
            if(x == 8)
            {
                if(y == 8)
                    break;//We're done!  Yay!
                else
                {
                    nextX = 0;
                    nextY++;
                }
            }
            else
            {
                nextX++;
            }
            nextBoard(nextX, nextY);
        }
    }
    board[x][y] = 0;
}

public boolean legalMove(int x, int y, int current) {
    for(int i=0;i<9;i++) {
        if(current == board[x][i])
            return false;
    }
    for(int i=0;i<9;i++) {
        if(current == board[i][y])
            return false;
    }
    int cornerX = 0;
    int cornerY = 0;
    if(x > 2)
        if(x > 5)
            cornerX = 6;
        else
            cornerX = 3;
    if(y > 2)
        if(y > 5)
            cornerY = 6;
        else
            cornerY = 3;
    for(int i=cornerX;i<10 && i<cornerX+3;i++)
        for(int j=cornerY;j<10 && j<cornerY+3;j++)
            if(current == board[i][j])
                return false;
    return true;
}

public void print()
{
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
            System.out.print(board[i][j] + "  ");
        System.out.println();
    }
}

public static void main(String[] args)
{
    SudokuGenerator sg = new SudokuGenerator();
    sg.nextBoard();
    sg.print(); 
}
int[][] board;
}

使用Javascript:

//Recursive method that attempts to place every number in a square
function driver()
{
    board = new Array(10);
    for(var i=0;i<9;i++)
        board[i] = new Array(10);
    nextBoard(0,0);
    print();
}

function nextBoard(x, y)
{
    var nextX = x;
    var nextY = y;
    for(var i=1;i<10;i++) {
        console.log(y + " " + x + " " + i);
        document.getElementById(y + " " + x).innerHTML = i;
        if(legalMove(x, y, i)) {
            board[x][y] = i;
            if(x === 8) {
                if(y === 8)
                    return board;//We're done!  Yay!
                else {
                    nextX = 0;
                    nextY++;
                }
            }
            else
                nextX++;
            nextBoard(nextX, nextY);
        }
    }
    //This is needed for legalMove to work, otherwise [x][y] == 9
    board[x][y] = undefined;
}

function legalMove(x, y, current) {
    for(var i=0;i<9;i++) {
        if(current === board[x][i])
            return false;
    }
    for(var i=0;i<9;i++) {
        if(current === board[i][y])
            return false;
    }
    var cornerX = 0;
    var cornerY = 0;
    if(x > 2)
        if(x > 5)
            cornerX = 6;
        else
            cornerX = 3;
    if(y > 2)
        if(y > 5)
            cornerY = 6;
        else
            cornerY = 3;
    for(var i=cornerX;i<10 && i<cornerX+3;i++)
        for(var j=cornerY;j<10 && j<cornerY+3;j++)
            if(current === board[i][j])
                return false;
    return true;
}

function print() {
    for(var i=0;i<9;i++)
        for(var j=0;j<9;j++)
        {
            document.getElementById(i + " " + j).innerHTML = board[i][j];
            console.log(board[i][j]);           
        }
}

var board;

Answer 1

爪哇：

1. 您应该初始化board变量，您可能希望在构造函数中初始化它：

   public class SudokuGenerator {
   
       public static final int BOARD_WIDTH = 9;
       public static final int BOARD_HEIGHT = 9;
   
       public SudokuGenerator() {
           board = new int[BOARD_WIDTH][BOARD_HEIGHT];
       }
   }
   

2. 我相信你的循环迭代器在函数 nextBoard 中是错误的：

   for(int i=1;i<10;i++){ ... }

   我认为你想从 0 迭代到 9。

3. 在函数 nextBoard 中，您还需要检查变量：

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

   如果您得到一个java.lang.ArrayIndexOutOfBoundsException，您应该将其从 0 初始化为 8，否则您尝试访问板行号 9 并会收到运行时错误。

4. 您需要解决的另一个问题是 x 在函数中被设置为 9 nextBoard()。nextBoard(int x, int y)使用这些参数“手动”调用该函数：nextBoard(7,3)您就会明白为什么 x 被设置为 9。具体检查变量的值nextX。

我相信如果您使用调试器来检查此类错误，它会对您很有帮助，这里有一个带有视频解释的很好的教程（如果您使用的是 Eclipse IDE）。

希望能帮助到你。