Gerador aleatório de Sudoku

13

Eu quero gerar um Sudoku completamente aleatório .

Defina uma grade Sudoku como uma grade de números inteiros entre 1 e 9, onde alguns elementos podem ser omitidos. Uma grade é um quebra-cabeça válido se houver uma maneira única de completá-la para corresponder às restrições do Sudoku (cada linha, coluna e quadrado 3 × 3 alinhado não tem elemento repetido) e é mínima nesse sentido (ou seja, se você omitir mais elemento do quebra-cabeça tem várias soluções).9×9193×3

Como posso gerar um quebra-cabeça aleatório do Sudoku, de modo que todos os quebra-cabeças do Sudoku sejam equivalentes?

algorithms randomness sudoku Justin
fonte
Isto parece uma solução viável: dryicons.com/blog/2009/08/14/...
Joe
1
Agora há uma meta questão sobre isso. Por favor, discuta lá ou no chat.
21412 Kevin

Respostas:

15

Gerando o exato distribuição uniforme de todos os quebra-cabeças do sudoku pode ser feita dessa maneira: você pode gerar aleatoriamente uma grade 9x9 e mantê-la apenas se for uma grade correta do sudoku; caso contrário, tente novamente.

917 apenas gerando uma grade 8x8 aleatória e preenchendo as duas linhas restantes. Essa ainda é uma distribuição aleatória, mas ainda muito ineficiente.

[1,2,..9]9!

Talvez você veja onde eu estou indo: responder a esse problema de uma maneira inteligente provavelmente o levará a pensar sobre as simetrias subjacentes das grades do sudoku. Muito trabalho foi feito nessa direção para provar o fato de que 17 é o número mínimo de pistas para um sudoku ( consulte este artigo ) e você pode ir aqui para ver esta enumeração precisa de 5.472.730.538 classes de 3.359.232 grades semelhantes, que as utiliza simetrias:

  1. Permutações de dígitos
  2. Permutações de linhas (as faixas e as linhas dentro de cada banda)
  3. O mesmo vale para colunas
  4. Transposição

9!,64,64,2

EDIT: para adaptar isso a quebra-cabeças incompletos, você pode escolher aleatoriamente um subconjunto de sua grade, verificar se a solução é exclusiva com um solucionador de sudoku e tentar novamente, se não. Esta não é uma distribuição uniforme, pois o número de quebra-cabeças incompletos com uma solução única pode ser diferente para duas grades. (Eu ficaria muito surpreso caso contrário)

jmad
fonte
Mas Justin está pedindo uma maneira de gerar um quebra-cabeça incompleto, de modo que exista uma maneira única de completá-lo. Mesmo se você gerar uma grade 9x9 que satisfaça as restrições do Sudoku, não está claro por que remover um subconjunto específico das células forneceria um quebra-cabeça que pode ser concluído de uma maneira única.
Janoma
1
@Janoma: oh, meu mal, eu vou editar. Mas não faz muito sentido se não se define o que é um quebra-cabeça adequado. (Uma grade com apenas uma célula vazia é um quebra-cabeça?). Queremos uma grade mínima (se você remover um dígito, a solução não será mais exclusiva?) Essa é uma pergunta interessante.
Jmad
"Alguns elementos podem ser omitidos" é suficientemente preciso (ou seja, "um ou mais" elementos podem ser removidos). Por exemplo, um quebra-cabeça válido com uma célula vazia pode ser concluído de uma maneira única, enquanto um quebra-cabeça vazio não pode, pois há mais de um quebra-cabeça válido. Além disso, um quebra-cabeça válido concluído pode ser concluído de uma maneira única (trivial, vazia). A pergunta sobre a grade mínima também é interessante, mas diferente desta.
Janoma
@Janoma, jmad: um quebra-cabeça válido é normalmente mínimo, esqueci de mencionar isso.
Gilles 'SO- stop be evil' em
@ Gilles Isso é uma definição? Gostaria de saber se esse é realmente o significado pretendido do OP. Isso torna o problema muito mais difícil :-)
Janoma