Video: Describing a Knight's Tour with Prolog

[triska]

Dear all,

today I uploaded a short video, Describing a Knight's Tour with Prolog.

Thank you all for motivating me to make this!

It was specifically Christian Jendreiko's interest in the formatting code that motivated me to start it, and it is due to all your great contributions and interest that I was able to finish it! Thank you a again!

I hope to see many of you in Vienna at the Scryer Prolog Meetup 2024!

Enjoy!

All the best,
Markus

[jjtolton]

This is very cool, I didn't know about these clpz conjunctions and disjunctions! And I'm only 7 minutes into the video!
🍿 🍿 🍿

[bakaq]

today I uploaded a short video

If this is a short video I really want to see a long one.

Absolutely amazing, it covers many different topics. I will definitely going to try the challenge problem!

[dcnorris]

So rich with ideas, will require revisiting again and again!
I find it interesting [spoiler alert!] how your recourse to circuit/1 resembles the recourse to arithmetic alluded to in a Perlis epigram (no. 65),

Make no mistake about it: Computers process numbers — not symbols.
We measure our understanding (and con­trol) by the extent to which we
can arithmetize an activity.

Also many elegant flourishes here, including this ­dynamic, on-the-fly testing — which I'd never thought to do:

[jjtolton]

"Ready? Go."

WOW what a payoff!!

🍿🍿🍿

Hollywood should be taking notes!!

[jjtolton]

I used to think Python, with its exceptional string interpolation and very easy string formatting language, was king of string formatting -- even the concept of "declarative output" was not enough to convince me otherwise.

Until I saw the combination of DCGs+ string formatting.

Now THAT is power! 👑🤴

[jjtolton]

Ok overall takeaways, and these are just the pragmatic ones, not even touching on the philosophical
ones:

• Fantastic discussion of some lesser known and advanced clpz features (tuples, circuit, conjunctions, disjunction)
• Great explanation of foldl (only actual example I've come across)
• Great explanation of how to write a lambda and some useful examples (only actual example I've come across)
• Amazing combination of DCGs+format!!
• Great intuition on approaching constraint problems, and some new vocabulary (weak consistency, strong consistency, bounds consistency, domain consistency).

We really need to get together and index @triska 's videos!

[dcnorris]

I endorse the ideas of indexing these, as well as Power of Prolog!
Perhaps the index should be itself a Prolog library distributed with Scryer.

[jjtolton]

Well here's a start, anyway!

I learn so many things from the videos and completely forget where there were.

[UWN]

No contracting/1?

[triska]

Yes thank you good point, I briefly explain clpz:contracting/1 here:

As an example, let's consider a weakly propagating case from the video, and let's focus on the domain of Y:

?- Y+\(Ps = [1-1,2-1,3-1,4-1,X-Y],
       different_squares(Ps),
       [X,Y] ins 1..4).
   clpz:(Y in 1..4), clpz:(#Y#\=1#<==> #_A), clpz:(#Y#\=1#<==> #_B), clpz:(#Y#\=1#<==> #_C), clpz:(#Y#\=1#<==> #_D), clpz:(_A in 0..1), clpz:(#_E#\/ #_A#<==>1), clpz:(_E in 0..1), clpz:(#_F#\=4#<==> #_E), clpz:(_F in 1..4), clpz:(#_F#\=3#<==> #_G), clpz:(#_F#\=2#<==> #_H), clpz:(#_F#\=1#<==> #_I), clpz:(_G in 0..1), clpz:(#_G#\/ #_B#<==>1), clpz:(_B in 0..1), clpz:(_H in 0..1), clpz:(#_H#\/ #_C#<==>1), clpz:(_C in 0..1), clpz:(_I in 0..1), clpz:(#_I#\/ #_D#<==>1), clpz:(_D in 0..1).

We see the weak propagation mentioned in the video, in particular that 1 still appears in the domain of Y as a domain boundary that has no support in X. At the same time, the constraint solver recognizes that Y cannot be 1:

?- Y+\(Ps = [1-1,2-1,3-1,4-1,X-Y],
       different_squares(Ps),
       [X,Y] ins 1..4,
       Y = 1).
   false.

clpz:contracting/1 automates what we could naively do in such situations: procedurally speaking, try the domain boundaries as values in bindings, and remove elements where the binding fails, until an element is reached where the binding no longer fails. In the constraint programming literature, this approach is also called shaving.

In the above example, we get:

?- Y+\(Ps = [1-1,2-1,3-1,4-1,X-Y],
       different_squares(Ps),
       [X,Y] ins 1..4,
       clpz:contracting([X,Y])).
   clpz:(Y in 2..4), clpz:(_A in 1..4).

So, in fact, we have now (with some difficulty), reached bounds consistency in this example.

How useful is this?

A key attraction of clpz:contracting/1 seems to be that it lets us use information which the solver "immediately (i.e., without search) knows" about the situation with mostly acceptable performance, namely worst-case proportional to the sum (instead of product) of all domain sizes, in the hope that not even the entire domain will be considered but only a few elements at the boundaries need to be removed. Note that the worst-case runtime is, although linear in the domain size, exponential in the size of the input! A case of pseudo-polynomial runtime!

On the other hand:

1. clpz:contracting/1 does not ensure domain consistency, because it only tries values at the domain boundaries and not from inside the domain. For instance, considering the case where all squares in rank 2 are occupied:

?- Y+\(Ps = [1-2,2-2,3-2,4-2,X-Y],
       different_squares(Ps),
       [X,Y] ins 1..4,
       clpz:contracting([X,Y])).
   clpz:(Y in 1..4), clpz:(#Y#\=2#<==> #_A), clpz:(#Y#\=2#<==> #_B), clpz:(#Y#\=2#<==> #_C), clpz:(#Y#\=2#<==> #_D), clpz:(_A in 0..1), clpz:(#_E#\/ #_A#<==>1), clpz:(_E in 0..1), clpz:(#_F#\=4#<==> #_E), clpz:(_F in 1..4), clpz:(#_F#\=3#<==> #_G), clpz:(#_F#\=2#<==> #_H), clpz:(#_F#\=1#<==> #_I), clpz:(_G in 0..1), clpz:(#_G#\/ #_B#<==>1), clpz:(_B in 0..1), clpz:(_H in 0..1), clpz:(#_H#\/ #_C#<==>1), clpz:(_C in 0..1), clpz:(_I in 0..1), clpz:(#_I#\/ #_D#<==>1), clpz:(_D in 0..1).

2. In general, clpz:contracting/1 does not even guarantee bounds consistency, which we can for example see from:

?- Vs = [A,B,C,D], all_different(Vs), Vs ins 0..2, clpz:contracting(Vs).
   Vs = [A,B,C,D], clpz:(A in 0..2), clpz:all_different([A,B,C,D]), clpz:(B in 0..2), clpz:(C in 0..2), clpz:(D in 0..2).

The above example is inconsistent, but clpz:contracting/1 does not detect this.

A search finds no solutions:

?- Vs = [A,B,C,D], all_different(Vs), Vs ins 0..2, clpz:contracting(Vs), label(Vs).
   false.

These properties seem to limit the usefulness of clpz:contracting/1 in such highly combinatorial examples.

[jjtolton]

So many goodies in this video. These are the moments that stood out to me:

• 06:00 - using clpz disjunction/conjunction constraints
• 07:00 - foldl/3 explanation
• 14:13 - most general query example
• 15:08 - predicate overgeneralization example, explanation, and tradeoff explanation
• 16:50 - pairs library, pairs_key_value/3 predicate, label/1 predicate
• 18:50 - use of lambda to project away bindings
• 21:29 - core relations and conventions in constraint programming
• 21:35 - labeling/2 guarantees
• 26:42 - first example of thrashing with visualization
• 27:40 - example of ff options for labeling/2
• 27:47 - second example of thrashing with visualization
• 29:10 - discussion of weak propagation properties of clpz conjunctions and disjunctions
• 32:06 - base8 representation of chess board
• 33:15 - second example of weak propagation
• 35:27 - introduction of tuples_in/2 and all_different/1
• 37:46 - practical example of tuples_in/2 and all_different/1 used in a relation
• 38:29 - bounds consistency
• 39:02 - domain consistency
• 41:07 - third example of thrashing
• 43:51 - defining model as in "modeling a task"
• 45:05 - discussion of mental model of declarative programming
• 48:53 - overview of clpz combinatorial constraints
• 49:00 - tuples_in/2
• 49:07 - global_cardinality/3
• 49:20 - circuit/1
• 50:00 - circuit/1 explanation and demonstration
• 51:40 - representing knight's tour as a graph
• 52:37 - base N coordinate n_x_y_x/4 relation development and intuition
• 53:47 - knight_move/3 state transition / successor relation rewrite
• 56:08 - n_tour/2 development and rewrite
• 56:11 - knight_graph/4 predicate development and intuition
• 60:05 - practical usage of lambda with foldl/3 and clever inline toplevel query for iterative development
• 61:49 - discussion of operational constraings using circuit/1
• 64:22- "Ready? Go". Successful knight tour.
• 65:10 - observations
• 68:01 - developing a readable output
• 68:59 - another example of foldl/3 usage
• 69:40 - example of nth1/3 usage
• 71:45 - usage DCGs in to develop format string
• 78:14- recap of modeling and discussion of mental model for Prolog and conclusion

[aarroyoc]

Wow, I liked the video a lot. It shows a real journey, that I've experienced myself too while solving some problems. And this video not only reflects many of the stages in a problem solving, but also puts names and teaches many things in the middle. In my case, I already knew the final answer because I read Constraint Solving and Planning with Picat which uses this example too. It's a good introduction to constraints with the only downside that it uses Picat, not Prolog.

[jjtolton]

We have a thread over here discussing this very topic! I'll try to add some more resources.

[jjtolton]

@dcnorris : #2521 (comment)

[triska]

One note on terminology: In logic programming, the term constraint programming is used exclusively in the latter sense, i.e., always to mean that we use available constraints, possibly also to define additional constraints. For the other meaning, we say that someone implements a constraint solver, works on constraints or implements constraints etc.

A key attraction of constraint programming is that only very few people will ever have to write a constraint solver, and everyone benefits from being able to use the existing constraints in their programs. Implementing a constraint solver often takes many years and thorough understanding of the available literature and filtering algorithms. In contrast, using a constraint solver is easy. In CLP, the provided constraints are available as predicates like any built-in. Constraints thus blend in completely seamlessly into logic programming, making logic programming a particularly useful and natural environment for constraints. In fact, (=)/2 itself can also be regarded as a constraint.

Analogously, when someone says for example "I do Rust programming", we do not ask: "Do you mean you write a Rust compiler, or that you program in Rust?" It is always presumed that the latter is the case, while the chances of the former are so vanishingly small that the case is not even considered.

[jjtolton]

Analogously, when someone says for example "I do Rust programming", we do not ask: "Do you mean you write a Rust compiler, or that you program in Rust?" It is always presumed that the latter is the case, while the chances of the former are so vanishingly small that the case is not even considered.

To be fair on this discussion board the number of active participants who "do Prolog programming" in both senses is probably greater than 50% 🤣

A key attraction of constraint programming is that only very few people will ever have to write a constraint solver, and everyone benefits from being able to use the existing constraints in their programs. Implementing a constraint solver often takes many years and thorough understanding of the available literature and filtering algorithms.

For the aspiring members of the "vanishingly small" population, would you have any leads on such literature? 😁 😁 😁

[triska]

A good starting point are recent implementation descriptions of Prolog systems with strong and efficient constraint solvers, such as GNU Prolog and SICStus Prolog, and the references included therein:

• On the Implementation of GNU Prolog
• SICStus Prolog — the first 25 years

As an example of an important and frequently used constraint, the strong filtering algorithm of the all_distinct/1 constraint is described in A filtering algorithm for constraints of difference in CSPs.

[ocharles]

I'm very confused about the ff thing. Can anyone help me understand why it seems to just try "1" in a few fixed places over and over again? It seems like it plans where "1" goes, and then fails to find anywhere "2" can go, and then instantly retries the first move? But this is really weird because for any first move there is at least a second move available!

[triska]

As a hint, think in terms of how variables are labeled. In case anyone wants to share an opinion on this, please also let us know! I think it is valuable to think about this.

[ocharles]

My other comment would be that this is overall a fantastic video, but does have that minor feeling of "aha, there just so happens to be the perfect tool that solves this problem!". This is of course a simplification, the leap of modelling to notice that you can use circuit is non-trivial. Nonetheless, I'm left with a minor feeling of: what if circuit wasn't there? Or: what if my problem can't be modeled with the available constraints? Is clp(Z) open enough that I could write circuit myself, or does it have to be part of the core library?

[jjtolton]

Great questions! Several us are also very curious about constraint programming, both from an implementation and usage standpoint (see above!). Maybe another question to ask is what is missing from clpz? Because in general it seems like it is broadly applicable (if you know how to apply constraints!)

My understanding is that clpz is meant to be (deliberately) completely comatible with SICStus Prolog constraint APIs so that you can switch to an upgraded engine for commercial work if that ever becomes needed.

Your question makes me think probably a lot of these questions could be answered by looking at the SICStus clp(fd) documentation for some bigger picture understanding of where some of the ideas came from! I will have to investigate myself, as I have had many similar questions but did not stop to think about that source of information until now.

[triska]

@ocharles: Thank you a lot for your kind words!

Regarding "there just so happens": Note that the earlier models didn't find solutions, so we kept trying, and we stopped remodeling when we found a model that yields solutions! There may well be a model that works even better!

Regarding "what if circuit wasn't there": In the concrete case of circuit, we can rest assured by the fact that it is there, but the general concern is very justified, and best phrased like this: Which other constraints would be useful to have?

There are many useful constraints that currently are not provided by library(clpz), one especially powerful and lacking example is the geost/N family of constraints provided by SICStus Prolog, allowing us to express geometric constraints over k-dimensional objects and shapes subject to business rules. This would be extremely interesting to have, and also seems very hard to implement, it would likely take many years to implement it fully. A less powerful version could be easier to implement and could for example be done—or at least partially done—in an advanced Master's thesis.

In addition, there may also well be constraints that currently no Prolog system has! Note that this was the starting point for all Prolog systems, and not that long ago! It took time and effort to find the constructs that we now take almost for granted in Prolog systems. It wasn't obvious at all how to integrate finite domain solvers in Prolog, neither how to implement them within Prolog (which still isn't that clear, with attributed variables and meta-structures as possible underlying formalisms), nor how they should be used in Prolog programs. For instance, in the very first finite domain systems, you would state the domains of variables in ad hoc "directives", instead of using predicates such as (in)/2 which we now regard as "obvious".

It was completely not obvious how this all should work, and I think there are also now very interesting opportunities for implementation improvements of constraint solvers in breadth and depth. As an excellent starting point to get into the right mindset for such improvements, I recommend Constraint Logic Programming—A Personal Perspective by Pascal Van Hentenryck.

[UWN]

Or: what if my problem can't be modeled with the available constraints?

Apart from the concrete constraints available currently, you always have the choice to use Prolog's more pedestrian means like chronological backtracking. When combined with the existing constraints, they may already be sufficiently efficient. In fact the serialized constraints did not exist in early implementations, but by appropriately combining a naive (and pure) Prolog version together with the linear constraints, it became possible to prove optimality for the famous bridge construction problem.