Generate a list based on constraint result, using Prolog's CLPFD

3
votes

I'm attempting to implement a Skyscraper puzzle solver in Prolog, using constraints (CLPFD).

I've realized a great constraint would be calculating the number of times the maximum switches whilst traversing each row and column and matching it with the side clue.

Here's an example of a single row:

*2* [ _ | _ | _ | _ ] *3*   ->   *2* [ 1 | 4 | 3 | 2 ] *3*

The list [1, 4, 3, 2] works for clue 2 because it has 2 maximum switches (0 -> 1 -> 4).
It also works for clue 3 because the same list reversed - [2, 3, 4, 1] - has 3 maximum switches (0 -> 2 -> 3 -> 4).

I've managed to program a predicate that returns me the number of maximum switches of a list.
The issue is how to actually utilize it to generate a new constraint? I can't pass my list/matrix directly because it isn't yet initialized.

It should probably be something like:

calculate_max_switches(List, Switches),
% Generate a list whose Switches value is equal to the clue number.

Thank you.

1
prologconstraintsclpfd
No, other way around. You start with a predicate that generates all possible assignments, and then you apply the constraints. – Tomas By
For example, create a list 1..N and then call permutation/2. – Tomas By
Here is a previous question on this (among other things). – Tomas By

1 Answers

3
votes

Without seeing your code, here is my hint, adapted from my previous answer:

:- use_module(library(clpfd)).

skyscrape_row(Left, Right, Heights) :-
    constraint_view(0, Heights, LHeights),
    sum(LHeights, #=, Left),
    reverse(Heights, Heights_),
    constraint_view(0, Heights_, RHeights),
    sum(RHeights, #=, Right).

constraint_view(_, [], []).
constraint_view(Top, [V|Vs], [R|Rs]) :-
    R #<==> V #> 0 #/\ V #> Top,
    Max #= max(Top, V),
    constraint_view(Max, Vs, Rs).

that applied to your example yields

?- L=[A,B,C,D], L ins 1..4, all_different(L), skyscrape_row(2,3,L), label(L).

A = 1,
B = 4,
C = 3,
D = 2,
L = [1, 4, 3, 2]
A = 2,
B = 4,
C = 3,
D = 1,
L = [2, 4, 3, 1]
A = 3,
B = 4,
C = 2,
D = 1,
L = [3, 4, 2, 1]

Live code is available in SWISH