Solve the no connection puzzle
You are given a box with eight holes labelled A-to-H, connected by fifteen straight lines in the pattern as shown
A B /|\ /|\ / | X | \ / |/ \| \ C - D - E - F \ |\ /| / \ | X | / \|/ \|/ G H
You are also given eight pegs numbered 1-to-8. The idea is to place the pegs in the holes so that the (absolute) difference between any two numbers connected by any line is greater than one.
For example, in this attempt:
4 7 /|\ /|\ / | X | \ / |/ \| \ 8 - 1 - 6 - 2 \ |\ /| / \ | X | / \|/ \|/ 3 5
Note that 7 and 6 are connected and have a difference of 1 so it is not a solution.
The task is to produce and show here one solution to the puzzle.
- Reference
No Connection Puzzle (Video).
Go
A simple recursive brute force solution. <lang go>package main
import ( "fmt" "strings" )
func main() { p, tests, swaps := Solution() fmt.Println(p) fmt.Println("Tested", tests, "positions and did", swaps, "swaps.") }
// Holes A=0, B=1, …, H=7 // With connections: const conn = `
A B /|\ /|\ / | X | \ / |/ \| \ C - D - E - F \ |\ /| / \ | X | / \|/ \|/ G H`
var connections = []struct{ a, b int }{ {0, 2}, {0, 3}, {0, 4}, // A to C,D,E {1, 3}, {1, 4}, {1, 5}, // B to D,E,F {6, 2}, {6, 3}, {6, 4}, // G to C,D,E {7, 3}, {7, 4}, {7, 5}, // H to D,E,F {2, 3}, {3, 4}, {4, 5}, // C-D, D-E, E-F }
type pegs [8]int
// Valid checks if the pegs are a valid solution. // If the absolute difference between any pair of connected pegs is // greater than one it is a valid solution. func (p *pegs) Valid() bool { for _, c := range connections { if absdiff(p[c.a], p[c.b]) <= 1 { return false } } return true }
// Solution is a simple recursive brute force solver, // it stops at the first found solution. // It returns the solution, the number of positions tested, // and the number of pegs swapped. func Solution() (p *pegs, tests, swaps int) { var recurse func(int) bool recurse = func(i int) bool { if i >= len(p)-1 { tests++ return p.Valid() } // Try each remain peg from p[i:] in p[i] for j := i; j < len(p); j++ { swaps++ p[i], p[j] = p[j], p[i] if recurse(i + 1) { return true } p[i], p[j] = p[j], p[i] } return false } p = &pegs{1, 2, 3, 4, 5, 6, 7, 8} recurse(0) return }
func (p *pegs) String() string { return strings.Map(func(r rune) rune { if 'A' <= r && r <= 'H' { return rune(p[r-'A'] + '0') } return r }, conn) }
func absdiff(a, b int) int { if a > b { return a - b } return b - a }</lang>
- Output:
3 4 /|\ /|\ / | X | \ / |/ \| \ 7 - 1 - 8 - 2 \ |\ /| / \ | X | / \|/ \|/ 5 6 Tested 12094 positions and did 20782 swaps.
Python
A brute force search solution. <lang python>from __future__ import print_function from itertools import permutations
connections = ((0, 2), (0, 3), (0, 4), # A-to-H become 0-to-7 respectively.
(1, 3), (1, 4), (1, 5), (6, 2), (6, 3), (6, 4), (7, 3), (7, 4), (7, 5), (2, 3), (3, 4), (4, 5))
def ok(conn, perm):
"""Connected numbers ok?""" this, that = conn return abs(perm[this] - perm[that]) != 1
def solve():
return [perm for perm in permutations(range(1, 9)) if all(ok(conn, perm) for conn in connections)]
if __name__ == '__main__':
solutions = solve() print("A, B, C, D, E, F, G, H =", ', '.join(str(i) for i in solutions[0]))</lang>
- Output:
A, B, C, D, E, F, G, H = 3, 4, 7, 1, 8, 2, 5, 6
- All solutions pretty printed
Add the following code after that above: <lang python>def pp(solution):
"""Prettyprint a solution""" boardformat = r""" A B /|\ /|\ / | X | \ / |/ \| \ C - D - E - F \ |\ /| / \ | X | / \|/ \|/ G H""" for letter, number in zip("ABCDEFGH", solution): boardformat = boardformat.replace(letter, str(number)) print(boardformat)
if __name__ == '__main__':
for i, s in enumerate(solutions, 1): print("\nSolution", i, end=) pp(s)</lang>
- Extra output
Solution 1 3 4 /|\ /|\ / | X | \ / |/ \| \ 7 - 1 - 8 - 2 \ |\ /| / \ | X | / \|/ \|/ 5 6 Solution 2 3 5 /|\ /|\ / | X | \ / |/ \| \ 7 - 1 - 8 - 2 \ |\ /| / \ | X | / \|/ \|/ 4 6 Solution 3 3 6 /|\ /|\ / | X | \ / |/ \| \ 7 - 1 - 8 - 2 \ |\ /| / \ | X | / \|/ \|/ 4 5 Solution 4 3 6 /|\ /|\ / | X | \ / |/ \| \ 7 - 1 - 8 - 2 \ |\ /| / \ | X | / \|/ \|/ 5 4 Solution 5 4 3 /|\ /|\ / | X | \ / |/ \| \ 2 - 8 - 1 - 7 \ |\ /| / \ | X | / \|/ \|/ 6 5 Solution 6 4 5 /|\ /|\ / | X | \ / |/ \| \ 2 - 8 - 1 - 7 \ |\ /| / \ | X | / \|/ \|/ 6 3 Solution 7 4 5 /|\ /|\ / | X | \ / |/ \| \ 7 - 1 - 8 - 2 \ |\ /| / \ | X | / \|/ \|/ 3 6 Solution 8 4 6 /|\ /|\ / | X | \ / |/ \| \ 7 - 1 - 8 - 2 \ |\ /| / \ | X | / \|/ \|/ 3 5 Solution 9 5 3 /|\ /|\ / | X | \ / |/ \| \ 2 - 8 - 1 - 7 \ |\ /| / \ | X | / \|/ \|/ 6 4 Solution 10 5 4 /|\ /|\ / | X | \ / |/ \| \ 2 - 8 - 1 - 7 \ |\ /| / \ | X | / \|/ \|/ 6 3 Solution 11 5 4 /|\ /|\ / | X | \ / |/ \| \ 7 - 1 - 8 - 2 \ |\ /| / \ | X | / \|/ \|/ 3 6 Solution 12 5 6 /|\ /|\ / | X | \ / |/ \| \ 7 - 1 - 8 - 2 \ |\ /| / \ | X | / \|/ \|/ 3 4 Solution 13 6 3 /|\ /|\ / | X | \ / |/ \| \ 2 - 8 - 1 - 7 \ |\ /| / \ | X | / \|/ \|/ 4 5 Solution 14 6 3 /|\ /|\ / | X | \ / |/ \| \ 2 - 8 - 1 - 7 \ |\ /| / \ | X | / \|/ \|/ 5 4 Solution 15 6 4 /|\ /|\ / | X | \ / |/ \| \ 2 - 8 - 1 - 7 \ |\ /| / \ | X | / \|/ \|/ 5 3 Solution 16 6 5 /|\ /|\ / | X | \ / |/ \| \ 2 - 8 - 1 - 7 \ |\ /| / \ | X | / \|/ \|/ 4 3
REXX
<lang rexx>/**REXX program solves the "no-connection" puzzle (with eight pegs).*/ @. = @.1 = 'A C D E' ; @.5 = 'E A B D F' @.2 = 'B D E F' ; @.6 = 'F B E G' @.3 = 'C A D G' ; @.7 = 'G C D E' @.4 = 'D A C E G' ; @.8 = 'H D E F'
do nodes=1 while @.nodes\==; _=word(@.nodes,1) subs=0 /* [↓] create list of node paths*/ do #=1 for words(@.nodes)-1 __=word(@.nodes,#+1); if __>_ then iterate subs=subs+1; !._.subs=__ end /*#*/ !._.0=subs /*assign the number of node paths*/ end /*nodes*/
pegs=nodes-1 /*number of pegs to be seated. */ _=' ' /*_ is used for padding output.*/
do a=1 for pegs; if ?('A') then iterate do b=1 for pegs; if ?('B') then iterate do c=1 for pegs; if ?('C') then iterate do d=1 for pegs; if ?('D') then iterate do e=1 for pegs; if ?('E') then iterate do f=1 for pegs; if ?('F') then iterate do g=1 for pegs; if ?('G') then iterate do h=1 for pegs; if ?('H') then iterate say 'a='a _ 'b='||b _ 'c='c _ 'd='d _ 'e='e _ 'f='f _ 'g='g _ 'h='h leave a /*◄───delete to see all solutions*/ end /*h*/ end /*g*/ end /*f*/ end /*e*/ end /*d*/ end /*c*/ end /*b*/ end /*a*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────? subroutine────────────────────────*/ ?: parse arg node; nn=value(node); nL=nn-1; nH=nn+1
do cn=c2d('A') to c2d(node)-1; if value(d2c(cn))==nn then return 1; end /* [↑] see if any are duplicates*/ do ch=1 for !.node.0 /* [↓] see if any ¬ = ±1 value*/ $=!.node.ch; fn=value($) /*node name and its current peg# */ if nL==fn | nH==fn then return 1 /*if ≡ ±1, then it can't be used.*/ end /*ch*/ /* [↑] looking for suitable num.*/
return 0 /*the sub arg value passed is OK.*/</lang> output
a=1 b=2 c=7 d=3 e=8 f=4 g=5 h=6