Estou tentando criar um gerador de quebra-cabeça Sudoku. É muito mais difícil do que eu esperava e quanto mais eu entro, mais difícil fica!
Minha abordagem atual é dividir o problema em 2 etapas:
- Gere um quebra-cabeça completo (resolvido) de Sudoku.
- Remova os números até que seja solucionável e tenha apenas 1 solução.
Na etapa 1, como estou usando métodos de força bruta, estou enfrentando alguns problemas de tempo de execução. Existe uma maneira ideal de preencher um quebra-cabeça completo de Sudoku?
Na etapa 2, que tipo de algoritmo devo usar para "confundir" um sudoku resolvido?
algorithm
puzzle
content-generation
user223150
fonte
fonte
Respostas:
Eu tenho um jogo de Sudoku mais vendido na loja de aplicativos iOS. Aqui está como eu criei quebra-cabeças.
Primeiro, tenho um aplicativo gerador de quebra-cabeças. Mas isso não faz parte do código do jogo. É um aplicativo independente que eu uso para fazer quebra-cabeças. É altamente modificado para que eu possa configurá-lo para criar diferentes tipos de padrões, classificações de dificuldade, número de dados, etc. Gerar quebra-cabeças e obter um nível de dificuldade consistente é difícil de fazer em tempo real e leva mais tempo do que um jogador gostaria de esperar. Então, eu gero o que chamo de "quebra-cabeças" e é isso que é usado pelo código do jogo para gerar os quebra-cabeças que as pessoas jogam.
Não estou respondendo como codificar um gerador aqui. Você pode pesquisar no Google e encontrar on-line toneladas de código gerador de quebra-cabeças. Comece por aí. Mas para fazer um bom jogo, você precisa fazer um bom jogo. Meu jogo não gera quebra-cabeças em tempo real.
A maneira como meu aplicativo gerador de quebra-cabeça funciona é que ele gera milhares de quebra-cabeças por minuto, mas eles não são todos bons e nem correspondem a uma classificação de dificuldade específica. O gerador cria um quebra-cabeça, depois o resolve e calcula uma classificação de dificuldade, e classifica o quebra-cabeça com base nas técnicas necessárias para resolvê-lo e determina se é necessário adivinhar para resolvê-lo (o que geralmente é ruim). Ele joga fora todos os quebra-cabeças que não correspondem a um critério. Para quebra-cabeças difíceis, mas não impossíveis, em uma máquina rápida, pode levar uma hora para gerar 100 quebra-cabeças que correspondem às minhas especificações exatas. É por isso que não faço isso no aplicativo. Gerar quebra-cabeças em tempo real com essas especificações difíceis não funcionaria para a qualidade dos quebra-cabeças que tenho no meu aplicativo.
Os quebra-cabeças são seqüências de caracteres, 162 caracteres, 81 caracteres com números e traços ou pontos em que os espaços em branco estarão, depois outros 81 com a solução. Em seguida, colunas para cada uma das estatísticas, como quantos singles, duplos, etc.
Minha saída de todas as sessões de geração são linhas delimitadas por vírgula com as estatísticas como colunas. Vou pegar talvez 10.000 quebra-cabeças, trazê-los para o excel e classificá-los por dificuldade. Em seguida, traga-os para um aplicativo para vê-los no tabuleiro do jogo. Também os olho para apelo visual e padrões visíveis ao quebra-cabeça. Então eu mão escolher daqueles.
Eu os chamo de quebra-cabeças e aqui está o que eu quero dizer. Os números em um jogo de sudoku são realmente apenas fichas. Em vez de serem os números de 1 a 9, eles podem ser cores, símbolos ou letras. Então meus enigmas de sementes não são números, são as letras ai. Cada quebra-cabeça inicial é alterado rapidamente para criar um quebra-cabeça jogável:
Portanto, cada quebra-cabeça de semente pode criar 5.806.080 variações. Eu testei isso em campo com jogadores reais. As pessoas não sabem que estão essencialmente jogando o mesmo quebra-cabeça. Na verdade, é impossível. Somente se eles perceberem que o padrão em que estão os dados é sempre o mesmo. Mas, mesmo com 100 sementes diferentes, ninguém notará. Um milhão de usuários do meu jogo não. Também testei com aplicativos solucionadores. Um aplicativo solucionador não resolve um quebra-cabeça da mesma maneira quando é girado ou flopado. Às vezes, ele até o analisa como uma classificação de dificuldade diferente, embora seja tecnicamente o mesmo quebra-cabeça.
No entanto, o Big Bad Sudoku Book possui dezenas de milhares de quebra-cabeças de sementes em 5 níveis de dificuldade e vários tipos de padrões de quebra-cabeças. Isso significa que existem bilhões de quebra-cabeças no meu jogo. A cada 10.000 quebra-cabeças de sementes, há 58.060.800.000 quebra-cabeças diferentes.
Na versão 4 do Sudoku Book (prevista para 2016), descobri uma maneira de poder especificar um quebra-cabeça exato desses 58 bilhões e obter o mesmo quebra-cabeça no dispositivo de cada jogador.
fonte
Existe uma maneira fácil de preencher um quebra-cabeça completo do Sudoku - preenchimento de grupo e troca circular.
Para impedir que o usuário observe o padrão óbvio, pode ser uma boa idéia aleatoriamente a ordem das linhas e das colunas para que não exista mais nenhum padrão. Desde que todos os 9 números em cada linha / coluna se movam juntos como uma unidade atômica, o quadro Sudoku sempre permanecerá válido.
Você recebe um quebra-cabeça completo de Sudoku. Para mais detalhes, você pode pesquisar "make Sudoku".
fonte
Não é muito difícil, desde que você tenha um solucionador de sudoku.
Criar resolvedores de sudoku é um problema difícil / interessante, por isso é melhor salvá-lo para uma pergunta diferente. Ou você pode simplesmente ler isso e ver como vai.
1, 2, 3, 4, ...
e escolha o primeiro que funcione. Você precisa embaralhar essa ordem para que ela tente, digamos4, 7, 2, 9, ...
,. Esse processo deve ser tão rápido quanto o seu solucionador.Este é um método muito simples (e ingênuo), portanto, não há garantia de que você terá quebra-cabeças com certa dificuldade - além do número de números ausentes - ou se você pode remover a quantidade de números que deseja. Espero que isso ajude de qualquer maneira.
fonte
Apenas acho interessante apontar esta página da Web , pois me ajudou muito no desenvolvimento do projeto. Fazer um sudoku com uma solução única está longe de ser uma tarefa simples. No link, você encontra como o autor (ele realmente fez um ótimo trabalho, não sou eu eh!), Encontrou várias estratégias diferentes. Você pode ter uma ideia para gerar seu próprio solucionador de Sudoku.
Agora, seguindo o tópico, também há uma maneira de gerar sudokus semelhantes, apenas
Saúde e boa sorte com o algoritmo: D
fonte
Meu solucionador está usando força bruta e pode encontrar uma solução em 20 milissegundos. Usando o método de exclusão descrito acima, meu gerador produz um quebra-cabeça em 200 milissegundos.
Geralmente, gera um quebra-cabeça com cerca de 24 a 34 dígitos restantes, e ainda não sei como eles conseguem produzir um quebra-cabeça de 17 dígitos.
fonte