Describing a Knight's Tour with Prolog

A knight's tour is a sequence of knight moves on a chessboard such that every square is visited exactly once. With Prolog, we can easily express different models of this task, yielding different amounts of pruning power. Powerful global constraints such as circuit/1 reduce the search space significantly, and allow us to find solutions with a short and general program.
The code is available from: www.metalevel....

[@jamestolton6882]

6:00 - using clpz disunction/conjunction constraints
7: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
1:00:05 - practical usage of lambda with foldl/3 and clever inline toplevel query for iterative development
1:01:49 - discussion of operational constraings using circuit/1
1:04:22 - "Ready? Go". Successful knight tour.
1:05:10 - observations
1:08:01 - developing a readable output
1:08:59 - another example of foldl/3 usage
1:09:40 - example of nth1/3 usage
1:11:45 - usage DCGs in to develop format string
1:18:14 - recap of modeling and discussion of mental model for Prolog and conclusion
*Note* for curious non-prolog developers: The name/number syntax indicates to other Prolog programmers predicate/arrity. If you have never worked with predicates before, it is easiest to categorize them as "Prolog functions" (but you will also soon see that the differences between them are great enough that the phrase "Prolog function" would make most Prolog developers instantly cringe -- I'm just mentioning this to help you orient yourself to this comment if the syntax is unfamiliar)
*Note1:* DCGs stands for Definite Clause Grammars, Markus has another excellent video on them. He also has a **great video just on string formatting in Prolog.

[@wowzers1237____]

Awesome. Thank you.

[@simeondermaats]

I'll be following a course on Prolog at uni next semester, and I can already tell this'll be a very useful channel. Thank you for the content you put out!

[@wowzers1237____]

Finally! I'm always waiting for these.

[@duartedias271]

Hello Markus, could you create a video about CHR? You're the best resource for learning Prolog. Thanks!

[@tankerwife2001]

Let's go

[@librarianmage]

Any hamiltonian path can be extended into a cycle by adding an additional vertex that connects the start and end of the path, so I imagine a way to model all knights tours is to add a (N*N + 1)th vertex that connects to all of the squares and consider the vertices next to it on the path as the ends of the tour.

[@guilhermepimenta_prodabel]

The problem is for some boards, like 5x5, there is no circuit, but there is a complete path.

[@guilhermepimenta_prodabel]

If you create the new state "out of the board", you must start and end in out of border. The first move from out of board can go to any position and the last move can go from any position to out of board, the condition is: if all squares are not empty you go to out of board. It will, at least I hope, create all possible paths. In graph representation, is a new node that is connected to all nodes, and it is the start point of the circuit. What do you think?

[@hobbified]

That's the same idea I came up with. I think it works fine. By forcing it to be the start point, you also (via `circuit`'s enforcement that nodes only appear once) forbid it from ending up anywhere in the middle of the path, cheaply. But by making it the neighbor of everything we say that the path can end anywhere. And the length constraint will make sure that the tour is complete.

[@SylvainSoliman]

I think that most of the arguments about readability (for foldl or the final definition of knight_move) are not really convincing (people not used to functional programming have no idea what foldl does for instance).
I also think that saying that there is no disjunction in an equality constraint with an absolute value… is only true if one knows how the solver is programmed ;)
For the rest, didn't watch everything, but it seemed pretty nice !!! 👍🏼