You are given a box with eight holes labelled   A-to-H,   connected by fifteen straight lines in the pattern as shown below:

             A   B
            /│\ /│\
           / │ X │ \
          /  │/ \│  \
         C───D───E───F
          \  │\ /│  /
           \ │ X │ /
            \│/ \│/
             G   H

You are also given eight pegs numbered   1-to-8.



Objective

Place the eight pegs in the holes so that the (absolute) difference between any two numbers connected by any line is greater than one.



Example

In this attempt:

             4   7
            /│\ /│\
           / │ X │ \
          /  │/ \│  \
         8───1───6───2
          \  │\ /│  /
           \ │ X │ /
            \│/ \│/
             3   5

Note that   7   and   6   are connected and have a difference of   1,   so it is   not   a solution.



Task
Produce and show here   one   solution to the puzzle.



Related tasks

   A* search algorithm
   Solve a Holy Knight's tour
   Knight's tour
   N-queens problem
   Solve a Hidato puzzle
   Solve a Holy Knight's tour
   Solve a Hopido puzzle
   Solve a Numbrix puzzle
   4-rings or 4-squares puzzle


See also
No Connection Puzzle (youtube).




:- 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).
 
 