Aller au contenu
Eternity II

Retour arrière

La recherche en profondeur prise au sérieux : ordres de remplissage, tri des candidats, indices de rupture, redémarrages. C'est la famille derrière chaque backtracker record.

Pourquoi c'est dur

résultat
Pourquoi un ordinateur plus rapide ne change rien
résultat
La théorie complexe : compter l'arbre de recherche avant de le parcourir
résultat
L'immédiateté des contraintes : chaque ordre de remplissage paie les mêmes 480
résultat
L'emplacement des indices l'emporte sur leur nombre

Écrire un solveur

référence
Les benchmarks de la communauté
page
Comment cherchent les solveurs record
concept
Ordres de remplissage
concept
Redémarrages et lois à queue lourde
concept
Résoudre en réparti : essaims, syndicats et fermes de cœurs
concept
Décoder les records
référence
Nombres de référence

Le laboratoire

expérience
Benchmark mono-cœur
expérience
Presets CSP, à la mesure
page
Le moteur de référence qui fait tourner ce site
expérience
CLOISTER
page
L'étude DFS
page
Comment l'étude DFS est construite
page
Ce que l'étude DFS a montré
page
L'étude sur les indices
page
Comment l'étude sur les indices est construite
page
Ce que l'étude sur les indices a montré
expérience
REPLAY
concept
Aller vite : quand un solveur dépense son budget en vitesse
expérience
Le backtracker JIT : du Rust portable à égalité avec du C optimisé sur les plateaux difficiles
expérience
Un élagage correct par comptage des couleurs pour la recherche tolérante aux ruptures
outil
L'échelle de tailles
expérience
Le backtracker C de McGavin : l'histoire du débit, reconstruit ici
expérience
Le solveur de Blackwood, décodé et exécuté ici
page
eii de Verhaard : le solveur qui a remporté l'unique prix

Voies voisines

Les neuf voies
Réduire la recherche

Écarter les états sans espoir avant que la recherche s'y épuise.

Aller plus vite

Astuces de bits et cache, et pourquoi la vitesse brute ne suffira pas.