I was playing around with s(CASP) in SWISH and tried to solve a simple graph coloring problem (three vertices connected like a triangle):

```
vertex(a).
vertex(b).
vertex(c).
edge(a,b).
edge(b,c).
edge(c,a).
color(red).
color(green).
colorize(N,C) :- vertex(N), color(C).
:- edge(N1,N2), colorize(N1,C), colorize(N2,C).
```

My query is …

```
?- ? colorize(N,C).
```

… which should yield no results, since it is not possible with two colors, but it does give me some results.

Questions:

What am I missing?
When adding a third color, how can I get the colorization result as a list? For example:
```
[(a, red), (b, green), (c, blue)]
```

jan
May 25, 2022, 4:11pm
#2

scasp_user:

What am I missing?

That is fairly easy Global constraints in the Prolog embedded mode should be written as

```
false :- edge(N1,N2), colorize(N1,C), colorize(N2,C).
```

instead of just `:- edge(N1,N2), colorize(N1,C), colorize(N2,C).`

as this is Prolog’s syntax for directives .

With that you get indeed no models. But … you also get no models with three colors. See SWISH -- SWI-Prolog for SHaring

I am not entirely sure why not It is consistent in the SWISH, commandline and original Ciao version and I think it is a misconception about what global constraints mean.

If you can generate a model you can use scasp/2 to extract the model:

`?- scasp(Query, [model(Model)]).`

1 Like

Xuaco
May 25, 2022, 4:38pm
#4

jan:

With that you get indeed no models. But … you also get no models with three colors. See SWISH – SWI-Prolog for SHaring

I am not entirely sure why not It is consistent in the SWISH , commandline and original Ciao version and I think it is a misconception about what global constraints mean.

Hi Jan, you are right, it is difficult to work with global constraints from Prolog’s point of view…
Note that the predicate colorize/2 is always true, there is only one model in which each node is colorized with each color…

To generate various models and prune the incorrect models you need even loops.

1 Like

Thank you all for the replies, I have a working solution now. However, it does not utilize a global constraint:

```
:- use_module(library(scasp)).
vertex(a).
vertex(b).
vertex(c).
edge(a,b).
edge(b,c).
edge(c,a).
color(red).
color(green).
color(blue).
colorize(N,C) :- vertex(N), color(C), not sameColoredNeighbor(N,C), not doubleColored(N,C).
sameColoredNeighbor(N,C) :- edge(N,OtherN), colorize(OtherN, C).
doubleColored(N,C) :- color(OtherC), C \= OtherC, colorize(N, OtherC).
```

And the query:

```
scasp(colorize(_,_), [model(Model)]), findall((N,C), member(colorize(N,C), Model), Colorization).
```

However, this needs 2.8 seconds for all solutions, which seems a bit much for three vertices …

Still, I would prefer the global constraint (if it would work), because it is much more readable.