Sudoku生成器的递归解决方案 [英] Recursive solution to Sudoku generator
问题描述
我正在尝试编写一个算法，用Java或Javascript创建合法的数独板。既不工作，也不完全确定原因。
I'm trying to code an algorithm that creates a legal Sudoku board in either Java or Javascript. Neither work, and I'm not entirely sure why.
基本上，两个程序中的问题是x或y的增加量超过它应该增加（跳过广场）。我不能为我的生活弄清楚这是怎么回事。如果需要，我可以提供完成JS解决方案的HTML。
Essentially, the problem in both programs is that either x or y is getting incremented more than it should (skipping the square). I can't for the life of me figure out how this is happening. I can provide the HTML that completes the JS solution if need be.
我最好的猜测是它与我如何使用递归创建堆栈有关，但是据我所知，它应该工作。
在我的旧代码中有一个不正确的for循环，我知道这一点。我粘贴了一个旧版本，现在已修复。
My best guess is it has to do with how I've created a stack using recursion, but as far as I can tell, it should work. In my old code there was an incorrect for loop, I'm aware of this. I pasted an old version, it's fixed now.
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：
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;
推荐答案
Java：
-
您应该初始化
board变量，您可能希望在构造函数中初始化它：
You should initialize your
boardvariable, you may want to initialize it in a constructor:
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];
}
}
我相信你的循环迭代器在函数nextBoard它错了：
I believe that your loop iterator in the function nextBoard it is wrong:
for（int i = 1; i< 10; i ++）{...}
我认为你想要从0迭代到9。
I think that you want to iterate from 0 to 9.
在函数中nextBoard，你还需要检查变量：
In the function nextBoard, you also need to check the variable:
int [] toCheck = {1,2,3,4,5,6,7 ，8,9};
你得到一个 java.lang.ArrayIndexOutOfBoundsException ，你应该将它从0初始化为8，否则你会尝试访问第9行的板行，并且会出现运行时错误。
You get an java.lang.ArrayIndexOutOfBoundsException, you should initialize it from 0 to 8, otherwise you try to access the board row number 9 and you get a runtime error.
你需要的另一个问题求解是在 nextBoard（）函数中将x设置为9。使用以下参数调用函数 nextBoard（int x，int y）手动： nextBoard（7,3）你会明白为什么x被设置为9。具体检查变量 nextX 的值。
Another problem that you need to solve is that x is being set to nine in nextBoard() function. Call the function nextBoard(int x, int y) "manually" with these parameteres: nextBoard(7,3) and you will understand why x is being set to nine. Check specifically the values of the variable nextX.
我相信如果您使用调试器检查此类错误，这里你有一个很好的教程，有一个视频解释（如果你正在使用Eclipse IDE）。
I believe it will really help you if you use a debugger to check this kind of errors, here you have a nice tutorial with a video explanation(in case your are using the Eclipse IDE).
希望它有所帮助。
这篇关于Sudoku生成器的递归解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
