Você consegue resolver o quebra - cabeça das oito rainhas em tempo de compilação?
Escolha qualquer formato de saída adequado.
Estou particularmente interessado em uma solução de metaprogramação de modelos C ++, mas você pode usar linguagens que têm construções semelhantes, como, por exemplo, o sistema de tipos de Haskell.
Idealmente, seu metaprograma produziria todas as soluções. Sem codificação.
puzzle-solver
compile-time
R. Martinho Fernandes
fonte
fonte
Respostas:
Meu metaprograma encontra todas as 92 soluções. Eles são impressos como mensagens de erro:
Isso significa que a primeira dama deve ser colocada em y = 1, a segunda em y = 5, a terceira em y = 8 e assim por diante.
Primeiro, algumas meta-funções úteis:
Então, duas meta-funções interessantes (observe o singular e o plural):
A variável
queensarmazena as coordenadas y das rainhas colocadas no tabuleiro até o momento. As três variáveis a seguir armazenam as linhas e diagonais que já estão ocupadas por rainhas.xeydeve ser auto-explicativo.O primeiro argumento para
if_then_elseverificar se a posição atual está bloqueada. Se for, a recursão pára retornando o resultado (sem sentido) 0. Caso contrário, a dama é colocada no tabuleiro e o processo continua na próxima coluna.Quando x atinge 8, encontramos uma solução:
Como o
printmodelo não tem membrosolution, o compilador gera um erro.E, finalmente, para iniciar o processo, inspecionamos o
valuemembro do tabuleiro vazio:O programa completo pode ser encontrado em ideone .
fonte
Eu vim com uma solução que usa o sistema do tipo Haskell. Pesquisei um pouco por uma solução existente para o problema no nível de valor , mudei um pouco e levantei-a para o nível de tipo. Foi preciso muita reinvenção. Eu também tive que habilitar várias extensões do GHC.
Primeiro, como números inteiros não são permitidos no nível de tipo, eu precisava reinventar os números naturais mais uma vez, desta vez como tipos:
O algoritmo que adaptei faz acréscimos e subtrações aos naturais, então tive que reinventá-los também. As funções no nível de tipo são definidas com recurso às classes de tipo. Isso requer extensões para várias classes de tipo de parâmetro e dependências funcionais. As classes de tipo não podem "retornar valores"; portanto, usamos um parâmetro extra para isso, de maneira semelhante a PROLOG.
A recursão é implementada com asserções de classe, portanto, a sintaxe parece um pouco atrasada.
Em seguida foram os booleanos:
E uma função para fazer comparações de desigualdade:
E lista ...
ifs também estão ausentes no nível de tipo ...E com isso, todas as máquinas de apoio que eu usei estavam no lugar. Hora de resolver o problema em si!
Começando com uma função para testar se adicionar uma dama a um quadro existente está correto:
Observe o uso de asserções de classe para obter resultados intermediários. Como os valores de retorno são realmente um parâmetro extra, não podemos simplesmente chamar as asserções diretamente uma da outra. Novamente, se você já usou o PROLOG antes, pode achar esse estilo um pouco familiar.
Depois de fazer algumas alterações para remover a necessidade de lambdas (que eu poderia ter implementado, mas decidi sair por mais um dia), é a aparência da solução original:
mapé uma função de ordem superior. Eu pensei que a implementação de meta-funções de ordem superior seria muito complicada (mais uma vez as lambdas), então eu apenas segui com uma solução mais simples: como eu sei quais funções serão mapeadas, eu posso implementar versões especializadas demapcada uma, para que elas não sejam funções de ordem superior.E a última meta-função pode ser escrita agora:
Tudo o que resta é algum tipo de driver para persuadir o mecanismo de verificação de tipo para encontrar as soluções.
Esse metaprograma deve ser executado no verificador de tipos, para que você possa iniciar
ghcie solicitar o tipo dequeens eight:Isso excederá o limite de recursão padrão bastante rápido (são apenas 20). Para aumentar esse limite, precisamos chamar
ghcicom a-fcontext-stack=Nopção, ondeNestá a profundidade da pilha desejada (N = 1000 e quinze minutos não é suficiente). Ainda não vi essa execução completa, pois leva muito tempo, mas consegui executá-laqueens four.Existe um programa completo em ideone com algumas máquinas para imprimir os tipos de resultados, mas só
queens twopode ser executado sem exceder os limites :(fonte
C, através do pré-processador
Penso que o comitê ANSI fez uma escolha consciente de não estender o pré-processador C ao ponto de estar completo em Turing. De qualquer forma, não é realmente poderoso o suficiente para resolver o problema das oito rainhas. Não de maneira geral.
Mas isso pode ser feito, se você quiser codificar os contadores de loop. Não há uma maneira real de fazer o loop, é claro, mas você pode usar a autoinclusão (via
#include __FILE__) para obter um tipo limitado de recursão.Apesar da quantidade horrível de conteúdo repetitivo, garanto-lhe que ele realmente está resolvendo o problema das oito rainhas algoritmicamente. Infelizmente, a única coisa que não pude fazer com o pré-processador é implementar uma estrutura geral de dados da pilha push-down. O resultado é que eu tive que codificar o valor de
ionde quer que fosse usado para selecionar outro valor para definir. (Ao contrário de recuperar valores, o que poderia ser feito de maneira geral. É por isso que a#ifparte superior do arquivo, que decide se uma dama pode ser adicionada na posição atual, não precisa ser repetida oito vezes.)Dentro do código pré-processador,
iejindicar a posição atual que está sendo considerado, enquantor,penmanter o controle dos quais fileiras e diagonais estão actualmente indisponíveis para a colocação. No entanto,itambém funciona como o contador que marca a profundidade atual da recursão; portanto, na verdade, todos os outros valores realmente usam i como uma espécie de subscrito, para que seus valores sejam preservados ao retomar de uma recursão. (E também devido à séria dificuldade de modificar o valor de um símbolo de pré-processador sem substituí-lo completamente.)O programa compilado imprime todas as 92 soluções. As soluções são incorporadas diretamente no executável; a saída do pré-processador é assim:
Isso pode ser feito, mesmo que claramente não deva.
fonte
Aqui está uma solução C ++ 11 sem nenhum modelo:
A solução é codificada como dígitos decimais, como nas respostas do FredOverflow. O GCC 4.7.1 compila o arquivo acima na seguinte fonte de montagem com
g++ -S -std=c++11 8q.cpp:O valor do símbolo
placesé 84136275, ou seja, a primeira rainha está em a8, a segunda em b4 etc.fonte
O modelo c ++, com apenas uma classe de modelo, está definido:
então a mensagem de erro será semelhante a:
erro C2440: 'tipo de conversão': não é possível converter de 'int' para 'char [15863724]'
fonte