Solving Sudoku with Prolog (2016)

https://www.metalevel.at/sudoku/

by hjek • 7 years ago

179 73 7 years ago

triska9• 7 years ago

Thank you very much for the publicity, I greatly appreciate your interest!

Prolog is extremely well-suited for solving combinatorial tasks like Sudoku puzzles, and also for tough practical challenges such such as timetabling, scheduling and allocation tasks on an industrial scale.

The key feature that makes Prolog so efficient and frequently used for such tasks is constraint propagation, provided via libraries or as a built-in feature in many Prolog system. Fast and efficient constraint propagation is often an important reason for buying a commercial Prolog system.

In this example, I am using CLP(FD/ℤ), constraint logic programming over finite domains/integers, the amalgamation of constraint programming (CP) and logic programming (LP), which blend especially seamlessly. I have uploaded a short video that shows how it works for Sudoku puzzles:

https://www.metalevel.at/prolog/videos/sudoku

If you are interested in constraint solving, a few related videos may also be useful:

https://www.metalevel.at/prolog/videos/n_queens

https://www.metalevel.at/prolog/videos/knights_and_knaves

https://www.metalevel.at/prolog/videos/map_colouring

These videos are all work in progress, and they may be replaced by better versions at any time. However, the links above will always point to the latest version.

Enjoy!

aidos• 7 years ago

I studied prolog years ago at university and more recently rediscovered the power of solvers (like SCIP). Is not really thought about how the 2 crossed over before. How does prolog compare to a solver these days?

triska9• 7 years ago

The primary attraction of CLP, i.e., the combination of constraint programming (CP) and logic programming (LP), is that you get a full-blown programming language (most frequently: Prolog) and in addition seamlessly integrated solvers (over integers, rational numbers, Herbrand terms etc.).

CP can of course be hosted on — or provided as library for — other languages too. However, it blends in most seamlessly with a logic programming language like Prolog as its host language.

Regarding efficiency, the top-of-the-line Prolog systems provide many of the most efficient and most sophisticated algorithms for combinatorial optimization tasks that are commercially used.

See for example the customers page of SICStus Prolog for several interesting applications:

https://sicstus.sics.se/customers.html

SilasX• 7 years ago

I'm not sure if this is a well-formed question, but ... how does this approach compare to solving such problems with general SAT-solvers? Don't the latter allow you to use techniques that search the space more efficiently?

Or is it hot-swappable in some sense? Could you take Prolog and have it solve a CP problem with a SAT solver doing the work under the hood?

triska9• 7 years ago

The question is perfectly well-formed!

It is, however, very broad, and I try to answer it very broadly.

First, SAT solvers are powerful and efficient. SAT is one of the most studied problems in CS, both from a theoretical and practical perspective. Donald Knuth dedicates a huge portion of The Art of Computer Programming to exactly this topic. For example, quoting from https://www-cs-faculty.stanford.edu/~knuth/news.html:

Satisfiability is far from an abstract exercise in understanding formal systems. Revolutionary methods for solving such problems emerged at the beginning of the twenty-first century, and they've led to game-changing applications in industry. These so-called “SAT solvers” can now routinely find solutions to practical problems that involve millions of variables and were thought until very recently to be hopelessly difficult.

I highly recommend this as a profound treatment of the subject for readers at all levels of expertise.

Second, SAT solvers can be combined seamlessly with Prolog. In Prolog terminology, SAT is CLP(B), constraint logic programming over Boolean variables.

From the perspective of a Prolog application programmer, you simply state what must hold about the variables, using Prolog predicates like conjunction, disjunction etc., you state which variables must be 1 and which must be 0 etc.

Internally, a Prolog system may invoke an external SAT solver, or implement its own version of SAT solving, to find a satisfying assignment. Both approaches exist in the literature and in practice. For example, see A Pearl on SAT Solving in Prolog by Jacob M. Howe and Andy King:

http://www.staff.city.ac.uk/~jacob/solver/

As another approach and reference, I have put together a small page about a different CLP(B) system that internally uses Binary Decision Diagrams (BDDs) to solve SAT instances:

https://www.metalevel.at/clpb/

Third and finally, SAT is a comparatively low-level approach for expressing combinatorial tasks. Perfectly doable (for example, by automatic translation/compilation to SAT), but still low-level. That does not mean that it's inadequate. In fact, some aspects of the "true structure" of a problem may reveal themselves and allow an efficient solution only at that low level.

It is perfectly possible to express Sudoku as a SAT problem, using CLP(B). For example:

    sudoku(Rows) :-
            length(Rows, 9), maplist(same_length(Rows), Rows),
            maplist(row_booleans, Rows, BRows),
            maplist(booleans_distinct, BRows),
            transpose(BRows, BColumns),
            maplist(booleans_distinct, BColumns),
            BRows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
            blocks(As, Bs, Cs), blocks(Ds, Es, Fs), blocks(Gs, Hs, Is).

    blocks([], [], []).
    blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
            booleans_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
            blocks(Ns1, Ns2, Ns3).

    booleans_distinct(Bs) :-
            transpose(Bs, Ts),
            maplist(card1, Ts).

    card1(Bs) :- sat(card([1],Bs)).

    row_booleans(Row, Bs) :-
            same_length(Row, Bs),
            maplist(cell_boolean, Row, Bs).

    cell_boolean(Num, Bs) :-
            length(Bs, 9),
            sat(card([1],Bs)),
            element(Num, Bs, 1).

But the general point remains: Working - for example - with integers or Herbrand terms, or rational numbers etc., is more high-level and a more natural fit for many combinatorial tasks of practical relevance, and often allows also more efficient and more complete propagation, because more of the high-level structure of a task can be taken into account.

bcrosby95• 7 years ago

I've toyed with trying to use Prolog for procedural map generation in my hobby RPG game. The idea is to feed it a high level human designed map and let it fill in the details. Not sure if you have any thoughts on if it might be suitable for something like that or not.

triska9• 7 years ago

In general, Prolog is extremely well suited for tasks where partial information needs to be taken into account.

The presence of logic variables, i.e., "true" variables in the sense of logic, is one of the defining characteristics of logic programming languages like Prolog. In comparison, what other programming languages call a "variable", is not really a variable but just some concrete value. In contrast, a logic variable truly stands for anything at all and may be bound to any term (in its domain).

For this reason, Prolog is especially well suited for data that has "holes" in it. For example, Prolog was successfully used to investigate the folding structure of DNA, where hypotheses were available about some aspects, but the overall structure of parts was yet unknown. A Prolog specification allows to "leave out" parts of the specification that are unknown.

Hence, a map generation task where some constraints are specified sounds like a very nice project and potentially great application for a logic programming language. Enjoy!

samwalrus• 7 years ago

Check out: http://cplint.lamping.unife.it/example/inference/tile_map.pl

https://www.youtube.com/watch?v=wDr7v94G_MU

https://books.google.co.uk/books?hl=en&lr=&id=oaxwDwAAQBAJ&o...

hjek13• 7 years ago

I've truly enjoyed all the Prolog videos on your channel[0].

I had to program a timetabling system where each event had a specific set of requirements, and your article and video about solving sudokus and the n-queens helped me grasp the problem.

I have only been using Prolog for a month, but I could not go back to Lisp now (at least not without MiniKanren). There's still plenty of stuff I don't understand about Prolog, but it feels very expressive and powerful even with just a superficial understanding of the language.

Thank you so much for your work! Your teaching materials are very accessible for beginners. Hope you will one day make a video about DCGs (Definite Clause Grammars). I wonder if reading Noam Chomsky will help my understanding of them?

Since we are on Hacker News, I think it's interesting to look at PG's experience with Prolog, which unfortunately hasn't been as rewarding as mine:

There are features, most notably Prolog-style pattern-matching, that seem to promise great savings in length, but turn out only to be useful for writing a few basic sequence operations like append, remove, and so on. Prolog is a great language for writing append; after that it's all downhill.[1]
A way of expressing programs that was more abstract, but made your programs longer, would not be very enticing. (This is not just a hypothetical example. It happens in Prolog.)[2]

From watching your videos, it's easy to see how concise Prolog programs are though. I find that my own Prolog programs also tend to be extremely brief (compared to Lisp or SQL).

[0] https://invidio.us/channel/UCFFeNyzCEQDS4KCecugmotg

[1] http://www.paulgraham.com/arcchallenge.html

[2] http://www.paulgraham.com/arcll1.html

triska9• 7 years ago

Thank you very much for your kind words! I greatly appreciate your feedback, and I am very glad that you benefit from the videos!

Also, I would like to take this opportunity to thank you all collectively for your thoughtful participation in this thread, your comments and endorsements. Your feedback, encouragement and insights are making this work especially worthwhile!

abecedarius2• 7 years ago

more abstract, but made your programs longer

There are a few main reasons for Prolog code to come out longer than Lisp:

- Prolog style is mostly first order -- there's not a direct equivalent of lambda.

- Mutation is also used less.

- There's an equivalent of Lisp macros, but it's also less common.

- You don't nest function calls, but pass common named arguments instead.

So I can see where he was coming from. On the other hand I'd guess he had his Prolog experience before constraint logic programming was well supported, and certainly before MiniKanren which gives back the conveniences of Lisp and helps you take the pure-declarative subset further.

new4thaccount4• 7 years ago

Thanks for your hard work. I really want to like Prolog, but I often don't know how to fit it into an actual system of use.

My field is power systems which involves solving numerical problems with large sparse matrices and very large scale optimization problems (millions of constraints) using LP and MIP solvers.

The first class of problems can be easily solved with tools like Matlab, Fortran, Python, Julia, C++...etc. The optimization problems can be solved with any language that has a library to talk to a solver.

Prolog is really cool, but I doubt it could solve problems of that size even if given days, much less a few minutes. I'd love to be proven wrong, but it seems like it really excels at these small toy problems. Could you enlighten my ignorance on how it can be used on larger scale problems? Thanks in advance!

hjek13• 7 years ago

I haven't used Prolog at that scale myself, but I'll just add completely unsubstantiated hearsay from the ##Prolog IRC on FreeNode: Someone reported no problems using SWI Prolog for running queries on "59 million facts".

It might also be worth checking Triska's video about n-queens[0] where the last 2/3 is all about optimising the search and using different labelling strategies.

Don't know if it's relevant for your problem, but memoization is also a thing in Prolog[1] like in other languages.

Maybe not the answer you're looking for. Is your system relatively simple to describe? Then we can give it a try...

[0] https://invidio.us/watch?v=l_tbL9RjFdo

[1] https://swish.swi-prolog.org/example/tabling.swinb

ggggtez2• 7 years ago

Prolog is good for discrete search like this, mostly because it's just hiding the underlying search algorithm that other languages would be to be explicit about (but as a result, other languages can search more efficiently).

segmondy2• 7 years ago

All computer science problems can be reduced to sorting & searching. ;-D

randomsearch• 7 years ago

Is this really true? I was wondering about complexity analysis, for example.

jodrellblank• 7 years ago

Other languages can search more efficiently if you write a more efficient search in them, but Prolog can search more efficiently if you write a more efficient search in it, too.

"That's it. On backtracking, this generates increasingly longer lists Ls, and invokes p/1 only on lists of bounded length. Bamm! Iterative deepening. [..] asymptotically optimal under very general assumptions, and you can make it easily available in Prolog yourself. I guess mostly for this reason, the default execution strategy is kept extremely simple. When needed, you can easily implement other search strategies on top of it." - https://www.reddit.com/r/prolog/comments/47fchf/why_depthfir...

segmondy2• 7 years ago

Solving Sudoku smartly with Prolog.

The nice thing with Prolog is that if you don't understand how to program but you understand the rules/logic of the problem. In this case you understand the rules of Sudoku, you can define the board and the rules and Prolog will brute force it for you. Harder to do in other languages.

alexbanks• 7 years ago

This was a final project in a course I took in college surveying programming languages. I thought Prolog was insanely interesting. Through most of the project I thought it was crazy, but when I finished it made excellent sense.

Since then I've thought a lot about using Prolog for optimized job/task scheduling, but I've never had an actual need to do it.

justkez• 7 years ago

I did a module in my undergrad degree that used Prolog as the learning tool/language. At the time I didn't understand why Prolog was such a different paradigm (declarative); all I remember is feeling a true sense of joy writing prolog code and running it.

I've never found/made up a reason to try it out since then and no language/system/paradigm has given me the same enjoyment since!

protomyth• 7 years ago

I love the embedded PostScript in the source code. Its always fun to see how other people write their code.

triska9• 7 years ago

Thank you for noting this!

PostScript is currently underappreciated, and I highly recommend learning it. Among many other uses, I like to use PostScript as a portable animation language to visualize search processes like in this case.

Also, programming PostScript is great fun and in a sense quite timeless: In all likelihood, these definitions will work without change also in the distant future, because PostScript is so widely spread and frequently used.

Newer graphics languages and concepts also take many ideas from PostScript, but PostScript is in my experience still the most fun and flexible of them, at least for a very large set of important use cases.

bluetwo• 7 years ago

Curious about 2 things:

1) Can it solve especially hard Sudoku puzzles? (ie, expert level where humans often get stuck)

2) Is there a resource somewhere that lists the types of Prolog problems that it excels at solving?

hjek13• 7 years ago

1) Yes, and (when there is only one unique solution) it can apparently be found in Prolog without doing an search at all by using constraint logic programming. Check the video in the sudoku article.

2) I'm not the best at answering this as I'm quite new to Prolog, but I'll try. I'd say a) anything you'd use a general purpose programming languge for, b) anything you'd use SQL for, and c) anything that's too difficult to do in either of those.

SWI Prolog[0] has a large standard library and feels very "batteries included".

Perhaps what I wouldn't use it for is mobile apps..? (But then again, there's Tau Prolog[1] which could probably work in a Cordova app).

[0] http://www.swi-prolog.org/

[1] http://tau-prolog.org/

taeric4• 7 years ago

I'm curious on your first point. There are puzzles that have multiple legal plays but only a single solution. In those, guessing/searching is basically required, right?

new4thaccount4• 7 years ago

How is Prolog ideal for when you'd use SQL? I can understand it if you're talking about querying a CSV file, but the advantage to SQL is that the database with all your data natively supports SQL and it can usually run pretty fast.

Btw: what would it look like to query a small sample CSV file. Like the below example if you wanted to find all cars that are made by Ford?

Brand,Model,Year,Color/n Ford,F150,1999,Black/n Toyota,Yaris,2013,Yellow/n Ford,Mustang,1969,Blue/n

Edit: sorry for not knowing how to format HN properly and show the newline on each of the rows.

ufo• 7 years ago

In my experience you need a very contrived Sudoku instance to make it hard for a computer. Usually even the "hard" instances can be quickly solved by a computer search.

OJFord2• 7 years ago

I love the simplicity or prolog; I often think it/datalog would be great as a query language for applications.

e.g. instead of Jira having its JQL or whatever, it would just have a prelude, then you'd write things like:

    my_team_working_on_it(ticket) :-
        assigned(ticket, user),
        on_team(user, team),
        on_team(current_user, team).

Or to search for tickets assigned to you (like defining a board filter):

    assigned(_, current_user)

elamje• 7 years ago

Check out datomic database

fiddlerwoaroof• 7 years ago

Also datascript

OJFord2• 7 years ago

Thought it rang a bell from a databases lecture - seems it 'extends' datalog:

https://docs.datomic.com/cloud/whatis/data-model.html#datalo...

Thanks for reminding me, must find an excuse to play with it!

pezo1919• 7 years ago

The only thing prevents me using prolog for proper tasks is not getting its IO: reading/writing files: csv, json.

Any cool (video) tuts on it? I searched a lot but did not find anything "easy".

hjek13• 7 years ago

Say you have a file, `foo.json`, with the content:

   {"foo":"bar"}

Run `swipl` and first load the JSON library:

    ?- [library(http/json)].
    true.

Then open the file `foo.json` (in read mode) as Stream which JSON read translates to Term:

    ?- open('foo.json', read, Stream), json_read(Stream, Term).
    Stream = <stream>(0x557f0cbfb1c0),
    Term = json([foo=bar]).

(Both instances of `Stream` are the same because of unification.)

Say `foo.csv` containts:

    foo,bar

Then go:

    ?- [library(csv)].
    true.
    
    ?- csv_read_file("foo.csv",Rows).
    Rows = [row(foo, bar)].

Triska's videos are quite theoretical. Anne Ogborn has a lot of good real world programming tutorials[0]. Can highly recommend the web app tutorial[1].

I don't know any good videos that cover this. I'm happy to help with what I can though, and I've also found the ##Prolog IRC on Freenode helpful.

[0] http://www.pathwayslms.com/swipltuts/

[1] http://www.pathwayslms.com/swipltuts/html/index.html

GavinMcG• 7 years ago

Peter Norvig's Sudoku solver using constrain propagation is a nice demonstration of the mini-Kanren approach.[0]

I spoke at RubyConf a few years ago on the basics of logic programming and constraint propagation, and demoed a (poorly-coded) solver interface.[1]

[0]https://norvig.com/sudoku.html

[1]https://m.youtube.com/watch?v=f5Bi6_GOIB8

triska9• 7 years ago

In my opinion, a key attraction of Prolog is the regularity of its syntax and the relation between its syntax and semantics.

I mean not only homoiconicity, but something beyond that.

For example, one of the first questions of Prolog beginners is usually: "Why does my predicate fail for a specific query?"

Prolog allows us to mechanically find and give a minimal explanation why a query fails. We can do this by systematically generalizing the program and show a minimal fragment that still fails. We can mechanically generalize a program by using logic variables instead of concrete values, and by removing goals (i.e., constraints) from conjunctions.

A key attraction of Prolog is that if you take any pure program, and replace any of the goals by true/0, you still get a valid and more general (or at least equally general) program.

For example, take the Prolog program:

    my_list(Ls) :-
        Ls = [a,b|Rs],
        Ls = [a,c|Rs].

In this example, I am using trivial constraints (only (=)/2), and the mistake is quite obvious. But the point remains: We can remove and generalize any and all goals and give explanations why a query fails.

For example, why does the most general query, i.e., ?- my_list(Ls)., fail?

A possible explanation could like like this:

    my_list(Ls) :-
        Ls = [a,b|Rs],
        * Ls = [a,c|Rs].

here, I have used ( * )/1 to "generalize away" a goal, using a suitable definition of ( * )/1 like:

    :- op(920,fy, *). *_.

The fact that the query then succeeds tells us that the second goal is, in a sense, a reason for the failure.

No other language I have seen gives comparable guarantees and ways of debugging. For example, suppose I remove a single form in a miniKanren program. The result may no longer even constitute a valid program, and even if it does, I am not aware of any meaningful general property that can be said about the remaining program.

The ability to systematically generate explanations like this seems to be quite unique to logic programming languages like Prolog.

maebert• 7 years ago

I can’t help but to feel delightfully nostalgic whenever I read about Prolog, thanks for writing this up. If you’re interested, I’ve created a set of Prolog exercises about 10 years ago when I was teaching this in college, including one for “advanced Sudoku”:

https://github.com/maebert/prolog_puzzles/blob/master/readme...

tmaly• 7 years ago

I would love to see Prolog implemented in hardware like the Lisp machines.

tom_mellior3• 7 years ago

It's been done, though only in an academic setting:

https://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5991.html

https://www.researchgate.net/publication/242056713_Special_o... (sorry to link to ResearchGateKeeper, though somehow by closing the tab, deleting cookies, and opening the tab I managed to get it to give me the PDF without needing to log in, lol)

https://www.sciencedirect.com/science/article/pii/S074310669... (Elsevier, urgh)

I'm sure a bit of web searching will turn up more. It looks like having special purpose hardware for Prolog is useful, which I don't find too surprising. But if you make hardware, you need someone to give you money for it.

As an aside, I wonder now much of the use of Lisp machines was non-academic. I know that there were actual commercial companies selling them, but where those mostly university spinoffs selling back to universities?

lispm• 7 years ago

It's been done, though only in an academic setting

See the Melcom PSI computer from Mitsubishi.

http://museum.ipsj.or.jp/en/computer/other/0009.html

As an aside, I wonder now much of the use of Lisp machines was non-academic. I know that there were actual commercial companies selling them, but where those mostly university spinoffs selling back to universities?

I would think that roughly 10000 hardware Lisp machines were built (incl. embedded boards). Quite a lot went into research, but not just academic research, but also company R&D.

Some machines were built as deployment machines and were used by military, government agencies (like NASA) and also commercial.

Notable were for example the graphics systems by Symbolics which were widely used in high-end graphics for TV and animation studios. A lot of computer animated logos you were seeing in TV in the mid/end 80s were done with them.

Examples:

https://www.youtube.com/watch?v=Cwer_xKrmI4

https://www.youtube.com/watch?v=n21FSKDjObg

But there were a bunch of other early deployed applications on Lisp Machines: 3d cad (iCAD), American Express Authorizer (credit authorization expert system), scheduling for the Hubble Space Station, scheduling for power plant operations, seat allocation optimization for swissair, early military troop virtual reality training system, satellite image processing, ...

carapace• 7 years ago

Triska on the front page! Sweet.

It was in large part thanks to "The Power of Prolog" that I was able to figure out a nice solution to the "Zebra" puzzle:

    /*

    Via https://www.metalevel.at/prolog/puzzles

    The "Zebra Puzzle" https://en.wikipedia.org/wiki/Zebra_Puzzle

    -    There are five houses.
    -    The Englishman lives in the red house.
    -    The Spaniard owns the dog.
    -    Coffee is drunk in the green house.
    -    The Ukrainian drinks tea.
    -    The green house is immediately to the right of the ivory house.
    -    The Old Gold smoker owns snails.
    -    Kools are smoked in the yellow house.
    -    Milk is drunk in the middle house.
    -    The Norwegian lives in the first house.
    -    The man who smokes Chesterfields lives in the house next to the man with the fox.
    -    Kools are smoked in the house next to the house where the horse is kept.
    -    The Lucky Strike smoker drinks orange juice.
    -    The Japanese smokes Parliaments.
    -    The Norwegian lives next to the blue house.

    Now, who drinks water? Who owns the zebra?

    In the interest of clarity, it must be added that each of the five houses is painted
    a different color, and their inhabitants are of different national
    extractions, own different pets, drink different beverages and smoke
    different brands of American cigarets [sic].
    One other thing: in statement 6, right means your right.

    */
    :- use_module(library(clpfd)).


    house_next_to(H0, H1) :- abs(H0 - H1) #= 1.
    /* Thanks https://www.metalevel.at/prolog/puzzles */

    puzzle(Vars) :- 
 
     Vars = [GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse,
      Englishman, Spaniard, Ukrainian, Norwegian, Japanese,
      Dog, Snails, Fox, Horse, Zebra,
      Coffee, Tea, Milk, OrangeJuice, Water,
      OldGold, Kools, Chesterfields, LuckyStrike, Parliaments
     ],
 
     Vars ins 1..5,
 
     all_distinct([GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse]),
     all_distinct([Englishman, Spaniard, Ukrainian, Norwegian, Japanese]),
     all_distinct([Dog, Snails, Fox, Horse, Zebra]),
     all_distinct([Coffee, Tea, Milk, OrangeJuice, Water]),
     all_distinct([OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]),
 
     Englishman #= RedHouse,
     Spaniard #= Dog,
     Coffee #= GreenHouse,
     Ukrainian #= Tea,
     GreenHouse #= 1 + IvoryHouse,
     OldGold #= Snails,
     Kools #= YellowHouse,
     Milk #= 3,
     Norwegian #= 1,
     house_next_to(Chesterfields, Fox),
     house_next_to(Kools, Horse),
     LuckyStrike #= OrangeJuice,
     Japanese #= Parliaments,
     house_next_to(Norwegian, BlueHouse).


    /*

    Then to print out the solution after loading the program above use:

    puzzle([
     GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse,
     Englishman, Spaniard, Ukrainian, Norwegian, Japanese,
     Dog, Snails, Fox, Horse, Zebra,
     Coffee, Tea, Milk, OrangeJuice, Water,
     OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]),
    label([
     GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse,
     Englishman, Spaniard, Ukrainian, Norwegian, Japanese,
     Dog, Snails, Fox, Horse, Zebra,
     Coffee, Tea, Milk, OrangeJuice, Water,
     OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]).

    */

See also "Boring Sudoku":

    /*
    Boring Prolog Sudoku.
    */
    :- use_module(library(clpfd)).


    puzzle(Vars) :-

        Vars = [
            A11, A12, A13, A14, A15, A16, A17, A18, A19,
            A21, A22, A23, A24, A25, A26, A27, A28, A29,
            A31, A32, A33, A34, A35, A36, A37, A38, A39,
            A41, A42, A43, A44, A45, A46, A47, A48, A49,
            A51, A52, A53, A54, A55, A56, A57, A58, A59,
            A61, A62, A63, A64, A65, A66, A67, A68, A69,
            A71, A72, A73, A74, A75, A76, A77, A78, A79,
            A81, A82, A83, A84, A85, A86, A87, A88, A89,
            A91, A92, A93, A94, A95, A96, A97, A98, A99],

        Vars ins 1..9,

        all_distinct([A11, A12, A13, A14, A15, A16, A17, A18, A19]),
        all_distinct([A21, A22, A23, A24, A25, A26, A27, A28, A29]),
        all_distinct([A31, A32, A33, A34, A35, A36, A37, A38, A39]),
        all_distinct([A41, A42, A43, A44, A45, A46, A47, A48, A49]),
        all_distinct([A51, A52, A53, A54, A55, A56, A57, A58, A59]),
        all_distinct([A61, A62, A63, A64, A65, A66, A67, A68, A69]),
        all_distinct([A71, A72, A73, A74, A75, A76, A77, A78, A79]),
        all_distinct([A81, A82, A83, A84, A85, A86, A87, A88, A89]),
        all_distinct([A91, A92, A93, A94, A95, A96, A97, A98, A99]),

        all_distinct([A11, A21, A31, A41, A51, A61, A71, A81, A91]),
        all_distinct([A12, A22, A32, A42, A52, A62, A72, A82, A92]),
        all_distinct([A13, A23, A33, A43, A53, A63, A73, A83, A93]),
        all_distinct([A14, A24, A34, A44, A54, A64, A74, A84, A94]),
        all_distinct([A15, A25, A35, A45, A55, A65, A75, A85, A95]),
        all_distinct([A16, A26, A36, A46, A56, A66, A76, A86, A96]),
        all_distinct([A17, A27, A37, A47, A57, A67, A77, A87, A97]),
        all_distinct([A18, A28, A38, A48, A58, A68, A78, A88, A98]),
        all_distinct([A19, A29, A39, A49, A59, A69, A79, A89, A99]),

        all_distinct([A11, A21, A31, A12, A22, A32, A13, A23, A33]),
        all_distinct([A41, A51, A61, A42, A52, A62, A43, A53, A63]),
        all_distinct([A71, A81, A91, A72, A82, A92, A73, A83, A93]),
        all_distinct([A14, A24, A34, A15, A25, A35, A16, A26, A36]),
        all_distinct([A44, A54, A64, A45, A55, A65, A46, A56, A66]),
        all_distinct([A74, A84, A94, A75, A85, A95, A76, A86, A96]),
        all_distinct([A17, A27, A37, A18, A28, A38, A19, A29, A39]),
        all_distinct([A47, A57, A67, A48, A58, A68, A49, A59, A69]),
        all_distinct([A77, A87, A97, A78, A88, A98, A79, A89, A99]).

todd83• 7 years ago

For comparison, here is my own solution in Python 3 to the Zebra Puzzle. To me this solution seems sorter and easier to understand:

  from itertools import permutations as perms
  houses = range(1,6)                                # houses numbered 1,2,3,4,5
  for Englishman, Spaniard, Ukrainian, Norwegian, Japanese in perms(houses):
      if Norwegian != 1: continue                                      # rule 10
      for red, green, ivory, yellow, blue in perms(houses):
          if Englishman != red: continue                               # rule 2
          if green != ivory + 1: continue                              # rule 6
          if Norwegian not in [blue-1,blue+1]: continue                # rule 15
          for coffee, tea, milk, oj, water in perms(houses):
              if coffee != green: continue                             # rule 4
              if Ukrainian != tea: continue                            # rule 5
              if milk != 3: continue                                   # rule 9
              for oldgold, kools, chesterfields, luckys, parliaments in perms(houses):
                  if kools != yellow: continue                         # rule 8
                  if luckys != oj: continue                            # rule 13
                  if Japanese != parliaments: continue                 # rule 14
                  for dog, snails, fox, horse, zebra in perms(houses):
                      if Spaniard != dog: continue                     # rule 3
                      if oldgold != snails: continue                   # rule 7
                      if chesterfields not in [fox-1,fox+1]: continue  # rule 11
                      if kools not in [horse-1, horse+1]: continue     # rule 12

                      person = {Englishman: 'Englishman', Spaniard: 'Spainard',
                                Ukrainian: 'Ukrainian', Norwegian: 'Norwegian', Japanese: 'Japanese'}

                      print(f'{person[water]} drinks water')
                      print(f'{person[zebra]} owns the zebra')

anewhnaccount2• 7 years ago

Enumerating all solutions and checking will always be the simplest approach for find the set of inputs returning true for a decision problem. However, a constraint solver will not necessarily have to enumerate all solutions.

hjek13• 7 years ago

Brilliant! Cool to see the two paradigms side-by-side.

If there was a similar puzzle that had more than one solution, would it be straight-forward to do that using for loops as well in Python? (Curious if you can do backtracking that way)

falsedan• 7 years ago

The deep nesting and negation of the tests made this look weird to me and harder to see how the main idea was exhaustive searching of all permutations. I think it's clearer when the constraints are separated from the searching:

  People = collections.namedtuple('People', ['Englishman', 'Spaniard', 'Ukrainian', 'Norwegian', 'Japanese'])  # etc.

  def rule_10(people): return people.Norwegian == 0
  def rule_2(people, color): return people.Englishman == color.Red
  def rule_6(color): return color.Ivory - color.Green == 1
  def rule_15(people, color): return abs(people.Norwegian - color.Blue) == 1
  def rule_4(beverage, color): return beverage.Coffee == color.Green
  # etc.

  constraints = [ rule_1, rule_2, ... ]  # etc.

  def inject(func, vars=locals):
      signature = inspect.signature(func)
      args_from = operator.attrgetter(signature.parameters.keys())
      return func(*args_from(vars))

  houses = range(0,5)
  for people in map(People._make, perms(houses)):
    for color in map(Color._make, perms(houses)):
      for beverage in map(Beverage._make, perms(houses)):
        for cigarette in map(Cigarette._make, perms(houses)):
          for pet in map(Pet._make, perms(houses)):
            if all(map(inject, constraints)):
              print(f'The {People._fields[beverage.Water]} drinks water')
              print(f'The {People._fields[pet.Zebra]} owns the zebra')
              sys.exit(0)
  print(f'Sorry, no idea who drinks water or owns a zebra')
  sys.exit(1)

No pruning of the solution space but `all` will exit early if it can. You could change `inject` (terrible name) to pass the list of rules & call those whose signatures are fulfilled at the beginning of each for-loop, and return a list of the uncalled rules + the results of the called rules, and test the results with `all` & keep the uncalled rules handy for the next for-loop. I didn't do it because there's already too much boilerplate in the for-loops

fjfaase• 7 years ago

I personally think it is a little overkill to use Prolog to solve sudokus, as there is a simple mapping of sudokus to exact covers. The resulting exact covers are rather small and can usually be solved within a fraction of a second using Knuth's Algorithm X, even for hard sudokus. http://www.iwriteiam.nl/D1009.html#9

Solving Sudoku with Prolog (2016)

Related Stories