Skip to Main content Skip to Navigation
Journal articles

Fast Global Filtering for Eternity II

Eric Bourreau 1 Thierry Benoist 2 
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Eric Bourreau Connect in order to contact the contributor
Submitted on : Wednesday, February 25, 2009 - 5:01:30 PM
Last modification on : Tuesday, September 6, 2022 - 5:00:32 PM
Long-term archiving on: : Saturday, November 26, 2016 - 6:04:10 AM


Publisher files allowed on an open archive


  • HAL Id : lirmm-00364330, version 1



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



Record views


Files downloads