Actividad 6: Los Sudokus Parte 1

Descripción

Eres el encargado de desarrollar un sistema para resolver Sudokus. El sistema debe incluir las siguientes funcionalidades:

1. Generar Sudoku: Permitir a los usuarios generar un Sudoku aleatorio de 9x9.

2. Resolver Sudoku: Permitir a los usuarios resolver un Sudoku ingresando los números en las posiciones correspondientes.

3. Validar Sudoku: Permitir a los usuarios validar si un Sudoku es correcto o no.

4. Mostrar Sudoku: Permitir a los usuarios mostrar el Sudoku en un formato legible.

5. Guardar Sudoku: Permitir a los usuarios guardar el Sudoku en un archivo de texto.

Requisitos

• El sistema debe ser desarrollado en Java.

• Utilizar arreglos bidimensionales para almacenar el Sudoku.

• Utilizar JOptionPane para la interacción con el usuario.

• El sistema debe ser modular y seguir el principio de responsabilidad única.

• El Sudoku debe ser generado de forma aleatoria y debe cumplir con las reglas del Sudoku.

• El Sudoku debe ser resuelto utilizando un algoritmo de backtracking.

• El Sudoku debe ser validado verificando que no haya números repetidos en filas, columnas y subcuadrantes.

• El Sudoku debe ser mostrado en un formato legible utilizando JOptionPane.

Desarrollo de la Actividad

Para este entregable crearemos el paquete com.tec.games.sudoku, y nos centraremos en crear la clase SudokuGenerator que se encargará de generar un Sudoku aleatorio usando un algoritmo de backtracking. La clase debe incluir los siguientes métodos:

• generateSudoku(): Genera un Sudoku aleatorio de 9x9.

• isValid(int row, int col, int num): Verifica si es válido colocar un número en una posición específica.

• isValidRow(int row, int num): Verifica si el número ya existe en la fila.

• isValidColumn(int col, int num): Verifica si el número ya existe en la columna.

• isValidBox(int row, int col, int num): Verifica si el número ya existe en el subcuadrante.

• printSudoku(): Imprime el Sudoku en un formato legible.

La clase debe de contar con los siguientes atributos:

• int[][] sudoku: Matriz que representa el Sudoku, recuerda que el Sudoku es una matriz de 9x9.

Solución paso a paso

1. Crear el paquete com.tec.games.sudoku: En este paquete, define la clase SudokuGenerator.

2. Implementar el método generateSudoku(): Este método debe generar un Sudoku aleatorio de 9x9 utilizando un algoritmo de backtracking.

3. Implementar el método fillboard(int row, int col): Este método debe llenar el Sudoku de forma recursiva.

   • Si la fila y la columna son mayores a 8, significa que se ha llenado todo el Sudoku y se debe retornar true.

   • Si la columna es mayor a 8, se debe incrementar la fila y reiniciar la columna a 0.

   • Se debe generar un número aleatorio entre 1 y 9 y verificar si es válido colocarlo en la posición (row, col).

   • Si es válido, se debe colocar el número en la posición (row, col) y continuar con el siguiente número.

   • Si no es válido, se debe intentar colocar otro número en la misma posición.

4. Implementar el método isValid(int row, int col, int num): Este método debe verificar si es válido colocar un número en una posición específica del Sudoku.

5. **Implementar los métodos isValidRow(int row, int num), isValidColumn(int col, int num) y isValidBox(int row, int col, int num): Estos métodos deben verificar si el número ya existe en la fila, columna o subcuadrante correspondiente.

6. Implementar el método isValidColumn(int col, int num): Este método debe verificar si el número ya existe en la columna. Para ello se debe recorrer la columna y comparar el número que se quiere colocar con los números que ya existen en la columna. Si el número ya existe, se debe retornar false, de lo contrario se debe retornar true.

   • Ten en cuenta que existe la clase IntStream que permite recorrer un arreglo de enteros y la función noneMatch que permite verificar si un número no existe en el arreglo.

   • IntStream.range(0, sudoku.length).noneMatch(i -> sudoku[i][col] == num);

7. Implementar el método isValidRow(int row, int num): Este método debe verificar si el número ya existe en la fila. Para ello se debe recorrer la fila y comparar el número que se quiere colocar con los números que ya existen en la fila. Si el número ya existe, se debe retornar false, de lo contrario se debe retornar true.

   • Ten en cuenta que existe la clase IntStream que permite recorrer un arreglo de enteros y la función noneMatch que permite verificar si un número no existe en el arreglo.

   • IntStream.range(0, sudoku.length).noneMatch(i -> sudoku[row][i] == num);

8. Implementar el método isValidBox(int row, int col, int num): Este método debe verificar si el número ya existe en el subcuadrante. Para ello se debe recorrer el subcuadrante y comparar el número que se quiere colocar con los números que ya existen en el subcuadrante. Si el número ya existe, se debe retornar false, de lo contrario se debe retornar true.

   • Recuerda que puedes obtener una submatriz de 3x3 utilizando un bucle anidado que recorra las filas y columnas del subcuadrante, o bien utilizando la función Arrays.copyOfRange para copiar la submatriz.

   • int startRow = (row / 3) * 3; int startCol = (col / 3) * 3; for (int i = startRow; i < startRow + 3; i++) { for (int j = startCol; j < startCol + 3; j++) { if (sudoku[i][j] == num) { return false; } } } return true;
   • IntStream.range(0, 3).noneMatch(i -> IntStream.range(0, 3).noneMatch(j -> sudoku[startRow + i][startCol + j] == num));

   • Recuerda que en cualquier caso debes calcular la posición inicial del subcuadrante utilizando la división entera entre 3, y multiplicar el resultado por 3.

9. Implementar el método printSudoku(): Este método debe imprimir el Sudoku en un formato legible utilizando JOptionPane.

10. Crear una clase Main: En esta clase, crea un menú de opciones que permita a los usuarios generar un Sudoku, resolverlo, validarlo y mostrarlo. Utiliza la clase SudokuGenerator para implementar la funcionalidad del sistema.

Las funciones isValidRow, isValidColumn y isValidBox deben de ser privadas, ya que no se utilizarán fuera de la clase SudokuGenerator.

fillboard

El proceso de llenado del Sudoku se realiza de forma recursiva de la siguiente manera:

1. Se verifica si la fila es distinta de 9, lo que indica que hemos llenado todo el Sudoku, en cuyo caso se retorna true.

2. En caso contrario, tomamos un número aleatorio entre 1 y 9 y verificamos si es válido colocarlo en la posición (row, col).

3. Si es válido, colocamos el número en la posición (row, col) y llamamos recursivamente a fillboard con la siguiente posición

   • nextRow = (column == 8) ? row + 1 : row;

   • nextColumn = (column + 1) % 9;

4. Si la llamada recursiva retorna true, significa que hemos llenado el Sudoku correctamente y retornamos true.

5. Si la llamada recursiva retorna false, significa que no hemos podido llenar el Sudoku, por lo que debemos eliminar el número colocado en la posición (row, col), por lo que lo igualamos a 0 y continuar con el siguiente número.

6. Si no hemos podido colocar ningún número en la posición (row, col), retornamos false.

El proceso previo se ejemplifica en el siguiente código:

Entregables

• Código fuente del sistema.

• Pruebas funcionales que demuestren el correcto funcionamiento de cada una de las funcionalidades.

• Portada con datos de identificación del equipo de trabajo.

Criterios de Evaluación

Notas

• El sistema debe ser entregado en un archivo comprimido (zip) que contenga el código fuente y las pruebas.

• La fecha de entrega es el 16 de mayo de 2025 a las 23:59 horas.