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.
video youtube
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 😉