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




#include <array>
#include <iostream>
#include <vector>
 
std::vector<std::pair<int, int>> connections = {
    {0, 2}, {0, 3}, {0, 4}, // A to C,D,E
    {1, 3}, {1, 4}, {1, 5}, // B to D,E,F
    {6, 2}, {6, 3}, {6, 4}, // G to C,D,E
    {7, 3}, {7, 4}, {7, 5}, // H to D,E,F
    {2, 3}, {3, 4}, {4, 5}, // C-D, D-E, E-F
};
std::array<int, 8> pegs;
int num = 0;
 
void printSolution() {
    std::cout << "----- " << num++ << " -----\n";
    std::cout << "  " /*     */ << pegs[0] << ' ' << pegs[1] << '\n';
    std::cout << pegs[2] << ' ' << pegs[3] << ' ' << pegs[4] << ' ' << pegs[5] << '\n';
    std::cout << "  " /*     */ << pegs[6] << ' ' << pegs[7] << '\n';
    std::cout << '\n';
}
 
bool valid() {
    for (size_t i = 0; i < connections.size(); i++) {
        if (abs(pegs[connections[i].first] - pegs[connections[i].second]) == 1) {
            return false;
        }
    }
    return true;
}
 
void solution(int le, int ri) {
    if (le == ri) {
        if (valid()) {
            printSolution();
        }
    } else {
        for (size_t i = le; i <= ri; i++) {
            std::swap(pegs[le], pegs[i]);
            solution(le + 1, ri);
            std::swap(pegs[le], pegs[i]);
        }
    }
}
 
int main() {
    pegs = { 1, 2, 3, 4, 5, 6, 7, 8 };
    solution(0, pegs.size() - 1);
    return 0;
}