8 ms·

Using Prolog for Sudoku Variants

92 points by triska 5y ago

triska 5y ago
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 http://www.staff.city.ac.uk/~jacob/solver/flops.pdf
- TimTheTinker 5y ago
  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 5y ago
    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 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.html/Placement-Constraints.html 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 http://contraintes.inria.fr/~jmartin/CBM08cp.pdf Implementing these constraints with the efficiency, generality and correctness that SICStus provides is a huge project.
    - jhgb 5y ago
      > 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. Surely the same thing could be accomplished in Lisp as well?
      - dreamcompiler 5y ago
        Yes but it would take more work. Prolog is tailor-made for solving logic and constraint problems like Sudoku out of the box; Lisp is not. That said, it's relatively easy to write a version of Prolog in Lisp and then just use that to solve the problem. Both pg and Peter Norvig show that in their Lisp books.
      - simplify 5y ago
        It can indeed! Both lisp and prolog are homoiconic :)
      - Tomte 5y ago
        Yes, and commercial Lisp implementations often include a reasonably performant Prolog. If you'd like to see how to do that yourself: https://github.com/norvig/paip-lisp https://github.com/norvig/paip-lisp
  - mzl 5y ago
    The underlying implementation of the main classical part of the solvers are fairly similar. See for example the overview of how to implements such systems by the main authors of SICStus Prolog and Gecode in https://chschulte.github.io/papers/schultecarlsson-cph-2006.html https://chschulte.github.io/papers/schultecarlsson-cph-2006.... . Choosing a solver to solve a specific problem comes down to experience, familiarity, available global constraints, and suitability for the problem and implementation environment at hand. With that said, solvers such as OR-Tools (in their newer CP-SAT engine) and Chuffed are using something called Lazy Clause Generation, which can be very effective for many problems. This is partly a newer way to implements CP solvers that uses a built-in SAT solver as the domain store. I know of no Prolog system that uses this architecture.
- alserio 5y ago
  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 5y ago
    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 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/conformity_testing 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 5y ago
      Thanks!
  - jjgreen 5y ago
    SWI is still going strong, the main git repo looks to be consistently merging 3-4 PRs a month.
  - oldsecondhand 5y ago
    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.
- castratikron 5y ago
  I've found that a lot of "logic" problems on standardized tests like the LSAT or whatever are really just puzzles that force you to permute through the problem space and apply rules. I was able to do this pretty quickly when I discovered Prolog (very bored during covid). I've become convinced that there is likely at least one person employed in writing these tests that generated these questions with the same technique.
- TimTheTinker 5y ago
  Is it possible for Prolog to beat OptaPlanner in terms of convenience and usability in a production context? As I understand it, local search and simulated annealing enable constraints to be expressed as arbitrary functions that return a Boolean or integer -- which can be much easier to express and connect to domain models than first-class logical predicates (at the price of a guaranteed optimum solution).
  - freemint 5y ago
    Not for planning tasks. Prolog essentially expands a search tree depth first. OptaPlanner can and probably does do better things. Yes you could implement OptaPlanner in Prolog but then you are no longer using the Prolog language facilities.
wgetch 5y ago
Answer set programming is also well suited for combinatorial search problems such as this. The classic approach for ASP solvers is to reduce a logic program into an instance of the boolean SAT problem and feed that into a SAT solver. The language used in ASP is a variant of Prolog called AnsProlog. AnsProlog programs may have variables which are grounded before solving, and programs may produce any number of stable models (satisfiable solutions). Here is my own general Sudoku solver in AnsProlog: #const d=3. #const n=d*d. 1 { s(X,Y,1..n) } 1 :- X=1..n, Y=1..n. % Achieved: A value is chosen for each cell X1=X2 :- s(X1,Y,N), s(X2,Y,N). Y1=Y2 :- s(X,Y1,N), s(X,Y2,N). % Achieved: No value is duplicated for any given row or column r(X,Y,Z) :- X=1..n, Y=1..n, Z=((X-1)/d)*d+((Y-1)/d)+1. (X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)=0 :- s(X1,Y1,N), s(X2,Y2,N), r(X1,Y1,Z), r(X2,Y2,Z). % Achieved: No value is duplicated within a d*d region #show s/3. The program above can be used to generate completed puzzles from scratch, or it can be combined with an input file containing an incomplete puzzle to generate any or all valid solutions. Due to the semantics of ASP, additional constraints can be appended to the program to support Sudoku variants without modifying the existing lines.
Agentlien 5y ago
While I studied AI at the KULeuven in Belgium we had a course in logic programming and one of the assignments was using Prolog to solve Sudoku. In fact we were taught a number of logic programing languages and had a set of games, including Sudoku which we had to create solvers for in each of the languages.
asah 5y ago
Don't get me wrong, Prolog is cool... but in 2021, why use a completely different language and not a SAT solver DSL (domain specific language) bound into your favorite imperative language, e.g. Python. Then you get all your favorite libraries for I/O, data transformation, UI/UX, etc. Examples include Google OR-tools, Microsoft Z3, etc. https://developers.google.com/optimization https://developers.google.com/optimization https://github.com/Z3Prover/z3 https://github.com/Z3Prover/z3
- maweki 5y ago
  I understand the sentiment for a problem where the instance size is quite known. SAT solvers have become incredibly fast. Just note that encoding terms of various shapes in SAT is very difficult. Encoding terms of unknown size doubly so. Encoding problems in Prolog is very easy in that sense, as you can build arbitrarily shaped terms very easily and you can constrain variables within terms and not only on the top level. The sudoku example, with the fixed shape and all variables at the top level is a prime example for SAT solving though.

92 points by triska 5y ago

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 http://www.staff.city.ac.uk/~jacob/solver/flops.pdf

TimTheTinker 5y ago
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 5y ago
  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 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.html/Placement-Constraints.html 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 http://contraintes.inria.fr/~jmartin/CBM08cp.pdf Implementing these constraints with the efficiency, generality and correctness that SICStus provides is a huge project.
  - jhgb 5y ago
    > 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. Surely the same thing could be accomplished in Lisp as well?
    - dreamcompiler 5y ago
      Yes but it would take more work. Prolog is tailor-made for solving logic and constraint problems like Sudoku out of the box; Lisp is not. That said, it's relatively easy to write a version of Prolog in Lisp and then just use that to solve the problem. Both pg and Peter Norvig show that in their Lisp books.
    - simplify 5y ago
      It can indeed! Both lisp and prolog are homoiconic :)
    - Tomte 5y ago
      Yes, and commercial Lisp implementations often include a reasonably performant Prolog. If you'd like to see how to do that yourself: https://github.com/norvig/paip-lisp https://github.com/norvig/paip-lisp
- mzl 5y ago
  The underlying implementation of the main classical part of the solvers are fairly similar. See for example the overview of how to implements such systems by the main authors of SICStus Prolog and Gecode in https://chschulte.github.io/papers/schultecarlsson-cph-2006.html https://chschulte.github.io/papers/schultecarlsson-cph-2006.... . Choosing a solver to solve a specific problem comes down to experience, familiarity, available global constraints, and suitability for the problem and implementation environment at hand. With that said, solvers such as OR-Tools (in their newer CP-SAT engine) and Chuffed are using something called Lazy Clause Generation, which can be very effective for many problems. This is partly a newer way to implements CP solvers that uses a built-in SAT solver as the domain store. I know of no Prolog system that uses this architecture.
alserio 5y ago
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 5y ago
  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 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/conformity_testing 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 5y ago
    Thanks!
- jjgreen 5y ago
  SWI is still going strong, the main git repo looks to be consistently merging 3-4 PRs a month.
- oldsecondhand 5y ago
  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.
castratikron 5y ago
I've found that a lot of "logic" problems on standardized tests like the LSAT or whatever are really just puzzles that force you to permute through the problem space and apply rules. I was able to do this pretty quickly when I discovered Prolog (very bored during covid). I've become convinced that there is likely at least one person employed in writing these tests that generated these questions with the same technique.
TimTheTinker 5y ago
Is it possible for Prolog to beat OptaPlanner in terms of convenience and usability in a production context? As I understand it, local search and simulated annealing enable constraints to be expressed as arbitrary functions that return a Boolean or integer -- which can be much easier to express and connect to domain models than first-class logical predicates (at the price of a guaranteed optimum solution).
- freemint 5y ago
  Not for planning tasks. Prolog essentially expands a search tree depth first. OptaPlanner can and probably does do better things. Yes you could implement OptaPlanner in Prolog but then you are no longer using the Prolog language facilities.

wgetch 5y ago

Answer set programming is also well suited for combinatorial search problems such as this. The classic approach for ASP solvers is to reduce a logic program into an instance of the boolean SAT problem and feed that into a SAT solver. The language used in ASP is a variant of Prolog called AnsProlog. AnsProlog programs may have variables which are grounded before solving, and programs may produce any number of stable models (satisfiable solutions). Here is my own general Sudoku solver in AnsProlog: #const d=3. #const n=d*d. 1 { s(X,Y,1..n) } 1 :- X=1..n, Y=1..n. % Achieved: A value is chosen for each cell X1=X2 :- s(X1,Y,N), s(X2,Y,N). Y1=Y2 :- s(X,Y1,N), s(X,Y2,N). % Achieved: No value is duplicated for any given row or column r(X,Y,Z) :- X=1..n, Y=1..n, Z=((X-1)/d)*d+((Y-1)/d)+1. (X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)=0 :- s(X1,Y1,N), s(X2,Y2,N), r(X1,Y1,Z), r(X2,Y2,Z). % Achieved: No value is duplicated within a d*d region #show s/3. The program above can be used to generate completed puzzles from scratch, or it can be combined with an input file containing an incomplete puzzle to generate any or all valid solutions. Due to the semantics of ASP, additional constraints can be appended to the program to support Sudoku variants without modifying the existing lines.

Agentlien 5y ago

While I studied AI at the KULeuven in Belgium we had a course in logic programming and one of the assignments was using Prolog to solve Sudoku. In fact we were taught a number of logic programing languages and had a set of games, including Sudoku which we had to create solvers for in each of the languages.

asah 5y ago

Don't get me wrong, Prolog is cool... but in 2021, why use a completely different language and not a SAT solver DSL (domain specific language) bound into your favorite imperative language, e.g. Python. Then you get all your favorite libraries for I/O, data transformation, UI/UX, etc. Examples include Google OR-tools, Microsoft Z3, etc. https://developers.google.com/optimization https://developers.google.com/optimization https://github.com/Z3Prover/z3 https://github.com/Z3Prover/z3

maweki 5y ago
I understand the sentiment for a problem where the instance size is quite known. SAT solvers have become incredibly fast. Just note that encoding terms of various shapes in SAT is very difficult. Encoding terms of unknown size doubly so. Encoding problems in Prolog is very easy in that sense, as you can build arbitrarily shaped terms very easily and you can constrain variables within terms and not only on the top level. The sudoku example, with the fixed shape and all variables at the top level is a prime example for SAT solving though.