Solve the no connection puzzle: Difference between revisions

=={{header|Prolog}}==

Works with SWi-Prolog with module clpfd written by '''Markus Triska'''

We first compute a list of nodes, with sort this list, and we attribute a value at the nodes.

<lang Prolog>:- use_module(library(clpfd)).

edge(a, c).

edge(a, d).

edge(a, e).

edge(b, d).

edge(b, e).

edge(b, f).

edge(c, d).

edge(c, g).

edge(d, e).

edge(d, g).

edge(d, h).

edge(e, f).

edge(e, g).

edge(e, h).

edge(f, h).

connected(A, B) :-

( edge(A,B); edge(B, A)).

no_connection_puzzle(Vs) :-

% construct the arranged list of the nodes

bagof(A, B^(edge(A,B); edge(B, A)), Lst),

sort(Lst, L),

length(L, Len),

% construct the list of the values

length(Vs, Len),

Vs ins 1..Len,

all_distinct(Vs),

% two connected nodes must have values different for more than 1

set_constraints(L, Vs),

label(Vs).

set_constraints([], []).

set_constraints([H | T], [VH | VT]) :-

set_constraint(H, T, VH, VT),

set_constraints(T, VT).

set_constraint(_, [], _, []).

set_constraint(H, [H1 | T1], V, [VH | VT]) :-

connected(H, H1),

( V - VH #> 1; VH - V #> 1),

set_constraint(H, T1, V, VT).

set_constraint(H, [H1 | T1], V, [_VH | VT]) :-

\+connected(H, H1),

set_constraint(H, T1, V, VT).

</lang>

Output :

<pre> ?- no_connection_puzzle(Vs).

Vs = [4, 3, 2, 8, 1, 7, 6, 5] .

27 ?- setof(Vs, no_connection_puzzle(Vs), R), length(R, Len).

R = [[3, 4, 7, 1, 8, 2, 5, 6], [3, 5, 7, 1, 8, 2, 4|...], [3, 6, 7, 1, 8, 2|...], [3, 6, 7, 1, 8|...], [4, 3, 2, 8|...], [4, 5, 2|...], [4, 5|...], [4|...], [...|...]|...],

Len = 16.

</pre>