BysMax

Programa que resuelve un SUDOKU en JAVA

Authors
14 min read
·
Published on

Solución en Java

/**
 * Resolución de Sudoku mediante Backtracking en Java.
 *
 * Este programa implementa un algoritmo de backtracking para resolver un juego de Sudoku.
 * El Sudoku es un rompecabezas numérico que consiste en llenar una cuadrícula de 9x9 celdas
 * con números del 1 al 9, respetando ciertas reglas de colocación para evitar repeticiones
 * en filas, columnas y subcuadrículas de 3x3. El algoritmo prueba recursivamente números
 * válidos en celdas vacías, retrocediendo cuando se alcanza una solución inválida.
 *
 * El tablero inicial se muestra antes y después de intentar resolverlo, indicando si se logró
 * completar con éxito o no. Este programa proporciona una solución interactiva para resolver
 * un Sudoku utilizando programación en Java.
 *
 */

public class Sudoku {

  public static int TAMANO_SUDOKU = 9;

  public static void main(String[] args) {
    int[][] tablero = {
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 }
    };
    imprimirTablero(tablero);
    System.out.println(validarTablero(tablero) ? "Se resolvio correctamente" : "No se pudo resolver");
    imprimirTablero(tablero);
  }

  public static void imprimirTablero(int[][] tablero) {
    System.out.println("-".repeat(TAMANO_SUDOKU + 4));
    for (int fila = 0; fila < TAMANO_SUDOKU; fila++) {
      for (int columna = 0; columna < TAMANO_SUDOKU; columna++) {
        if (columna % 3 == 0) {
          System.out.print("|");
        }
        System.out.print(tablero[fila][columna]);
      }
      System.out.print("|");
      System.out.println();
      System.out.println("-".repeat(TAMANO_SUDOKU + 4));
    }
  }

  public static boolean enFila(int[][] tablero, int numero, int fila) {
    for (int i = 0; i < TAMANO_SUDOKU; i++) {
      if (tablero[fila][i] == numero) {
        return true;
      }
    }
    return false;
  }

  public static boolean enColumna(int[][] tablero, int numero, int columna) {

    for (int i = 0; i < TAMANO_SUDOKU; i++) {
      if (tablero[i][columna] == numero) {
        return true;
      }
    }

    return false;
  }

  public static boolean en3x3(int[][] tablero, int numero, int fila, int columna) {

    int posFila3x3 = fila - fila % 3;
    int posColumna3x3 = columna - columna % 3;

    for (int i = posFila3x3; i < posFila3x3 + 3; i++) {

      for (int j = posColumna3x3; j < posColumna3x3 + 3; j++) {
        if (tablero[i][j] == numero) {
          return true;
        }
      }

    }

    return false;
  }

  public static boolean esPosicionValida(int[][] tablero, int numero, int fila, int columna) {
    return !enFila(tablero, numero, fila) &&
        !enColumna(tablero, numero, columna) &&
        !en3x3(tablero, numero, fila, columna);
  }

  public static boolean validarTablero(int[][] tablero) {
    for (int fila = 0; fila < TAMANO_SUDOKU; fila++) {
      for (int columna = 0; columna < TAMANO_SUDOKU; columna++) {
        if (tablero[fila][columna] == 0) {
          for (int numero = 1; numero < TAMANO_SUDOKU + 1; numero++) {
            if (esPosicionValida(tablero, numero, fila, columna)) {
              tablero[fila][columna] = numero;
              if (validarTablero(tablero)) {
                return true;
              } else {
                tablero[fila][columna] = 0;
              }
            }
          }
          return false;
        }
      }
    }
    return true;
  }

}