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




type hole = int;
param A : hole = 1;
param B : hole = A+1;
param C : hole = B+1;
param D : hole = C+1;
param E : hole = D+1;
param F : hole = E+1;
param G : hole = F+1;
param H : hole = G+1;
param starting : int = 0;
const holes : domain(hole) = { A,B,C,D,E,F,G,H };
const graph : [holes] domain(hole) = [  A => { C,D,E },
                                        B => { D,E,F },
                                        C => { A,D,G },
                                        D => { A,B,C,E,G,H },
                                        E => { A,B,D,F,G,H },
                                        F => { B,E,H },
                                        G => { C,D,E },
                                        H => { D,E,F } 
                                      ];
 
proc check( configuration : [] int, idx : hole ) : bool {
  var good = true;
  for adj in graph[idx] {
    if adj >= idx then continue;
    if abs( configuration[idx] - configuration[adj] ) <= 1 {
      good = false;
      break;
    }
  }
 
  return good;
}
 
proc solve( configuration : [] int, pegs : domain(int), idx : hole = A ) : bool {
  for value in pegs {
    configuration[idx] = value;
    if check( configuration, idx ) {
      if idx < holes.size {
        var prePegs = pegs;
        if solve( configuration, prePegs - value, idx + 1 ){
          return true;  
        }
      } else {
        return true;
      }
    }
  }
  configuration[idx] = starting;
  return false;
}
 
proc printBoard( configuration : [] int ){
return 
"\n       " + configuration[A] + "   " + configuration[B]+ "\n" +
"      /|\\ /|\\ \n"+
"     / | X | \\ \n"+
"    /  |/ \\|  \\ \n"+
"   " + configuration[C] +" - " + configuration[D] + " - " + configuration[E] + " - " + configuration[F] + " \n"+
"    \\  |\\ /|  / \n"+
"     \\ | X | / \n"+
"      \\|/ \\|/ \n"+
"       " + configuration[G] + "   " + configuration[H]+ "\n";
 
}
 
 
 
proc main(){
  var configuration : [holes] int;
  for idx in holes do configuration[idx] = starting;
 
  var pegs : domain(int) = {1,2,3,4,5,6,7,8};
  solve( configuration, pegs );
 
  writeln( printBoard( configuration ) );
 
}
 