Solve the no connection puzzle: Difference between revisions
→{{header|Quackery}}: added commentary
m (J: restate connections in connection matrix) |
(→{{header|Quackery}}: added commentary) |
||
(110 intermediate revisions by 37 users not shown) | |||
Line 1:
You are given a box with eight holes labelled A-<small>to</small>-H, connected by fifteen straight lines in the pattern as shown below:
'''A''' '''B'''
/
/
/
'''C'''
\
\
\
'''G''' '''H'''
You are also given eight pegs numbered 1-<small>to</small>-8.
;Objective:
Place the eight pegs in the holes so that the (absolute) difference between any two numbers connected by any line is <u>greater</u> 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
[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 56 ⟶ 99:
begin
Ada.Text_IO.Put_Line( Connection_Types.Image(Result) );
end;</
<
Package Connection_Types with Pure is
Line 103 ⟶ 146:
Function Image ( Input : Partial_Board ) Return String;
End Connection_Types;</
<syntaxhighlight lang="ada">
Pragma Ada_2012;
Line 111 ⟶ 154:
Function Connection_Combinations return Partial_Board;
</syntaxhighlight>
<
Package Body Connection_Types is
Line 184 ⟶ 227:
end Image;
End Connection_Types;</
<
begin
Line 258 ⟶ 301:
End return;
End Connection_Combinations;
</syntaxhighlight>
{{out}}
<pre> 4 5
Line 269 ⟶ 312:
\|/ \|/
3 6
</pre>
=={{header|APL}}==
{{works with|Dyalog APL 17.0 Unicode}}
<syntaxhighlight lang="apl">
perms←{
⍝∇ 20100513/20140818 ra⌈ --()--
1=⍴⍴⍵:⍵[∇ ''⍴⍴⍵]
↑{0∊⍴⍵:⍵ ⋄ (⍺[1]⌷⍵),(1↓⍺)∇ ⍵~⍺[1]⌷⍵}∘(⍳⍵)¨↓⍉1+(⌽⍳⍵)⊤¯1+⍳!⍵
}
solution←{
links← (3 4 5) (4 5 6) (1 4 7) (1 2 3 5 7 8) (1 2 4 6 7 8) (2 5 8) (3 4 5) (4 5 6) ⍝ node i connects with nodes i⊃links
tries←8 perms 8
fails←{1∊{1∊⍵∊¯1 0 1}¨|⍺-¨⍺∘{⍺[⍵]}¨⍵}
⍝ ⍴⍸~tries fails ⍤1⊢links
⍝ 16
solns←⍸~tries fails ⍤1⊢links
tries[''⍴solns;]
}
</syntaxhighlight>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program noconnpuzzle.s */
/************************************/
/* Constantes */
/************************************/
.equ STDOUT, 1 @ Linux output console
.equ EXIT, 1 @ Linux syscall
.equ WRITE, 4 @ Linux syscall
.equ NBBOX, 8
.equ POSA, 5
/*********************************/
/* Initialized data */
/*********************************/
.data
sMessDeb: .ascii "a="
sMessValeur_a: .fill 11, 1, ' ' @ size => 11
.ascii "b="
sMessValeur_b: .fill 11, 1, ' ' @ size => 11
.ascii "c="
sMessValeur_c: .fill 11, 1, ' ' @ size => 11
.ascii "d="
sMessValeur_d: .fill 11, 1, ' ' @ size => 11
.ascii "\n"
.ascii "e="
sMessValeur_e: .fill 11, 1, ' ' @ size => 11
.ascii "f="
sMessValeur_f: .fill 11, 1, ' ' @ size => 11
.ascii "g="
sMessValeur_g: .fill 11, 1, ' ' @ size => 11
.ascii "h="
sMessValeur_h: .fill 11, 1, ' ' @ size => 11
szCarriageReturn: .asciz "\n************************\n"
szMessLine1: .asciz " \n"
szMessLine2: .asciz " /|\\ /|\\ \n"
szMessLine3: .asciz " / | X | \\ \n"
szMessLine4: .asciz " / |/ \\| \\ \n"
szMessLine5: .asciz " - - | - \n"
szMessLine6: .asciz " \\ |\\ /| / \n"
szMessLine7: .asciz " \\ | X | / \n"
szMessLine8: .asciz " \\|/ \\|/ \n"
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
.align 4
iValues_a: .skip 4 * NBBOX
iValues_b: .skip 4 * NBBOX - 1
iValues_c: .skip 4 * NBBOX - 2
iValues_d: .skip 4 * NBBOX - 3
iValues_e: .skip 4 * NBBOX - 4
iValues_f: .skip 4 * NBBOX - 5
iValues_g: .skip 4 * NBBOX - 6
iValues_h: .skip 4 * NBBOX - 7
sConvValue: .skip 12
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
mov r0,#1
mov r1,#8
bl searchPb
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrszCarriageReturn: .int szCarriageReturn
/******************************************************************/
/* search problem unique solution */
/******************************************************************/
/* r0 contains start digit */
/* r1 contains end digit */
searchPb:
push {r0-r12,lr} @ save registers
@ init
ldr r3,iAdriValues_a @ area value a
mov r4,#0
1: @ loop init value a
str r0,[r3,r4,lsl #2]
add r4,#1
add r0,#1
cmp r0,r1
ble 1b
mov r12,#-1
2:
add r12,#1 @ increment indice a
cmp r12,#NBBOX-1
bgt 90f
ldr r0,iAdriValues_a @ area value a
ldr r1,iAdriValues_b @ area value b
mov r2,r12 @ indice a
mov r3,#NBBOX @ number of origin values
bl prepValues
mov r11,#-1
3:
add r11,#1 @ increment indice b
cmp r11,#NBBOX - 2
bgt 2b
ldr r0,iAdriValues_b @ area value b
ldr r1,iAdriValues_c @ area value c
mov r2,r11 @ indice b
mov r3,#NBBOX -1 @ number of origin values
bl prepValues
mov r10,#-1
4:
add r10,#1
cmp r10,#NBBOX - 3
bgt 3b
ldr r0,iAdriValues_a
ldr r0,[r0,r12,lsl #2]
ldr r1,iAdriValues_c
ldr r1,[r1,r10,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 4b
ldr r0,iAdriValues_c
ldr r1,iAdriValues_d
mov r2,r10
mov r3,#NBBOX - 2
bl prepValues
mov r9,#-1
5:
add r9,#1
cmp r9,#NBBOX - 4
bgt 4b
@ control d / a b c
ldr r0,iAdriValues_d
ldr r0,[r0,r9,lsl #2]
ldr r1,iAdriValues_a
ldr r1,[r1,r12,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 5b
ldr r1,iAdriValues_b
ldr r1,[r1,r11,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 5b
ldr r1,iAdriValues_c
ldr r1,[r1,r10,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 5b
ldr r0,iAdriValues_d
ldr r1,iAdriValues_e
mov r2,r9
mov r3,#NBBOX - 3
bl prepValues
mov r8,#-1
6:
add r8,#1
cmp r8,#NBBOX - 5
bgt 5b
@ control e / a b d
ldr r0,iAdriValues_e
ldr r0,[r0,r8,lsl #2]
ldr r1,iAdriValues_a
ldr r1,[r1,r12,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 6b
ldr r1,iAdriValues_b
ldr r1,[r1,r11,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 6b
ldr r1,iAdriValues_d
ldr r1,[r1,r9,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 6b
ldr r0,iAdriValues_e
ldr r1,iAdriValues_f
mov r2,r8
mov r3,#NBBOX - 4
bl prepValues
mov r7,#-1
7:
add r7,#1
cmp r7,#NBBOX - 6
bgt 6b
@ control f / b e
ldr r0,iAdriValues_f
ldr r0,[r0,r7,lsl #2]
ldr r1,iAdriValues_b
ldr r1,[r1,r11,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 7b
ldr r1,iAdriValues_e
ldr r1,[r1,r8,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 7b
ldr r0,iAdriValues_f
ldr r1,iAdriValues_g
mov r2,r7
mov r3,#NBBOX - 5
bl prepValues
mov r6,#-1
8:
add r6,#1
cmp r6,#NBBOX - 7
bgt 7b
@ control g / c d e
ldr r0,iAdriValues_g
ldr r0,[r0,r6,lsl #2]
ldr r1,iAdriValues_c
ldr r1,[r1,r10,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 8b
ldr r1,iAdriValues_d
ldr r1,[r1,r9,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 8b
ldr r1,iAdriValues_e
ldr r1,[r1,r8,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 8b
ldr r0,iAdriValues_g
ldr r1,iAdriValues_h
mov r2,r6
mov r3,#NBBOX - 6
bl prepValues
mov r5,#-1
9:
add r5,#1
cmp r5,#NBBOX - 8
bgt 8b
@ control h / d e f
ldr r0,iAdriValues_h
ldr r0,[r0,r5,lsl #2]
ldr r1,iAdriValues_d
ldr r1,[r1,r9,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 9b
ldr r1,iAdriValues_e
ldr r1,[r1,r8,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 9b
ldr r1,iAdriValues_f
ldr r1,[r1,r7,lsl #2]
subs r2,r1,r0
mvnlt r2,r2
addlt r2,#1
cmp r2,#1
beq 9b
@ solution ok display text
ldr r0,iAdriValues_a
ldr r0,[r0,r12,lsl #2]
ldr r1,iAdrsMessValeur_a
bl conversion10
ldr r0,iAdriValues_b
ldr r0,[r0,r11,lsl #2]
ldr r1,iAdrsMessValeur_b
bl conversion10
ldr r0,iAdriValues_c
ldr r0,[r0,r10,lsl #2]
ldr r1,iAdrsMessValeur_c
bl conversion10
ldr r0,iAdriValues_d
ldr r0,[r0,r9,lsl #2]
ldr r1,iAdrsMessValeur_d
bl conversion10
ldr r0,iAdriValues_e
ldr r0,[r0,r8,lsl #2]
ldr r1,iAdrsMessValeur_e
bl conversion10
ldr r0,iAdriValues_f
ldr r0,[r0,r7,lsl #2]
ldr r1,iAdrsMessValeur_f
bl conversion10
ldr r0,iAdriValues_g
ldr r0,[r0,r6,lsl #2]
ldr r1,iAdrsMessValeur_g
bl conversion10
ldr r0,iAdriValues_h
ldr r0,[r0,r5,lsl #2]
ldr r1,iAdrsMessValeur_h
bl conversion10
ldr r0,iAdrsMessDeb
bl affichageMess
@ display design
ldr r0,iAdriValues_a
ldr r0,[r0,r12,lsl #2]
ldr r1,iAdrsConvValue
bl conversion10
ldrb r2,[r1]
ldr r0,iAdrszMessLine1
strb r2,[r0,#POSA]
ldr r0,iAdriValues_b
ldr r0,[r0,r11,lsl #2]
ldr r1,iAdrsConvValue
bl conversion10
ldrb r2,[r1]
ldr r0,iAdrszMessLine1
strb r2,[r0,#POSA+4]
bl affichageMess
ldr r0,iAdrszMessLine2
bl affichageMess
ldr r0,iAdrszMessLine3
bl affichageMess
ldr r0,iAdrszMessLine4
bl affichageMess
ldr r0,iAdriValues_c
ldr r0,[r0,r10,lsl #2]
ldr r1,iAdrsConvValue
bl conversion10
ldrb r2,[r1]
ldr r0,iAdrszMessLine5
strb r2,[r0,#POSA-4]
ldr r0,iAdriValues_d
ldr r0,[r0,r9,lsl #2]
ldr r1,iAdrsConvValue
bl conversion10
ldrb r2,[r1]
ldr r0,iAdrszMessLine5
strb r2,[r0,#POSA]
ldr r0,iAdriValues_e
ldr r0,[r0,r8,lsl #2]
ldr r1,iAdrsConvValue
bl conversion10
ldrb r2,[r1]
ldr r0,iAdrszMessLine5
strb r2,[r0,#POSA+4]
ldr r0,iAdriValues_f
ldr r0,[r0,r7,lsl #2]
ldr r1,iAdrsConvValue
bl conversion10
ldrb r2,[r1]
ldr r0,iAdrszMessLine5
strb r2,[r0,#POSA+8]
bl affichageMess
ldr r0,iAdrszMessLine6
bl affichageMess
ldr r0,iAdrszMessLine7
bl affichageMess
ldr r0,iAdrszMessLine8
bl affichageMess
ldr r0,iAdriValues_g
ldr r0,[r0,r6,lsl #2]
ldr r1,iAdrsConvValue
bl conversion10
ldrb r2,[r1]
ldr r0,iAdrszMessLine1
strb r2,[r0,#POSA]
ldr r0,iAdriValues_h
ldr r0,[r0,r5,lsl #2]
ldr r1,iAdrsConvValue
bl conversion10
ldrb r2,[r1]
ldr r0,iAdrszMessLine1
strb r2,[r0,#POSA+4]
bl affichageMess
//b 9b @ loop for other solution
90:
100:
pop {r0-r12,lr} @ restaur registers
bx lr @return
iAdriValues_a: .int iValues_a
iAdriValues_b: .int iValues_b
iAdriValues_c: .int iValues_c
iAdriValues_d: .int iValues_d
iAdriValues_e: .int iValues_e
iAdriValues_f: .int iValues_f
iAdriValues_g: .int iValues_g
iAdriValues_h: .int iValues_h
iAdrsMessValeur_a: .int sMessValeur_a
iAdrsMessValeur_b: .int sMessValeur_b
iAdrsMessValeur_c: .int sMessValeur_c
iAdrsMessValeur_d: .int sMessValeur_d
iAdrsMessValeur_e: .int sMessValeur_e
iAdrsMessValeur_f: .int sMessValeur_f
iAdrsMessValeur_g: .int sMessValeur_g
iAdrsMessValeur_h: .int sMessValeur_h
iAdrsMessDeb: .int sMessDeb
iAdrsConvValue: .int sConvValue
iAdrszMessLine1: .int szMessLine1
iAdrszMessLine2: .int szMessLine2
iAdrszMessLine3: .int szMessLine3
iAdrszMessLine4: .int szMessLine4
iAdrszMessLine5: .int szMessLine5
iAdrszMessLine6: .int szMessLine6
iAdrszMessLine7: .int szMessLine7
iAdrszMessLine8: .int szMessLine8
/******************************************************************/
/* copy value area and substract value of indice */
/******************************************************************/
/* r0 contains the address of values origin */
/* r1 contains the address of values destination */
/* r2 contains value indice to substract */
/* r3 contains origin values number */
prepValues:
push {r1-r6,lr} @ save registres
mov r4,#0 @ indice origin value
mov r5,#0 @ indice destination value
1:
cmp r4,r2 @ substract indice ?
beq 2f @ yes -> jump
ldr r6,[r0,r4,lsl #2] @ no -> copy value
str r6,[r1,r5,lsl #2]
add r5,#1 @ increment destination indice
2:
add r4,#1 @ increment origin indice
cmp r4,r3 @ end ?
blt 1b
100:
pop {r1-r6,lr} @ restaur registres
bx lr @return
/******************************************************************/
/* display text with size calculation */
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
push {r0,r1,r2,r7,lr} @ save registres
mov r2,#0 @ counter length
1: @ loop length calculation
ldrb r1,[r0,r2] @ read octet start position + index
cmp r1,#0 @ if 0 its over
addne r2,r2,#1 @ else add 1 in the length
bne 1b @ and loop
@ so here r2 contains the length of the message
mov r1,r0 @ address message in r1
mov r0,#STDOUT @ code to write to the standard output Linux
mov r7, #WRITE @ code call system "write"
svc #0 @ call systeme
pop {r0,r1,r2,r7,lr} @ restaur des 2 registres */
bx lr @ return
/******************************************************************/
/* Converting a register to a decimal unsigned */
/******************************************************************/
/* r0 contains value and r1 address area */
/* r0 return size of result (no zero final in area) */
/* area size => 11 bytes */
.equ LGZONECAL, 10
conversion10:
push {r1-r4,lr} @ save registers
mov r3,r1
mov r2,#LGZONECAL
1: @ start loop
bl divisionpar10U @ unsigned r0 <- dividende. quotient ->r0 reste -> r1
add r1,#48 @ digit
strb r1,[r3,r2] @ store digit on area
cmp r0,#0 @ stop if quotient = 0
subne r2,#1 @ else previous position
bne 1b @ and loop
@ and move digit from left of area
mov r4,#0
2:
ldrb r1,[r3,r2]
strb r1,[r3,r4]
add r2,#1
add r4,#1
cmp r2,#LGZONECAL
ble 2b
@ and move spaces in end on area
mov r0,r4 @ result length
mov r1,#' ' @ space
3:
strb r1,[r3,r4] @ store space in area
add r4,#1 @ next position
cmp r4,#LGZONECAL
ble 3b @ loop if r4 <= area size
100:
pop {r1-r4,lr} @ restaur registres
bx lr @return
/***************************************************/
/* division par 10 unsigned */
/***************************************************/
/* r0 dividende */
/* r0 quotient */
/* r1 remainder */
divisionpar10U:
push {r2,r3,r4, lr}
mov r4,r0 @ save value
ldr r3,iMagicNumber @ r3 <- magic_number raspberry 1 2
umull r1, r2, r3, r0 @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0)
mov r0, r2, LSR #3 @ r2 <- r2 >> shift 3
add r2,r0,r0, lsl #2 @ r2 <- r0 * 5
sub r1,r4,r2, lsl #1 @ r1 <- r4 - (r2 * 2) = r4 - (r0 * 10)
pop {r2,r3,r4,lr}
bx lr @ leave function
iMagicNumber: .int 0xCCCCCCCD
</syntaxhighlight>
<pre>
a=3 b=4 c=7 d=1
e=8 f=2 g=5 h=6
************************
3 4
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
5 6
</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">oGrid := [[ "", "X", "X"] ; setup oGrid
,[ "X", "X", "X", "X"]
,[ "", "X", "X"]]
oNeighbor := [], oCell := [], oRoute := [] , oVisited := [] ; initialize objects
for row, oRow in oGrid
for col, val in oRow
if val ; for each valid cell in oGrid
oNeighbor[row, col] := Neighbors(row, col, oGrid) ; list valid no-connection neighbors
Solve:
for row, oRow in oGrid
for col , val in oRow
if val ; for each valid cell in oGrid
if (oSolution := SolveNoConnect(row, col, 1)).8 ; solve for this cell
break, Solve ; if solution found stop
; show solution
for i , val in oSolution
oCell[StrSplit(val, ":").1 , StrSplit(val, ":").2] := i
A := oCell[1, 2] , B := oCell[1, 3]
C := oCell[2, 1], D := oCell[2, 2] , E := oCell[2, 3], F := oCell[2, 4]
G := oCell[3, 2] , H := oCell[3, 3]
sol =
(
%A% %B%
/|\ /|\
/ | X | \
/ |/ \| \
%C% - %D% - %E% - %F%
\ |\ /| /
\ | X | /
\|/ \|/
%G% %H%
)
MsgBox % sol
return
;-----------------------------------------------------------------------
SolveNoConnect(row, col, val){
global
oRoute.push(row ":" col) ; save route
oVisited[row, col] := true ; mark this cell visited
if oRoute[8] ; if solution found
return true ; end recursion
for each, nn in StrSplit(oNeighbor[row, col], ",") ; for each no-connection neighbor of cell
{
rowX := StrSplit(nn, ":").1 , colX := StrSplit(nn, ":").2 ; get coords of this neighbor
if !oVisited[rowX, colX] ; if not previously visited
{
oVisited[rowX, colX] := true ; mark this cell visited
val++ ; increment
if (SolveNoConnect(rowX, colX, val)) ; recurse
return oRoute ; if solution found return route
}
}
oRoute.pop() ; Solution not found, backtrack oRoute
oVisited[row, col] := false ; Solution not found, remove mark
}
;-----------------------------------------------------------------------
Neighbors(row, col, oGrid){ ; return distant neighbors of oGrid[row,col]
for r , oRow in oGrid
for c, v in oRow
if (v="X") && (abs(row-r) > 1 || abs(col-c) > 1)
list .= r ":"c ","
if (row<>2) && oGrid[row, col]
list .= oGrid[row, col+1] ? row ":" col+1 "," : oGrid[row, col-1] ? row ":" col-1 "," : ""
return Trim(list, ",")
}</syntaxhighlight>
Outputs:<pre>
3 5
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
4 6</pre>
=={{header|C}}==
{{trans|Go}}
<syntaxhighlight lang="c">#include <stdbool.h>
#include <stdio.h>
#include <math.h>
int connections[15][2] = {
{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
};
int pegs[8];
int num = 0;
bool valid() {
int i;
for (i = 0; i < 15; i++) {
if (abs(pegs[connections[i][0]] - pegs[connections[i][1]]) == 1) {
return false;
}
}
return true;
}
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
void printSolution() {
printf("----- %d -----\n", num++);
printf(" %d %d\n", /* */ pegs[0], pegs[1]);
printf("%d %d %d %d\n", pegs[2], pegs[3], pegs[4], pegs[5]);
printf(" %d %d\n", /* */ pegs[6], pegs[7]);
printf("\n");
}
void solution(int le, int ri) {
if (le == ri) {
if (valid()) {
printSolution();
}
} else {
int i;
for (i = le; i <= ri; i++) {
swap(pegs + le, pegs + i);
solution(le + 1, ri);
swap(pegs + le, pegs + i);
}
}
}
int main() {
int i;
for (i = 0; i < 8; i++) {
pegs[i] = i + 1;
}
solution(0, 8 - 1);
return 0;
}</syntaxhighlight>
{{out}}
<pre>----- 0 -----
3 4
7 1 8 2
5 6
----- 1 -----
3 5
7 1 8 2
4 6
----- 2 -----
3 6
7 1 8 2
4 5
----- 3 -----
3 6
7 1 8 2
5 4
----- 4 -----
4 3
2 8 1 7
6 5
----- 5 -----
4 5
2 8 1 7
6 3
----- 6 -----
4 5
7 1 8 2
3 6
----- 7 -----
4 6
7 1 8 2
3 5
----- 8 -----
5 3
2 8 1 7
6 4
----- 9 -----
5 4
2 8 1 7
6 3
----- 10 -----
5 4
7 1 8 2
3 6
----- 11 -----
5 6
7 1 8 2
3 4
----- 12 -----
6 3
2 8 1 7
5 4
----- 13 -----
6 3
2 8 1 7
4 5
----- 14 -----
6 4
2 8 1 7
5 3
----- 15 -----
6 5
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}}
<syntaxhighlight lang="cpp">#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;
}</syntaxhighlight>
{{out}}
<pre>----- 0 -----
3 4
7 1 8 2
5 6
----- 1 -----
3 5
7 1 8 2
4 6
----- 2 -----
3 6
7 1 8 2
4 5
----- 3 -----
3 6
7 1 8 2
5 4
----- 4 -----
4 3
2 8 1 7
6 5
----- 5 -----
4 5
2 8 1 7
6 3
----- 6 -----
4 5
7 1 8 2
3 6
----- 7 -----
4 6
7 1 8 2
3 5
----- 8 -----
5 3
2 8 1 7
6 4
----- 9 -----
5 4
2 8 1 7
6 3
----- 10 -----
5 4
7 1 8 2
3 6
----- 11 -----
5 6
7 1 8 2
3 4
----- 12 -----
6 3
2 8 1 7
5 4
----- 13 -----
6 3
2 8 1 7
4 5
----- 14 -----
6 4
2 8 1 7
5 3
----- 15 -----
6 5
2 8 1 7
4 3</pre>
=={{header|Chapel}}==
<syntaxhighlight lang="chapel">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 ) );
}
</syntaxhighlight>
<pre>
4 5
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
3 6
</pre>
=={{header|D}}==
<
import std.stdio, std.math, std.algorithm, std.traits, std.string;
enum Peg { A, B, C, D, E, F, G, H }
immutable Peg[2][15] connections =
[[Peg.A, Peg.C], [Peg.A, Peg.D], [Peg.A, Peg.E],
Line 295 ⟶ 1,437:
G H";
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);
}</
{{out}}
<pre>
Line 317 ⟶ 1,458:
Using a simple backtracking.
{{trans|Go}}
<
// Holes A=0, B=1, ..., H=7
Line 381 ⟶ 1,522:
board.tr("ABCDEFGH", "%(%d%)".format(sol.p)).writeln;
writeln("Tested ", sol.tests, " positions and did ", sol.swaps, " swaps.");
}</
{{out}}
<pre>
Line 394 ⟶ 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]]
<syntaxhighlight lang="elixir"># It solved if connected A and B, connected G and H (according to the video).
# require HLPsolver
adjacent = for i <- -2..2, j <- -2..2, not(i in -1..1 and j in -1..1), do: {i,j}
layout = ~S"""
A - B
/|\ /|\
/ | X | \
/ |/ \| \
C - D - E - F
\ |\ /| /
\ | X | /
\|/ \|/
G - H
"""
board = """
. 0 0 .
0 1 0 0
. 0 0 .
"""
HLPsolver.solve(board, adjacent, false)
|> Enum.sort |> Enum.map(fn {_,cell} -> cell.value end)
|> 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</syntaxhighlight>
{{out}}
<pre>
4 - 6
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
3 - 5
</pre>
=={{header|Factor}}==
<syntaxhighlight lang="factor">USING: assocs interpolate io kernel math math.combinatorics
math.ranges math.parser multiline pair-rocket sequences
sequences.generalizations ;
STRING: diagram
${} ${}
/|\ /|\
/ | X | \
/ |/ \| \
${} - ${} - ${} - ${}
\ |\ /| /
\ | X | /
\|/ \|/
${} ${}
;
CONSTANT: adjacency
H{
0 => { 2 3 4 }
1 => { 3 4 5 }
2 => { 0 3 6 }
3 => { 0 1 2 4 6 7 }
4 => { 0 1 3 5 6 7 }
5 => { 1 4 7 }
6 => { 2 3 4 }
7 => { 3 4 5 }
}
: any-consecutive? ( seq n -- ? ) [ - abs 1 = ] curry any? ;
: neighbors ( elt seq i -- seq elt )
adjacency at swap nths swap ;
: solution? ( permutation-seq -- ? )
dup [ neighbors any-consecutive? ] with find-index nip not ;
: find-solution ( -- seq )
8 [1,b] [ solution? ] find-permutation ;
: display-solution ( seq -- )
[ number>string ] map 8 firstn diagram interpolate>string
print ;
: main ( -- ) find-solution display-solution ;
MAIN: main</syntaxhighlight>
{{out}}
<pre>
3 4
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | 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>
=={{header|FreeBASIC}}==
{{trans|Phix}}
<syntaxhighlight lang="vbnet">Dim As String txt = "" _
" A B" & Chr(10) & _
" /|\ /|\" & Chr(10) & _
" / | X | \" & Chr(10) & _
" / |/ \| \" & Chr(10) & _
" C - D - E - F" & Chr(10) & _
" \ |\ /| /" & Chr(10) & _
" \ | X | /" & Chr(10) & _
" \|/ \|/" & Chr(10) & _
" G H"
Dim Shared As String links(1 To 8)
links(1) = "": links(2) = "": links(3) = "A": links(4) = "ABC"
links(5) = "ABD": links(6) = "BE": links(7) = "CDE": links(8) = "DEF"
Sub ReplaceString(Byref cad As String, oldChar As String, newChar As String)
Dim As Integer posic
Do
posic = Instr(cad, oldChar)
If posic = 0 Then Exit Do
cad = Left(cad, posic - 1) & newChar & Mid(cad, posic + 1)
Loop
End Sub
Function solve(s As String, idx As Integer, part As String) As String
Dim As Integer v, p, i, j
Dim As String res
For i = 1 To Len(s)
v = Val(Mid(s, i, 1))
For j = 1 To Len(links(idx))
p = Asc(Mid(links(idx), j, 1)) - 64
If Abs(v - Val(Mid(part, p, 1))) < 2 Then v = 0: Exit For
Next j
If v <> 0 Then
If Len(s) = 1 Then Return part + Chr(48 + v)
res = solve(Left(s, i - 1) & Mid(s, i + 1), idx + 1, part & Chr(48 + v))
If Len(res) > 0 Then Return res
End If
Next i
Return ""
End Function
Dim As String result = solve("12345678", 1, "")
For i As Integer = 1 To Len(result)
ReplaceString(txt, Chr(64 + i), Mid(result, i, 1))
Next i
Print txt
Sleep</syntaxhighlight>
{{out}}
<pre>Same as Phix entry.</pre>
=={{header|Go}}==
A simple recursive brute force solution.
<
import (
Line 486 ⟶ 2,179:
}
return b - a
}</
{{out}}
<pre>
Line 502 ⟶ 2,195:
</pre>
=={{header|Groovy}}==
{{trans|Java}}
<syntaxhighlight lang="groovy">import java.util.stream.Collectors
import java.util.stream.IntStream
class NoConnection {
// adopted from Go
static int[][] links = [
[2, 3, 4], // A to C,D,E
[3, 4, 5], // B to D,E,F
[2, 4], // D to C, E
[5], // E to F
[2, 3, 4], // G to C,D,E
[3, 4, 5], // H to D,E,F
]
static int[] pegs = new int[8]
static void main(String[] args) {
List<Integer> vals = IntStream.range(1, 9)
.mapToObj({ it })
.collect(Collectors.toList())
while (true) {
Collections.shuffle(vals)
for (int i = 0; i < pegs.length; i++) {
pegs[i] = vals.get(i)
}
if (solved()) {
break
}
}
printResult()
}
static boolean solved() {
for (int i = 0; i < links.length; i++) {
for (int peg : links[i]) {
if (Math.abs(pegs[i] - peg) == 1) {
return false
}
}
}
return true
}
static void printResult() {
println(" ${pegs[0]} ${pegs[1]}")
println("${pegs[2]} ${pegs[3]} ${pegs[4]} ${pegs[5]}")
println(" ${pegs[6]} ${pegs[7]}")
}
}</syntaxhighlight>
{{out}}
<pre> 6 7
2 3 8 1
4 5</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import Data.List (permutations)
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 = " " <> s</syntaxhighlight>
{{Out}}
<pre style="font-size:80%">A = 3
B = 4
C = 7
D = 1
E = 8
F = 2
G = 5
H = 6
3 4
7 1 8 2
5 6 </pre>
=={{header|J}}==
Line 507 ⟶ 2,303:
Supporting code:
<
connections=:".;._2]0 :0
Line 513 ⟶ 2,309:
holes e.;:'D E F' NB. B
holes e.;:'A D G' NB. C
holes e.;:'A B C E
holes e.;:'A B D F
holes e.;:'B E H' NB. F
holes e.;:'C D E' NB. G
Line 539 ⟶ 2,335:
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 561 ⟶ 2,356:
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
<
3 4
/|\ /|\
Line 576 ⟶ 2,371:
5 6
</syntaxhighlight>
'''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):
<syntaxhighlight lang="j"> (#~ 1<attempt"1) pegs
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</syntaxhighlight>
The first of these looks like this:
<syntaxhighlight lang="j"> disp {. (#~ 1<attempt"1) pegs
3 - 5
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
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.
=={{header|Java}}==
The backtracking is getting tiresome, we'll try a stochastic solution for a change.<br>
{{works with|Java|8}}
<syntaxhighlight lang="java">import static java.lang.Math.abs;
import java.util.*;
import static java.util.stream.Collectors.toList;
import static java.util.stream.IntStream.range;
public class NoConnection {
// adopted from Go
static int[][] links = {
{2, 3, 4}, // A to C,D,E
{3, 4, 5}, // B to D,E,F
{2, 4}, // D to C, E
{5}, // E to F
{2, 3, 4}, // G to C,D,E
{3, 4, 5}, // H to D,E,F
};
static int[] pegs = new int[8];
public static void main(String[] args) {
List<Integer> vals = range(1, 9).mapToObj(i -> i).collect(toList());
do {
Collections.shuffle(vals);
for (int i = 0; i < pegs.length; i++)
pegs[i] = vals.get(i);
} while (!solved());
printResult();
}
static boolean solved() {
for (int i = 0; i < links.length; i++)
for (int peg : links[i])
if (abs(pegs[i] - peg) == 1)
return false;
return true;
}
static void printResult() {
System.out.printf(" %s %s%n", pegs[0], pegs[1]);
System.out.printf("%s %s %s %s%n", pegs[2], pegs[3], pegs[4], pegs[5]);
System.out.printf(" %s %s%n", pegs[6], pegs[7]);
}
}</syntaxhighlight>
(takes about 500 shuffles on average)
<pre> 4 5
2 8 1 7
6 3 </pre>
=={{header|JavaScript}}==
===ES6===
{{Trans|Haskell}}
<syntaxhighlight lang="javascript">(() => {
'use strict';
// -------------- NO CONNECTION PUZZLE ---------------
// solvedPuzzle :: () -> [Int]
const solvedPuzzle = () => {
// universe :: [[Int]]
const universe = permutations(enumFromTo(1)(8));
// isSolution :: [Int] -> Bool
const isSolution = ([a, b, c, d, e, f, g, h]) =>
all(x => abs(x) > 1)([
a - d, c - d, g - d, e - d, a - c, c - g,
g - e, e - a, b - e, d - e, h - e, f - e,
b - d, d - h, h - f, f - b
]);
return universe[
until(i => isSolution(universe[i]))(
succ
)(0)
];
}
// ---------------------- TEST -----------------------
const main = () => {
const
firstSolution = solvedPuzzle(),
[a, b, c, d, e, f, g, h] = firstSolution;
return unlines(
zipWith(
a => n => a + ' = ' + n.toString()
)(enumFromTo('A')('H'))(firstSolution)
.concat([
[],
[a, b],
[c, d, e, f],
[g, h]
].map(
xs => unwords(xs.map(show))
.padStart(5, ' ')
))
);
}
// ---------------- GENERIC FUNCTIONS ----------------
// abs :: Num -> Num
const abs =
// Absolute value of a given number - without the sign.
Math.abs;
// all :: (a -> Bool) -> [a] -> Bool
const all = p =>
// True if p(x) holds for every x in xs.
xs => [...xs].every(p);
// compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
const compose = (...fs) =>
// A function defined by the right-to-left
// composition of all the functions in fs.
fs.reduce(
(f, g) => x => f(g(x)),
x => x
);
// enumFromTo :: Enum a => a -> a -> [a]
const enumFromTo = m => n => {
const [x, y] = [m, n].map(fromEnum),
b = x + (isNaN(m) ? 0 : m - x);
return Array.from({
length: 1 + (y - x)
}, (_, i) => toEnum(m)(b + i));
};
// fromEnum :: Enum a => a -> Int
const fromEnum = x =>
typeof x !== 'string' ? (
x.constructor === Object ? (
x.value
) : parseInt(Number(x))
) : x.codePointAt(0);
// length :: [a] -> Int
const length = xs =>
// Returns Infinity over objects without finite
// length. This enables zip and zipWith to choose
// the shorter argument when one is non-finite,
// like cycle, repeat etc
'GeneratorFunction' !== xs.constructor
.constructor.name ? (
xs.length
) : Infinity;
// list :: StringOrArrayLike b => b -> [a]
const list = xs =>
// xs itself, if it is an Array,
// or an Array derived from xs.
Array.isArray(xs) ? (
xs
) : Array.from(xs || []);
// permutations :: [a] -> [[a]]
const permutations = xs => (
ys => ys.reduceRight(
(a, y) => a.flatMap(
ys => Array.from({
length: 1 + ys.length
}, (_, i) => i)
.map(n => ys.slice(0, n)
.concat(y)
.concat(ys.slice(n))
)
), [
[]
]
)
)(list(xs));
// show :: a -> String
const show = x =>
JSON.stringify(x);
// succ :: Enum a => a -> a
const succ = x =>
1 + x;
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = n =>
// The first n elements of a list,
// string of characters, or stream.
xs => 'GeneratorFunction' !== xs
.constructor.constructor.name ? (
xs.slice(0, n)
) : [].concat.apply([], Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}));
// toEnum :: a -> Int -> a
const toEnum = e =>
// The first argument is a sample of the type
// allowing the function to make the right mapping
x => ({
'number': Number,
'string': String.fromCodePoint,
'boolean': Boolean,
'object': v => e.min + v
} [typeof e])(x);
// unlines :: [String] -> String
const unlines = xs =>
// A single string formed by the intercalation
// of a list of strings with the newline character.
xs.join('\n');
// until :: (a -> Bool) -> (a -> a) -> a -> a
const until = p =>
f => x => {
let v = x;
while (!p(v)) v = f(v);
return v;
};
// unwords :: [String] -> String
const unwords = xs =>
// A space-separated string derived
// from a list of words.
xs.join(' ');
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = f =>
// Use of `take` and `length` here allows
// zipping with non-finite lists
// i.e. generators like cycle, repeat, iterate.
xs => ys => {
const n = Math.min(length(xs), length(ys));
return Infinity > n ? (
(([as, bs]) => Array.from({
length: n
}, (_, i) => f(as[i])(
bs[i]
)))([xs, ys].map(
compose(take(n), list)
))
) : zipWithGen(f)(xs)(ys);
};
return main();
})();</syntaxhighlight>
{{Out}}
<pre>A = 3
B = 4
C = 7
D = 1
E = 8
F = 2
G = 5
H = 6
3 4
7 1 8 2
5 6</pre>
=={{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 589 ⟶ 2,694:
'''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 612 ⟶ 2,707:
# 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 624 ⟶ 2,720:
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 661 ⟶ 2,759:
| $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
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
3 4
</pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">
using Combinatorics
const HOLES = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
const PEGS = [1, 2, 3, 4, 5, 6, 7, 8]
const EDGES = [('A', 'C'), ('A', 'D'), ('A', 'E'),
('B', 'D'), ('B', 'E'), ('B', 'F'),
('C', 'G'), ('C', 'D'), ('D', 'G'),
('D', 'E'), ('D', 'H'), ('E', 'F'),
('E', 'G'), ('E', 'H'), ('F', 'H')]
goodperm(p) = all(e->abs(p[e[1]-'A'+1] - p[e[2]-'A'+1]) > 1, EDGES)
goodplacements() = [p for p in permutations(PEGS) if goodperm(p)]
const BOARD = raw"""
A B
/|\ /|\
/ | X | \
/ |/ \| \
C - D - E - F
\ |\ /| /
\ | X | /
\|/ \|/
G H
"""
function printsolutions()
solutions = goodplacements()
println("Found $(length(solutions)) solutions.")
for soln in solutions
board = BOARD
for (i, n) in enumerate(soln)
board = replace(board, string('A' + i - 1) => string(n))
end
println(board); exit(1) # remove this exit for all solutions
end
end
printsolutions()
</syntaxhighlight> {{output}} <pre>
Found 16 solutions.
3 4
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
5 6
</pre>
=={{header|Kotlin}}==
{{trans|Go}}
<syntaxhighlight lang="scala">// version 1.2.0
import kotlin.math.abs
// Holes A=0, B=1, …, H=7
// With connections:
const val conn = """
A B
/|\ /|\
/ | X | \
/ |/ \| \
C - D - E - F
\ |\ /| /
\ | X | /
\|/ \|/
G H
"""
val connections = listOf(
0 to 2, 0 to 3, 0 to 4, // A to C, D, E
1 to 3, 1 to 4, 1 to 5, // B to D, E, F
6 to 2, 6 to 3, 6 to 4, // G to C, D, E
7 to 3, 7 to 4, 7 to 5, // H to D, E, F
2 to 3, 3 to 4, 4 to 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.
fun isValid(pegs: IntArray): Boolean {
for ((a, b) in connections) {
if (abs(pegs[a] - pegs[b]) <= 1) return false
}
return true
}
fun swap(pegs: IntArray, i: Int, j: Int) {
val 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.
fun solve(): Triple<IntArray, Int, Int> {
val pegs = IntArray(8) { it + 1 }
var tests = 0
var swaps = 0
fun recurse(i: Int): Boolean {
if (i >= pegs.size - 1) {
tests++
return isValid(pegs)
}
// Try each remaining peg from pegs[i] onwards
for (j in i until pegs.size) {
swaps++
swap(pegs, i, j)
if (recurse(i + 1)) return true
swap(pegs, i, j)
}
return false
}
recurse(0)
return Triple(pegs, tests, swaps)
}
fun pegsAsString(pegs: IntArray): String {
val ca = conn.toCharArray()
for ((i, c) in ca.withIndex()) {
if (c in 'A'..'H') ca[i] = '0' + pegs[c - 'A']
}
return String(ca)
}
fun main(args: Array<String>) {
val (p, tests, swaps) = solve()
println(pegsAsString(p))
println("Tested $tests positions and did $swaps swaps.")
}</syntaxhighlight>
{{out}}
<pre>
3 4
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
5 6
Tested 12094 positions and did 20782 swaps.
</pre>
=={{header|M2000 Interpreter}}==
Final Version, print all solutions (16 from 40320 permutations)
Press space bar to see solutions so far.
<syntaxhighlight lang="m2000 interpreter">
Module no_connection_puzzle {
\\ Holes
Inventory Connections="A":="CDE","B":="DEF","C":="ADG", "D":="ABCEGH"
Append Connections, "E":="ABDFGH","F":="HEB", "G":="CDE","H":="DEF"
Inventory ToDelete, Solutions
\\ eliminate double connnections
con=each(Connections)
While con {
m$=eval$(con, con^)
c$=eval$(con)
If c$="*" Then continue
For i=1 to len(C$) {
d$=mid$(c$,i,1)
r$=Filter$(Connections$(d$), m$)
If r$<>"" Then {
Return connections, d$:=r$
} else {
If m$=connections$(d$) Then {
Return connections, d$:="*" : If not exist(todelete, d$) Then Append todelete, d$
}
}
}
}
con=each(todelete)
While con {
Delete Connections, eval$(con)
}
Inventory Holes
For i=0 to 7 : Append Holes, Chr$(65+i):=i : Next i
CheckValid=lambda Holes, Connections (a$, arr) -> {
val=Array(arr, Holes(a$))
con$=Connections$(a$)
res=True
For i=1 to Len(con$) {
If Abs(Array(Arr, Holes(mid$(con$,i,1)))-val)<2 Then res=False: Exit
}
=res
}
a=(1,2,3,4,5,6,7,8)
h=(,)
solution=(,)
done=False
counter=0
Print "Wait..."
P(h, a)
sol=Each(Solutions)
While sol {
Print "Solution:";sol^+1
Disp(Eval(Solutions))
aa$=Key$
}
Sub P(h, a)
If len(a)<=1 Then process(cons(h, a)) : Exit Sub
local b=cons(a)
For i=1 to len(b) {
b=cons(cdr(b),car(b))
P(cons(h,car(b)), cdr(b))
}
End Sub
Sub Process(a)
counter++
Print counter
If keypress(32) Then {
local sol=Each(Solutions)
aa$=Key$
While sol {
Print "Solution:";sol^+1
Disp(Eval(Solutions))
aa$=Key$
}
}
hole=each(Connections)
done=True
While hole {
If not CheckValid(Eval$(hole, hole^), a) Then done=False : Exit
}
If done Then Append Solutions, Len(Solutions):=a : Print a
End Sub
Sub Disp(a)
Print format$(" {0} {1}", array(a), array(a,1))
Print " /|\ /|\"
Print " / | X | \"
Print " / |/ \| \"
Print Format$("{0} - {1} - {2} - {3}", array(a,2),array(a,3), array(a,4), array(a,5))
Print " \ |\ /| /"
Print " \ | X | /"
Print " \|/ \|/"
Print Format$(" {0} {1}", array(a,6), array(a,7))
End Sub
}
no_connection_puzzle
</syntaxhighlight>
{{out}}
<pre>
3 5
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
4 6
</pre >
=={{header|m4}}==
{{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.
<syntaxhighlight lang="mathematica">sol = Fold[
Select[#,
Function[perm, Abs[perm[[#2[[1]]]] - perm[[#2[[2]]]]] > 1]] &,
Permutations[
Range[8]], {{1, 3}, {1, 4}, {1, 5}, {2, 4}, {2, 5}, {2, 6}, {3,
4}, {3, 7}, {4, 5}, {4, 7}, {4, 8}, {5, 6}, {5, 7}, {5, 8}, {6,
8}}][[1]];
Print[StringForm[
" `` ``\n /|\\ /|\\\n / | X | \\\n / |/ \\| \\\n`` - `` \
- `` - ``\n \\ |\\ /| /\n \\ | X | /\n \\|/ \\|/\n `` ``",
Sequence @@ sol]];</syntaxhighlight>
{{out}}
<pre> 3 4
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
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}}==
<syntaxhighlight lang="perl">#!/usr/bin/perl
use strict;
use warnings;
my $gap = qr/.{3}/s;
find( <<terminator );
-AB-
CDEF
-GH-
terminator
sub find
{
my $p = shift;
$p =~ /(\d)$gap.{0,2}(\d)(??{abs $1 - $2 <= 1 ? '' : '(*F)'})/ ||
$p =~ /^.*\n.*(\d)(\d)(??{abs $1 - $2 <= 1 ? '' : '(*F)'})/ and return;
if( $p =~ /[A-H]/ )
{
find( $p =~ s/[A-H]/$_/r ) for grep $p !~ $_, 1 .. 8;
}
else
{
print $p =~ tr/-/ /r;
exit;
}
}</syntaxhighlight>
{{out}}
<pre>
34
7182
56
</pre>
=={{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.
<!--<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;">"""
A B
/|\ /|\
/ | X | \
/ |/ \| \
\ |\ /| /
\ | X | /
\|/ \|/
"""</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>
3 4
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
5 6
</pre>
=={{header|
<syntaxhighlight lang="picat">import cp.
no_connection_puzzle(X) =>
N = 8,
X = new_list(N),
X :: 1..N,
Graph =
{{1,3}, {1,4}, {1,5},
{2,4}, {2,5}, {2,6},
{3,1}, {3,4}, {3,7},
{4,1}, {4,2}, {4,3}, {4,5}, {4,7}, {4,8},
{5,1}, {5,2}, {5,4}, {5,6}, {5,7}, {5,8},
{6,2}, {6,5}, {6,8},
{7,3}, {7,4}, {7,5},
{8,4}, {8,5}, {8,6}},
all_distinct(X),
foreach(I in 1..Graph.length)
abs(X[Graph[I,1]]-X[Graph[I,2]]) #> 1
end,
% symmetry breaking
X[1] #< X[N],
solve(X),
println(X),
nl,
[A,B,C,D,E,F,G,H] = X,
Solution = to_fstring(
" %d %d \n"++
" /|\\ /|\\ \n"++
" / | X | \\ \n"++
" / |/ \\| \\ \n"++
"%d - %d - %d - %d \n"++
" \\ |\\ /| / \n"++
" \\ | X | / \n"++
" \\|/ \\|/ \n"++
" %d %d \n",
A,B,C,D,E,F,G,H),
println(Solution).</syntaxhighlight>
{{out}}
<pre>
Picat> no_connection_puzzle(_X)
[3,4,7,1,8,2,5,6]
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
5 6
</pre>
=={{header|Prolog}}==
Line 714 ⟶ 3,441:
We first compute a list of nodes, with sort this list, and we attribute a value at the nodes.
<
edge(a, c).
Line 769 ⟶ 3,496:
set_constraint(H, T1, V, VT).
</syntaxhighlight>
Output :
<pre> ?- no_connection_puzzle(Vs).
Line 782 ⟶ 3,509:
=={{header|Python}}==
A brute force search solution.
<
from itertools import permutations
from enum import Enum
Line 808 ⟶ 3,535:
if __name__ == '__main__':
solutions = solve()
print("A, B, C, D, E, F, G, H =", ', '.join(str(i) for i in solutions[0]))</
{{out}}
Line 817 ⟶ 3,544:
Add the following code after that above:
<
"""Prettyprint a solution"""
boardformat = r"""
Line 837 ⟶ 3,564:
for i, s in enumerate(solutions, 1):
print("\nSolution", i, end='')
pp(s)</
;Extra output:
Line 1,015 ⟶ 3,742:
\|/ \|/
4 3</pre>
=={{header|Quackery}}==
<code>rank->perm</code> and <code>!</code> are defined at [[Permutations/Rank of a permutation#Quackery]].
<syntaxhighlight lang="Quackery"> [ ' [ [ 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 ] ] ] is connections ( --> [ )
[ dip dup do
unrot peek dip peek - abs 1 = ] is invalid ( [ [ --> b )
[ true swap
connections witheach
[ dip dup invalid if
[ dip not conclude ] ]
drop ] is allvalid ( [ --> b )
say " A B C D E F G H" cr
8 ! times
[ i^ 8 rank->perm
allvalid if
[ sp
i^ 8 rank->perm
witheach
[ sp 1+ echo ]
cr conclude ] ]</syntaxhighlight>
{{out}}
<pre> A B C D E F G H
3 4 7 1 8 2 5 6
</pre>
As noted in the talk for this page, "According to the video, A and B, G and H are also connected".
Adding these to the list of connections (i.e. <code>[ 0 1 ] [ 6 7 ]</code>) and generating all the solutions by removing the word <code>conclude</code> from the last line of the code gives:
{{out}}
<pre> A B C D E F G H
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
</pre>
=={{header|Racket}}==
<
;; Solve the no connection puzzle. Tim Brown Oct. 2014
Line 1,060 ⟶ 3,835:
"~a") pzl))
(render-puzzle (find-good-network '(1 2 3 4 5 6 7 8)))</
{{out}}
Line 1,072 ⟶ 3,847:
\|/ \|/
5 6</pre>
=={{header|Raku}}==
(formerly Perl 6)
This uses a Warnsdorff solver, which cuts down the number of tries by more than a factor of six over the brute force approach. This same solver is used in:
* [[Solve a Hidato puzzle#Raku|Solve a Hidato puzzle]]
* [[Solve a Hopido puzzle#Raku|Solve a Hopido puzzle]]
* [[Solve a Holy Knight's tour#Raku|Solve a Holy Knight's tour]]
* [[Solve a Numbrix puzzle#Raku|Solve a Numbrix puzzle]]
* [[Solve the no connection puzzle#Raku|Solve the no connection puzzle]]
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" line>my @adjacent = gather -> $y, $x {
take [$y,$x] if abs($x|$y) > 2;
} for flat -5 .. 5 X -5 .. 5;
solveboard q:to/END/;
. _ . . _ .
. . . . . .
_ . _ 1 . _
. . . . . .
. _ . . _ .
END
sub solveboard($board) {
my $max = +$board.comb(/\w+/);
my $width = $max.chars;
my @grid;
my @known;
my @neigh;
my @degree;
@grid = $board.lines.map: -> $line {
[ $line.words.map: { /^_/ ?? 0 !! /^\./ ?? Rat !! $_ } ]
}
sub neighbors($y,$x --> List) {
eager gather for @adjacent {
my $y1 = $y + .[0];
my $x1 = $x + .[1];
take [$y1,$x1] if defined @grid[$y1][$x1];
}
}
for ^@grid -> $y {
for ^@grid[$y] -> $x {
if @grid[$y][$x] -> $v {
@known[$v] = [$y,$x];
}
if @grid[$y][$x].defined {
@neigh[$y][$x] = neighbors($y,$x);
@degree[$y][$x] = +@neigh[$y][$x];
}
}
}
print "\e[0H\e[0J";
my $tries = 0;
try_fill 1, @known[1];
sub try_fill($v, $coord [$y,$x] --> Bool) {
return True if $v > $max;
$tries++;
my $old = @grid[$y][$x];
return False if +$old and $old != $v;
return False if @known[$v] and @known[$v] !eqv $coord;
@grid[$y][$x] = $v; # conjecture grid value
print "\e[0H"; # show conjectured board
for @grid -> $r {
say do for @$r {
when Rat { ' ' x $width }
when 0 { '_' x $width }
default { .fmt("%{$width}d") }
}
}
my @neighbors = @neigh[$y][$x][];
my @degrees;
for @neighbors -> \n [$yy,$xx] {
my $d = --@degree[$yy][$xx]; # conjecture new degrees
push @degrees[$d], n; # and categorize by degree
}
for @degrees.grep(*.defined) -> @ties {
for @ties.reverse { # reverse works better for this hidato anyway
return True if try_fill $v + 1, $_;
}
}
for @neighbors -> [$yy,$xx] {
++@degree[$yy][$xx]; # undo degree conjectures
}
@grid[$y][$x] = $old; # undo grid value conjecture
return False;
}
say "$tries tries";
}</syntaxhighlight>
{{out}}
<pre> 4 3
2 8 1 7
6 5
18 tries</pre>
=={{header|Red}}==
===Basic version===
<syntaxhighlight lang="red">Red ["Solve the no connection puzzle"]
points: [a b c d e f g h]
; 'links' series will be scanned by pairs: [a c], [a d] etc.
links: [a c a d a e b d b e b f c d c g d e d g d h e f e g e h f h]
allpegs: [1 2 3 4 5 6 7 8]
; check if two points are connected (then game is lost) i.e.
; both are have a value (not zero) and absolute difference is 1
connected: func [x y] [all [
x * y <> 0
1 = absolute (x - y)
]]
; a list of points is valid if no connexion is found
isvalid: function [pegs [block!]] [
; assign pegs values to points, or 0 for remaining points
set points append/dup copy pegs 0 8
foreach [x y] links [if connected get x get y [return false]]
true
]
; recursively build a list of up to 8 valid points
check: function [pegs [block!]] [
if isvalid pegs [
rest: difference allpegs pegs
either empty? rest [
print rejoin ["Here is a solution: " pegs]
halt ; comment this line to get all solutions
][
foreach peg rest [check append copy pegs peg]
]
]
]
; start with and empty list
check []
</syntaxhighlight>
{{out}}
<pre>Here is a solution: 3 4 7 1 8 2 5 6
(halted)
</pre>
===With graphics===
<syntaxhighlight lang="red">Red [Needs: 'View]
points: [a b c d e f g h]
; 'links' series will be scanned by pairs: [a c], [a d] etc.
links: [a c a d a e b d b e b f c d c g d e d g d h e f e g e h f h]
allpegs: [1 2 3 4 5 6 7 8]
; check if two points are connected (then game is lost) i.e.
; both are have a value (not zero) and absolute difference is 1
connected: func [x y] [all [
x * y <> 0
1 = absolute (x - y)
]]
; a list of points is valid if no connexion is found
isvalid: function [pegs [block!]] [
; assign pegs values to points, or 0 for remaining points
set points append/dup copy pegs 0 8
foreach [x y] links [if connected get x get y [return false]]
true
]
; recursively build a list of up to 8 valid points
check: function [pegs [block!]] [
if isvalid pegs [
rest: difference allpegs pegs
either empty? rest [
vis points
][
foreach peg rest [check append copy pegs peg]
]
]
]
; view solution found
vis: function [points] [
pos: [100x0 200x0 0x100 100x100 200x100 300x100 100x200 200x200]
offs: 30x30
pos-of: function [x] [pick pos index? find points x]
val-at: function [p] [get pick points index? find pos p]
visu: layout [img: image 362x262 draw []]
foreach [x y] links [append img/draw reduce [
'line offs + pos-of x offs + pos-of y]]
append img/draw [fill-pen snow]
foreach p pos [append img/draw reduce [
'circle offs + p 15 'text 21x15 + p form val-at p]]
view/options visu [text: "Solution to the no-connection puzzle"]
]
; start with and empty list
check []
</syntaxhighlight>
{{out}}
[https://raw.githubusercontent.com/Palaing/redlib/master/games/images/noconnexion.png graphical output image]
=={{header|REXX}}==
===unannotated solutions===
<
parse arg limit .
if limit=='' | 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
@.7 = 'G C D E' /* ║ \│/ \│/ ║ */
@.8 = 'H D E F' /* ║ G H ║ */
cnt= 0 /* ╚═══════════════════════════╝ */
pegs=
do b=1 for pegs;
do c=1 for pegs;
do d=1 for pegs;
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 _
cnt= cnt + 1; if cnt==limit then leave a
end /*h*/
end /*g*/
end /*f*/
end /*e*/
end /*d*/
end /*c*/
end /*b*/
say /*display a blank line to
s= left('s', cnt\==1) /*handle the case of plurals (or not).*/
say 'found ' cnt " solution"s'.' /*display the number of solutions found*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
?:
nH= nn+1
do cn=c2d('A') to c2d(node)-1; if value( d2c(cn) )==nn then return
nL= nn-1
end /*ch*/ /* [↑] looking for suitable number. */
return 0 /*the subroutine arg value passed is OK.*/</syntaxhighlight>
{{out|output|text= when using the default input:}}
<pre>
a=3 b=4 c=7 d=1 e=8 f=2 g=5 h=6
Line 1,136 ⟶ 4,125:
found 1 solution.
</pre>
{{out|output|text= when using the default input of: <tt> 999 </tt>}}
<pre>
a=3 b=4 c=7 d=1 e=8 f=2 g=5 h=6
Line 1,160 ⟶ 4,148:
===annotated solutions===
Usage note: if the '''limit''' (the 1<sup>st</sup> argument) is negative, a diagram (node graph) is shown.
<syntaxhighlight lang="rexx">/*REXX program solves the "no─connection" puzzle (the puzzle has eight pegs). */
@abc= 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
parse arg limit . /*number of solutions wanted.*/ /* ╔═══════════════════════════╗ */
@.
@.
@.
@.
@.
@.
@.
@.
cnt= 0 /* ╚═══════════════════════════╝ */
do
do
__=
subs=
!._.0= subs
pegs= pegs - 1
do
do
do
do
do
do
end /*
end /*
end /*
say
say 'found ' cnt " solution"s'.' /*display the number of solutions found*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
?: parse arg node; nn= value(node)
nH= nn+1
end /*cn*/ /* [↑] see if there're any duplicates.*/
nL= nn-1
$= !.node.ch; fn= value($) /*the node name and its current peg #.*/
return 0 /*the subroutine arg value passed is OK*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
showNodes:
show= 0
do box=1 for sourceline() while oLimit<0 /*Negative? Then display the diagram. */
xw= sourceline(box) /*get a source line of this program. */
if \show
xb=
xt= xb /*get a working copy of the box. */
xt= translate(xt, value(@), @) /*substitute the peg name with a value.*/
end /*jx*/ /* [↑] graph is limited to 26 nodes.*/
say _ xb _ _ xt /*display
if pos('╝', xw)\==0 then return /*Is this last line of graph? Then stop*/
end /*box*/
say _ 'a='a _ "b="||b _ 'c='c _ "d="d _ ' e='e _ "f="f _ 'g='g _ "h="h
return</syntaxhighlight>
{{out|output|text= when using the default inputs of: <tt> -1 </tt>}}
<pre>
╔═══════════════════════════╗ ╔═══════════════════════════╗
Line 1,250 ⟶ 4,241:
║ \│/ \│/ ║ ║ \│/ \│/ ║
║ G H ║ ║ 5 6 ║
╚═══════════════════════════╝ ╚═══════════════════════════╝
╔═══════════════════════════╗ ╔═══════════════════════════╗
║ A B ║ ║ 3 5 ║
║ /│\ /│\ ║ ║ /│\ /│\ ║
║ / │ \/ │ \ ║ ║ / │ \/ │ \ ║
║ / │ /\ │ \ ║ ║ / │ /\ │ \ ║
║ / │/ \│ \ ║ ║ / │/ \│ \ ║
║ C────D────E────F ║ ║ 7────1────8────2 ║
║ \ │\ /│ / ║ ║ \ │\ /│ / ║
║ \ │ \/ │ / ║ ║ \ │ \/ │ / ║
║ \ │ /\ │ / ║ ║ \ │ /\ │ / ║
║ \│/ \│/ ║ ║ \│/ \│/ ║
║ G H ║ ║ 4 6 ║
╚═══════════════════════════╝ ╚═══════════════════════════╝
╔═══════════════════════════╗ ╔═══════════════════════════╗
║ A B ║ ║ 3 6 ║
║ /│\ /│\ ║ ║ /│\ /│\ ║
║ / │ \/ │ \ ║ ║ / │ \/ │ \ ║
║ / │ /\ │ \ ║ ║ / │ /\ │ \ ║
║ / │/ \│ \ ║ ║ / │/ \│ \ ║
║ C────D────E────F ║ ║ 7────1────8────2 ║
║ \ │\ /│ / ║ ║ \ │\ /│ / ║
║ \ │ \/ │ / ║ ║ \ │ \/ │ / ║
║ \ │ /\ │ / ║ ║ \ │ /\ │ / ║
║ \│/ \│/ ║ ║ \│/ \│/ ║
║ G H ║ ║ 4 5 ║
╚═══════════════════════════╝ ╚═══════════════════════════╝
found
</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
#
Line 1,282 ⟶ 4,299:
g.board[H[0]][H[1]].adj = [A,B,C,G]
g.solve
</syntaxhighlight>
{{out}}
<pre>
Line 1,295 ⟶ 4,312:
6 4
</pre>
=={{header|Scala}}==
{{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)].
<syntaxhighlight lang="scala">object NoConnection extends App {
private def links = Seq(
Seq(2, 3, 4), // A to C,D,E
Seq(3, 4, 5), // B to D,E,F
Seq(2, 4), // D to C, E
Seq(5), // E to F
Seq(2, 3, 4), // G to C,D,E
Seq(3, 4, 5)) // H to D,E,F
private def genRandom: LazyList[Seq[Int]] = util.Random.shuffle((1 to 8).toList) #:: genRandom
private def notSolved(links: Seq[Seq[Int]], pegs: Seq[Int]): Boolean =
links.indices.forall(
i => !links(i).forall(peg => math.abs(pegs(i) - peg) == 1))
private def printResult(pegs: Seq[Int]) = {
println(f"${pegs(0)}%3d${pegs(1)}%2d")
println(f"${pegs(2)}%1d${pegs(3)}%2d${pegs(4)}%2d${pegs(5)}%2d")
println(f"${pegs(6)}%3d${pegs(7)}%2d")
}
printResult(genRandom.dropWhile(!notSolved(links, _)).head)
}</syntaxhighlight>
=={{header|Tcl}}==
{{tcllib|struct::list}}
<
package require struct::list
Line 1,342 ⟶ 4,387:
break
}
}</
{{out}}
<pre> 3 4
/|\ /|\
/ | X | \
Line 1,353 ⟶ 4,397:
\ | X | /
\|/ \|/
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 1,393 ⟶ 4,541:
until Hole = 8;
Text(0, Str);
]</
{{out}}
Line 1,406 ⟶ 4,554:
\|/ \|/
3 4
</pre>
=={{header|Zig}}==
<syntaxhighlight lang="Zig">const std = @import("std");
const print = std.debug.print;
const PA = 0;
const PB = 1;
const PC = 2;
const PD = 3;
const PE = 4;
const PF = 5;
const PG = 6;
const PH = 7;
const Pair = struct { u8, u8 };
const Pairs = [_]Pair{ .{ PA, PC }, .{ PA, PD }, .{ PA, PE }, .{ PB, PD }, .{ PB, PE }, .{ PB, PF }, .{ PC, PG }, .{ PC, PD }, .{ PD, PE }, .{ PD, PG }, .{ PD, PH }, .{ PE, PG }, .{ PE, PH }, .{ PF, PH }, .{ PE, PF } };
var t: [8]u32 = .{0} ** 8;
inline fn abs(p: Pair) u32 {
if (t[p.@"0"] < t[p.@"1"]) return t[p.@"1"] - t[p.@"0"];
return t[p.@"0"] - t[p.@"1"];
}
fn check() bool {
var r: bool = true;
for (Pairs) |p| {
r = r and abs(p) > 1;
if (!r) break;
}
return r;
}
fn has(a: u32) bool {
for (t) |v| {
if (v == a) return true;
}
return false;
}
fn solve(lvl: u32) bool {
if (lvl == 8) return check();
for (1..9) |v| {
if (has(v)) continue;
t[lvl] = v;
if (solve(lvl + 1)) return true;
}
t[lvl] = 0;
return false;
}
pub fn main() void {
_ = solve(0);
print("{{ A, B, C, D, E, F, G, H }} = {any}", .{t});
}
</syntaxhighlight>
Output:
<pre>
{ A, B, C, D, E, F, G, H } = { 3, 4, 7, 1, 8, 2, 5, 6 }
</pre>
<syntaxhighlight lang="Zig">const std = @import("std");
const print = std.debug.print;
const PA = 0;
const PB = 1;
const PC = 2;
const PD = 3;
const PE = 4;
const PF = 5;
const PG = 6;
const PH = 7;
const Pair = struct { u8, u8 };
const Pairs = [_]Pair{ .{ PA, PC }, .{ PA, PD }, .{ PA, PE }, .{ PB, PD }, .{ PB, PE }, .{ PB, PF }, .{ PC, PG }, .{ PC, PD }, .{ PD, PE }, .{ PD, PG }, .{ PD, PH }, .{ PE, PG }, .{ PE, PH }, .{ PF, PH }, .{ PE, PF } };
var t: [8]u32 = .{0} ** 8;
inline fn abs(p: Pair) u32 {
if (t[p.@"0"] < t[p.@"1"]) return t[p.@"1"] - t[p.@"0"];
return t[p.@"0"] - t[p.@"1"];
}
fn check() bool {
var r: bool = true;
for (Pairs) |p| {
r = r and abs(p) > 1;
if (!r) break;
}
return r;
}
fn has(a: u32) bool {
for (t) |v| {
if (v == a) return true;
}
return false;
}
fn solve(lvl: u32) bool {
if (lvl == 8) return check();
for (1..9) |v| {
if (has(v)) continue;
t[lvl] = v;
if (solve(lvl + 1)) {
print("{{ A, B, C, D, E, F, G, H }} = {any}\n", .{t});
}
}
t[lvl] = 0;
return false;
}
pub fn main() void {
_ = solve(0);
}
</syntaxhighlight>
Output:
<pre>
{ A, B, C, D, E, F, G, H } = { 3, 4, 7, 1, 8, 2, 5, 6 }
{ A, B, C, D, E, F, G, H } = { 3, 5, 7, 1, 8, 2, 4, 6 }
{ A, B, C, D, E, F, G, H } = { 3, 6, 7, 1, 8, 2, 4, 5 }
{ A, B, C, D, E, F, G, H } = { 3, 6, 7, 1, 8, 2, 5, 4 }
{ A, B, C, D, E, F, G, H } = { 4, 3, 2, 8, 1, 7, 6, 5 }
{ A, B, C, D, E, F, G, H } = { 4, 5, 2, 8, 1, 7, 6, 3 }
{ A, B, C, D, E, F, G, H } = { 4, 5, 7, 1, 8, 2, 3, 6 }
{ A, B, C, D, E, F, G, H } = { 4, 6, 7, 1, 8, 2, 3, 5 }
{ A, B, C, D, E, F, G, H } = { 5, 3, 2, 8, 1, 7, 6, 4 }
{ A, B, C, D, E, F, G, H } = { 5, 4, 2, 8, 1, 7, 6, 3 }
{ A, B, C, D, E, F, G, H } = { 5, 4, 7, 1, 8, 2, 3, 6 }
{ A, B, C, D, E, F, G, H } = { 5, 6, 7, 1, 8, 2, 3, 4 }
{ A, B, C, D, E, F, G, H } = { 6, 3, 2, 8, 1, 7, 4, 5 }
{ A, B, C, D, E, F, G, H } = { 6, 3, 2, 8, 1, 7, 5, 4 }
{ A, B, C, D, E, F, G, H } = { 6, 4, 2, 8, 1, 7, 5, 3 }
{ A, B, C, D, E, F, G, H } = { 6, 5, 2, 8, 1, 7, 4, 3 }
</pre>
=={{header|zkl}}==
{{trans|D}}
<
connections:=T(
T(PegA, PegC), T(PegA, PegD), T(PegA, PegE),
Line 1,416 ⟶ 4,698:
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();
#<<< // Use "raw" string in a "here doc" so \ isn't a quote char
board:=
0'$ A B
#<<< // end "here doc"
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;
break; // comment out to see all 16 solutions
}</syntaxhighlight>
The filter1 method stops on the first True, so it acts like a conditional or.
{{out}}
|