[HN Gopher] Using Prolog for Sudoku Variants
___________________________________________________________________
Using Prolog for Sudoku Variants
Author : triska
Score : 43 points
Date : 2021-07-19 20:06 UTC (2 hours ago)
(HTM) web link (dstrohmaier.com)
(TXT) w3m dump (dstrohmaier.com)
| triska wrote:
| Prolog is exceptionally well suited for solving such
| combinatorial puzzles, and of course also for much tougher tasks
| like timetabling instances in schools, workforce rosters,
| tournament schedules etc.
|
| The key feature that makes Prolog so attractive for such tasks is
| the availability of _constraint solvers_ that ship with many
| Prolog systems and which can be used to elegantly express these
| tasks in terms of relations between integers, Boolean variables,
| rational numbers and other domains. The sophistication and
| efficiency of constraint solvers depend heavily on the used
| Prolog system, and fast constraint solvers are often an important
| motivation for buying a commercial Prolog system such as SICStus
| Prolog.
|
| Interestingly, constraint solvers can themselves be implemented
| elegantly and efficiently in Prolog too. See for example _A Pearl
| on SAT Solving in Prolog_ by Howe and King, where the authors use
| Prolog and its delay declarations to implement a succinct SAT
| solver with watched literals and unit propagation:
|
| http://www.staff.city.ac.uk/~jacob/solver/flops.pdf
| TimTheTinker wrote:
| I'm curious how solvers in commercial Prolog systems compare to
| the family of MiniZinc solvers, like Google's OR-Tools or
| GECode.
|
| There are plenty of examples of Sudoku models in MiniZinc, and
| models for many other combinatorial problems as well.
| triska wrote:
| Yes, it is easy to express simple tasks like Sudoku in
| MiniZinc. However, in terms of sophistication and
| convenience, Prolog is hard to beat, since it is a full-
| fledged programming language that can also be used to fetch,
| process and transform any available input in any way
| necessary to make it amenable to all built-in constraint
| solvers.
|
| Compared to a Prolog program, a MiniZinc model is quite hard
| to parse and reason about programmatically: Every Prolog
| program is also a valid Prolog term, and can be reasoned
| about logically as long as we keep to the pure monotonic core
| of Prolog, which also includes constraints. Pure Prolog
| programs can be debugged declaratively by generalizing away
| goals, whereas for example removing a line of a MiniZinc
| model may render the model invalid.
|
| In addition, Prolog provides logic variables and therefore
| allows interesting questions to be asked about the model,
| such as queries about _partially known_ data. This, in
| combination with Prolog being a programming language, allows
| its application in a way that is not readily available, or
| may not be possible at all, with more special-purpose tools
| and modeling languages. For instance, David C. Norris is
| using Scryer Prolog and its integer constraints to model and
| analyse dose escalation trials as they arise in clinical
| oncology, exceeding the expressiveness of other modeling
| languages:
|
| https://github.com/dcnorris/precautionary
|
| Regarding sophistication, a good example are dedicated
| placement constraints of SICStus Prolog such as the geost/N
| family of constraints:
|
| https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.ht.
| ..
|
| The publication _A Geometric Constraint over k-Dimensional
| Objects and Shapes Subject to Business Rules_ by Carlsson,
| Beldiceanu and Martin gives an overview of what is going on
| behind the scenes when these constraints are posted:
|
| http://contraintes.inria.fr/~jmartin/CBM08cp.pdf
|
| Implementing these constraints with the efficiency,
| generality and correctness that SICStus provides is a huge
| project.
| alserio wrote:
| I've really liked Prolog during university, but I've never used
| a constraint solver embedded in Prolog. Do you know of any non
| commercial Prolog system with this kind of integration to play
| with? I remember using SWIProlog at the time
| triska wrote:
| GNU Prolog has one of the fastest constraint solvers over
| finite domains (i.e., small integers), and its constraints
| are available out of the box, without loading any library.
| For example: $ gprolog GNU Prolog
| 1.4.5 (64 bits) Compiled Mar 24 2020, 20:46:07 with
| gcc By Daniel Diaz Copyright (C) 1999-2020
| Daniel Diaz | ?- X #> 3. X =
| _#2(4..268435455) yes
|
| GNU Prolog 1.5.0 was recently released, and the source
| repository is now available at:
|
| https://github.com/didoudiaz/gprolog
|
| GNU Prolog is a nice Prolog system for learning Prolog, also
| because it is currently the only free system that correctly
| handles all syntactic ISO conformity tests collected at:
|
| https://www.complang.tuwien.ac.at/ulrich/iso-
| prolog/conformi...
|
| This means that GNU Prolog can be reliably used to learn what
| is valid Prolog syntax and what is not.
| alserio wrote:
| Thanks!
| jjgreen wrote:
| SWI is still going strong, the main git repo looks to be
| consistently merging 3-4 PRs a month.
| oldsecondhand wrote:
| SWI Prolog also comes with constraint solvers. It has CLP(B)
| (booleans), CLP(FD)(finite domain), CLP(Q,R) (rationals and
| reals) and CHR (constraint handling rules). These come as
| standard libraries, no additional installation needed.
|
| If you want to get started, I recommend starting with CLP(FD)
| as that has a lot of tutorials and is highly compatible
| between Prolog implementations.
___________________________________________________________________
(page generated 2021-07-19 23:00 UTC)