Algoritmo del generador de sudoku

Question

Hice un algoritmo para generar sudokus, pero fue terriblemente ineficiente. Cada rompecabezas tomó minutos para generar. Así que ahora estoy tratando de escribirlo de nuevo de manera óptima. Pero estoy experimentando algunos problemas con los que necesito ayuda.

1. Hay dos enfoques, comience con la cuadrícula en blanco y agregue números, luego verifique si se puede resolver. El segundo enfoque es crear una cuadrícula válida con todos los 81 números y luego eliminar hasta que estemos contentos con el número de números restantes y todavía se puede resolver.

Primero utilicé el primer enfoque, pero ahora voy a usar el segundo porque creo que es más efectivo (estamos empezando con un acertijo válido que se puede resolver). Tengo razón en que el segundo enfoque es mejor?

1. Cuando intento generar una grilla llena llena de dificultades, me encuentro con dificultades. Mi algoritmo es:

   • Establezca los candidatos para cada celda. Inicialmente son los números del 1 al 9.
   • Elija la celda aleatoria sin valor.
   • Seleccione candidato aleatorio de esa celda y asígnelo como valor de celda. Otros candidatos son descartados.
   • Ahora para cada fila, celda y la plaza correspondiente a la celda asignada Me quite valor de la celda a partir de estos candidatos, por lo que cada número es único en una fila/columna/cuadrado
   • Repita

Este La técnica garantiza una cuadrícula aleatoria sin números duplicados. Sin embargo, la mayoría de las veces, cuando no rompo ninguna regla de colocación, corro el conflicto, como las celdas vacías donde todos los candidatos han sido eliminados, etc. y necesito comenzar de nuevo. ¿Hay alguna manera más elegante/eficiente de llenar toda la cuadrícula con números sin romper las reglas de ubicación y números aleatorios?

Gracias.

Answer 1

¿Has mirado algoritmos y/o códigos existentes?

Consulte http://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf para obtener una descripción algorítmica y el artículo de Peter Norvig en http://norvig.com/sudoku.html.

Existen algunas implementaciones en Python. Hasta ahora, nunca he visto una solución de C# publicada.

¡Buena suerte!

Answer 2

Si está viendo algunos algoritmos existentes, entonces hay un proyecto de C# para eso. Eso viene directamente de la misma solución que la de Peter Norvig. Obtenga más información al respecto here

Espero que esto ayude!

Answer 3

Uso la programación para eliminar todas las entradas anteriores que entren en conflicto con la última entrada. Con este método, puedo ingresar algunos datos y periódicamente contar las soluciones o ingresar a toda la red. No he utilizado la entrada aleatoria de toda la cuadrícula porque la eliminación aleatoria de las entradas anteriores podría dar como resultado una configuración larga. Para la entrada aleatoria, esperaría que bloquear la entrada de un conflicto llevara a una celda en blanco, por lo que la respuesta podría ser vivir con una configuración larga mientras se eliminan las entradas conflictivas anteriores.Tendrá que volver a todas las celdas vacías hasta que no quede ninguna celda vacía. Cuando se llenan todas las celdas, la solución debe ser válida; de lo contrario, se habría eliminado un conflicto.