Generador de Sudoku aleatorio

13

Quiero generar un Sudoku completamente al azar .

Defina una cuadrícula de Sudoku como una cuadrícula de enteros de entre 1 y 9 donde se pueden omitir algunos elementos. Una cuadrícula es un rompecabezas válido si hay una manera única de completarla para que coincida con las restricciones de Sudoku (cada línea, columna y cuadrado alineado 3 × 3 no tiene elementos repetidos) y es mínimo en ese sentido (es decir, si omite más) elemento del rompecabezas tiene múltiples soluciones).9 9×9 919 93×3

¿Cómo puedo generar un rompecabezas de Sudoku aleatorio, de modo que todos los rompecabezas de Sudoku sean equipables?

algorithms randomness sudoku Justin
fuente
Esto parece una solución viable: dryicons.com/blog/2009/08/14/…
Joe
1
Ahora hay una meta pregunta con respecto a esto. Por favor discuta allí o en el chat.
Kevin

Respuestas:

15

La generación de la distribución uniforme exacta de todos los rompecabezas de sudoku se puede hacer de esa manera: puede generar aleatoriamente una cuadrícula de 9x9 y luego solo mantenerla si es una cuadrícula de sudoku correcta, de lo contrario, vuelva a intentarlo.

Este enfoque de fuerza bruta le garantiza una distribución uniforme, pero claramente no es eficiente, ya que puede multiplicar la probabilidad de que la cuadrícula sea correcta por solo generando una cuadrícula aleatoria de 8x8 y luego llene las dos líneas restantes. Esta sigue siendo una distribución aleatoria, pero sigue siendo demasiado ineficiente.9 917

También se puede obligar a la primera línea de ser , luego genera aleatoriamente el resto de la cuadrícula y luego selecciona aleatoriamente una permutación de todos los dígitos. ¡Todavía elegirás todas las cuadrículas con la misma probabilidad pero 9 ! Más rápido.[1,2,..9 9]9 9!

Quizás vea a dónde voy: responder este problema de una manera inteligente probablemente lo llevará a preguntarse sobre las simetrías subyacentes de las cuadrículas de sudoku. Se hizo mucho trabajo en esta dirección para demostrar el hecho de que 17 es el número mínimo de pistas para un sudoku ( vea este artículo ) y puede ir aquí para ver esta enumeración precisa de 5.472.730.538 clases de 3.359.232 cuadrículas similares, que utiliza estas simetrías

  1. Permutaciones de dígitos
  2. Permutaciones de filas (las bandas y las filas dentro de cada banda)
  3. Lo mismo para las columnas.
  4. Transposición

Con este marco, puede elegir aleatoriamente una de las 5.472.730.538 clases (en realidad se pueden comprimir en 6 GB) y luego elegir uno de los representantes para cada simetría, ¡uno de cada .9 9!,6 64 4,6 64 4,2

EDITAR: para adaptar esto a rompecabezas incompletos, puede elegir aleatoriamente un subconjunto de su cuadrícula, verificar si la solución es única con un solucionador de sudoku e intentar nuevamente si no. Esta no es una distribución uniforme ya que el número de rompecabezas incompletos con una solución única puede ser diferente para dos cuadrículas. (Estaría muy sorprendido de lo contrario)

jmad
fuente
Pero Justin está pidiendo una forma de generar un rompecabezas incompleto de tal manera que haya una forma única de completarlo. Incluso si genera una cuadrícula de 9x9 que satisfaga las restricciones de Sudoku, no está claro por qué eliminar un subconjunto específico de las celdas le daría un rompecabezas que se puede completar de una manera única.
Janoma
1
@ Janoma: oh, mi mal, voy a editar. Pero no es muy significativo si uno no define qué es un rompecabezas apropiado. (¿Una cuadrícula con una sola celda vacía es un rompecabezas?). ¿Queremos una cuadrícula mínima (es decir, si elimina un dígito, la solución ya no es única?) Esa es una pregunta interesante.
jmad
"Algunos elementos se pueden omitir" es lo suficientemente preciso (es decir, se pueden eliminar "uno o más" elementos). Por ejemplo, un rompecabezas válido con una celda vacía se puede completar de una manera única, mientras que un rompecabezas vacío no, ya que hay más de un rompecabezas válido. Además, un rompecabezas válido completado se puede completar de una manera única (trivial, vacía). La pregunta sobre la cuadrícula mínima también es interesante, pero diferente de esta.
Janoma
@Janoma, jmad: un rompecabezas válido es normalmente mínimo, olvidé mencionar eso.
Gilles 'SO- deja de ser malvado'
@Gilles ¿Es esa una definición? Me pregunto si ese es realmente el significado previsto del PO. Hace que el problema sea mucho más difícil :-)
Janoma