Problème De N-Queens..Où pouvons-nous aller?
Les N-Reines Problème:
ce problème indique qu'étant donné un échiquier de taille N par N, trouver les différentes permutations dans lesquelles N reines peut être placé sur l'échiquier sans aucune menace l'un l'autre.
Ma question est:
Quelle est la valeur maximale de N pour laquelle un programme peut calculer la réponse dans un délai raisonnable? Ou quel est le plus grand N que nous ayons vu jusqu'à présent?
Voici mon programme CLPFD (Prolog):
generate([],_).
generate([H|T],N) :-
H in 1..N ,
generate(T,N).
lenlist(L,N) :-
lenlist(L,0,N).
lenlist([],N,N).
lenlist([_|T],P,N) :-
P1 is P+1,
lenlist(T,P1,N).
queens(N,L) :-
generate(L,N),lenlist(L,N),
safe(L),
!,
labeling([ffc],L).
notattack(X,Xs) :-
notattack(X,Xs,1).
notattack(X,[],N).
notattack(X,[Y|Ys],N) :-
X #= Y,
X #= Y - N,
X #= Y + N,
N1 is N + 1,
notattack(X,Ys,N1).
safe([]).
safe([F|T]) :-
notattack(F,T),
safe(T).
Ce programme fonctionne très bien, mais le temps que cela prend augmente avec N. Voici un exemple d'exécution:
?- queens(4,L).
L = [2, 4, 1, 3] ;
L = [3, 1, 4, 2] ;
No
cela signifie que vous placez les 4 reines à la ligne 2 de la colonne 1, La Ligne 4 à la colonne 2, La Ligne 1 à la ligne 3 et la ligne 3 à la ligne 4.(Dans un 4 Par 4 échiquier)
voyons maintenant comment ce programme fonctionne (temps pris pour calculer la première permutation):
Pour N = 4,5.....10 calcule en une seconde
Pour N = 11-30 Entre -1-3 secondes
Pour N = 40..50 calcule encore en une minute!--7-->
À n = 60, il sort de la pile globale (L'espace de recherche étant énorme).
je suis également intéressé à voir des implémentations alternatives dans d'autres langues(ce qui fonctionne mieux que mon implémentation) ou S'il y a de la place pour l'amélioration de mon algorithme/programme
9 réponses
#!/usr/bin/env python
from itertools import permutations
n = 12
cols = range(n)
for vec in permutations(cols):
if (n == len(set(vec[i] + i for i in cols))
== len(set(vec[i] - i for i in cols))):
print vec
calculer toutes les permutations n'est pas évolutif, cependant (O(n!))
cette discussion regroupe trois problèmes de calcul différents: (1) Trouver une solution au problème de n queens, (2) énumérer toutes les solutions pour un certain n fixe, et (3) compter toutes les solutions pour un certain N. fixe.le premier problème semble délicat au début pour une taille de conseil tel que N=8. Cependant, comme Wikipedia le suggère, il est facile de le faire quand N est grand. Les reines sur une grande planche ne communiquent pas beaucoup. Sauf pour les contraintes de mémoire, une réparation heuristique algorithme a un travail plus facile et plus facile que n augmente.
énumérer chaque solution est une question différente. Cela peut probablement être fait avec un bon code de programmation dynamique jusqu'à une taille qui est assez grande qu'il n'y a aucun point dans la lecture de la sortie.
la version La plus intéressante de la question est de compter les solutions. L'état de l'art est résumé dans une référence fabuleuse connue sous le nom de The Encyclopedia of Integer Sequences. Il a été calculé jusqu'à n = 26. Je suppose que cela utilise également la programmation dynamique, mais contrairement au cas de la liste de toutes les solutions, le problème algorithmique est beaucoup plus profond et ouvert à de nouvelles avancées.
Loren Pechtel a dit: "Maintenant pour de la vraie folie: 29 a pris 9 secondes. Ça a pris presque 6 minutes!"
ce fascinant manque de prévisibilité dans le backtrack-complexité pour différentes tailles de carte était la partie de ce puzzle qui m'a le plus intéressé. Pendant des années, j'ai construit une liste des "comptes" des étapes de l'algorithme nécessaires pour trouver le première solution pour chaque taille de carte-en utilisant l'algorithme simple et bien connu de depth-first, Dans un récursif Fonction C++.
Voici une liste de tous ces "comptes" pour les conseils jusqu'à n=49 ... moins n = 46 et n = 48 qui sont toujours en cours de travail:
http://queens.cspea.co.uk/csp-q-allplaced.html
(j'ai cette liste dans L'Encyclopedia of Integer Sequences (OEIS) comme A140450)
cette page inclut un lien vers une liste des premières solutions correspondantes.
(Ma liste de premier Solutions est OEIS numéro de Séquence A141843)
Je ne Note Pas principalement combien de temps de traitement chaque solution exige, mais je note plutôt combien de queen-placements manqués ont été nécessaires avant la découverte de la solution algorithmique première de chaque conseil. Bien sûr, le taux de placement de queen dépend de la performance du CPU, mais avec un test rapide sur un CPU particulier et une taille de carte particulière, il est facile de calculer combien de temps il a fallu pour résoudre l'un des ces solutions "trouvées".
par exemple, sur un processeur Intel Pentium D 3.4 GHz, en utilisant un seul thread CPU -
- pour n = 35 mon programme "plaçait" 24 millions de reines par seconde et ne prenait que 6 minutes pour trouver la première solution.
- pour n = 47 mon programme "plaçait" 20,5 millions de reines par seconde et prenait 199 jours.
mon i7-860 actuel de 2,8 GHz traverse environ 28,6 millions de reines par seconde, essayant de trouver la première solution pour N = 48. Jusqu'à présent, il a fallu plus de 550 jours (en théorie, s'il n'avait jamais été ininterrompu) pour placer sans succès 1 369 331 731 000 000 de reines (et grimpant rapidement).
mon site web ne montre pas (encore) de code C++, mais je donne un lien sur cette page Web à mon illustration simple de chacune des 15 étapes de l'algorithme nécessaires pour résoudre le tableau N=5.
C'est un délicieux puzzle en effet!
quel système Prolog utilisez-vous? Par exemple, avec les versions récentes de SWI-Prolog, vous pouvez facilement trouver des solutions pour N=80 et N=100 en fractions de seconde, en utilisant votre code d'origine. Beaucoup d'autres systèmes Prolog seront beaucoup plus rapides que cela.
le problème N-queens est même présenté dans L'un des exemples en ligne de SWI-Prolog, disponible comme CLP(FD) queens