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 metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00364330
Contributor : Eric Bourreau <>
Submitted on : Wednesday, February 25, 2009 - 5:01:30 PM
Last modification on : Thursday, May 24, 2018 - 3:59:23 PM
Long-term archiving on: Saturday, November 26, 2016 - 6:04:10 AM

File

Bourreau_CPL08_eternity.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : lirmm-00364330, version 1

Collections

Citation

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

Share

Metrics

Record views

349

Files downloads

435