3

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.

braX
  • 11,506
  • 5
  • 20
  • 33
Miguel Mano
  • 103
  • 1
  • 12
  • 1
    No, other way around. You start with a predicate that generates all possible assignments, and then you apply the constraints. – Tomas By Dec 20 '17 at 17:23
  • For example, create a list 1..N and then call [`permutation/2`](http://www.swi-prolog.org/pldoc/man?predicate=permutation%2f2). – Tomas By Dec 20 '17 at 17:25
  • 1
    Here is [a previous question](https://stackoverflow.com/questions/8458945/optimizing-pathfinding-in-constraint-logic-programming-with-prolog) on this (among other things). – Tomas By Dec 20 '17 at 17:28

1 Answers1

3

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

CapelliC
  • 59,646
  • 5
  • 47
  • 90