Resolver sudokus con Java y recursividad

Hoy traemos el código necesario para resolver sudokus en Java utilizando recursividad.
Tendremos dos clases una Principal.java con el main y otra clase sudoku.java.
La clase sudoku.java contendrá la funcion resolverSudoku() que utilizará recursividad. Y las funciones necesarias para comprobar que el numero introducido en la celda es correcto(esValido()):

package sudoku;

/**
 *
 * @author Javi
 */
public class Sudoku {
    
    
    private int tablero[][];
    static final int  SIN_ASIGNAR=0;
    
    public Sudoku(int sudoku[][]){
        this.tablero=sudoku;
    }
    
    
    public boolean resolverSudoku(){
        
        for(int fila=0;fila <9;fila++){
            for (int columna=0;columna<9;columna++){
                if(tablero[fila][columna]==SIN_ASIGNAR){
                    for (int numero =1;numero<=9;numero++){
                        if(esValido(fila,columna,numero)){
                            tablero[fila][columna]=numero;
                            if(resolverSudoku()){
                                return true;
                            }else{
                                tablero[fila][columna]=SIN_ASIGNAR;
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean esValido (int fila, int columna, int numero){
        return !(contieneFila(fila,numero)||contieneColumna(columna,numero)||contieneCaja(fila,columna,numero));
    }
    
    private boolean contieneFila(int fila,int numero){
        for(int columna=0;columna<9;columna++){
            if(tablero[fila][columna]==numero){
                return true;
            }
        }
        return false;
    }
    
    private boolean contieneColumna(int columna,int numero){
        for(int fila=0;fila<9;fila++){
            if(tablero[fila][columna]==numero){
                return true;
            }
        }
        return false;
    }
    
    private boolean contieneCaja(int fila, int columna,int numero){
        int f = fila - fila % 3;
        int c = columna -columna % 3;
        for(int i =f;i<f+3;i++){
            for(int j = c; j<c+3;j++){
                if(tablero[i][j]==numero){
                    return true;
                }
            }
        }
        return false;
    }
    
public void ImprimirSudoku(){
    for(int i=0;i<9;i++){
        for (int j=0;j<9;j++){
            System.out.print(tablero[i][j]);
        }
        System.out.println("");
    }
}    

    
}

Con esta clase conseguimos que nos devuelva un sudoku solucionado.
Con la clase principal.java creamos el objeto miSudoku y le pasamos el tablero que queremos que resuelva.

package sudoku;

/**
 *
 * @author Javi
 */
public class Principal {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        
        int tablero[][]={{6,9,5,3,7,1,8,4,2},
                         {0,0,0,0,0,0,0,0,0},
                         {8,4,1,2,9,6,3,7,5},
                         {0,0,0,0,0,0,0,0,6},
                         {0,0,0,0,0,0,0,0,8},
                         {5,6,2,0,1,7,4,3,9},
                         {0,0,0,0,0,0,1,8,7},
                         {0,0,0,0,0,0,0,0,0},
                         {7,5,4,0,0,0,0,0,0}};
        
        Sudoku miSudoku=new Sudoku(tablero);
        miSudoku.resolverSudoku();
        miSudoku.ImprimirSudoku();
                
        }
        
    }

En este video aprendí como era el algoritmo.

He hecho una versión del código anterior en PHP pero el algoritmo es el mismo, lo podeis probar https://dornisoft.es/sudoku

Espero que te guste 😉

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *