Sudoku生成器的递归解决方案

我正在尝试编写一个算法，用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 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 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。

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

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

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

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

我相信如果您使用调试器来检查这种错误，它将真正帮助您， 在这里您有一个很好的教程与video说明（如果您使用Eclipse IDE）。

希望能帮助到你。

Answer 2

在Java代码中：我将它转换为psuedocode：

 for all z values: If for current (x,y), the number 'z' is legal then: insert z to current (x,y) if finished hooray! else go to next square else try next number 

但是，如果你不能在那里放任何数字，因为它最终是非法的（也就是你不能在特定方格中插入任何数字的板子）怎么办？

你没有解决这个问题。 你需要做的是通过回溯来实现它：

 for all z values: If for current (x,y) the number 'z' is legal then: insert z to current (x,y) go to next(x,y) try to complete the board // recursive call if you completed the board // == the result of the recursion is legal return the completed board If all z values have been attempted return "cannot complete board" increment z, try again with current (x,y) 

Answer 3

Java的：

你在nextBoard中的循环迭代器的范围是1到9.我不认为你的意思。 在函数legalMove中相同….将cornerX和cornerY初始化为0。

Answer 4

有趣的问题，我刚刚注意到Java代码中的这个错误：不是对Collection.shuffle（）的调用没用，因为在调用之后toCheck数组将保持未修改（未调整）？ 这是我的快速修复（我确信有更聪明的方法）：

 List lst = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9); Collections.shuffle(lst); for (int i=0; i 

Answer 5

在Java中，数组索引是从零开始的。 在nextBoard你为i循环nextBoard并将其用作toCheck的索引，它将跳过索引0处的第一个元素并超过数组的末尾。 如果到达包含toCheck[i]的行，并且i等于9则抛出ArrayIndexOutOfBoundsException 。

Answer 6

 import java.io.File; import java.io.FileNotFoundException; import java.util.Arrays; import java.util.Scanner; import java.util.logging.Level; import java.util.logging.Logger; public class SudokuNrupen { public static int[][] p; public static int tmp[] ; public static int tmp2D[][] ; public static void main(String[] args){ tmp = new int[9]; tmp2D = new int[3][3]; p = new int[9][9]; System.out.print("Enter the name of he file below "); Scanner scan = new Scanner (System.in); String name = scan.nextLine(); File file = new File( name ); if ( file.exists()){ try { Scanner inFile = new Scanner( file ); for(int i=0; i<9; i++){ for(int j=0; j<9; j++){ if(inFile.hasNextInt()){ p[i][j] = inFile.nextInt(); } } } inFile.close(); } catch (FileNotFoundException ex) { Logger.getLogger(SudokuNrupen.class.getName()).log(Level.SEVERE, null, ex); } } display(p); solve(p); System.out.println("Solved Sudoku is:"); display(p); } public static void display(int [][] p) { for(int i=0; i