Solve the no connection puzzle: Difference between revisions
Add C# implementation
(→{{header|REXX}}: add/changed whitespace and comments, align statements, used templates for the output sections.) |
(Add C# implementation) |
||
(20 intermediate revisions by 11 users not shown) | |||
Line 56:
[https://www.youtube.com/watch?v=AECElyEyZBQ No Connection Puzzle] (youtube).
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">V 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)]
F ok(conn, perm)
R abs(perm[conn[0]] - perm[conn[1]]) != 1
F solve()
[[Int]] r
V perm = Array(1..8)
L
I all(:connections.map(conn -> ok(conn, @perm)))
r [+]= copy(perm)
I !perm.next_permutation()
L.break
R r
V solutions = solve()
print(‘A, B, C, D, E, F, G, H = ’solutions[0].join(‘, ’))</syntaxhighlight>
{{out}}
<pre>
A, B, C, D, E, F, G, H = 3, 4, 7, 1, 8, 2, 5, 6
</pre>
=={{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.
<syntaxhighlight lang="ada">
With
Ada.Text_IO,
Line 69 ⟶ 99:
begin
Ada.Text_IO.Put_Line( Connection_Types.Image(Result) );
end;</
<
Package Connection_Types with Pure is
Line 116 ⟶ 146:
Function Image ( Input : Partial_Board ) Return String;
End Connection_Types;</
<syntaxhighlight lang="ada">
Pragma Ada_2012;
Line 124 ⟶ 154:
Function Connection_Combinations return Partial_Board;
</syntaxhighlight>
<
Package Body Connection_Types is
Line 197 ⟶ 227:
end Image;
End Connection_Types;</
<
begin
Line 271 ⟶ 301:
End return;
End Connection_Combinations;
</syntaxhighlight>
{{out}}
<pre> 4 5
Line 288 ⟶ 318:
{{works with|Dyalog APL 17.0 Unicode}}
<syntaxhighlight lang="apl">
Line 306 ⟶ 336:
tries[''⍴solns;]
}
</
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
Line 849 ⟶ 879:
iMagicNumber: .int 0xCCCCCCCD
</syntaxhighlight>
<pre>
a=3 b=4 c=7 d=1
Line 867 ⟶ 897:
=={{header|AutoHotkey}}==
<
,[ "X", "X", "X", "X"]
,[ "", "X", "X"]]
Line 939 ⟶ 969:
list .= oGrid[row, col+1] ? row ":" col+1 "," : oGrid[row, col-1] ? row ":" col-1 "," : ""
return Trim(list, ",")
}</
Outputs:<pre>
3 5
Line 953 ⟶ 983:
=={{header|C}}==
{{trans|Go}}
<
#include <stdio.h>
#include <math.h>
Line 1,015 ⟶ 1,045:
solution(0, 8 - 1);
return 0;
}</
{{out}}
<pre>----- 0 -----
Line 1,096 ⟶ 1,126:
2 8 1 7
4 3</pre>
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
using System.Collections.Generic;
using System.Linq;
public class NoConnection
{
// adopted from Go
static int[][] links = new int[][] {
new int[] {2, 3, 4}, // A to C,D,E
new int[] {3, 4, 5}, // B to D,E,F
new int[] {2, 4}, // D to C, E
new int[] {5}, // E to F
new int[] {2, 3, 4}, // G to C,D,E
new int[] {3, 4, 5}, // H to D,E,F
};
static int[] pegs = new int[8];
public static void Main(string[] args)
{
List<int> vals = Enumerable.Range(1, 8).ToList();
Random rng = new Random();
do
{
vals = vals.OrderBy(a => rng.Next()).ToList();
for (int i = 0; i < pegs.Length; i++)
pegs[i] = vals[i];
} while (!Solved());
PrintResult();
}
static bool Solved()
{
for (int i = 0; i < links.Length; i++)
foreach (int peg in links[i])
if (Math.Abs(pegs[i] - peg) == 1)
return false;
return true;
}
static void PrintResult()
{
Console.WriteLine($" {pegs[0]} {pegs[1]}");
Console.WriteLine($"{pegs[2]} {pegs[3]} {pegs[4]} {pegs[5]}");
Console.WriteLine($" {pegs[6]} {pegs[7]}");
}
}
</syntaxhighlight>
{{out}}
<pre>
6 1
4 3 8 7
2 5
</pre>
=={{header|C++}}==
{{trans|C}}
<
#include <iostream>
#include <vector>
Line 1,148 ⟶ 1,240:
solution(0, pegs.size() - 1);
return 0;
}</
{{out}}
<pre>----- 0 -----
Line 1,231 ⟶ 1,323:
=={{header|Chapel}}==
<
param A : hole = 1;
param B : hole = A+1;
Line 1,309 ⟶ 1,401:
}
</syntaxhighlight>
<pre>
4 5
Line 1,323 ⟶ 1,415:
=={{header|D}}==
<
import std.stdio, std.math, std.algorithm, std.traits, std.string;
Line 1,349 ⟶ 1,441:
return board.tr("ABCDEFGH", "%(%d%)".format(perm)).writeln;
while (perm[].nextPermutation);
}</
{{out}}
<pre>
Line 1,366 ⟶ 1,458:
Using a simple backtracking.
{{trans|Go}}
<
// Holes A=0, B=1, ..., H=7
Line 1,430 ⟶ 1,522:
board.tr("ABCDEFGH", "%(%d%)".format(sol.p)).writeln;
writeln("Tested ", sol.tests, " positions and did ", sol.swaps, " swaps.");
}</
{{out}}
<pre>
Line 1,443 ⟶ 1,535:
5 6
Tested 12094 positions and did 20782 swaps.</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
{ This item would normally be in a separate library. It is presented here for clarity}
{Permutator object steps through all permutation of array items}
{Zero-Based = True = 0..Permutions-1 False = 1..Permutaions}
{Permutation set on "Create(Size)" or by "Permutations" property}
{Permutation are contained in the array "Indices"}
type TPermutator = class(TObject)
private
FZeroBased: boolean;
FBase: integer;
FPermutations: integer;
procedure SetZeroBased(const Value: boolean);
procedure SetPermutations(const Value: integer);
protected
FMax: integer;
public
Indices: TIntegerDynArray;
constructor Create(Size: integer);
procedure Reset;
function Next: boolean;
property ZeroBased: boolean read FZeroBased write SetZeroBased;
property Permutations: integer read FPermutations write SetPermutations;
end;
procedure TPermutator.Reset;
var I: integer;
begin
FMax:=High(Indices);
for I:= 0 to High(Indices) do Indices[I]:= I+FBase;
end;
procedure TPermutator.SetPermutations(const Value: integer);
begin
if FPermutations<>Value then
begin
FPermutations := Value;
SetLength(Indices,Value);
Reset;
end;
end;
constructor TPermutator.Create(Size: integer);
begin
ZeroBased:=True;
Permutations:=Size;
Reset;
end;
function TPermutator.Next: boolean;
{Returns true when sequence completed}
var I,T: integer;
begin
while true do
begin
T:= Indices[0];
for I:=0 to FMax-1 do Indices[I]:= Indices[I+1];
Indices[FMax]:= T;
if T<>(FMax+FBase) then
begin
FMax:=High(Indices);
break;
end
else FMax:= FMax-1;
if FMax<0 then break;
end;
Result:=FMax<1;
if Result then Reset;
end;
procedure TPermutator.SetZeroBased(const Value: boolean);
begin
if FZeroBased<>Value then
begin
FZeroBased := Value;
if Value then FBase:=0
else FBase:=1;
Reset;
end;
end;
{------------------------------------------------------------------------------}
{Network structures}
{Puzzle node}
type TPuzNode = record
Name: string;
Value: integer;
end;
type PPuzNode = ^TPuzNode;
{Edges connecting nodes}
type TPuzEdge = record
N1,N2: ^TPuzNode;
end;
{All edges in puzzle}
var Edges: array [0..14] of TPuzEdge;
{All nodes in puzzle}
var A: TPuzNode = (Name: 'A'; Value: 1);
var B: TPuzNode = (Name: 'B'; Value: 2);
var C: TPuzNode = (Name: 'C'; Value: 3);
var D: TPuzNode = (Name: 'D'; Value: 4);
var E: TPuzNode = (Name: 'E'; Value: 5);
var F: TPuzNode = (Name: 'F'; Value: 6);
var G: TPuzNode = (Name: 'G'; Value: 7);
var H: TPuzNode = (Name: 'H'; Value: 8);
{Array of pointers to puzzle nodes }
var PuzNodes: array [0..7] of Pointer;
procedure BuildNetwork;
{Build puzzle net work}
begin
{Put pointers to nodes in array}
PuzNodes[0]:=@A;
PuzNodes[1]:=@B;
PuzNodes[2]:=@C;
PuzNodes[3]:=@D;
PuzNodes[4]:=@E;
PuzNodes[5]:=@F;
PuzNodes[6]:=@G;
PuzNodes[7]:=@H;
{Set up all edges}
Edges[0].N1:=@A; Edges[0].N2:=@C;
Edges[1].N1:=@A; Edges[1].N2:=@D;
Edges[2].N1:=@A; Edges[2].N2:=@E;
Edges[3].N1:=@B; Edges[3].N2:=@D;
Edges[4].N1:=@B; Edges[4].N2:=@E;
Edges[5].N1:=@B; Edges[5].N2:=@F;
Edges[6].N1:=@G; Edges[6].N2:=@C;
Edges[7].N1:=@G; Edges[7].N2:=@D;
Edges[8].N1:=@G; Edges[8].N2:=@E;
Edges[9].N1:=@H; Edges[9].N2:=@D;
Edges[10].N1:=@H; Edges[10].N2:=@E;
Edges[11].N1:=@H; Edges[11].N2:=@F;
Edges[12].N1:=@C; Edges[12].N2:=@D;
Edges[13].N1:=@D; Edges[13].N2:=@E;
Edges[14].N1:=@E; Edges[14].N2:=@F;
end;
function ValidPattern: boolean;
{Test if pattern of node values is valid}
{i.e., edges values are greater than 1}
var I: integer;
begin
Result:=False;
for I:=0 to High(Edges) do
if abs(Edges[I].N2.Value-Edges[I].N1.Value)<2 then exit;
Result:=True;
end;
function Permutate: boolean;
{Use permutator object to iterate through all combinations}
var PM: TPermutator;
var I: integer;
begin
{Create with 8 items}
PM:=TPermutator.Create(8);
try
{Set to make it 1..8}
PM.ZeroBased:=False;
Result:=True;
{Iterate through all permutation}
while not PM.Next do
begin
{Copy permutation into network}
for I:=0 to High(PM.Indices) do
PPuzNode(PuzNodes[I])^.Value:=PM.Indices[I];
{If permutation is valid exit}
if ValidPattern then exit;
end;
{No valid permutation found}
Result:=False;
finally PM.Free; end;
end;
{String to display game board}
var GameBoard: string =
' A B'+CRLF+
' /|\ /|\'+CRLF+
' / | X | \'+CRLF+
' / |/ \| \'+CRLF+
' C - D - E - F'+CRLF+
' \ |\ /| /'+CRLF+
' \ | X | /'+CRLF+
' \|/ \|/'+CRLF+
' G H'+CRLF;
procedure ShowPuzzle(Memo: TMemo);
{Display game board with correct answer inserted}
var I,Inx: integer;
var S: string;
var PN: TPuzNode;
begin
S:=GameBoard;
{Search for Letters A..H}
for I:=1 to Length(S) do
if S[I] in ['A'..'H'] then
begin
{Convert A..H to index}
Inx:=byte(S[I]) - $41;
{Get node A..H}
PN:=PPuzNode(PuzNodes[Inx])^;
{Store value in corresponding node}
S[I]:=char(PN.Value+$30);
end;
{Display board}
Memo.Lines.Add(S);
end;
procedure ConnectionPuzzle(Memo: TMemo);
{Solve connection puzzle}
var S: string;
var I: integer;
var PN: TPuzNode;
begin
BuildNetwork;
Permutate;
{Display result}
S:='';
for I:=0 to High(PuzNodes) do
begin
PN:=PPuzNode(PuzNodes[I])^;
S:=S+PN.Name+'='+IntToStr(PN.Value)+' ';
end;
Memo.Lines.Add(S);
{Show puzzle with values inserted}
ShowPuzzle(Memo);
end;
</syntaxhighlight>
{{out}}
<pre>
A=5 B=6 C=7 D=1 E=8 F=2 G=3 H=4
5 6
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
3 4
Elapsed Time: 2.092 ms.
</pre>
=={{header|Elixir}}==
{{trans|Ruby}}
This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#Elixir | here]]
<
# require HLPsolver
Line 1,472 ⟶ 1,844:
|> 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)
|> IO.puts</
{{out}}
Line 1,488 ⟶ 1,860:
=={{header|Factor}}==
<
math.ranges math.parser multiline pair-rocket sequences
sequences.generalizations ;
Line 1,533 ⟶ 1,905:
: main ( -- ) find-solution display-solution ;
MAIN: main</
{{out}}
<pre>
Line 1,544 ⟶ 1,916:
\ | X | /
\|/ \|/
5 6
</pre>
=={{header|Fortran}}==
{{works with|gfortran|11.2.1}}
<syntaxhighlight lang="fortran">! This is free and unencumbered software released into the public domain,
! via the Unlicense.
! For more information, please refer to <http://unlicense.org/>
program no_connection_puzzle
implicit none
! The names of the holes.
integer, parameter :: a = 1
integer, parameter :: b = 2
integer, parameter :: c = 3
integer, parameter :: d = 4
integer, parameter :: e = 5
integer, parameter :: f = 6
integer, parameter :: g = 7
integer, parameter :: h = 8
integer :: holes(a:h)
call find_solutions (holes, a)
contains
recursive subroutine find_solutions (holes, current_hole_index)
integer, intent(inout) :: holes(a:h)
integer, intent(in) :: current_hole_index
integer :: peg_number
! Recursively construct and print possible solutions, quitting
! any partial solution that does not satisfy constraints.
do peg_number = 1, 8
holes(current_hole_index) = peg_number
if (satisfies_the_constraints (holes, current_hole_index)) then
if (current_hole_index == h) then
call print_solution (holes)
write (*, '()')
else
call find_solutions (holes, current_hole_index + 1)
end if
end if
end do
end subroutine find_solutions
function satisfies_the_constraints (holes, i) result (satisfies)
integer, intent(inout) :: holes(a:h)
integer, intent(in) :: i ! Where the new peg goes.
logical :: satisfies
integer :: j
! The most recently inserted peg must not be a duplicate of one
! already inserted.
satisfies = all (holes(a : i - 1) /= holes(i))
if (satisfies) then
! ‘Fill’ the unfilled holes with fake pegs that cause
! differences with them always to be larger than 1.
do j = i + 1, h
holes(j) = 100 * j
end do
! Check that the differences are satisfactory.
satisfies = 1 < abs (holes(a) - holes(c)) .and. &
& 1 < abs (holes(a) - holes(d)) .and. &
& 1 < abs (holes(a) - holes(e)) .and. &
& 1 < abs (holes(c) - holes(g)) .and. &
& 1 < abs (holes(d) - holes(g)) .and. &
& 1 < abs (holes(e) - holes(g)) .and. &
& 1 < abs (holes(b) - holes(d)) .and. &
& 1 < abs (holes(b) - holes(e)) .and. &
& 1 < abs (holes(b) - holes(f)) .and. &
& 1 < abs (holes(d) - holes(h)) .and. &
& 1 < abs (holes(e) - holes(h)) .and. &
& 1 < abs (holes(f) - holes(h)) .and. &
& 1 < abs (holes(c) - holes(d)) .and. &
& 1 < abs (holes(d) - holes(e)) .and. &
& 1 < abs (holes(e) - holes(f))
end if
end function satisfies_the_constraints
subroutine print_solution (holes)
integer, intent(in) :: holes(a:h)
write (*, '(I5, I4)') holes(a), holes(b)
write (*, '(" /│\ /│\")')
write (*, '(" / │ X │ \")')
write (*, '(" / │/ \│ \")')
write (*, '(3(I1, "───"), I1)') holes(c), holes(d), holes(e), holes(f)
write (*, '(" \ │\ /│ /")')
write (*, '(" \ │ X │ /")')
write (*, '(" \│/ \│/")')
write (*, '(I5, I4)') holes(g), holes(h)
end subroutine print_solution
end program no_connection_puzzle</syntaxhighlight>
The first solution printed:
{{out}}
<pre>
3 4
/│\ /│\
/ │ X │ \
/ │/ \│ \
7───1───8───2
\ │\ /│ /
\ │ X │ /
\│/ \│/
5 6
</pre>
Line 1,549 ⟶ 2,034:
=={{header|Go}}==
A simple recursive brute force solution.
<
import (
Line 1,638 ⟶ 2,123:
}
return b - a
}</
{{out}}
<pre>
Line 1,656 ⟶ 2,141:
=={{header|Groovy}}==
{{trans|Java}}
<
import java.util.stream.IntStream
Line 1,706 ⟶ 2,191:
println(" ${pegs[6]} ${pegs[7]}")
}
}</
{{out}}
<pre> 6 7
Line 1,713 ⟶ 2,198:
=={{header|Haskell}}==
<
solution :: [Int]
solution@(a : b : c : d : e : f : g : h : _) =
head $
filter isSolution (permutations [1 .. 8])
where
isSolution :: [Int] -> Bool
isSolution (a : b : c : d : e : f : g : h : _) =
all ((> 1) . abs) $
zipWith
(-)
[a, c, g, e, a, c, g, e, b, d, h, f, b, d, h, f]
[d, d, d, d, c, g, e, a, e, e, e, e, d, h, f, b]
main :: IO ()
main =
(putStrLn . unlines) $
unlines
( zipWith
(\x y -> x : (" = " <> show y))
['A' .. 'H']
solution
) :
( rightShift . unwords . fmap show
<$> [[], [a, b], [c, d, e, f], [g, h]]
)
where
rightShift s
| length s > 3 = s
| otherwise = " "
{{Out}}
<pre style="font-size:80%">A = 3
Line 1,753 ⟶ 2,247:
Supporting code:
<
connections=:".;._2]0 :0
Line 1,786 ⟶ 2,280:
disp=:verb define
rplc&(,holes;&":&>y) box
)</
Intermezzo:
<
3 4 7 1 8 2 5 6
3 5 7 1 8 2 4 6
Line 1,806 ⟶ 2,300:
6 3 2 8 1 7 5 4
6 4 2 8 1 7 5 3
6 5 2 8 1 7 4 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
/|\ /|\
Line 1,821 ⟶ 2,315:
5 6
</syntaxhighlight>
'''Video'''
Line 1,827 ⟶ 2,321:
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
6 4 2 8 1 7 5 3</
The first of these looks like this:
<
3 - 5
/|\ /|\
Line 1,845 ⟶ 2,339:
\|/ \|/
4 - 6
</syntaxhighlight>
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.
Line 1,852 ⟶ 2,346:
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;
Line 1,897 ⟶ 2,391:
System.out.printf(" %s %s%n", pegs[6], pegs[7]);
}
}</
(takes about 500 shuffles on average)
<pre> 4 5
Line 1,906 ⟶ 2,400:
===ES6===
{{Trans|Haskell}}
<
'use strict';
Line 2,116 ⟶ 2,610:
return main();
})();</
{{Out}}
<pre>A = 3
Line 2,132 ⟶ 2,626:
=={{header|jq}}==
{{works with|jq|1.
'''Also works with gojq, the Go implementation of 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.
Line 2,142 ⟶ 2,638:
'''Part 1: Generic functions'''
<syntaxhighlight lang="jq">
# permutations of 0 .. (n-1) inclusive
def permutations(n):
# Given a single array, generate a stream by inserting n at different positions:
Line 2,165 ⟶ 2,651:
# Count the number of items in a stream
def count(f): reduce f as $_ (0; .+1);
</syntaxhighlight>
'''Part 2: The no-connections puzzle for N pegs and holes'''
<syntaxhighlight lang="jq">
# Generate a stream of solutions.
# Input should be the connections array, i.e. an array of [i,j] pairs;
# N is the number of pegs and holds.
Line 2,177 ⟶ 2,664:
def ok(connections):
. as $p
|
. as $connections | permutations(N) | select(ok($connections));
</syntaxhighlight>
'''Part 3: The 8-peg no-connection puzzle'''
<syntaxhighlight lang="jq">
# The connectedness matrix
# In this table, 0 represents "A", etc, and an entry [i,j]
# signifies that the holes with indices i and j are connected.
Line 2,214 ⟶ 2,703:
| $letters
| reduce range(0;length) as $i ($board; index($letters[$i]) as $ix | .[$ix] = $in[$i] + 48)
| implode;</
'''Examples''':
<
# solve | pp
# To count the number of solutions:
# count(solve)
# => 16
limit(1; solve) | pp
</syntaxhighlight>
{{output}}
Invocation: jq -n -r -f no_connection.jq
<pre>
5 6
/|\ /|\
Line 2,240 ⟶ 2,725:
\ | X | /
\|/ \|/
3 4
</pre>
=={{header|Julia}}==
<
using Combinatorics
Line 2,283 ⟶ 2,769:
printsolutions()
</
Found 16 solutions.
3 4
Line 2,298 ⟶ 2,784:
=={{header|Kotlin}}==
{{trans|Go}}
<
import kotlin.math.abs
Line 2,381 ⟶ 2,867:
println(pegsAsString(p))
println("Tested $tests positions and did $swaps swaps.")
}</
{{out}}
Line 2,402 ⟶ 2,888:
Press space bar to see solutions so far.
<syntaxhighlight lang="m2000 interpreter">
Module no_connection_puzzle {
\\ Holes
Line 2,495 ⟶ 2,981:
no_connection_puzzle
</syntaxhighlight>
{{out}}
<pre>
Line 2,509 ⟶ 2,995:
</pre >
=={{header|
{{trans|Fortran}}
Unlike the Fortran from which it was migrated, this m4 program stops at the first solution. The holes are represented by positions in a string; you can regard the string as a variable-size array. (m4 is, of course, a string-manipulation language.)
The program ought to work with any POSIX-compliant m4. The display has been changed to use only ASCII characters, because very old m4 cannot handle UTF-8.
<syntaxhighlight lang="m4">divert(-1)
define(`abs',`eval(((( $1 ) < 0) * (-( $1 ))) + ((0 <= ( $1 )) * ( $1 )))')
define(`display_solution',
` substr($1,0,1) substr($1,1,1)
/|\ /|\
/ | X | \
/ |/ \| \
substr($1,2,1)`---'substr($1,3,1)`---'substr($1,4,1)`---'substr($1,5,1)
\ |\ /| /
\ | X | /
\|/ \|/
substr($1,6,1) substr($1,7,1)')
define(`satisfies_constraints',
`eval(satisfies_no_duplicates_constraint($1) && satisfies_difference_constraints($1))')
define(`satisfies_no_duplicates_constraint',
`eval(index(all_but_last($1),last($1)) == -1)')
define(`satisfies_difference_constraints',
`pushdef(`A',ifelse(eval(1 <= len($1)),1,substr($1,0,1),100))`'dnl
pushdef(`B',ifelse(eval(2 <= len($1)),1,substr($1,1,1),200))`'dnl
pushdef(`C',ifelse(eval(3 <= len($1)),1,substr($1,2,1),300))`'dnl
pushdef(`D',ifelse(eval(4 <= len($1)),1,substr($1,3,1),400))`'dnl
pushdef(`E',ifelse(eval(5 <= len($1)),1,substr($1,4,1),500))`'dnl
pushdef(`F',ifelse(eval(6 <= len($1)),1,substr($1,5,1),600))`'dnl
pushdef(`G',ifelse(eval(7 <= len($1)),1,substr($1,6,1),700))`'dnl
pushdef(`H',ifelse(eval(8 <= len($1)),1,substr($1,7,1),800))`'dnl
eval(1 < abs((A) - (C)) &&
1 < abs((A) - (D)) &&
1 < abs((A) - (E)) &&
1 < abs((C) - (G)) &&
1 < abs((D) - (G)) &&
1 < abs((E) - (G)) &&
1 < abs((B) - (D)) &&
1 < abs((B) - (E)) &&
1 < abs((B) - (F)) &&
1 < abs((D) - (H)) &&
1 < abs((E) - (H)) &&
1 < abs((F) - (H)) &&
1 < abs((C) - (D)) &&
1 < abs((D) - (E)) &&
1 < abs((E) - (F)))'`dnl
popdef(`A',`B',`C',`D',`E',`F',`G',`H')')
define(`all_but_last',`substr($1,0,decr(len($1)))')
define(`last',`substr($1,decr(len($1)))')
define(`last_is_eight',`eval((last($1)) == 8)')
define(`strip_eights',`ifelse(last_is_eight($1),1,`$0(all_but_last($1))',`$1')')
define(`incr_last',`all_but_last($1)`'incr(last($1))')
define(`solve_puzzle',`_$0(1)')
define(`_solve_puzzle',
`ifelse(eval(len($1) == 8 && satisfies_constraints($1)),1,`display_solution($1)',
satisfies_constraints($1),1,`$0($1`'1)',
last_is_eight($1),1,`$0(incr_last(strip_eights($1)))',
`$0(incr_last($1))')')
divert`'dnl
dnl
solve_puzzle</syntaxhighlight>
{{out}}
<pre> 3 4
/|\ /|\
/ | X | \
/ |/ \| \
7---1---8---2
\ |\ /| /
\ | X | /
\|/ \|/
5 6</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
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]] &,
Line 2,521 ⟶ 3,091:
" `` ``\n /|\\ /|\\\n / | X | \\\n / |/ \\| \\\n`` - `` \
- `` - ``\n \\ |\\ /| /\n \\ | X | /\n \\|/ \\|/\n `` ``",
Sequence @@ sol]];</
{{out}}
<pre> 3 4
Line 2,532 ⟶ 3,102:
\|/ \|/
5 6</pre>
=={{header|Nim}}==
{{trans|C++}}
I choose to use one-based indexing for the array of pegs. It seems more logical here and Nim allows to choose any starting index for static arrays.
<syntaxhighlight lang="nim">import strformat
const Connections = [(1, 3), (1, 4), (1, 5), # A to C, D, E
(2, 4), (2, 5), (2, 6), # B to D, E, F
(7, 3), (7, 4), (7, 5), # G to C, D, E
(8, 4), (8, 5), (8, 6), # H to D, E, F
(3, 4), (4, 5), (5, 6)] # C-D, D-E, E-F
type
Peg = 1..8
Pegs = array[1..8, Peg]
func valid(pegs: Pegs): bool =
for (src, dst) in Connections:
if abs(pegs[src] - pegs[dst]) == 1:
return false
result = true
proc print(pegs: Pegs; num: Positive) =
echo &"----- {num} -----"
echo &" {pegs[1]} {pegs[2]}"
echo &"{pegs[3]} {pegs[4]} {pegs[5]} {pegs[6]}"
echo &" {pegs[7]} {pegs[8]}"
echo()
proc findSolution(pegs: var Pegs; left, right: Natural; solCount = 0): Natural =
var solCount = solCount
if left == right:
if pegs.valid():
inc solCount
pegs.print(solCount)
else:
for i in left..right:
swap pegs[left], pegs[i]
solCount = pegs.findSolution(left + 1, right, solCount)
swap pegs[left], pegs[i]
result = solCount
when isMainModule:
var pegs = [Peg 1, 2, 3, 4, 5, 6, 7, 8]
discard pegs.findSolution(1, 8)</syntaxhighlight>
{{out}}
<pre>----- 1 -----
3 4
7 1 8 2
5 6
----- 2 -----
3 5
7 1 8 2
4 6
----- 3 -----
3 6
7 1 8 2
4 5
----- 4 -----
3 6
7 1 8 2
5 4
----- 5 -----
4 3
2 8 1 7
6 5
----- 6 -----
4 5
2 8 1 7
6 3
----- 7 -----
4 5
7 1 8 2
3 6
----- 8 -----
4 6
7 1 8 2
3 5
----- 9 -----
5 3
2 8 1 7
6 4
----- 10 -----
5 4
2 8 1 7
6 3
----- 11 -----
5 4
7 1 8 2
3 6
----- 12 -----
5 6
7 1 8 2
3 4
----- 13 -----
6 3
2 8 1 7
5 4
----- 14 -----
6 3
2 8 1 7
4 5
----- 15 -----
6 4
2 8 1 7
5 3
----- 16 -----
6 5
2 8 1 7
4 3</pre>
=={{header|Perl}}==
<
use strict;
Line 2,561 ⟶ 3,263:
exit;
}
}</
{{out}}
<pre>
Line 2,572 ⟶ 3,274:
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.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">txt</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
\ |\
\ |
G H
"""</span>
<span style="color: #000080;font-style:italic;">--constant links = "CA DA DB DC EA EB ED FB FE GC GD GE HD HE HF"</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">links</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"A"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"ABC"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"ABD"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"BE"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"CDE"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"DEF"</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">part</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">res</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">v</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">links</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'@'</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">v</span><span style="color: #0000FF;">-</span><span style="color: #000000;">part</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">])<</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">v</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">part</span><span style="color: #0000FF;">&</span><span style="color: #000000;">v</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]&</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$],</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">part</span><span style="color: #0000FF;">&</span><span style="color: #000000;">v</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">res</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">substitute_all</span><span style="color: #0000FF;">(</span><span style="color: #000000;">txt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"ABCDEFGH"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"12345678"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)))</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,619 ⟶ 3,324:
=={{header|Picat}}==
<
no_connection_puzzle(X) =>
Line 2,658 ⟶ 3,363:
" %d %d \n",
A,B,C,D,E,F,G,H),
println(Solution).</syntaxhighlight>
{{out}}
<pre>
Picat> no_connection_puzzle(_X)
Line 2,680 ⟶ 3,385:
We first compute a list of nodes, with sort this list, and we attribute a value at the nodes.
<
edge(a, c).
Line 2,735 ⟶ 3,440:
set_constraint(H, T1, V, VT).
</syntaxhighlight>
Output :
<pre> ?- no_connection_puzzle(Vs).
Line 2,748 ⟶ 3,453:
=={{header|Python}}==
A brute force search solution.
<
from itertools import permutations
from enum import Enum
Line 2,774 ⟶ 3,479:
if __name__ == '__main__':
solutions = solve()
print("A, B, C, D, E, F, G, H =", ', '.join(str(i) for i in solutions[0]))</
{{out}}
Line 2,783 ⟶ 3,488:
Add the following code after that above:
<
"""Prettyprint a solution"""
boardformat = r"""
Line 2,803 ⟶ 3,508:
for i, s in enumerate(solutions, 1):
print("\nSolution", i, end='')
pp(s)</
;Extra output:
Line 2,984 ⟶ 3,689:
=={{header|Racket}}==
<
;; Solve the no connection puzzle. Tim Brown Oct. 2014
Line 3,026 ⟶ 3,731:
"~a") pzl))
(render-puzzle (find-good-network '(1 2 3 4 5 6 7 8)))</
{{out}}
Line 3,051 ⟶ 3,756:
The idiosyncratic adjacency diagram is dealt with by the simple expedient of bending the two vertical lines <tt>||</tt> into two bows <tt>)(</tt>, such that adjacency can be calculated simply as a distance of 2 or less.
<syntaxhighlight lang="raku"
take [$y,$x] if abs($x|$y) > 2;
} for flat -5 .. 5 X -5 .. 5;
Line 3,145 ⟶ 3,850:
say "$tries tries";
}</
{{out}}
Line 3,157 ⟶ 3,862:
=={{header|Red}}==
===Basic version===
<
points: [a b c d e f g h]
Line 3,191 ⟶ 3,896:
; start with and empty list
check []
</syntaxhighlight>
{{out}}
Line 3,199 ⟶ 3,904:
===With graphics===
<
points: [a b c d e f g h]
Line 3,246 ⟶ 3,951:
; start with and empty list
check []
</syntaxhighlight>
{{out}}
Line 3,253 ⟶ 3,958:
=={{header|REXX}}==
===unannotated solutions===
<
parse arg limit . /*number of solutions wanted.*/ /* ╔═══════════════════════════╗ */
if limit=='' | limit=="," then limit= 1 /* ║ A B ║ */
Line 3,309 ⟶ 4,014:
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.*/</
{{out|output|text= when using the default input:}}
<pre>
Line 3,340 ⟶ 4,045:
===annotated solutions===
Usage note: if the '''limit''' (the 1<sup>st</sup> argument) is negative, a diagram (node graph) is shown.
<
@abc= 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
parse arg limit . /*number of solutions wanted.*/ /* ╔═══════════════════════════╗ */
Line 3,417 ⟶ 4,122:
end /*box*/
say _ 'a='a _ "b="||b _ 'c='c _ "d="d _ ' e='e _ "f="f _ 'g='g _ "h="h
return</
{{out|output|text= when using the default inputs of: <tt> -1 </tt>}}
<pre>
Line 3,465 ⟶ 4,170:
=={{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
#
Line 3,490 ⟶ 4,195:
g.board[H[0]][H[1]].adj = [A,B,C,G]
g.solve
</syntaxhighlight>
{{out}}
<pre>
Line 3,507 ⟶ 4,212:
{{libheader|Scala sub-repositories}}
{{Out}}Best seen in running your browser either by [https://scalafiddle.io/sf/Ub2LEup/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/ZXGSJLFEQe21Frh4Vwp0WA Scastie (remote JVM)].
<
private def links = Seq(
Line 3,530 ⟶ 4,235:
printResult(genRandom.dropWhile(!notSolved(links, _)).head)
}</
=={{header|Tcl}}==
{{tcllib|struct::list}}
<
package require struct::list
Line 3,578 ⟶ 4,283:
break
}
}</
{{out}}
<pre> 3 4
Line 3,589 ⟶ 4,294:
\|/ \|/
5 6</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-dynamic}}
<syntaxhighlight lang="wren">import "./dynamic" for Tuple
var Solution = Tuple.create("Solution", ["p", "tests", "swaps"])
// Holes A=0, B=1, …, H=7
// With connections:
var conn = "
A B
/|\\ /|\\
/ | X | \\
/ |/ \\| \\
C - D - E - F
\\ |\\ /| /
\\ | X | /
\\|/ \\|/
G H
"
var 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
]
// 'isValid' 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.
var isValid = Fn.new { |pegs|
for (c in connections) {
if ((pegs[c[0]] - pegs[c[1]]).abs <= 1) return false
}
return true
}
var swap = Fn.new { |pegs, i, j|
var tmp = pegs[i]
pegs[i] = pegs[j]
pegs[j] = tmp
}
// 'solve' 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.
var solve
solve = Fn.new {
var pegs = List.filled(8, 0)
for (i in 0..7) pegs[i] = i + 1
var tests = 0
var swaps = 0
var recurse // recursive closure
recurse = Fn.new { |i|
if (i >= pegs.count - 1) {
tests = tests + 1
return isValid.call(pegs)
}
// Try each remaining peg from pegs[i] onwards
for (j in i...pegs.count) {
swaps = swaps + 1
swap.call(pegs, i, j)
if (recurse.call(i + 1)) return true
swap.call(pegs, i, j)
}
return false
}
recurse.call(0)
return Solution.new(pegs, tests, swaps)
}
var pegsAsString = Fn.new { |pegs|
var ca = conn.toList
var i = 0
for (c in ca) {
if ("ABCDEFGH".contains(c)) ca[i] = String.fromByte(48 + pegs[c.bytes[0] - 65])
i = i + 1
}
return ca.join()
}
var s = solve.call()
System.print(pegsAsString.call(s.p))
System.print("Tested %(s.tests) positions and did %(s.swaps) swaps.")</syntaxhighlight>
{{out}}
<pre>
3 4
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
5 6
Tested 12094 positions and did 20782 swaps.
</pre>
=={{header|XPL0}}==
<
int Hole, Max, I;
Line 3,627 ⟶ 4,437:
until Hole = 8;
Text(0, Str);
]</
{{out}}
Line 3,644 ⟶ 4,454:
=={{header|zkl}}==
{{trans|D}}
<
connections:=T(
T(PegA, PegC), T(PegA, PegD), T(PegA, PegE),
Line 3,670 ⟶ 4,480:
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}}
|