数独回溯无效的数独 [英] Sudoku Backtracking Non valid Sudoku
问题描述
我创建了Sudoku Backtracking解算器，并且效果很好， 但是现在我想给出一个错误，如果数独不能解决，因为它是无效的 例如，如果给出了这个数独:
I created a Sudoku Backtracking solver and it works just fine, but now i want to give out an error if the sudoku cant be solved because it isnt valid for example if this sudoku is given:
http://img5.imageshack.us/img5/2241/sudokugq.jpg
如果无法解决，我该怎么办才能使我的解决方法发出错误? 我总是以零结束或陷入循环.
what can i do to make my solving method give out an error if it isnt solveable? I always end up with Zeros or stuck in a loop.
public void solve( int row, int col ) throws Exception
{
// Throw an exception to stop the process if the puzzle is solved
if( row > 8 ){
//Gelöst
}
// If the cell is not empty, continue with the next cell
if( sudo[row][col] != 0 ){
next( row, col ) ;
}
else
{
// Find a valid number for the empty cell
for( int num = 1; num < 10; num++ )
{
if( checkHorizontal(row,num) == false && checkVertikal(col,num)== false&& checkBox(row,col,num)== false )
{
sudo[row][col] = num ;
// Delegate work on the next cell to a resudosive call
next( row, col ) ;
}
}
// No valid number was found, clean up and return to caller
sudo[row][col] = 0 ;
}
}
//Ruft solve für das nächste Feld auf
public void next( int row, int col ) throws Exception
{
if( col < 8 )
solve( row, col + 1 ) ;
else
solve( row + 1, 0 ) ;
}
推荐答案
当然，当您按下sudo[row][col] = 0 ;代码时，您刚刚完成了对一个方格中的每个值的尝试，但找不到任何解决方案.当然，这是您决定放弃无解决方案状态的关键所在.
Surely when you hit the sudo[row][col] = 0 ; code you have just finished trying every value in a square and found no solution with any of them. Surely that is the point where you decide to give up with a no-solution state.
进一步思考-我怀疑我几乎是正确的.如果您按此代码 ，并且这是您尝试的第一个单元格(即找到的第一个空单元格)，那么这就是您的失败时刻.
Thinking about it further - I suspect I am only nearly right. If you hit this code and this is the first cell you are trying (i.e. the first empty cell you found) then that is your fail moment.
顺便说一句-我不确定使用Exception来指示您在注释中建议的解决方案是否是个好主意.
BTW - I'm not sure it would be a good idea to use an Exception to indicate a solution as you suggest in your comment.
这现在可以正确地拒绝您发布的公告板-请注意，第一行不仅有两个"3"，而且第一栏中也有两个"5".这段代码现在似乎对我有用.也许您可以在一个无法解决的问题上尝试一下.
This now correctly rejects the board you posted - notice that not only are there two "3"s on the first row there are also two "5"s in the first column. This code seems to work for me now. Perhaps you could try it on an insoluble one.
public class Test {
static final int S = 9;
int[][] sudo;
public Test() {
// Just leave it empty.
sudo = new int[S][S];
}
public Test(int[][] sudo) {
this.sudo = sudo;
}
// This number should not appear anywhere in the row.
public boolean checkHorizontal(int row, int num) {
for (int i = 0; i < S; i++) {
if (sudo[row][i] == num) {
return false;
}
}
return true;
}
// This number should not appear anywhere in the col.
public boolean checkVertical(int col, int num) {
for (int i = 0; i < S; i++) {
if (sudo[i][col] == num) {
return false;
}
}
return true;
}
// This number should not appear anywhere in the box.
private boolean checkBox(int row, int col, int num) {
// Round down to nearest 3.
int r = (row / 3) * 3;
int c = (col / 3) * 3;
for (int i = r; i < r + 3; i++) {
for (int j = c; j < c + 3; j++) {
if (sudo[i][j] == num) {
return false;
}
}
}
return true;
}
boolean check(int row, int col, int num) {
// All checks must pass.
return checkHorizontal(row, num)
&& checkVertical(col, num)
&& checkBox(row, col, num);
}
public boolean solve(int row, int col) {
// Got to the end?
if (row >= S) {
//Gelöst
return true;
}
// If the cell is empty
if (sudo[row][col] == 0) {
// Find a valid number for the empty cell
for (int num = 1; num < 10; num++) {
// Can this number be put there?
if (check(row, col, num)) {
// Yes!
sudo[row][col] = num;
// Try that.
if (next(row, col)) {
return true;
}
}
}
// Clean up.
sudo[row][col] = 0;
} else {
// Move on.
if (next(row, col)) {
return true;
}
}
// Failed to find a solution.
return false;
}
//Ruft solve für das nächste Feld auf
public boolean next(int row, int col) {
if (col < S - 1) {
// Step right.
return solve(row, col + 1);
} else {
// Step down.
return solve(row + 1, 0);
}
}
public boolean boardOk() {
// Initial test to ensure it is a valid array.
// Must have that many rows.
boolean ok = sudo.length == S;
for (int row = 0; ok && row < S; row++) {
// Each row must be that long.
ok &= sudo[row].length == S;
for (int col = 0; ok && col < S; col++) {
// Each filled square must be valid.
if (sudo[row][col] != 0) {
int num = sudo[row][col];
// Remove it.
sudo[row][col] = 0;
// Check it can be added.
ok &= check(row, col, num);
// Put it back.
sudo[row][col] = num;
}
}
}
return ok;
}
void solve() {
if (boardOk()) {
boolean solved = solve(0, 0);
if (solved) {
System.out.println("Solved!");
print();
}
} else {
System.out.println("Insoluble!");
print();
}
}
public void print() {
for (int i = 0; i < sudo.length; i++) {
System.out.println(Arrays.toString(sudo[i]));
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
new Test().solve();
int[][] test = {
{0, 0, 6, 5, 8, 3, 3, 2, 7},
{0, 0, 0, 0, 9, 0, 0, 5, 0},
{5, 8, 0, 0, 0, 0, 0, 0, 3},
{0, 3, 1, 0, 4, 0, 5, 0, 0},
{0, 0, 0, 9, 2, 0, 3, 0, 6},
{0, 0, 0, 0, 0, 0, 0, 0, 1},
{3, 4, 2, 0, 0, 6, 9, 1, 5},
{5, 0, 5, 4, 0, 9, 0, 3, 2},
{0, 1, 0, 0, 0, 0, 0, 0, 4},};
new Test(test).solve();
}
}
这篇关于数独回溯无效的数独的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
