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?
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?
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).
Hence, if you somehow manage to take into account all the initially available information, then no search is required, because, in a sense, the given hints already narrow down the entire space of (ostensibly) possible assignments to a single one.
There are constraint solvers that do this. For example, with the CLP(B) version based on BDDs that I mentioned, the solver internally constructs a Binary Decision Diagram (BDD) which is like a (ideally: more compact) truth table of all assignments that satisfy the requirements.
Therefore, with the CLP(B) version I posted, search is never necessary for valid Sudoku puzzles, because they admit precisely one solution, and the constraint solver deduces this unique solution by reasoning about the decision diagram.
There's a severe drawback to this: The BDD may be exponential in the number of variables. That's a problem, because there are dozens of variables in many Sudoku puzzles. In practice, we are often lucky, and the worst-case space requirements do not arise.
For comparison, the CLP(FD/ℤ) formulation is based on constraint propagation that ensures a certain kind of consistency for all individual constraints in isolation, but not necessarily for the combination of all constraints, i.e., the problem as a whole.
In practice, at least for Sudoku puzzles, this also often leads to finding the unique solution without any search. This may also be the case if only the minimum number of clues for a valid Sudoku puzzle (i.e., 17, per https://arxiv.org/abs/1201.0749) is specified, as the parent mentions. In general, search is still required. In the concrete case of (standard) Sudoku, the required search, if there is any at all, is typically very small, because the many constraints usually narrow down the entire space considerably.
Reducing the amount of required search is the key attraction and goal of the consistency techniques that are used by constraint systems. The available systems differ in how much and how fast they are able to prune inconsistent values, leading to notions such as global consistency, domain consistency, bounds consistency etc. that give some indication of propagation strength.
Assuming the CLP(B) solver is correctly implemented, the CLP(B) solution I posted will give the unique solution without any search.
On the other hand, it is comparatively easy to find puzzles where the CLP(ℤ) version will require search, even if only a small amount.
Apparently no guessing is required!
In Prolog it's fine for a variable (that represents a square in a sudoku puzzle) to be somewhere between 1 and 9. (Yes, that can be a bit mind-boggling, because in most other programming languages a variable can't really be either this or that. As far as I know, not even in SQL which is also somewhat declarative.)
You might get in a situation where one square (let's call it A) is between 1 and 3 and two other squares on the same row (let's call them B and C) are both between 1 and 2. One constraint that we have given is that all numbers on a row must be distinct (because that's one of the rules of a sudoku puzzle), so given those constraints and facts, Prolog can deduce that the value of the first square must be 3.
Therefore no guessing (or searching + backtracking) is required; only constraint propagation.
This is what the query would look like in a Prolog REPL:
[library(clpfd)], % load library for constraint logic over finite domains
A in 1..3, B in 1..2, C in 1..2, all_distinct([A,B,C]).
A = 3,
B in 1..2,
all_distinct([3, B, C]),
C in 1..2.
(Triska's explanation is probably more in depth and correct, but I thought I'd just chip in with my newbie way of explaining how I understand this. But seriously, check his videos. They're great stuff. The illustrations make the explanations accessible.)
That is, if you have a board where there are multiple legal moves on every open position, but only one solution, you still have to pick which constraint to propagate to find the solution. No?
A = 3,
B in 1..2,
all_distinct([3, B, C]),
C in 1..2.
If there's more than one soluton or no possible solution, then it's not a "well-posed" sudoku puzzle; at least according to Wikipedia here:
> The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.[0]
But yes, I guess for puzzles with multiple solutions, you'd necessarily have to search for them. It's also possible to make a mine sweeper field that has no valid assignment of mines[1], yet usually mine sweeper games don't do that.
As you note about this state,
B in 1..2,
all_distinct([B, C]),
C in 1..2.
[0]: https://en.wikipedia.org/wiki/Sudoku
[1]: https://worldcomp-proceedings.com/proc/p2016/PDP7565.pdf
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.
First we can load the csv library, then read the rows of the csv file, and assert those rows as facts using the `car` identifier. (Doesn't mean `car` like in lisp, obviously, but automobile.)
?- [library(csv)],
csv_read_file('cars.csv',Rows, [functor(car)]),
maplist(assert, Rows).
?- car('Ford', Model, Year, Colour).
Model = 'F150',
Year = 1999,
Colour = 'Black' ;
Model = 'Mustang',
Year = 1969,
Colour = 'Blue'.
(I should really have discarded the first line, because right now there's a car, whose brand is 'Brand', and so on. Well, well...)
If we just wanted a list of all the results, we could use the findall/3 predicate.
Something that's neat in Prolog is that you can define recursive relations. In SQL it's easy to define a parent/child relation, but what about ancestor/descendant? (Yes, you can use common table expressions, but the syntax is incredibly complicated.)
Also, you don't need to create database schemas and Prolog, and unification feels seamless as opposed to explicitly declaring the JOINs.
But, in my opinion, where Prolog really shines compared to SQL is that there just isn't that whole object-relational impedance mismatch[0].
[0]: https://en.wikipedia.org/wiki/Object-relational_impedance_mi...
Edit: Ok, my turn quiz!! Say we have these bicycles:
Brand, Colour, Year
Mosquito, Blue, 2010
Raleigh, Red, 2005
Suzuki, Red, 1998
In Prolog that would be:
bicycle(One_brand, Colour, _),
bicycle(Another_brand, Colour, _),
One_brand \= Another_brand.
I may have to give Prolog another shot at some point!
At first glance I thought it'd just be a group by + having followed by some sort of SELECT to get the first 2 in each group. But apparently doing that top-k in each group is a nightmare in SQL [1].
[1] https://stackoverflow.com/questions/8748986/get-records-with...
select b1.Brand as brand1, b2.Brand as brand2
from bicycles as b1
inner join bicycles as b2
on (b1.Colour = b2.Colour)
where b1.Brand <> b2.BrandThat is probably my main issue with SQL: That the names of some of the keywords are very table-ish and not very semantic; like LEFT OUTER JOIN. I mean, if we have some facts, like how old people are, and what they like to eat, then what does it even mean that any of those facts is to the left or on the inside of another? I can't fit that into my brain.
But let's take an example. We have these sets of facts (which, if they were in SQL, would be in two different tables):
age(alice, 20).
age(beatrice, 30).
age(charlie, 90).
likes(alice, carrots).
likes(alice, chips).
likes(charlie, crumpets).
age(Name,Age), likes(Name, Something).
I'm probably getting this wrong, but if we wanted LEFT OUTER JOIN it would be more like:
age(Name,Age); likes(Name, Something).
In Prolog, the comma means 'and', and the semicolon means 'or', so in the second query anyone, who has an age but doesn't like anything, will still be included. In this query, that would be Beatrice. That's a bit like a LEFT OUTER JOIN, isn't it?
> I find the idea of a simple Prolog, like a Datalog, very intriguing as a potential simple query engine for apps in mainstream languages–not having to worry about the maps, filters, reduces, flatmaps, and all the other operations we have to do to coax data into the right shapes in line-of-business apps.
Seen DataScript?[0] I think MiniKanren has also been implemented in most languages. I like how Prolog "forces" a declarative style though.