Fast Global Filtering for Eternity II - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Constraint Programming Letters (CPL) Year : 2008

Fast Global Filtering for Eternity II

Eric Bourreau


In this paper we consider the enumeration of all solutions of a 2D edge-matching puzzle. We show that a judicious modeling of the problem, combined with the use of appropriate data structures allows obtaining an effective filtering algorithm with complexity O(1) at each node of tree search. Our experiments show the relevancy of the proposed power/complexity trade-off, compared to the results of some of the best available brute force tree search algorithms and to classical Constraint Programming models.
Fichier principal
Vignette du fichier
Bourreau_CPL08_eternity.pdf (547.99 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive

Dates and versions

lirmm-00364330 , version 1 (25-02-2009)


  • HAL Id : lirmm-00364330 , version 1


Eric Bourreau, Thierry Benoist. Fast Global Filtering for Eternity II. Constraint Programming Letters (CPL), 2008, 3, pp.036-049. ⟨lirmm-00364330⟩
285 View
389 Download


Gmail Facebook X LinkedIn More