Sudokuソルバーのバグ

Question

私は何が間違っているのか分かりません。私はこのコードを一日中見てきました。これはJavaの「標準的な」数独ソルバで、空のスペースがあるところでint[][]に0をとります。私は35ホールのボードを通過するだけなので、これは大部分の問題を解決できるはずですが、〜66％しか解決できません。他のものには空きスペースが残っていますが、解決できないものがあります（つまり、不適切な数字がboardに書き込まれています）。ほとんどの場合、ほとんどの場合、それは失われています。

私は、このような単純な解決策がすべての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テストやログステートメントの作成は素晴らしいですが、難しいバグがある場合は、実際のブレークポイントデバッグを行う必要があります。

あなたの一般的なフレームワークは良いですし、データを保持するオブジェクトがありますし、いくつかの異なるメソッドを呼び出してそれらをループするクリーンな解決メソッドです。しかし、それらの方法のそれぞれは、うわー、彼らは確かに乱雑です。そのようなコード、同じ変数名を使ったたくさんのタイトなループ、たくさんの配列操作、そんなに簡単に何かをかぶってバグを取ってしまうとバグを見つけて見つけにくいです。

Eclipseを使用すると、これまでにない方法でJavaをデバッグするのが簡単になります。グッドチュートリアルがたくさんありますので、私は気にしません^ _〜

Answer 2

あなたはバックトラック機構を実装していないようです。正しいヒューリスティックが実装されていない場合、数を推測しなければならない場合があります。

ヒューリスティックは「トレードの術」であり、ここにはlist of common ones for sudokuがあります。

これらのうちのいくつかしかプログラミングしていないと、デッドエンドになり、推測する必要があります。これは、それらの推測が間違っている可能性があることを考慮する必要があるので、より困難になります。バックトラッキングは、いくつかの推測を「ロールバック」して別の推測を行う戦略です。それをスードクを解決するために何らかの力を発揮する可能性の木と考えてください。

だからあなたの2つの可能性は、より多くのヒューリスティックを実装したり、推測