/* 

  No connection puzzle in Picat.

  https://rosettacode.org/wiki/Solve_the_no_connection_puzzle
  """
  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. 
  """

  There are 16 possible solutions, and 8 with the symmetry breaking: X[1] #< X[N],

  Here is one solution:

    [3,4,7,1,8,2,5,6]

       3   4       
      /|\ /|\      
     / | X | \      
    /  |/ \|  \    
   7 - 1 - 8 - 2 
    \  |\ /|  /    
     \ | X | /      
      \|/ \|/      
       5   6       

  All 16 solutions:

    [3,4,7,1,8,2,5,6]
    [3,5,7,1,8,2,4,6]
    [3,6,7,1,8,2,4,5]
    [3,6,7,1,8,2,5,4]
    [4,3,2,8,1,7,6,5]
    [4,5,2,8,1,7,6,3]
    [4,5,7,1,8,2,3,6]
    [4,6,7,1,8,2,3,5]
    [5,3,2,8,1,7,6,4]
    [5,4,2,8,1,7,6,3]
    [5,4,7,1,8,2,3,6]
    [5,6,7,1,8,2,3,4]
    [6,3,2,8,1,7,4,5]
    [6,3,2,8,1,7,5,4]
    [6,4,2,8,1,7,5,3]
    [6,5,2,8,1,7,4,3]


  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.
import cp.

main => go.

%
% The task is to show one solution
%
go ?=>
  no_connect_puzzle,
  nl.

go => true.


%
% Show all solutions
%
go2 ?=>
  no_connect_puzzle,
  nl,
  fail,
  nl,

go2.

%
% Another CP approach, using
% edge/2 from the Prolog solution.
%
go3 ?=>
  % convert from edge/2
  Map = new_map([a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8]),

  N = 8,
  X = new_list(N),
  X :: 1..N,
  all_different(X),
  foreach(E in find_all([A,B],edge(A,B)))
    abs(X[Map.get(E[1])]-X[Map.get(E[2])]) #> 1
  end,

  solve(X),
  println(X),
  fail,

  nl.

go3 => true.


%
% Imperative approach
%
go4 ?=>
  Map = new_map([a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8]),
  Edges = [ [Map.get(A),Map.get(B)] : [A,B] in find_all([A,B],edge(A,B))],
  foreach(P in permutations(1..8))
    OK = true,
    % not OK if we find any matches, i.e abs = 1
    foreach(E in Edges, abs(P[E[1]]-P[E[2]]) <= 1)
      OK := false
    end,
    if OK then
      println(p=P)
    end
  end,
  nl.

go4 => true.



%
% Solve the no_connect_puzzle.
%
% Labeling
%     1   2
%    /│\ /│\
%   / │ X │ \
%  /  │/ \│  \
% 3 ─ 4 ─ 5 ─ 6
%  \  │\ /│  /
%   \ │ X │ /
%    \│/ \│/
%     7   8
%
no_connect_puzzle =>
  N = 8,
  X = new_list(N),
  X :: 1..N,
  Graph =
    {{1,3}, {1,4}, {1,5},
     {2,4}, {2,5}, {2,6},
     {3,1}, {3,4}, {3,7},
     {4,1}, {4,2}, {4,3}, {4,5}, {4,7}, {4,8},
     {5,1}, {5,2}, {5,4}, {5,6}, {5,7}, {5,8},
     {6,2}, {6,5}, {6,8},
     {7,3}, {7,4}, {7,5},
     {8,4}, {8,5}, {8,6}},
 
  all_distinct(X),
  foreach(I in 1..Graph.length) 
    abs(X[Graph[I,1]]-X[Graph[I,2]]) #> 1 
  end,
 
  % symmetry breaking
  X[1] #< X[N],
 
  solve(X),
  println(X),
  nl,
  [A,B,C,D,E,F,G,H] = X,
  Solution = to_fstring(
  "    %d   %d       \n"++
  "   /|\\ /|\\      \n"++
  "  / | X | \\      \n"++
  " /  |/ \\|  \\    \n"++
  "%d - %d - %d - %d \n"++
  " \\  |\\ /|  /    \n"++
  "  \\ | X | /      \n"++
  "   \\|/ \\|/      \n"++
  "    %d   %d       \n",
  A,B,C,D,E,F,G,H),
  println(Solution),
  nl.





% Edges, for the LP solution
% (from Prolog solution)
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).