Błąd rozwiązania sudoku

Question

Nie wiem, co robię źle, i cały dzień patrzę na ten kod. Jest to "standardowy" solver Sudoku w Javie, który pobiera int[][] z 0, gdzie znajdują się puste miejsca. Biorąc pod uwagę, że przechodzę tylko na planszę z 35 dołkami, powinno to być w stanie rozwiązać ogromną większość problemów, ale może rozwiązać tylko 66%. W pozostałych jest kilka (zwykle 2 lub 4) pustych miejsc, które są niemożliwe do rozwiązania (tj. Niewłaściwa liczba została zapisana w board.) Niemal zawsze będzie brakowało 9.

Rozumiem, że takie proste rozwiązanie nie rozwiąże wszystkich Sudokusów. Celowo to ułatwiam.

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; 
} 

Nadal jestem nowy w programowaniu, więc wszelkie rady inne niż rozwiązanie tego będą mile widziane. (Szczególnie optymalizacja possible. To najbardziej profanowski kod, jaki napisałem do tej pory.)

Dzięki!

Answer 1

Zacząłem czytać twój kod, ale czuję się dłużej niż powinien, a te pętle są dość nieładne. Nic natychmiast nie wyskakuje na mnie. Powiedziałeś, że nie chcesz tylko rozwiązań, ale porady.

Musisz dowiedzieć się, czy problem dotyczy Twojego projektu (nie działa w przypadku rozwiązywania sudoku), czy w implementacji jest tylko prosty błąd. Może przejrzeć i napisać komentarze na temat tego, co robi każda pętla, "test gumowych kaczuszek", w którym zmuszony do wyjaśnienia wszystkiego, zatrzymasz się i zdasz sobie sprawę, że coś jest niepotrzebne, lub nie jest tym, czym musi być. Pomaga to w problemach z projektowaniem.

Jeśli problem dotyczy implementacji, czy formalnie debugujesz aplikację? Ustaw punkty przerwania i postępuj zgodnie z instrukcją? Jeśli masz mały błąd, ale nie wiesz gdzie, to jest droga. Znajdź naprawdę prosty przypadek, który się nie powiedzie, a następnie uruchom ten test i rozbij go na początku. Przejdź przez i postępuj zgodnie z logiką. Mam nadzieję, że przekonasz się, gdzie to idzie nie tak. Pisanie testów JUnit lub logów jest świetne, ale kiedy masz podchwytliwy błąd, musisz przeprowadzić prawdziwe debugowanie.

Twoja ogólna struktura jest dobra, masz kilka obiektów do przechowywania danych i ładną, czystą metodę rozwiązywania, która wywołuje w nich kilka różnych metod i pętli. Ale każda z tych metod, wow, oni są pewni bałaganu. Ten rodzaj kodu, dużo ciasnych pętli używających tych samych nazw zmiennych, wiele manipulacji tablicą, jest tak łatwy do flubowania i otrzymywania błędów, co sprawia, że ​​naprawdę trudno jest go odczytać i znaleźć błąd.

Eclipse ułatwia debugowanie języka Java, jeśli jeszcze tego nie zrobiłeś. Mnóstwo dobrych samouczków w google, więc nie będę zawracać sobie głowy^_ ~

Answer 2

Nie wydajesz się implementować mechanizmu wycofywania. Niekiedy trzeba odgadnąć liczby, jeśli nie wprowadzono poprawnej heurystyki.

Heurystyki są "sztuczkami handlowymi", tutaj jest list of common ones for sudoku.

Jeśli zaprogramowałeś tylko kilka z nich, wejdziesz w ślepy zaułek i będziesz musiał zgadywać. To sprawia, że ​​jest to trudniejsze, ponieważ trzeba będzie wziąć pod uwagę, że te przypuszczenia mogą być błędne. Backtracking to strategia, która pozwoli Ci "cofnąć" kilka domysłów i stworzyć inne. Pomyśl o tym, jako o drzewie możliwości zrobienia jakiegoś rodzaju brutali, aby rozwiązać sudoku.

więc możliwości są 2 do wdrożenia więcej heurystyki lub znaleźć sposób, aby szerszy zakres domysły