Error de solución de sudoku

Question

No sé lo que estoy haciendo mal, y he estado mirando este código todo el día. Este es un solucionador de Sudoku "estándar" en Java, que toma un int[][] con 0's donde están los espacios vacíos. Dado que solo estoy pasando un tablero con 35 hoyos, esto debería ser capaz de resolver la gran mayoría de los problemas, pero solo puede resolver ~ 66%. En los demás, quedan unos pocos (normalmente 2 o 4) espacios vacíos, que son imposibles de resolver (es decir, se ha escrito un número incorrecto en board). Casi siempre, falta un 9.

Entiendo que una solución tan simple no resolverá todos los Sudokus. Estoy deliberadamente dando los más fáciles.

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

Soy nuevo en la programación, por lo que cualquier consejo que no sea resolverlo sería bienvenido. (Particularmente optimizando possible. Ese es el código más profano que he escrito hasta la fecha.)

¡Gracias!

Answer 1

Comencé a leer su código, pero parece más largo de lo que debería ser, y esos bucles se vuelven bastante complicados. Nada salta a mí de inmediato. Usted dijo que no solo quiere soluciones, sino consejos.

Tienes que averiguar si el problema es con tu diseño (no funciona para resolver el Sudoku) o si simplemente hay un error en algún lugar de la implementación. Tal vez revisar y escribir comentarios sobre lo que está logrando cada bucle, la "prueba de pato de hule", en la que se le obliga a explicar todo, se detendrá y se dará cuenta de que algo es innecesario, o no es lo que debe ser. Eso ayuda con los problemas de diseño.

Si el problema es la implementación, ¿sabes cómo depurar formalmente una aplicación? Establecer puntos de interrupción y recorrer instrucciones por instrucción? Si tienes un pequeño error, pero no ves dónde, ese es el camino a seguir. Encuentre un caso de ejemplo realmente simple que falla, luego ejecute esa prueba y bórrelo al principio. Paso a paso, y sigue la lógica. Con suerte, verá dónde va mal. Escribir pruebas de JUnit o declaraciones de registro es genial, pero cuando tienes un error complicado, tienes que hacer una verdadera depuración del punto de interrupción.

Su estructura general es buena, tiene algunos objetos para contener los datos, y un buen método de resolución limpia que llama a algunos métodos diferentes y pasa por ellos. Pero cada uno de esos métodos, wow, son seguros desordenados. Ese tipo de código, muchos bucles apretados que usan los mismos nombres de variable, mucha manipulación de matriz, es tan fácil arrojar algo y obtener un error y hace que sea muy difícil leer y encontrar el error.

Eclipse hace que sea muy fácil depurar java, si no lo hizo antes. Muchos buenos tutoriales en google, así que no me molestaré^_

Answer 2

Parece que no implementa un mecanismo de retroceso. Hay algunas veces que tienes que adivinar los números si no tienes implementada la heurística correcta.

Las heurísticas son "trucos del oficio", aquí hay un list of common ones for sudoku.

Si solo programó algunas de ellas, llegará a callejones sin salida y tendrá que adivinar. Esto lo hace más difícil ya que tendrá que tener en cuenta que esas suposiciones podrían ser incorrectas. Retroceder es una estrategia que le permitirá "retroceder" algunas suposiciones y hacer otras diferentes. Piense en ello como un árbol de posibilidades para crear algún tipo de fuerza bruta para resolver el sudoku.

lo tanto, sus posibilidades son 2 implementar más heurística o encontrar una manera de hacer una gama más amplia de conjeturas