在java中创建一个数独求解器。 [英] Create a sudoku solver in java .
问题描述
我的代码的目的，类似于迷宫的回溯算法，是为9×9数独计算解决方案。
和The Sudoku及其解决方案是像迷宫一样存储在二维int数组中。
我知道：回溯算法试图从空格[0.0]开始在自由字段中输入值1 ... 9（值然后是0），从段落1开始。测试这是否是有效值比迷宫稍微复杂一点，只需要检查单元格是否空闲。我认为使用这些方法是个好主意
isRowOk，
isColOk，
isBlockOk
检查是否允许值的优点，即块中尚未包含值。
然后这三个函数必须在回溯算法递归尝试输入值1之前给出它们的OK。 .. 9在下一个免费单元格中。否则 - 如果所有数字1 ... 9都已经尝试 - 搜索将被取消（回溯），并且将在呼叫搜索中尝试下一个可能的号码。
有没有人有更好的主意，因为我的代码无法正常工作？
我的尝试：
The aim of my code, similar to the backtracking algorithm for labyrinths, is to calculate solutions for a 9 × 9 sudoku.
and The Sudoku and its solution are stored like the labyrinth in a two-dimensional int array.
I know that :The backtracking algorithm tries to enter a value of 1 ... 9 from cell [0.0] starting in a free field (value is then 0), starting with paragraph 1. Testing whether this is a valid value is a little more complicated than the maze, where it only had to be checked whether the cell is free. I think it is a good idea to use the methods
isRowOk ,
isColOk ,
isBlockOk
To take advantage of the check whether value is allowed at all, i.e. not already contained in the block.
and then These three functions must all give their OK before the backtracking algorithm tries recursively to enter a value of 1 ... 9 in the next free cell. Otherwise-if all digits 1 ... 9 have been tried-the search will be canceled (backtracking) and the next possible number will be tried in the calling search.
Do anyone have a better idea, because my code doesn't work correctly?
What I have tried:
package test;
public class Sudoku {
private final int BLOCK_SIZE = 3;
private final int ROW_SIZE = BLOCK_SIZE * BLOCK_SIZE;
private int nrOfSolutions, nrOfTests;
private int[][] board;
private int[][][] testBoard = {
/* |---------|---------|---------| */
{ { 5, 3, 0, 0, 7, 0, 0, 0, 0 }, { 6, 0, 0, 1, 9, 5, 0, 0, 0 }, { 0, 9, 8, 0, 0, 0, 0, 6, 0 },
/* |---------|---------|---------| */
{ 8, 0, 0, 0, 6, 0, 0, 0, 3 }, { 4, 0, 0, 8, 0, 3, 0, 0, 1 }, { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
/* |---------|---------|---------| */
{ 0, 6, 0, 0, 0, 0, 2, 8, 0 }, { 0, 0, 0, 4, 1, 9, 0, 0, 5 }, { 0, 0, 0, 0, 8, 0, 0, 7, 9 } },
/* |---------|---------|---------| */
/* |---------|---------|---------| */
{ { 5, 3, 4, 6, 7, 8, 9, 1, 2 }, { 6, 7, 2, 1, 9, 5, 3, 4, 8 }, { 1, 9, 8, 3, 4, 2, 5, 6, 7 },
/* |---------|---------|---------| */
{ 8, 5, 9, 7, 6, 1, 4, 2, 3 }, { 4, 2, 6, 8, 5, 3, 7, 9, 1 }, { 7, 1, 3, 9, 2, 4, 8, 5, 6 },
/* |---------|---------|---------| */
{ 9, 6, 1, 5, 3, 7, 2, 8, 4 }, { 2, 8, 7, 4, 1, 9, 6, 3, 5 }, { 3, 4, 5, 2, 8, 6, 1, 7, 0 } },
/* |---------|---------|---------| */
/* |---------|---------|---------| */
{ { 0, 0, 0, 5, 4, 2, 0, 0, 0 }, { 9, 6, 7, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 3, 1, 8 },
/* |---------|---------|---------| */
{ 0, 0, 0, 0, 7, 0, 8, 6, 4 }, { 0, 2, 0, 6, 0, 4, 0, 9, 0 }, { 6, 4, 5, 0, 1, 0, 0, 0, 0 },
/* |---------|---------|---------| */
{ 8, 9, 1, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 5, 4, 7 }, { 0, 0, 0, 3, 2, 6, 0, 0, 0 } },
/* |---------|---------|---------| */
};
public void testSudokuSolver() {
for (int[][] s : this.testBoard) {
this.board = s;
this.print();
nrOfSolutions = 0;
nrOfTests = 0;
this.solve(0, 0);
}
}
private boolean isBlockOk(int row, int col, int num) {
int iRowStart = (row / BLOCK_SIZE) * BLOCK_SIZE;
int iColStart = (col / BLOCK_SIZE) * BLOCK_SIZE;
for ( int irow = iRowStart; irow < iRowStart + BLOCK_SIZE; irow++) {
for ( int icol = iColStart; icol < iColStart + BLOCK_SIZE; icol++) {
if (num == board[irow][icol]) {
return false;
}
}
}
return true;
}
private boolean isRowOk(int row, int num) {
for (int i = 0; i < ROW_SIZE; i++) {
if (num == board[row][i]) {
return false;
}
}
return true;
}
private boolean isColOK(int col, int num) {
for (int i = 0; i < ROW_SIZE; i++) {
if (num == board[i][col]) {
return false;
}
}
return true;
}
public void print() {
final String horizBorder = " ┼────────┼────────┼────────┼";
System.out.println();
for (int i = 0; i < ROW_SIZE; i++) {
if (0 == i % 3) {
System.out.println(horizBorder);
}
for (int j = 0; j < ROW_SIZE; j++) {
if (0 == j % 3) {
System.out.print(" │ ");
}
int num = board[i][j];
if (num == 0) {
System.out.print("_ ");
} else {
System.out.print(num + " ");
}
}
System.out.println(" │");
}
System.out.println(horizBorder);
}
private boolean isValid(int num, int row, int col) {
return (isBlockOk(row, col, num) && isColOK(col, num) && isRowOk(row, num));
}
public boolean solve(int row, int col) {
for (int i = 1; i < BLOCK_SIZE; i++) {
for (int j = 1; j < BLOCK_SIZE; j++) {
if (board[i][j] == 0) {
for (int k = 1; k <= 9; k++) {
board[i][j] = k;
if (isValid(i, j, k) && solve(i, col)) {
return true;
}
board[i][j] = 0;
}
return false;
}
}
}
return true;
}
public static void main(String[] args) {
new Sudoku().testSudokuSolver();
}
}
推荐答案
有没有更好的主意？
回溯原理有效，效率低下。
人类方法效率更高。
the principle of backtracking works, it is just inefficient.
Human method is more efficient.
因为我的代码无法正常工作？
because my code doesn't work correctly?
然后你需要调试你的代码！
首先，每次设置单元格时都要更改代码以显示每个板，并在下一步之前等待用户输入。当你看到一个错误的移动时，这意味着你的代码没有正确检查移动，这给你提示有关证明代码的位置。
调试器也是很棒的帮助：
你的代码没有你想象的那样，或者你不明白为什么！
几乎是通用的解决方案：一步一步地在调试器上运行代码，检查变量。
调试器在这里向您展示您的代码正在做什么，您的任务是与它应该做什么进行比较。
调试器中没有魔法，它不知道你的代码应该做什么，它没有发现错误，只是通过向你展示发生了什么来帮助你。当代码没有达到预期的效果时，你就接近了一个错误。
要查看你的代码在做什么：只需设置断点并查看代码是否正常运行，调试器允许你执行第1行第1行，并在执行时检查变量。
调试器 - 维基百科，免费的百科全书 [ ^ ]
掌握Visual Studio 2010中的调试 - 初学者指南 [ ^ ]
使用Visual Studio 2010进行基本调试 - YouTube [ ^ ]
http://docs.oracle.com/javase/7/docs /technotes/tools/windows/jdb.html [ ^ ]
https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html [ ^ ]
调试器在这里只显示你的内容你的代码正在做，你的任务是与它应该做的事情进行比较。
看看：
Andrew Stuart的解决方案 [ ^ ]
简单苏doku - 免费软件拼图制作者和解决者 [ ^ ]
解决数独游戏 [ ^ ]
Then you need to debug your code !
First thing, change your code to display each board each time you set a cell and wait for user input before next step. When you see a wrong move, it means that your code do not check correctly that move, this give you hints about where to proof code.
The debugger is also of great help:
Your code do not behave the way you expect, or you don't understand why !
There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your code is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.
Debugger - Wikipedia, the free encyclopedia[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]
http://docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html[^]
https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html[^]
The debugger is here to only show you what your code is doing and your task is to compare with what it should do.
Have a look at:
Sudoku Solver by Andrew Stuart[^]
Simple Sudoku - freeware puzzle maker and solver[^]
Solving Sudoku[^]
这篇关于在java中创建一个数独求解器。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
