数独求解器bug

Question

我不知道我做错了什么，我一直在盯着这个代码。这是Java中的一个“标准”Sudoku求解器，它需要一个int[][]，其中空格为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。这是我迄今为止写的最亵渎的代码。）

谢谢！

Answer 1

我开始阅读你的代码，但感觉比它应该更长，并且这些循环变得相当混乱。没有任何东西立即跳出来。你确实说过你不只是想要解决方案，而是建议。

你必须弄清楚问题出在你的设计上（它不能解决Sudoku问题），或者如果在实现中有一个简单的错误。也许要写一些关于每个循环完成的评论，即“橡皮鸭测试”，由此被迫解释所有事情，你会停下来，意识到一些事情是不必要的，或者不是它所需要的。这有助于解决设计问题。

如果问题是实现，你知道如何正式调试应用程序吗？设置断点并通过指令逐步完成指令？如果你有一个小错误，但你不知道在哪里，那就是要走的路。找到一个非常简单的示例失败案例，然后运行该测试并在开始时将其破解。逐步完成，并遵循逻辑。希望你能看到它出错的地方。编写JUnit测试或日志语句非常好，但是当您遇到棘手的错误时，您必须执行一些真正的断点调试。

你的一般框架是好的，你有一些对象来保存数据，以及一个很好的干净的解决方法，它调用几个不同的方法并通过它们循环。但是，这些方法中的每一种，哇，他们肯定是混乱的。这种类型的代码，使用相同变量名称的大量紧密循环，大量的数组操作，很容易漏掉某些东西并且得到一个bug，这使得很难阅读和发现错误。如果你以前没有使用Eclipse，那么Eclipse可以非常容易地调试java。在谷歌很多很好的教程，所以我不会打扰^ _〜

Answer 2

你似乎没有实现一个回溯机制。如果你没有实现正确的启发式方法，有时你需要猜测数字。

启发式是“交易的技巧”，这里是一个list of common ones for sudoku。

如果您只编程了其中的几个，您将陷入死胡同，并将不得不猜测。这使得它更加困难，因为必须考虑到这些猜测可能是错误的。回溯是一种策略，可让您“回滚”一些猜测并制作不同的策略。把它看作是一种可能性的树，用来解决数独问题。

所以，你的2种可能性来实现更多的启发式或找到一种方法，使更广泛的猜测