pith. sign in

arxiv: 1907.00245 · v1 · pith:G5CROCQSnew · submitted 2019-06-29 · 💻 cs.AI

Ludii and XCSP: Playing and Solving Logic Puzzles

C\'edric Piette , \'Eric Piette , Matthew Stephenson , Dennis J. N. J. Soemers , Cameron Browne This is my paper

Pith reviewed 2026-05-25 12:43 UTC · model grok-4.3

classification 💻 cs.AI
keywords logic puzzlesLudiiXCSPconstraint programmingCSP solversNP-complete puzzlesgeneral game systems
0
0 comments X

The pith

Logic puzzles from the Ludii system can be translated into XCSP instances and solved by any CSP solver.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out to show that logic puzzles expressed in the Ludii general game system can be converted into the XCSP formalism. Once in that form, any standard constraint solver can find solutions. A reader would care because many popular puzzles belong to the NP-complete class, so automated solving offers practical help for both generating and verifying solutions while constraint programming matches the declarative style of these puzzles.

Core claim

The central claim is that logic puzzles described in Ludii can be mapped to XCSP instances so that any CSP solver can be used to solve them, building on the observation that such puzzles are often NP-complete and that constraint programming is a natural fit for finding and checking their solutions.

What carries the argument

The mapping that turns a Ludii puzzle description into an equivalent XCSP instance while preserving the original rules and solution set.

If this is right

  • Any existing CSP solver becomes applicable to the full range of Ludii logic puzzles without custom code for each puzzle.
  • Verification of proposed solutions becomes straightforward once the instance is in XCSP form.
  • The same translation opens a route to solving other NP-complete puzzles that can be expressed in Ludii.
  • Puzzle designers gain access to off-the-shelf solvers for testing difficulty or uniqueness.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • An automated translator from Ludii to XCSP could be added to the Ludii platform to give users built-in solving support.
  • The approach might extend to generating new puzzles by searching the XCSP space for instances with desired properties.
  • Similar translations could link Ludii to other constraint or SAT frameworks beyond XCSP.

Load-bearing premise

Every logic puzzle that can be written in Ludii has an exact counterpart in XCSP that adds no extra solutions and loses none of the original meaning.

What would settle it

Take any Ludii puzzle with a known solution set, translate it to XCSP, and check whether the solver returns exactly the same solutions with no invalids and no omissions.

Figures

Figures reproduced from arXiv: 1907.00245 by Cameron Browne, C\'edric Piette, Dennis J. N. J. Soemers, \'Eric Piette, Matthew Stephenson.

Figure 3
Figure 3. Figure 3: Game description of a Sudoku puzzle on a [PITH_FULL_IMAGE:figures/full_fig_p002_3.png] view at source ↗
Figure 1
Figure 1. Figure 1: Game description of a Sudoku puzzle on a [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Example of a Sudoku puzzle on a 4×4 grid. quantification, distributed, probabilistic and qualitative rea￾soning. The new format is made compact, highly readable, and easy to parse. Similar to the philosophy of ludemes this format allows us to encapsulate the structure of the problem models, through the possibilities of declaring arrays of variables, and identifying syntactic and semantic groups of constrai… view at source ↗
read the original abstract

Many of the famous single-player games, commonly called puzzles, can be shown to be NP-Complete. Indeed, this class of complexity contains hundreds of puzzles, since people particularly appreciate completing an intractable puzzle, such as Sudoku, but also enjoy the ability to check their solution easily once it's done. For this reason, using constraint programming is naturally suited to solve them. In this paper, we focus on logic puzzles described in the Ludii general game system and we propose using the XCSP formalism in order to solve them with any CSP solver.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper claims that many single-player logic puzzles are NP-complete and that constraint programming is well-suited to solve them; it focuses on puzzles described in the Ludii general game system and proposes translating them into the XCSP formalism so that any CSP solver can be used.

Significance. A verified, semantics-preserving translation from Ludii ludemes to XCSP would allow reuse of mature CSP solvers on the growing library of Ludii puzzles, potentially improving both automated puzzle solving and the interoperability of general game-description systems with constraint technology.

major comments (2)
  1. [Abstract] Abstract: the central claim that 'logic puzzles described in the Ludii general game system' can be solved via XCSP encodings is asserted without any translation rules, equivalence proof, or example mapping; the manuscript therefore provides no evidence that the mapping is semantics-preserving or free of spurious solutions.
  2. [Abstract] Abstract: no account is given of how Ludii's higher-order constructs (dynamic ludeme evaluation, player-specific filters, etc.) are encoded in XCSP's static constraint language, leaving the claim that the approach works for 'every' expressible puzzle unverified.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. The concerns correctly identify that the current manuscript is a high-level proposal and does not yet contain the detailed translation machinery needed to substantiate the central claim. We will perform a major revision to address both points.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that 'logic puzzles described in the Ludii general game system' can be solved via XCSP encodings is asserted without any translation rules, equivalence proof, or example mapping; the manuscript therefore provides no evidence that the mapping is semantics-preserving or free of spurious solutions.

    Authors: We agree that the abstract asserts the claim without supporting material. The present manuscript is a short position paper and contains neither explicit translation rules nor an equivalence argument. In the revised version we will add (i) a section defining the mapping from a core set of Ludii ludemes to XCSP variables and constraints, (ii) a worked example for at least one puzzle (e.g., Sudoku), and (iii) a brief argument that the encoding preserves solutions for the supported ludemes and introduces no spurious solutions. revision: yes

  2. Referee: [Abstract] Abstract: no account is given of how Ludii's higher-order constructs (dynamic ludeme evaluation, player-specific filters, etc.) are encoded in XCSP's static constraint language, leaving the claim that the approach works for 'every' expressible puzzle unverified.

    Authors: The manuscript does not address higher-order or dynamic constructs. We will revise the abstract and introduction to restrict the claim to the static, single-player logic puzzles for which a direct mapping is feasible. We will also add a short discussion of the limitations, noting that dynamic ludeme evaluation would require a preprocessing step to produce an equivalent static XCSP instance and that player-specific filters are outside the current scope. revision: yes

Circularity Check

0 steps flagged

No circularity; methodological proposal with no self-referential derivation

full rationale

The paper proposes encoding logic puzzles from the Ludii system into XCSP instances for solution by CSP solvers. No equations, fitted parameters, predictions, or first-principles derivations are present that could reduce to their own inputs by construction. No self-citation load-bearing steps, uniqueness theorems, or ansatzes are invoked. The central claim is a direct methodological suggestion whose validity rests on the (unproven here) mapping assumption, but this does not constitute circularity under the defined patterns. The derivation chain is self-contained and non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proposal rests on the domain assumption that Ludii puzzles are naturally expressible as constraint satisfaction problems; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Logic puzzles expressible in Ludii can be faithfully represented as constraint satisfaction problems
    Invoked in the abstract when the authors state that XCSP can be used to solve them.

pith-pipeline@v0.9.0 · 5626 in / 1030 out tokens · 41026 ms · 2026-05-25T12:43:08.972701+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · 1 internal anchor

  1. [1]

    Collins, The Times Japanese Logic Puzzles: Hitori Hashi, Slitherlin k and Mosaic , London, 2006

    H. Collins, The Times Japanese Logic Puzzles: Hitori Hashi, Slitherlin k and Mosaic , London, 2006

    work page 2006

  2. [2]

    Realization of a general game-playing progr am

    J. Pitrat, “Realization of a general game-playing progr am.” in IFIP Congress, 1968, pp. 1570–1574

    work page 1968

  3. [3]

    A survey of Monte Carlo tree search methods,

    C. Browne, E. Powley, D. Whitehouse, S. Lucas, P . I. Cowli ng, P . Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton, “A survey of Monte Carlo tree search methods,” IEEE Transactions on Computational Intelligence and AI in Games , vol. 4, no. 1, pp. 1–49, 2012

    work page 2012

  4. [4]

    Learning simulation con trol in general game-playing agents,

    H. Finnsson and Y . Bj¨ ornsson, “Learning simulation con trol in general game-playing agents,” in Proceedings of AAAI’10 , 2010, pp. 954–959

    work page 2010

  5. [5]

    Single-player monte-carlo tree search fo r samegame,

    M. P . D. Schadd, M. H. M. Winands, M. J. W. Tak, and J. W. H. M. Uiterwijk, “Single-player monte-carlo tree search fo r samegame,” Know.-Based Syst., vol. 34, pp. 3–11, Oct. 2012

    work page 2012

  6. [6]

    Feature selection as a one-playe r game,

    R. Gaudel and M. Sebag, “Feature selection as a one-playe r game,” in Proceedings of ICML’10 , 2010, pp. 359–366

    work page 2010

  7. [7]

    The nature of puzzles,

    C. B. Browne, “The nature of puzzles,” Game & Puzzle Design , vol. 1, no. 1, pp. 23–34, 2015

    work page 2015

  8. [8]

    Computational complexity of games and puzz les,

    D. M. Costa, “Computational complexity of games and puzz les,” CoRR,

    work page

  9. [9]

    Available: http://arxiv.org/abs/1807.0 4724

    [Online]. Available: http://arxiv.org/abs/1807.0 4724

    work page

  10. [10]

    Generating and solving logi c puzzles through constraint satisfaction,

    B. O’Sullivan and J. Horan, “Generating and solving logi c puzzles through constraint satisfaction,” in Proceedings of AAAI’07, Canada , 2007, pp. 1974–1975

    work page 2007

  11. [11]

    Comparing ASP and CP on four grid puzzles,

    M. C ¸ elik, H. Erdogan, F. Tahaoglu, T. Uras, and E. Erdem , “Comparing ASP and CP on four grid puzzles,” in Proceedings of the 16th Inter- national RCRA W orkshop: Experimental Evaluation of Algori thms for Solving Problems with Combinatorial Explosion , 2009

    work page 2009

  12. [12]

    Constraint logic programmin g: A survey,

    J. Jaffar and M. J. Maher, “Constraint logic programmin g: A survey,” J. Log. Program., vol. 19/20, pp. 503–581, 1994

    work page 1994

  13. [13]

    Ludii - the ludemic general game sys tem,

    ´E. Piette, D. J. N. J. Soemers, M. Stephenson, C. F. Sironi, M. H. M. Winands, and C. Browne, “Ludii - the ludemic general game sys tem,” CoRR, vol. abs/1905.05013, 2019

    work page arXiv 1905

  14. [14]

    XCSP3: an in tegrated format for benchmarking combinatorial constrained proble ms,

    F. Boussemart, C. Lecoutre, and C. Piette, “XCSP3: an in tegrated format for benchmarking combinatorial constrained proble ms,” CoRR,

    work page

  15. [15]

    Available: http://arxiv.org/abs/1611.0 3398

    [Online]. Available: http://arxiv.org/abs/1611.0 3398

    work page

  16. [16]

    Modern techniques for ancient games,

    C. Browne, “Modern techniques for ancient games,” in IEEE Conference on CIG . IEEE, 2018, pp. 490–497

    work page 2018

  17. [17]

    A class grammar for general games,

    C. B. Browne, “A class grammar for general games,” in Advances in Computer Games , ser. LNCS, vol. 10068, 2016, pp. 167–182

    work page 2016

  18. [18]

    General game playing: Game description language specifica tion,

    N. Love, T. Hinrichs, D. Haley, E. Schkufza, and M. Genes ereth, “General game playing: Game description language specifica tion,” 2008

    work page 2008

  19. [19]

    Pspace-completeness of s liding-block puzzles and other problems through the nondeterministic co nstraint logic model of computation,

    R. A. Hearn and E. D. Demaine, “Pspace-completeness of s liding-block puzzles and other problems through the nondeterministic co nstraint logic model of computation,” CoRR, 2002

    work page 2002

  20. [20]

    Constr aint-based sym- metry detection in general game playing,

    F. Koriche, S. Lagrue, E. Piette, and S. Tabary, “Constr aint-based sym- metry detection in general game playing,” in Proceedings of IJCAI’17 , 2017, pp. 280–287

    work page 2017

  21. [21]

    Ludii and XCSP: Playing and Solving Logic Puzzles

    C. Browne, “Deductive search for logic puzzles,” in IEEE Conference on CIG , 2013, pp. 359–366. This figure "CaptureSudoku.PNG" is available in "PNG" format from: http://arxiv.org/ps/1907.00245v1

    work page internal anchor Pith review Pith/arXiv arXiv 2013