Sudoku生成器的递归解决方案

Question

我正在尝试编写一种算法，以Java或Javascript创建合法的Sudoku板。两者都不起作用，我也不完全清楚为什么。

本质上，两个程序中的问题是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

Java：

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。

1. 在功能nextBoard中，您还需要检查变量：

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

得到一个java.lang.ArrayIndexOutOfBoundsException，应将其初始化为0到8，否则尝试访问板的第9行，并且会出现运行时错误。

1. 您需要解决的另一个问题是x的nextBoard()功能设置为9 。nextBoard(int x, int y)使用以下参数“手动” 调用该函数：nextBoard(7,3)您将理解为什么x设置为9。专门检查变量的值nextX。

我相信，如果您使用调试器检查此类错误，它将真的对您有帮助。在这里，您有一个不错的教程，并附有视频说明（以防您使用Eclipse
IDE）。

希望能帮助到你。