Solve the no connection puzzle: Difference between revisions

/ │ X │ \

/ │/ \│ \

\ │\ /│ /

\ │ X │ /

/ │ X │ \

/ │/ \│ \

\ │\ /│ /

\ │ X │ /

[https://www.youtube.com/watch?v=AECElyEyZBQ No Connection Puzzle] (youtube).

<br><br>

=={{header|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.

With

Ada.Text_IO,

begin

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

 

Package Connection_Types with Pure is

Function Image ( Input : Partial_Board ) Return String;

 

Pragma Ada_2012;

 

 

Function Connection_Combinations return Partial_Board;

 

Package Body Connection_Types is

end Image;

 

 

begin

End return;

End Connection_Combinations;

{{out}}

<pre> 4 5

{{works with|Dyalog APL 17.0 Unicode}}

 

 

 

perms←{

⍝∇ 20100513/20140818 ra⌈ --()--

↑{0∊⍴⍵:⍵ ⋄ (⍺[1]⌷⍵),(1↓⍺)∇ ⍵~⍺[1]⌷⍵}∘(⍳⍵)¨↓⍉1+(⌽⍳⍵)⊤¯1+⍳!⍵

}

 

solution←{

⍝ 16

tries[''⍴solns;]

}

 

=={{header|AutoHotkey}}==

,[ "X", "X", "X", "X"]

,[ "", "X", "X"]]

list .= oGrid[row, col+1] ? row ":" col+1 "," : oGrid[row, col-1] ? row ":" col-1 "," : ""

return Trim(list, ",")

Outputs:<pre>

3 5

\|/ \|/

4 6</pre>

 

=={{header|Chapel}}==

param A : hole = 1;

param B : hole = A+1;

}

<pre>

4 5

 

=={{header|D}}==

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

 

return board.tr("ABCDEFGH", "%(%d%)".format(perm)).writeln;

while (perm[].nextPermutation);

{{out}}

<pre>

Using a simple backtracking.

{{trans|Go}}

 

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

board.tr("ABCDEFGH", "%(%d%)".format(sol.p)).writeln;

writeln("Tested ", sol.tests, " positions and did ", sol.swaps, " swaps.");

{{out}}

<pre>

5 6

Tested 12094 positions and did 20782 swaps.</pre>

 

=={{header|Elixir}}==

{{trans|Ruby}}

This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#Elixir | here]]

 

# require HLPsolver

|> Enum.zip(~w[A B C D E F G H])

|> Enum.reduce(layout, fn {n,c},acc -> String.replace(acc, c, to_string(n)) end)

 

{{out}}

 

=={{header|Factor}}==

math.ranges math.parser multiline pair-rocket sequences

sequences.generalizations ;

: main ( -- ) find-solution display-solution ;

 

{{out}}

<pre>

\ | X | /

\|/ \|/

5 6

</pre>

=={{header|Go}}==

A simple recursive brute force solution.

 

import (

}

return b - a

{{out}}

<pre>

Tested 12094 positions and did 20782 swaps.

</pre>

 

=={{header|Haskell}}==

 

solution :: [Int]

where

isSolution :: [Int] -> Bool

all ((> 1) . abs) $

 

main :: IO ()

main =

(putStrLn . unlines) $

{{Out}}

<pre style="font-size:80%">A = 3

Supporting code:

 

 

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

disp=:verb define

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

 

Intermezzo:

 

3 4 7 1 8 2 5 6

3 5 7 1 8 2 4 6

6 3 2 8 1 7 5 4

6 4 2 8 1 7 5 3

 

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.

 

3 4

/|\ /|\

5 6

 

 

'''Video'''

If we follow the video and also connect A and B as well as G and H, we get only four solutions (which we can see are reflections / rotations of each other):

 

3 5 7 1 8 2 4 6

4 6 7 1 8 2 3 5

5 3 2 8 1 7 6 4

 

The first of these looks like this:

 

3 - 5

/|\ /|\

\|/ \|/

4 - 6

 

For this puzzle, we can also see that the solution can be described as: put the starting and ending numbers in the middle - everything else follows from there. It's perhaps interesting that we get this solution even if we do not explicitly put that logic into our code - it's built into the puzzle itself and is still the only solution no matter how we arrive there.

The backtracking is getting tiresome, we'll try a stochastic solution for a change.<br>

{{works with|Java|8}}

import java.util.*;

import static java.util.stream.Collectors.toList;

System.out.printf(" %s %s%n", pegs[6], pegs[7]);

}

(takes about 500 shuffles on average)

<pre> 4 5

===ES6===

{{Trans|Haskell}}

'use strict';

 

 

 

// all :: (a -> Bool) -> [a] -> Bool

 

 

 

 

// enumFromTo :: Enum a => a -> a -> [a]

};

 

 

 

// permutations :: [a] -> [[a]]

 

// show :: a -> String

 

 

 

 

 

 

 

 

 

 

 

 

{{Out}}

<pre>A = 3

 

=={{header|jq}}==

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.

 

'''Part 1: Generic functions'''

def permutations(n):

# Given a single array, generate a stream by inserting n at different positions:

 

# Count the number of items in a stream

'''Part 2: The no-connections puzzle for N pegs and holes'''

# Input should be the connections array, i.e. an array of [i,j] pairs;

# N is the number of pegs and holds.

def ok(connections):

. as $p

 

'''Part 3: The 8-peg no-connection puzzle'''

# In this table, 0 represents "A", etc, and an entry [i,j]

# signifies that the holes with indices i and j are connected.

| $letters

| reduce range(0;length) as $i ($board; index($letters[$i]) as $ix | .[$ix] = $in[$i] + 48)

'''Examples''':

# solve | pp

 

# To count the number of solutions:

# count(solve)

 

5 6

/|\ /|\

\ | X | /

\|/ \|/

 

 

=={{header|Kotlin}}==

{{trans|Go}}

 

import kotlin.math.abs

println(pegsAsString(p))

println("Tested $tests positions and did $swaps swaps.")

 

{{out}}

 

Press space bar to see solutions so far.

Module no_connection_puzzle {

\\ Holes

no_connection_puzzle

 

{{out}}

<pre>

</pre >

 

This one simply takes all permutations of the pegs and filters out invalid solutions.

Select[#,

Function[perm, Abs[perm[[#2[[1]]]] - perm[[#2[[2]]]]] > 1]] &,

" `` ``\n /|\\ /|\\\n / | X | \\\n / |/ \\| \\\n`` - `` \

- `` - ``\n \\ |\\ /| /\n \\ | X | /\n \\|/ \\|/\n `` ``",

{{out}}

<pre> 3 4

5 6</pre>

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

{{out}}

 

=={{header|Phix}}==

Brute force solution. I ordered the links highest letter first, then grouped by start letter to eliminate things asap. Nothing

to eliminate when placing A and B, when placing C, check that CA>1, when placing D, check that DA,DB,DC are all >1, etc.

{{out}}

<pre>

\|/ \|/

5 6

</pre>

 

 

We first compute a list of nodes, with sort this list, and we attribute a value at the nodes.

 

edge(a, c).

set_constraint(H, T1, V, VT).

 

Output :

<pre> ?- no_connection_puzzle(Vs).

=={{header|Python}}==

A brute force search solution.

from itertools import permutations

from enum import Enum

if __name__ == '__main__':

solutions = solve()

 

{{out}}

 

Add the following code after that above:

"""Prettyprint a solution"""

boardformat = r"""

for i, s in enumerate(solutions, 1):

print("\nSolution", i, end='')

 

;Extra output:

=={{header|Racket}}==

 

;; Solve the no connection puzzle. Tim Brown Oct. 2014

 

"~a") pzl))

 

 

{{out}}

\|/ \|/

5 6</pre>

 

=={{header|REXX}}==

===unannotated solutions===

parse arg limit . /*number of solutions wanted.*/ /* ╔═══════════════════════════╗ */

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

@. = /* ║ / │ \/ │ \ ║ */

@.7 = 'G C D E' /* ║ \│/ \│/ ║ */

@.8 = 'H D E F' /* ║ G H ║ */

do #=1 for words(@.pegs) -1 /*create list of node paths.*/

end /*#*/

end /*pegs*/

say /*display a blank line to the terminal.*/

s= left('s', cnt\==1) /*handle the case of plurals (or not).*/

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

end /*cn*/ /* [↑] see if there any are duplicates.*/

do ch=1 for !.node.0 /* [↓] see if there any ¬= ±1 values.*/

if nL==fn | nH==fn then return 1 /*if ≡ ±1, then the node can't be used.*/

end /*ch*/ /* [↑] looking for suitable number. */

<pre>

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

found 1 solution.

</pre>

<pre>

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

===annotated solutions===

Usage note: &nbsp; if the &nbsp; '''limit''' &nbsp; (the 1^st argument) &nbsp; is negative, a diagram (node graph) is shown.

parse arg limit . /*number of solutions wanted.*/ /* ╔═══════════════════════════╗ */

@. = /* ║ / │ \/ │ \ ║ */

@.1 = 'A C D E' /* ║ / │ /\ │ \ ║ */

@.7 = 'G C D E' /* ║ \│/ \│/ ║ */

@.8 = 'H D E F' /* ║ G H ║ */

do #=1 for words(@.pegs) -1 /*create list of node paths.*/

end /*#*/

end /*pegs*/

say /*display a blank line to the terminal.*/

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

end /*cn*/ /* [↑] see if there're any duplicates.*/

do ch=1 for !.node.0 /* [↓] see if there any ¬= ±1 values.*/

if nL==fn | nH==fn then return 1 /*if ≡ ±1, then the node can't be used.*/

end /*ch*/ /* [↑] looking for suitable number. */

return 0 /*the subroutine arg value passed is OK*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

do box=1 for sourceline() while oLimit<0 /*Negative? Then display the diagram. */

if \show then iterate /*Not found? Then skip this line. */

say _ xb _ _ xt /*display one line of the graph. */

if pos('╝', xw)\==0 then return /*Is this last line of graph? Then stop*/

end /*box*/

<pre>

╔═══════════════════════════╗ ╔═══════════════════════════╗

=={{header|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 [http://rosettacode.org/wiki/Solve_a_Hidato_puzzle#With_Warnsdorff HLPSolver]:

# Solve No Connection Puzzle

#

g.board[H[0]][H[1]].adj = [A,B,C,G]

g.solve

{{out}}

<pre>

6 4

</pre>

 

=={{header|Tcl}}==

{{tcllib|struct::list}}

package require struct::list

 

break

}

{{out}}

/|\ /|\

/ | X | \

\ | X | /

\|/ \|/

</pre>

 

=={{header|XPL0}}==

 

int Hole, Max, I;

until Hole = 8;

Text(0, Str);

 

{{out}}

=={{header|zkl}}==

{{trans|D}}

connections:=T(

T(PegA, PegC), T(PegA, PegD), T(PegA, PegE),

board.translate("ABCDEFGH",p.apply('+(1)).concat()).println();

break; // comment out to see all 16 solutions

The filter1 method stops on the first True, so it acts like a conditional or.

{{out}}