blog.farhan.codes

Farhan's Personal and Professional Blog


Draw this shape without picking up your pen

For many years, while in a meeting or in a moment of free time, I have tried to draw this shape without picking up my pen or drawing over the same two points twice.

At best I would get 1 line away, but never completed the shape.

I wanted to know if it was even possible. So I wrote some python code to try every possible combination.

But, the code is below.

#!/usr/bin/env python3

import copy
import sys

lines = {
        1:[2,3],
        2:[1,3,4,6,7],
        3:[1,2,5,6,7],
        4:[2,5,6,7],
        5:[3,7],
        6:[2,3,4,7,8],
        7:[2,3,5,6,8],
        8:[6,7]
    }

def check(cstate):
    for offset in lines:
        if sorted(lines[offset]) != sorted(cstate[offset]):
            return
    print("Solution!")
    sys.exit()

def iteration(clocation, cstate):

    if len(cstate) == 8:
        check(cstate)

    for ilocation in lines[clocation]:
        nstate = copy.deepcopy(cstate)
        y = nstate.get(clocation, [])
        x = nstate.get(ilocation, [])

        if ilocation in y:
            continue

        y = y + [ilocation]
        x = x + [clocation]

        nstate[clocation] = y
        nstate[ilocation] = x
        iteration(ilocation, nstate)

iteration(1, {})
iteration(2, {})

The lines list is an abstraction of the possible points in the shape and where they can connect to. Point 1 is the top point, 2 and 3 are the top corners of the square, 4 and 5 are the far left and right points of the triangle, etc.

Starting at points 1 and 2. Point 1 is functionally the same as points 4, 5 and 8, while point 2 is the same as 2, 3, 6 and 7. No need for unnecessary iterations. Give its current location, the code recursively builds lines to all possible connection points. If no points are available, it just returns.

It breaks when all possible links are met, as seen by the check function. This is done by checking if every point is touched at least one, and then iterating through all points to see if that point is connected to every possible other line.

Turns out it is not possible.

Sucks.