Pouvez-vous résoudre le casse - tête des huit reines au moment de la compilation?
Choisissez n'importe quel format de sortie approprié.
Je suis particulièrement intéressé par une solution de métaprogrammation de modèles C ++, mais vous pouvez utiliser des langages ayant des constructions similaires, comme par exemple le système de types de Haskell.
Idéalement, votre métaprogramme afficherait toutes les solutions. Pas de codage en dur.
puzzle-solver
compile-time
R. Martinho Fernandes
la source
la source
Réponses:
Mon méta-programme trouve les 92 solutions. Ils sont imprimés sous forme de messages d'erreur:
Cela signifie que la première reine doit être placée à y = 1, la seconde à y = 5, la troisième à y = 8 et ainsi de suite.
Premièrement, quelques méta-fonctions utiles:
Ensuite, deux méta-fonctions intéressantes (notez le singulier et le pluriel):
La variable
queensstocke les coordonnées y des reines placées jusqu'à présent sur le tableau. Les trois variables suivantes stockent les lignes et les diagonales déjà occupées par des reines.xetydevrait être explicite.Le premier argument pour
if_then_elsevérifier si la position actuelle est bloquée. Si c'est le cas, la récursivité s'arrête en renvoyant le résultat (sans signification) 0. Sinon, la reine est placée sur le tableau et le processus se poursuit avec la colonne suivante.Quand x atteint 8, nous avons trouvé une solution:
Comme le
printmodèle n'a pas de membresolution, le compilateur génère une erreur.Et enfin, pour lancer le processus, nous inspectons le
valuemembre du tableau vide:Le programme complet peut être trouvé chez ideone .
la source
Je suis venu avec une solution qui utilise le système de type Haskell. J'ai cherché un peu une solution existante au problème au niveau de la valeur , puis je l'ai modifié un peu, puis je l'ai porté au niveau du type. Il a fallu beaucoup de réinventer. Je devais également activer plusieurs extensions GHC.
Premièrement, comme les entiers ne sont pas autorisés au niveau des types, je devais réinventer les nombres naturels une fois de plus, cette fois en tant que types:
L'algorithme que j'ai adapté effectue des additions et des soustractions sur les naturels, donc je devais les réinventer également. Les fonctions au niveau du type sont définies avec recours à des classes de types. Cela nécessite les extensions pour plusieurs classes de types de paramètres et dépendances fonctionnelles. Les classes de types ne peuvent pas "renvoyer de valeurs", nous utilisons donc un paramètre supplémentaire pour cela, d'une manière similaire à PROLOG.
La récursivité est implémentée avec des assertions de classe, la syntaxe est donc un peu en arrière.
Viennent ensuite les booléens:
Et une fonction pour faire des comparaisons d'inégalité:
Et des listes ...
ifs sont également absents au niveau du type ...Et avec cela, toutes les machines de soutien que j'ai utilisées étaient en place. Il est temps de s'attaquer au problème lui-même!
Commençant par une fonction pour tester si l'ajout d'une reine à un tableau existant est correct:
Notez l'utilisation d'assertions de classe pour obtenir des résultats intermédiaires. Comme les valeurs de retour sont en réalité un paramètre supplémentaire, nous ne pouvons pas appeler les assertions directement les unes des autres. Encore une fois, si vous avez déjà utilisé PROLOG, vous trouverez peut-être ce style un peu familier.
Après avoir apporté quelques modifications pour supprimer le besoin de lambdas (que j’aurais pu mettre en œuvre, mais j’ai décidé de partir un autre jour), voici à quoi ressemblait la solution initiale:
mapest une fonction d'ordre supérieur. Je pensais que mettre en œuvre des méta-fonctions d'ordre supérieur serait trop compliqué (encore une fois, les lambdas). Je me suis donc tourné vers une solution plus simple: puisque je sais quelles fonctions seront mappées, je peux implémenter des versions spécialiséesmappour chacune, de sorte que ce ne sont pas fonctions d'ordre supérieur.Et la dernière méta-fonction peut être écrite maintenant:
Il ne reste plus qu’une sorte de moteur pour convaincre les vérificateurs de types de trouver les solutions.
Ce méta-programme est supposé s'exécuter sur le vérificateur de types, on peut donc lancer
ghciet demander le type dequeens eight:Cela dépassera assez rapidement la limite de récursivité par défaut (c'est un maigre 20). Pour augmenter cette limite, nous devons appeler
ghciavec l'-fcontext-stack=Noption, oùNest la profondeur de pile souhaitée (N = 1000 et quinze minutes ne sont pas suffisants). Je n'ai pas encore vu ce processus aboutir, car cela prend beaucoup de temps, mais j'ai réussi à le fairequeens four.Il existe un programme complet sur ideone avec quelques machines pour imprimer les types de résultats, mais il ne
queens twopeut fonctionner que sans dépasser les limites :(la source
C, via le préprocesseur
Je pense que le comité ANSI a fait un choix conscient de ne pas étendre le pré-processeur C au point d’être Turing-complete. En tout cas, ce n'est pas assez puissant pour résoudre le problème des huit reines. Pas de manière générale.
Mais cela peut être fait si vous êtes prêt à coder en dur les compteurs de boucles. Bien sûr, il n'y a pas vraiment de moyen de boucler, mais vous pouvez utiliser l'auto-inclusion (via
#include __FILE__) pour obtenir une sorte de récursion limitée.Malgré la quantité horrible de contenu répétitif, laissez-moi vous assurer que le problème des huit reines est résolu de façon algorithmique. Malheureusement, la seule chose que je ne pouvais pas faire avec le préprocesseur est de mettre en place une structure de données de pile générale. Le résultat est que j'ai dû coder en dur la valeur de
ipartout où elle était utilisée pour sélectionner une autre valeur à définir. (Par opposition à la récupération de valeurs, ce qui pourrait être fait de manière très générale. C'est pourquoi le#ifdébut du fichier, qui détermine si une reine peut être ajoutée à la position actuelle, n'a pas besoin d'être répété huit fois.)Dans le code préprocesseur,
ietjindiquer la position actuelle étant considérée, alors quer,petnde garder trace dont les rangs et sont actuellement indisponibles diagonales pour le placement. Toutefois,iil sert également de compteur indiquant la profondeur actuelle de la récursivité. Par conséquent, toutes les autres valeurs utilisent réellement i comme une sorte d’indice, de sorte que leurs valeurs sont préservées lors de la reprise d’une récursion. (Et aussi à cause de la difficulté sérieuse de modifier la valeur d'un symbole de préprocesseur sans la remplacer complètement.)Le programme compilé imprime les 92 solutions. Les solutions sont intégrées directement dans l'exécutable; la sortie du préprocesseur ressemble à ceci:
Cela peut être fait, même si cela ne devrait clairement pas être le cas.
la source
Voici une solution C ++ 11 sans aucun modèle:
La solution est codée sous forme de chiffres décimaux, comme dans les réponses de FredOverflow. GCC 4.7.1 compile le fichier ci-dessus dans la source d'assemblage suivante avec
g++ -S -std=c++11 8q.cpp:La valeur du symbole
placesest 84136275, c'est-à-dire que la première reine est en a8, la seconde en b4, etc.la source
Modèle c ++, avec une seule classe de modèle définie:
le message d'erreur ressemblera à ceci:
erreur C2440: 'type cast': impossible de convertir de 'int' en 'char [15863724]'
la source