2026-07-20T15:07:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23870 2025-11-12T13:10:43Z ddc:004 open_access

Constraint Models for Klondike Dang, Nguyen Gent, Ian P. Nightingale, Peter Ulrich-Oltean, Felix Waller, Jack AI Planning Modelling Constraint Programming Solitaire and Patience Games Klondike is the most famous single-player card game, and remains a challenging search problem even in the "thoughtful" variant where all card locations are known. We consider the full game of Klondike except for one restriction that the unusual move of "worrying back" is disallowed. This model is able to determine the winnability of all instances of the game and in practice does so in less than 2000 secs for 10,000 instances we tested, which no other known algorithm can achieve. On some instances, however, other techniques can produce answers more quickly. We use constraint modelling to produce schedules for running our constraint model in combination with other techniques. The combination outperforms any single solver across a range of time limits. Using this combination we are able to significantly improve the best estimate of winnability of Klondike without worrying back. Finally we show how we can use this work to also improve the estimate of winnability of the regular game of Klondike. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nguyen Dang and Ian P. Gent and Peter Nightingale and Felix Ulrich-Oltean and Jack Waller 2025 Is Part Of LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2025.9 urn:nbn:de:0030-drops-238702 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.9 eng https://creativecommons.org/licenses/by/4.0/legalcode