Mostrar Mensajes
1
De todo un poco... / Cómo generar un nuevo tablero de Sudoku válido
« en: 03 de Diciembre 2021, 08:12 »
En la universidad me asignaron un proyecto para crear un juego de sudoku.
Me las he arreglado para hacer todo lo necesario, es un código bastante extenso ya que tiene que ser escrito todo en un solo script.
Mi problema no es, como podrán haberse imaginado, cómo resolver un sudoku dado, pues de esto hay suficientes métodos conocidos en internet y me las puedo apañar para implementar alguno de ellos. Mi problema es el siguiente: Debe haber una opción que me genere un nuevo tablero de sudoku con el que jugar.
Para esto pensé primeramente en generar un sudoku resuelto y luego eliminar casillas aleatoriamente. Sé que esto puede no generar un tablero válido (con solución única) en todos los casos, ese sería un problema. Pero el verdadero problema es que no puedo si quiera generar un sudoku resuelto.
Estuve buen rato intentando llenar casillas haciendo que el programa busque cuales son los números posibles en dicha casilla y colocar aleatoriamente cualquiera de estos números posibles. Pero se da el caso en algunas casillas del tablero donde no hay números posibles, pues al colocarse aleatoriamente los anteriores imposibilitaron a la casilla actual de poder llevar cualquier número. Para esto me las apañé demostrando cómo es posible en estos casos realizar permutaciones con otras casillas para resolver el problema, y así conseguí llenar 6 regiones (las regiones de 3x3) satisfactoriamente, pero al llegar a las últimas regiones las casillas no tenían números posibles y no conseguí patrón alguno para realizar permutaciones. Usando otro método similar conseguí llenar 7 regiones, pero las últimas dos restantes pues les pasó el mismo problema.
Sé que también se puede conseguir un tablero por fuerza bruta siguiendo ciertos métodos. Pero mi pregunta es: ¿Puede hacerse de forma lógica? Como lo que estaba intentando de realizar permutaciones cuando se encuentre con un caso inválido, o algo que siga ciertos pasos aplicables siempre.
Como habrán visto, esto es un problema de lógica y matemática, nada de código, quizá algo de pseudocódigo. Y es algo que me gustaría saber incluso aunque no pueda encontrar una solución lógica a tiempo para el proyecto.
Me las he arreglado para hacer todo lo necesario, es un código bastante extenso ya que tiene que ser escrito todo en un solo script.
Mi problema no es, como podrán haberse imaginado, cómo resolver un sudoku dado, pues de esto hay suficientes métodos conocidos en internet y me las puedo apañar para implementar alguno de ellos. Mi problema es el siguiente: Debe haber una opción que me genere un nuevo tablero de sudoku con el que jugar.
Para esto pensé primeramente en generar un sudoku resuelto y luego eliminar casillas aleatoriamente. Sé que esto puede no generar un tablero válido (con solución única) en todos los casos, ese sería un problema. Pero el verdadero problema es que no puedo si quiera generar un sudoku resuelto.
Estuve buen rato intentando llenar casillas haciendo que el programa busque cuales son los números posibles en dicha casilla y colocar aleatoriamente cualquiera de estos números posibles. Pero se da el caso en algunas casillas del tablero donde no hay números posibles, pues al colocarse aleatoriamente los anteriores imposibilitaron a la casilla actual de poder llevar cualquier número. Para esto me las apañé demostrando cómo es posible en estos casos realizar permutaciones con otras casillas para resolver el problema, y así conseguí llenar 6 regiones (las regiones de 3x3) satisfactoriamente, pero al llegar a las últimas regiones las casillas no tenían números posibles y no conseguí patrón alguno para realizar permutaciones. Usando otro método similar conseguí llenar 7 regiones, pero las últimas dos restantes pues les pasó el mismo problema.
Sé que también se puede conseguir un tablero por fuerza bruta siguiendo ciertos métodos. Pero mi pregunta es: ¿Puede hacerse de forma lógica? Como lo que estaba intentando de realizar permutaciones cuando se encuentre con un caso inválido, o algo que siga ciertos pasos aplicables siempre.
Como habrán visto, esto es un problema de lógica y matemática, nada de código, quizá algo de pseudocódigo. Y es algo que me gustaría saber incluso aunque no pueda encontrar una solución lógica a tiempo para el proyecto.
RSS