Solve the no connection puzzle: Difference between revisions

From Rosetta Code
Content added Content deleted
(Updated second D entry)
Line 317: Line 317:
Using a simple backtracking.
Using a simple backtracking.
{{trans|Go}}
{{trans|Go}}
<lang d>import std.stdio, std.algorithm, std.conv, std.string;
<lang d>import std.stdio, std.algorithm, std.conv, std.string, std.typecons;


// Holes A=0, B=1, ..., H=7
// Holes A=0, B=1, ..., H=7

Revision as of 15:33, 26 January 2015

Task
Solve the no connection puzzle
You are encouraged to solve this task according to the task description, using any language you may know.

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


        A   B
       /|\ /|\
      / | X | \
     /  |/ \|  \
    C - D - E - F
     \  |\ /|  /
      \ | X | /
       \|/ \|/
        G   H

You are also given eight pegs numbered 1-to-8. The idea is to place the pegs in the holes so that the (absolute) difference between any two numbers connected by any line is greater than one.

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

The task is to produce and show here one solution to the puzzle.

Reference

No Connection Puzzle (Video).

Related Tasks

Ada

This solution is a bit longer than it actually needs to be; however, it uses tasks to find the solution and the used types and solution-generating functions are well-separated, making it more amenable to other solutions or altering it to display all solutions. <lang Ada> With Ada.Text_IO, Connection_Types, Connection_Combinations;

procedure main is 

  Result : Connection_Types.Partial_Board renames Connection_Combinations;

begin 

  Ada.Text_IO.Put_Line( Connection_Types.Image(Result) );

end;</lang> <lang Ada>Pragma Ada_2012;

Package Connection_Types with Pure is 

  -- Name of the nodes.
  Type Node is (A, B, C, D, E, F, G, H);

  -- Type for indicating if a node is connected.
  Type Connection_List is array(Node) of Boolean
    with Size => 8, Object_Size => 8, Pack;

  Function "&"( Left : Connection_List; Right : Node ) return Connection_List;
  
  -- The actual map of the network connections.
  Network : Constant Array (Node) of Connection_List:=
    (
     A => (C|D|E	=> True, others => False),
     B => (D|E|F	=> True, others => False),
     C => (A|D|G	=> True, others => False),
     D => (C|A|B|E|H|G	=> True, others => False),
     E => (D|A|B|F|H|G => True, others => False),
     F => (B|E|H	=> True, others => False),
     G => (C|D|E	=> True, others => False),
     H => (D|E|F	=> True, others => False)
    );

  -- Values of the nodes.
  Type Peg is range 1..8;

  -- Indicator for which values have been assigned.
  Type Used_Peg is array(Peg) of Boolean
    with Size => 8, Object_Size => 8, Pack;

  Function "&"( Left : Used_Peg; Right : Peg ) return Used_Peg;



  -- Type describing the layout of the network.
  Type Partial_Board is array(Node range <>) of Peg;
  Subtype Board is Partial_Board(Node);

  -- Determines if the given board is a solution or partial-solution.
  Function Is_Solution	( Input : Partial_Board ) return Boolean;

  -- Displays the board as text.
  Function Image	( Input : Partial_Board ) Return String;

End Connection_Types;</lang> <lang Ada> Pragma Ada_2012;

with Connection_Types; use Connection_Types;

Function Connection_Combinations return Partial_Board; </lang> <lang Ada>Pragma Ada_2012;

Package Body Connection_Types is 

  New_Line : Constant String := ASCII.CR & ASCII.LF;

  ---------------------
  --  Solution Test  --
  ---------------------
  
  Function Is_Solution( Input : Partial_Board ) return Boolean is
    (for all Index in Input'Range =>
       (for all Connection in Node'Range =>
            (if Network(Index)(Connection) and Connection in Input'Range
             then abs (Input(Index) - Input(Connection)) > 1
            )
       )
    );
  
  ------------------------
  --  Concat Operators  --
  ------------------------
  
  Function "&"( Left : Used_Peg; Right : Peg ) return Used_Peg is
  begin
     return Result : Used_Peg := Left do
        Result(Right):= True;
     end return;
  end "&";

  Function "&"(Left : Connection_List; Right : Node) return Connection_List is
  begin
     Return Result : Connection_List := Left do
        Result(Right):= True;
     end return;        
  end "&";   

  -----------------------
  --  IMAGE FUNCTIONS  --
  -----------------------

  Function Image(Input : Peg) Return Character is
    ( Peg'Image(Input)(2) );

  Function Image(Input : Peg) Return String is
    ( 1 => Image(Input) );

  Function Image(Input : Partial_Board; Item : Node) Return String is
    ( 1 => (if Item not in Input'Range then '*' else Image(Input(Item)) ));

  Function Image( Input : Partial_Board ) Return String is
     A : String renames Image(Input, Connection_Types.A);
     B : String renames Image(Input, Connection_Types.B);
     C : String renames Image(Input, Connection_Types.C);
     D : String renames Image(Input, Connection_Types.D);
     E : String renames Image(Input, Connection_Types.E);
     F : String renames Image(Input, Connection_Types.F);
     G : String renames Image(Input, Connection_Types.G);
     H : String renames Image(Input, Connection_Types.H);
  begin
     return

" "&A&" "&B & New_Line & " /|\ /|\" & New_Line & " / | X | \" & New_Line & " / |/ \| \" & New_Line & " "&C&" - "&D&" - "&E&" - "&F & New_Line & " \ |\ /| /" & New_Line & " \ | X | /" & New_Line & " \|/ \|/" & New_Line & " "&G&" "&H & New_Line; 

  end Image;

End Connection_Types;</lang> <lang Ada>Function Connection_Combinations return Partial_Board is

begin 

  Return Result : Board do
     declare
        
        -- The Generate task takes two parameters
        --   (1) a list of pegs already in use, and
        --   (2) a partial-board
        -- and, if the state given is a viable yet incomplete solution, it
        -- takes a peg and adds it to the state creating a new task with
        -- that peg in its used list.
        --
        -- When a complete solution is found it is copied into result.
        task type Generate(
                           Pegs	: not null access Used_Peg:= new Used_Peg'(others => False);
                           State	: not null access Partial_Board:= new Partial_Board'(Node'Last..Node'First => <>)
                          ) is
        end Generate;

        -- An access to Generate and array thereof, for creating the
        -- children tasks.
        type Generator  is access all Generate;
        type Generators is array(Peg range <>) of Generator;
        
        -- Gen handles the actual creation of a new task and state.
        Function Gen(P : Peg; G : not null access Generate) return Generator is
        begin
           return (if G.Pegs(P) then null
                   else new Generate(
                     Pegs     => new Used_Peg'(G.Pegs.all & P),
                     State    => New Partial_Board'(G.All.State.All & P)
                    )
                  );
        end;

        task body Generate is
        begin
           if Is_Solution(State.All) then
              -- If the state is a partial board, we make children to
              -- complete the calculations.
              if State'Length <= Node'Pos(Node'Last) then
                 declare
                    Subtasks : Constant Generators:=
                      (
                       Gen(1, Generate'Access),
                       Gen(2, Generate'Access),
                       Gen(3, Generate'Access),
                       Gen(4, Generate'Access),
                       Gen(5, Generate'Access),
                       Gen(6, Generate'Access),
                       Gen(7, Generate'Access),
                       Gen(8, Generate'Access)
                      );
                 begin
                    null;
                 end;
              else
                 Result:= State.All;
              end if;
           else
              -- The current state is not a solution, so we do not continue it.
              Null;
           end if;
           
        end Generate;
        
        Master : Generate;
     begin
        null;
     end;
  End return;

End Connection_Combinations; </lang>

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

D

<lang d>void main() @safe { 

   import std.stdio, std.math, std.algorithm, std.traits, std.string;

   enum Peg { A, B, C, D, E, F, G, H }
   // immutable Peg[2][$] connections =
   immutable Peg[2][15] connections =
           [[Peg.A, Peg.C], [Peg.A, Peg.D], [Peg.A, Peg.E],
            [Peg.B, Peg.D], [Peg.B, Peg.E], [Peg.B, Peg.F],
            [Peg.C, Peg.D], [Peg.D, Peg.E], [Peg.E, Peg.F],
            [Peg.G, Peg.C], [Peg.G, Peg.D], [Peg.G, Peg.E],
            [Peg.H, Peg.D], [Peg.H, Peg.E], [Peg.H, Peg.F]];

   immutable board = r"
       A   B
      /|\ /|\
     / | X | \
    /  |/ \|  \
   C - D - E - F
    \  |\ /|  /
     \ | X | /
      \|/ \|/
       G   H";

   // Peg[$] perm = [EnumMembers!Peg];
   Peg[EnumMembers!Peg.length] perm = [EnumMembers!Peg];
   do if (connections[].all!(con => abs(perm[con[0]] - perm[con[1]]) > 1))
       return board.tr("ABCDEFGH", "%(%d%)".format(perm)).writeln;
   while (perm[].nextPermutation);

}</lang>

Output:
        2   3
       /|\ /|\
      / | X | \
     /  |/ \|  \
    6 - 0 - 7 - 1
     \  |\ /|  /
      \ | X | /
       \|/ \|/
        4   5

Alternative version

Using a simple backtracking.

Translation of: Go

<lang d>import std.stdio, std.algorithm, std.conv, std.string, std.typecons;

// Holes A=0, B=1, ..., H=7 // With connections: const board = r" 

      A   B
     /|\ /|\
    / | X | \
   /  |/ \|  \
  C - D - E - F
   \  |\ /|  /
    \ | X | /
     \|/ \|/
      G   H";

struct Connection { uint a, b; }

immutable Connection[] 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

];

alias Pegs = uint[8];

int absDiff(in uint a, in uint b) pure nothrow @safe @nogc { 

   return (a > b) ? (a - b) : (b - a);

}

/** Solution is a simple recursive brute force solver, it stops at the first found solution. It returns the solution, the number of positions tested, and the number of pegs swapped. */ Tuple!(Pegs,"p", uint,"tests", uint,"swaps") solve() pure nothrow @safe @nogc { 

   uint tests = 0, swaps = 0;
   Pegs p = [1, 2, 3, 4, 5, 6, 7, 8];

   bool recurse(in uint i) nothrow @safe @nogc {
       if (i >= p.length.signed - 1) {
           tests++;
           return connections.all!(c => absDiff(p[c.a], p[c.b]) > 1);
       }

       // Try each remain peg from.
       foreach (immutable j;  i .. p.length) {
           swaps++;
           swap(p[i], p[j]);
           if (recurse(i + 1))
               return true;
           swap(p[i], p[j]);
       }
       return false;
   }

   recurse(0);
   return typeof(return)(p, tests, swaps);

}

void main() { 

   immutable sol = solve();
   board.tr("ABCDEFGH", "%(%d%)".format(sol.p)).writeln;
   writeln("Tested ", sol.tests, " positions and did ", sol.swaps, " swaps.");

}</lang>

Output:
       3   4
      /|\ /|\
     / | X | \
    /  |/ \|  \
   7 - 1 - 8 - 2
    \  |\ /|  /
     \ | X | /
      \|/ \|/
       5   6
Tested 12094 positions and did 20782 swaps.

Go

A simple recursive brute force solution. <lang go>package main

import ( "fmt" "strings" )

func main() { p, tests, swaps := Solution() fmt.Println(p) fmt.Println("Tested", tests, "positions and did", swaps, "swaps.") }

// Holes A=0, B=1, …, H=7 // With connections: const conn = ` 

      A   B
     /|\ /|\
    / | X | \
   /  |/ \|  \
  C - D - E - F
   \  |\ /|  /
    \ | X | /
     \|/ \|/
      G   H`

var connections = []struct{ a, b int }{ {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 }

type pegs [8]int

// Valid checks if the pegs are a valid solution. // If the absolute difference between any pair of connected pegs is // greater than one it is a valid solution. func (p *pegs) Valid() bool { for _, c := range connections { if absdiff(p[c.a], p[c.b]) <= 1 { return false } } return true }

// Solution is a simple recursive brute force solver, // it stops at the first found solution. // It returns the solution, the number of positions tested, // and the number of pegs swapped. func Solution() (p *pegs, tests, swaps int) { var recurse func(int) bool recurse = func(i int) bool { if i >= len(p)-1 { tests++ return p.Valid() } // Try each remain peg from p[i:] in p[i] for j := i; j < len(p); j++ { swaps++ p[i], p[j] = p[j], p[i] if recurse(i + 1) { return true } p[i], p[j] = p[j], p[i] } return false } p = &pegs{1, 2, 3, 4, 5, 6, 7, 8} recurse(0) return }

func (p *pegs) String() string { return strings.Map(func(r rune) rune { if 'A' <= r && r <= 'H' { return rune(p[r-'A'] + '0') } return r }, conn) }

func absdiff(a, b int) int { if a > b { return a - b } return b - a }</lang>

Output:

       3   4
      /|\ /|\
     / | X | \
    /  |/ \|  \
   7 - 1 - 8 - 2
    \  |\ /|  /
     \ | X | /
      \|/ \|/
       5   6
Tested 12094 positions and did 20782 swaps.


J

Supporting code:

<lang J>holes=:;:'A B C D E F G H'

connections=:".;._2]0 :0 

holes e.;:'C D E'          NB. A
holes e.;:'D E F'          NB. B
holes e.;:'A D G'          NB. C
holes e.;:'A B C E G H'    NB. D
holes e.;:'A B D F G H'    NB. E
holes e.;:'B E H'          NB. F
holes e.;:'C D E'          NB. G
holes e.;:'D E F'          NB. H

) assert (-:|:) connections NB. catch typos

pegs=: 1+(A.&i.~ !)8

attempt=: [: <./@(-.&0)@,@:| connections * -/~


box=:0 :0 

       A   B
      /|\ /|\
     / | X | \
    /  |/ \|  \
   C - D - E - F
    \  |\ /|  /
     \ | X | /
      \|/ \|/
       G   H

)

disp=:verb define 

 rplc&(,holes;&":&>y) box

)</lang>

Intermezzo:

<lang J> (#~ 1<attempt"1) pegs 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</lang>

Since there's more than one arrangement where the pegs satisfy the task constraints, and since the task calls for one solution, we will need to pick one of them. We can use the "first" function to satisfy this important constraint.

<lang J> disp {. (#~ 1<attempt"1) pegs 

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

</lang>

jq

Works with: jq version 1.4

We present a generate-and-test solver for a slightly more general version of the problem, in which there are N pegs and holes, and in which the connectedness of holes is defined by an array such that holes i and j are connected if and only if [i,j] is a member of the array.

The jq index origin is 0, and so in the following, the pegs and holes are internally numbered from 0 to (N-1) inclusive. That is, we interpret a permutation, p, of 0 .. (N-1) as meaning that the i-th peg is numbered p[i], for i in 0 .. (N-1).

However the pretty-print function shows solutions using the 1-to-8 numbering scheme for pegs, and the A-to-H lettering scheme for holes.

Part 1: Generic functions <lang jq># Short-circuit determination of whether (a|condition)

  1. is true for all a in array:

def forall(array; condition): 

 def check:
   . as $ix
   | if $ix == (array|length) then true
     elif (array[$ix] | condition) then ($ix + 1) | check
     else false
     end;
 0 | check;
  1. permutations of 0 .. (n-1)

def permutations(n): 

 # Given a single array, generate a stream by inserting n at different positions:
 def insert(m;n):
    if m >= 0 then (.[0:m] + [n] + .[m:]), insert(m-1;n) else empty end;
 if n==0 then []
 elif n == 1 then [1]
 else
   permutations(n-1) | insert(n-1; n)
 end;
  1. Count the number of items in a stream

def count(f): reduce f as $_ (0; .+1);</lang>

Part 2: The no-connections puzzle for N pegs and holes <lang jq># Generate a stream of solutions.

  1. Input should be the connections array, i.e. an array of [i,j] pairs;
  2. N is the number of pegs and holds.

def solutions(N): 

 def abs: if . < 0 then -. else . end;

 # Is the proposed permutation (the input) ok?
 def ok(connections):
   . as $p
   | forall( connections; 
             (($p[.[0]] - $p[.[1]])|abs) != 1 );

  . as $connections | permutations(N) | select(ok($connections);</lang>

Part 3: The 8-peg no-connection puzzle <lang jq># The connectedness matrix:

  1. In this table, 0 represents "A", etc, and an entry [i,j]
  2. signifies that the holes with indices i and j are connected.

def connections: 

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

def solve: 

 connections | solutions(8);
  1. pretty-print a solution for the 8-peg puzzle

def pp: 

 def pegs: ["A", "B", "C", "D", "E", "F", "G", "H"];
 . as $in
 | ("
        A   B
       /|\\ /|\\
      / | X | \\
     /  |/ \\|  \\
    C - D - E - F
     \\  |\\ /|  /
      \\ | X | /
       \\|/ \\|/
        G   H

" | explode) as $board 

   | (pegs | map(explode)) as $letters
   | $letters
   | reduce range(0;length) as $i ($board; index($letters[$i]) as $ix | .[$ix] = $in[$i] + 48)
   | implode;</lang>

Examples: <lang jq># To print all the solutions:

  1. solve | pp
  1. To count the number of solutions:
  2. count(solve)
  1. jq 1.4 lacks facilities for harnessing generators,
  2. but the following will suffice here:

def one(f): reduce f as $s 

 (null; if . == null then $s else . end);

one(solve) | pp </lang>

Output:

<lang sh>$ jq -n -r -f no_connection.jq 

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

Perl 6

Using the Warnsdorff algorithm from Solve_a_Hidato_puzzle. The idiosyncratic adjacency diagram is dealt with by the simple expedient of bending the two vertical lines || into two bows )(, such that adjacency can be calculated simply as a distance of 2 or less. <lang perl6>my @adjacent = gather -> $y, $x { 

   take [$y,$x] if abs($x|$y) > 2;

} for -5 .. 5 X -5 .. 5;

solveboard q:to/END/; 

   . 0 . . 0 .
   . . . . . .
   0 . 0 1 . 0
   . . . . . .
   . 0 . . 0 .
   END</lang>
Output:
  4     3  
           
2   8 1   7
           
  6     5  
44 tries

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 : 

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

Python

A brute force search solution. <lang python>from __future__ import print_function from itertools import permutations from enum import Enum

A, B, C, D, E, F, G, H = Enum('Peg', 'A, B, C, D, E, F, G, H')

connections = ((A, C), (A, D), (A, E), 

              (B, D), (B, E), (B, F),
              (G, C), (G, D), (G, E),
              (H, D), (H, E), (H, F),
              (C, D), (D, E), (E, F))


def ok(conn, perm): 

   """Connected numbers ok?"""
   this, that = (c.value - 1 for c in conn)
   return abs(perm[this] - perm[that]) != 1


def solve(): 

   return [perm for perm in permutations(range(1, 9))
           if all(ok(conn, perm) for conn in connections)]


if __name__ == '__main__': 

   solutions = solve()
   print("A, B, C, D, E, F, G, H =", ', '.join(str(i) for i in solutions[0]))</lang>
Output:
A, B, C, D, E, F, G, H = 3, 4, 7, 1, 8, 2, 5, 6


All solutions pretty printed

Add the following code after that above: <lang python>def pp(solution): 

   """Prettyprint a solution"""
   boardformat = r"""
        A   B
       /|\ /|\
      / | X | \
     /  |/ \|  \
    C - D - E - F
     \  |\ /|  /
      \ | X | /
       \|/ \|/
        G   H"""
   for letter, number in zip("ABCDEFGH", solution):
       boardformat = boardformat.replace(letter, str(number))
   print(boardformat)


if __name__ == '__main__': 

   for i, s in enumerate(solutions, 1):
       print("\nSolution", i, end=)
       pp(s)</lang>
Extra output
Solution 1
         3   4
        /|\ /|\
       / | X | \
      /  |/ \|  \
     7 - 1 - 8 - 2
      \  |\ /|  /
       \ | X | /
        \|/ \|/
         5   6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Racket

<lang racket>#lang racket

Solve the no connection puzzle. Tim Brown Oct. 2014
absolute difference of a and b if they are both true

(define (and- a b) (and a b (abs (- a b))))

Finds the differences of all established connections in the network

(define (network-diffs (A #f) (B #f) (C #f) (D #f) (E #f) (F #f) (G #f) (H #f)) 

 (list (and- A C) (and- A D) (and- A E)
       (and- B D) (and- B E) (and- B F)
       (and- C D) (and- C G)
       (and- D E) (and- D G) (and- D H)
       (and- E F) (and- E G) (and- E H)
       (and- F G)))
Make sure there is “no connection” in the network N; return N if good

(define (good-network? N) 

 (and (for/and ((d (filter values (apply network-diffs N)))) (> d 1)) N))
possible optimisation is to reverse the arguments to network-diffs, reverse the return value from
this function and make this a cons but we're pretty quick here as it is.

(define (find-good-network pegs (n/w null)) 

 (if (null? pegs) n/w
     (for*/or ((p pegs))
       (define n/w+ (append n/w (list p)))
       (and (good-network? n/w+)
            (find-good-network (remove p pegs =) n/w+)))))

(define (render-puzzle pzl) 

 (apply printf (regexp-replace* "O" #<<EOS
   O   O
  /|\ /|\
 / | X | \
/  |/ \|  \

O - O - O - O 

\  |\ /|  /
 \ | X | /
  \|/ \|/
   O   O~%

EOS 

                                "~a") pzl))

(render-puzzle (find-good-network '(1 2 3 4 5 6 7 8)))</lang>

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

REXX

unannotated solutions

<lang rexx>/*REXX program solves the "no-connection" puzzle (with eight pegs). */ parse arg limit . /*# solutions*/ /* ╔═══════════════════════════╗ */ if limit== then limit=1 /* ║ A B ║ */ 

                                      /* ║         /│\  /│\          ║ */

@. = /* ║ / │ \/ │ \ ║ */ @.1 = 'A C D E' /* ║ / │ /\ │ \ ║ */ @.2 = 'B D E F' /* ║ / │/ \│ \ ║ */ @.3 = 'C A D G' /* ║ C────D────E────F ║ */ @.4 = 'D A B C E G' /* ║ \ │\ /│ / ║ */ @.5 = 'E A B D F H' /* ║ \ │ \/ │ / ║ */ @.6 = 'F B E G' /* ║ \ │ /\ │ / ║ */ @.7 = 'G C D E' /* ║ \│/ \│/ ║ */ @.8 = 'H D E F' /* ║ G H ║ */ cnt=0 /* ╚═══════════════════════════╝ */ 

                  do nodes=1  while  @.nodes\==;    _=word(@.nodes,1)
                  subs=0              /* [↓]  create list of node paths*/
                             do #=1  for  words(@.nodes)-1
                             __=word(@.nodes,#+1);  if __>_  then iterate
                             subs=subs+1;           !._.subs=__
                             end  /*#*/
                  !._.0=subs          /*assign the number of node paths*/
                  end   /*nodes*/

pegs=nodes-1 /*number of pegs to be seated. */ _=' ' /*_ is used for padding output.*/ 

       do a=1  for pegs;         if ?('A')  then iterate
        do b=1  for pegs;        if ?('B')  then iterate
         do c=1  for pegs;       if ?('C')  then iterate
          do d=1  for pegs;      if ?('D')  then iterate
           do e=1  for pegs;     if ?('E')  then iterate
            do f=1  for pegs;    if ?('F')  then iterate
             do g=1  for pegs;   if ?('G')  then iterate
              do h=1  for pegs;  if ?('H')  then iterate
              say _ 'a='a _ 'b='||b _ 'c='c _ 'd='d _ 'e='e _ 'f='f _ 'g='g _ 'h='h
              cnt=cnt+1;   if cnt==limit  then leave a
              end   /*h*/
             end    /*g*/
            end     /*f*/
           end      /*e*/
          end       /*d*/
         end        /*c*/
        end         /*b*/
       end          /*a*/

say /*display a blank line to screen.*/ s=left('s',cnt\==1) /*handle case of plurals (or not)*/ say 'found ' cnt " solution"s'.' /*display the number of solutions*/ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────? subroutine────────────────────────*/ ?: parse arg node; nn=value(node); nL=nn-1; nH=nn+1 

 do cn=c2d('A')  to c2d(node)-1; if value(d2c(cn))==nn then return 1; end
                                      /* [↑]  see if any are duplicates*/
    do ch=1  for !.node.0             /* [↓]  see if any  ¬ =  ±1 value*/
    $=!.node.ch;  fn=value($)         /*node name and its current peg#.*/
    if nL==fn | nH==fn  then return 1 /*if ≡ ±1, then it can't be used.*/
    end   /*ch*/                      /* [↑]  looking for suitable num.*/

return 0 /*the sub arg value passed is OK.*/</lang> output when using the default input: 

     a=3      b=4      c=7      d=1      e=8      f=2      g=5      h=6

found  1  solution.

output when using the input of:   999 

     a=3      b=4      c=7      d=1      e=8      f=2      g=5      h=6
     a=3      b=5      c=7      d=1      e=8      f=2      g=4      h=6
     a=3      b=6      c=7      d=1      e=8      f=2      g=4      h=5
     a=3      b=6      c=7      d=1      e=8      f=2      g=5      h=4
     a=4      b=3      c=2      d=8      e=1      f=7      g=6      h=5
     a=4      b=5      c=2      d=8      e=1      f=7      g=6      h=3
     a=4      b=5      c=7      d=1      e=8      f=2      g=3      h=6
     a=4      b=6      c=7      d=1      e=8      f=2      g=3      h=5
     a=5      b=3      c=2      d=8      e=1      f=7      g=6      h=4
     a=5      b=4      c=2      d=8      e=1      f=7      g=6      h=3
     a=5      b=4      c=7      d=1      e=8      f=2      g=3      h=6
     a=5      b=6      c=7      d=1      e=8      f=2      g=3      h=4
     a=6      b=3      c=2      d=8      e=1      f=7      g=4      h=5
     a=6      b=3      c=2      d=8      e=1      f=7      g=5      h=4
     a=6      b=4      c=2      d=8      e=1      f=7      g=5      h=3
     a=6      b=5      c=2      d=8      e=1      f=7      g=4      h=3

found  16  solutions.

annotated solutions

<lang rexx>/*REXX program solves the "no-connection" puzzle (with eight pegs). */ @abc='ABCDEFGHIJKLMNOPQRSTUVWXYZ' parse arg limit . /*# solutions*/ /* ╔═══════════════════════════╗ */ if limit== then limit=1 /* ║ A B ║ */ oLimit=limit; limit=abs(limit) /* ║ /│\ /│\ ║ */ @. = /* ║ / │ \/ │ \ ║ */ @.1 = 'A C D E' /* ║ / │ /\ │ \ ║ */ @.2 = 'B D E F' /* ║ / │/ \│ \ ║ */ @.3 = 'C A D G' /* ║ C────D────E────F ║ */ @.4 = 'D A B C E G' /* ║ \ │\ /│ / ║ */ @.5 = 'E A B D F H' /* ║ \ │ \/ │ / ║ */ @.6 = 'F B E G' /* ║ \ │ /\ │ / ║ */ @.7 = 'G C D E' /* ║ \│/ \│/ ║ */ @.8 = 'H D E F' /* ║ G H ║ */ cnt=0 /* ╚═══════════════════════════╝ */ 

                  do nodes=1  while  @.nodes\==;    _=word(@.nodes,1)
                  subs=0              /* [↓]  create list of node paths*/
                             do #=1  for  words(@.nodes)-1
                             __=word(@.nodes,#+1);  if __>_  then iterate
                             subs=subs+1;           !._.subs=__
                             end  /*#*/
                  !._.0=subs          /*assign the number of node paths*/
                  end   /*nodes*/

pegs=nodes-1 /*number of pegs to be seated. */ 

            do a=1  for pegs;               if ?('A')  then iterate
             do b=1  for pegs;              if ?('B')  then iterate
              do c=1  for pegs;             if ?('C')  then iterate
               do d=1  for pegs;            if ?('D')  then iterate
                do e=1  for pegs;           if ?('E')  then iterate
                 do f=1  for pegs;          if ?('F')  then iterate
                  do g=1  for pegs;         if ?('G')  then iterate
                   do h=1  for pegs;        if ?('H')  then iterate
                   call showNodes
                   cnt=cnt+1;         if cnt==limit  then leave a
                   end   /*h*/
                  end    /*g*/
                 end     /*f*/
                end      /*e*/
               end       /*d*/
              end        /*c*/
             end         /*b*/
            end          /*a*/

say /*display a blank line to screen.*/ s=left('s',cnt\==1) /*handle case of plurals (or not)*/ say 'found ' cnt " solution"s'.' /*display the number of solutions*/ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────? subroutine────────────────────────*/ ?: parse arg node; nn=value(node); nL=nn-1; nH=nn+1 

 do cn=c2d('A')  to c2d(node)-1; if value(d2c(cn))==nn then return 1; end
                                      /* [↑]  see if any are duplicates*/
    do ch=1  for !.node.0             /* [↓]  see if any  ¬ =  ±1 value*/
    $=!.node.ch;  fn=value($)         /*node name and its current peg#.*/
    if nL==fn | nH==fn  then return 1 /*if ≡ ±1, then it can't be used.*/
    end   /*ch*/                      /* [↑]  looking for suitable num.*/

return 0 /*the sub arg value passed is OK.*/ /*──────────────────────────────────SHOWNODES subroutine────────────────*/ showNodes: _=' ' /*_ is used for padding output.*/ show=0 /*indicates graph not found yet. */ 

 do box=1  for sourceline()  while oLimit<0   /*Negative?  Then show it*/
 xw=sourceline(box)                   /*get a line of this REXX program*/
 p2=lastpos('*',xw)                   /*position of    last   asterisk.*/
 p1=lastpos('*',xw,max(1,p2-1))       /*    "    " penultimate    "    */
 if pos('╔', xw)\==0  then show=1     /*Found the top-left box corner? */
 if \show             then iterate    /*Not found?  Then skip this line*/
 xb=substr(xw, p1+1, p2-p1-2)         /*extract the "box" part of line.*/
 xt=xb                                /*get a working copy of the box. */
       do jx=1  for pegs              /*do a substitution for all pegs.*/
       aa=substr(@abc,jx,1)           /*get the name of the peg (A──►Z)*/
       xt=translate(xt,value(aa),aa)  /*substitute peg name with value.*/
       end    /*jx*/                  /* [↑]  graph limited to 26 nodes*/
 say _ xb _ _ xt                      /*display one line of the graph. */
 if pos('╝',xw)\==0  then return      /*Last line of graph?  Then stop.*/
 end   /*box*/
                                      /* [↓]   show a simple solution. */

say _ 'a='a _ 'b='||b _ 'c='c _ 'd='d _ 'e='e _ 'f='f _ 'g='g _ 'h='h</lang> output when the input is:   -1 

       ╔═══════════════════════════╗              ╔═══════════════════════════╗
       ║          A    B           ║              ║          3    4           ║
       ║         /│\  /│\          ║              ║         /│\  /│\          ║
       ║        / │ \/ │ \         ║              ║        / │ \/ │ \         ║
       ║       /  │ /\ │  \        ║              ║       /  │ /\ │  \        ║
       ║      /   │/  \│   \       ║              ║      /   │/  \│   \       ║
       ║     C────D────E────F      ║              ║     7────1────8────2      ║
       ║      \   │\  /│   /       ║              ║      \   │\  /│   /       ║
       ║       \  │ \/ │  /        ║              ║       \  │ \/ │  /        ║
       ║        \ │ /\ │ /         ║              ║        \ │ /\ │ /         ║
       ║         \│/  \│/          ║              ║         \│/  \│/          ║
       ║          G    H           ║              ║          5    6           ║
       ╚═══════════════════════════╝              ╚═══════════════════════════╝

found  1  solution.

Ruby

Be it Golden Frogs jumping on trancendental lilly pads, or a Knight on a board, or square pegs into round holes this is essentially a Hidato Like Problem, so I use HLPSolver: <lang ruby>

  1. Solve No Connection Puzzle
  3. Nigel_Galloway
  4. October 6th., 2014

require 'HLPSolver' ADJACENT = 0,0 A,B,C,D,E,F,G,H = [0,1],[0,2],[1,0],[1,1],[1,2],[1,3],[2,1],[2,2]

board1 = <<EOS 

 . 0 0 .
 0 0 1 0 
 . 0 0 .

EOS g = HLPsolver.new(board1) g.board[A[0]][A[1]].adj = [B,G,H,F] g.board[B[0]][B[1]].adj = [A,C,G,H] g.board[C[0]][C[1]].adj = [B,E,F,H] g.board[D[0]][D[1]].adj = [F] g.board[E[0]][E[1]].adj = [C] g.board[F[0]][F[1]].adj = [A,C,D,G] g.board[G[0]][G[1]].adj = [A,B,F,H] g.board[H[0]][H[1]].adj = [A,B,C,G] g.solve </lang>

Output:
Problem:
     0  0
  0  0  1  0
     0  0

Solution:
     5  3
  2  8  1  7
     6  4

Tcl

Library: Tcllib (Package: struct::list)

<lang tcl>package require Tcl 8.6 package require struct::list

proc haveAdjacent {a b c d e f g h} { 

   expr {

[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] 

   }

} proc edge {x y} { 

   expr {abs($x-$y) == 1}

}

set layout [string trim { 

       A   B
      /|\ /|\ 
     / | X | \ 
    /  |/ \|  \ 
   C - D - E - F
    \  |\ /|  /
     \ | X | /
      \|/ \|/
       G   H

} \n] struct::list foreachperm p {1 2 3 4 5 6 7 8} { 

   if {![haveAdjacent {*}$p]} {

puts [string map [join [ lmap name {A B C D E F G H} val $p {list $name $val} ]] $layout] break 

   }

}</lang>

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

XPL0

<lang XPL0>include c:\cxpl\codes;

int Hole, Max, I; char Box(8), Str; def A, B, C, D, E, F, G, H; [for Hole:= 0 to 7 do Box(Hole):= Hole+1; Max:= 7; while abs(Box(D)-Box(A)) < 2 or abs(Box(D)-Box(C)) < 2 or 

       abs(Box(D)-Box(G)) < 2  or  abs(Box(D)-Box(E)) < 2  or
       abs(Box(A)-Box(C)) < 2  or  abs(Box(C)-Box(G)) < 2  or
       abs(Box(G)-Box(E)) < 2  or  abs(Box(E)-Box(A)) < 2  or
       abs(Box(E)-Box(B)) < 2  or  abs(Box(E)-Box(H)) < 2  or
       abs(Box(E)-Box(F)) < 2  or  abs(Box(B)-Box(D)) < 2  or
       abs(Box(D)-Box(H)) < 2  or  abs(Box(H)-Box(F)) < 2  or
       abs(Box(F)-Box(B)) < 2  do
          loop [I:= Box(0);                    \next permutation
               for Hole:= 0 to Max-1 do Box(Hole):= Box(Hole+1);
               Box(Max):= I;
               if I # Max+1 then [Max:= 7;  quit]
               else Max:= Max-1];

Str:= " 

   #   #
  /|\ /|\
 / | X | \
/  |/ \|  \
  1. - # - # - #
\  |\ /|  /
 \ | X | /
  \|/ \|/
   #   #

"; Hole:= 0; I:= 0; repeat if Str(I)=^# then [Str(I):= Box(Hole)+^0; Hole:= Hole+1]; 

       I:= I+1;

until Hole = 8; Text(0, Str); ]</lang>

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

zkl

Translation of: D

<lang zkl>const PegA=0, PegB=1, PegC=2, PegD=3, PegE=4, PegF=5, PegG=6, PegH=7; connections:=T( 

  T(PegA, PegC), T(PegA, PegD), T(PegA, PegE),
  T(PegB, PegD), T(PegB, PegE), T(PegB, PegF),
  T(PegC, PegD), T(PegD, PegE), T(PegE, PegF),
  T(PegG, PegC), T(PegG, PegD), T(PegG, PegE),
  T(PegH, PegD), T(PegH, PegE), T(PegH, PegF));

CZ:=connections.len(); board:= 0'$ A B$"\n" 0'$ /|\ /|\$"\n" 0'$ / | X | \$"\n" 0'$ / |/ \| \$"\n" 0'$ C - D - E - F$"\n" 0'$ \ |\ /| /$"\n" 0'$ \ | X | /$"\n" 0'$ \|/ \|/$"\n" 0'$ G H$;

perm:=T(PegA,PegB,PegC,PegD,PegE,PegF,PegG,PegH); // Peg[8] foreach p in (Utils.Helpers.permuteW(perm)){ // permutation iterator 

  if(connections.filter1('wrap([(a,b)]){ (p[a] - p[b]).abs()<=1 })) continue;
  tr(board,"ABCDEFGH",p.apply('+(1))).println(); 
  break;  // comment out to see all 16 solutions

}

fcn tr(src,as,bs){ 

  foreach a,b in (Utils.Helpers.zipW(as,bs)){ src=src.replace(a,b.toString()) }
  src

}</lang> The filter1 method stops on the first True, so it acts like a conditional or.

Output:
        5   6
       /|\ /|\
      / | X | \
     /  |/ \|  \
    7 - 1 - 8 - 2
     \  |\ /|  /
      \ | X | /
       \|/ \|/
        3   4
Retrieved from "https://rosettacode.org/wiki/Solve_the_no_connection_puzzle?oldid=250569"