我不知道我做错了什么,而且我整天都在盯着这段代码.这是Java中的"标准"数独求解器,它采用int[][]空格为0的0.鉴于我只是通过一个35洞的板,这应该能解决绝大多数问题,但只能解决~66%.在其他人中,有一些(通常是2或4个)空的空间,这是不可能解决的(即写入不正确的数字board.)几乎总是,它将是一个缺少的9.
我知道这样一个简单的解决方案不会解决所有Sudokus.我故意放弃它.
import java.util.ArrayList;
import java.util.List;
public class SudokuSolver
{
public SudokuSolver()
{
init();
}
public boolean solve()
{
/* Each method checks (in different ways) to see if it can find a new number
If said method does find a number, it sets off a chain reaction, starting back at the beginning.
*/
int countdown = 20;
while(!solved() && --countdown > 0)
{
if(given())
continue;
if(findSingletons())
continue;
if(zerosLeft() <= 4)
justGuess();
}
return solved();
}
public boolean given()
{
boolean repeat = false;
//Iterate through every given number
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(board[i][j] != 0 && !found[i][j])
{
repeat = true;
foundNum(i, j, board[i][j]);
}
}
}
//Call given every time a new number is found
return repeat;
}
public boolean findSingletons()
{
boolean repeat = false;
//LOTS of iteration, but I'm out of ideas.
int[] values;
ArrayList<Integer> singletons = new ArrayList<Integer>();
for(int i=0;i<9;i++)
{
values = new int[10];
singletons.clear();
for(int j=0;j<9;j++)
for(int k=0;k<possible[i][j].size();k++)
values[possible[i][j].get(k)]++;
for(int j=1;j<10;j++)
if(values[j] == 1)
singletons.add(j);
for(int j=0;j<9;j++)
for(int k=0;k<singletons.size();k++)
if(possible[i][j].contains(singletons.get(k)))
{
foundNum(i, j, singletons.get(k));
repeat = true;
}
}
for(int i=0;i<9;i++)
{
values = new int[10];
singletons.clear();
for(int j=0;j<9;j++)
for(int k=0;k<possible[j][i].size();k++)
values[possible[j][i].get(k)]++;
for(int j=1;j<10;j++)
if(values[j] == 1)
singletons.add(j);
for(int j=0;j<9;j++)
for(int k=0;k<singletons.size();k++)
if(possible[j][i].contains(singletons.get(k)))
{
foundNum(j, i, singletons.get(k));
repeat = true;
}
}
int[] corners = {0,3,6};
for(int a=0;a<3;a++)
for(int l=0;l<3;l++)
for(int i=corners[a];i<corners[a]+3;i++)
{
values = new int[10];
singletons.clear();
for(int j=corners[l];j<corners[l]+3;j++)
for(int k=0;k<possible[i][j].size();k++)
values[possible[i][j].get(k)]++;
for(int j=1;j<10;j++)
if(values[j] == 1)
singletons.add(j);
for(int j=0;j<9;j++)
for(int k=0;k<singletons.size();k++)
if(possible[i][j].contains(singletons.get(k)))
{
foundNum(i, j, singletons.get(k));
repeat = true;
}
}
return repeat;
}
public void justGuess()
{
outer:
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(board[i][j] == 0)
{
foundNum(i, j, possible[i][j].get(0));
break outer;
}
}
public void foundNum(int x, int y, int numFound)
{
if(board[x][y] != 0 && board[x][y] != numFound)
{
throw new RuntimeException("Attempting to place a number where one was already found");
}
board[x][y] = numFound;
possible[x][y].clear();
possible[x][y].add(numFound);
found[x][y] = true;
for(int i=0;i<9;i++) {
if(i != x)
if(possible[i][y].indexOf(numFound) != -1)
possible[i][y].remove(possible[i][y].indexOf(numFound));
}
for(int i=0;i<9;i++) {
if(i != y)
if(possible[x][i].indexOf(numFound) != -1)
possible[x][i].remove(possible[x][i].indexOf(numFound));
}
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(i != x && j != y)
if(possible[i][j].indexOf(numFound) != -1)
possible[i][j].remove(possible[i][j].indexOf(numFound));
}
public boolean solved() {
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(!found[i][j])
return false;
return true;
}
public void reset(int[][] board)
{
this.board = board;
init();
}
public void init()
{
possible = new ArrayList[9][9];
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
possible[i][j] = new ArrayList<Integer>();
for(int k=1;k<10;k++)
possible[i][j].add(k);
}
found = new boolean[9][9];
}
public void print()
{
for(int i=0;i<9;i++)
{
if(i%3==0 && i != 0)
System.out.println("- - - | - - - | - - -");
for(int j=0;j<9;j++)
{
if(j%3==0 & j != 0)
System.out.print("| ");
System.out.print(board[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
private int zerosLeft()
{
int empty = 0;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(board[i][j] == 0)
empty++;
return empty;
}
private void data(int difficulty)
{
int empty = 0;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(board[i][j] == 0)
empty++;
System.out.println(empty);
}
public static void main(String[] args)
{
SudokuGenerator sg = new SudokuGenerator();
SudokuSolver ss = new SudokuSolver();
int[][] tempBoard = {{4, 0, 1, 0, 9, 7, 0, 5, 8 },
{2, 0, 0, 5, 3, 1, 4, 0, 6 },
{5, 0, 6, 4, 0, 2, 0, 3, 9 },
{0, 9, 0, 0, 0, 4, 3, 0, 2 },
{0, 0, 0, 9, 0, 0, 6, 4, 7 },
{7, 0, 4, 0, 0, 0, 9, 0, 5 },
{0, 0, 7, 0, 0, 3, 8, 9, 4 },
{8, 5, 0, 1, 4, 9, 7, 0, 0 },
{9, 0, 3, 8, 7, 6, 0, 0, 0 }};
ss.reset(tempBoard);
System.out.println(ss.solve());
ss.print();
ss.data(35);
}
int[][] board;
ArrayList<Integer>[][] possible;
boolean[][] found;
}
我还是编程的新手,所以除了解决这个问题之外的任何建议都会受到欢迎.(特别是优化possible.这是我迄今为止写过的最亵渎的代码.)
谢谢!
我开始阅读你的代码，但感觉比应有的要长，而且这些循环变得非常混乱。没有什么立刻让我跳出来。您确实说过您不仅需要解决方案，还需要建议。
您必须弄清楚问题是否出在您的设计上（它不适用于解决数独），或者是否只是实现中的某个地方存在简单的错误。也许仔细检查每个循环正在完成的事情并写下评论，即“橡皮鸭测试”，被迫解释一切，你会停下来并意识到有些事情是不必要的，或者不是它需要的。这有助于解决设计问题。
如果问题是实现，您知道如何正式调试应用程序吗？设置断点并逐条指令地执行它？如果你有一个小错误，但你不知道在哪里，那就是正确的方法。找到一个失败的非常简单的示例案例，然后运行该测试并在开始时打破它。逐步执行并遵循逻辑。希望您能看到哪里出了问题。编写 JUnit 测试或日志语句很棒，但是当您遇到棘手的错误时，您必须进行一些真正的断点调试。
您的总体框架很好，您有一些对象来保存数据，以及一个漂亮的干净解决方法，该方法调用一些不同的方法并循环它们。但这些方法中的每一个，哇，它们确实很混乱。这种代码，大量使用相同变量名的紧密循环，大量数组操作，很容易弄乱某些东西并产生错误，这使得阅读和查找错误变得非常困难。
Eclipse 使调试 java 变得非常容易（如果您以前没有调试过的话）。google 上有很多很好的教程，就不麻烦了^_~
| 归档时间： |
|
| 查看次数： |
717 次 |
| 最近记录： |