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

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.
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
Loading...

Dates and versions

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

Identifiers

  • HAL Id : lirmm-00364330 , version 1

Cite

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

Share

Gmail Facebook X LinkedIn More