Solve the no connection puzzle: Difference between revisions

From Rosetta Code
Content added Content deleted
(New draft task and Python solution.)
 
(Enhance ASCII art.)
Line 3: Line 3:
straight lines in the pattern as shown
straight lines in the pattern as shown



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


You are also given eight pegs numbered 1-to-8. The idea is to place the pegs in
You are also given eight pegs numbered 1-to-8. The idea is to place the pegs in
Line 19: Line 20:
For example, in this attempt:
For example, in this attempt:


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


Note that 7 and 6 are connected and have a difference of 1 so it is ''not'' a solution.
Note that 7 and 6 are connected and have a difference of 1 so it is ''not'' a solution.

Revision as of 15:29, 4 October 2014

Solve the no connection puzzle is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

Python

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

connections = ((0, 2), (0, 3), (0, 4),

              (1, 3), (1, 4), (1, 5),
              (6, 2), (6, 3), (6, 4),
              (7, 3), (7, 4), (7, 5),
              (2, 3), (3, 4), (4, 5))


def 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