Skip to content

Instantly share code, notes, and snippets.

@jbergknoff jbergknoff/solve.py
Created Mar 27, 2020

Embed
What would you like to do?
Solving the Five Squared puzzle (חמש בריבוע)
# Solving the Five Squared puzzle
# seven 3-pieces, two 2-pieces
# A = vortex
# B = star
# C = pentagon
# D = bullseye
# E = triangle
three_pieces = [
['A', 'B', 'C'],
['A', 'C', 'B'],
['A', 'C', 'D'],
['A', 'E', 'C'],
['B', 'A', 'D'],
['B', 'D', 'E'],
['D', 'C', 'E'],
]
two_pieces = [
['B', 'E'],
['D', 'E'],
]
# cf. https://stackoverflow.com/a/6473724/349427
def transpose(list_of_lists):
return list(map(list, zip(*list_of_lists)))
five_by_three_layouts = [
# [ 0 ]
# [ 1 ]
# [ 2 ]
# [ 3 ]
# [ 4 ]
lambda five_threes: transpose(five_threes),
# [ 0 ]
# [ 1 ]
# [ ][ ][ ]
# [2][3][4]
# [ ][ ][ ]
lambda five_threes: transpose(five_threes[:2] + transpose(five_threes[2:5])),
# [ 0 ]
# [ ][ ][ ]
# [2][3][4]
# [ ][ ][ ]
# [ 1 ]
lambda five_threes: transpose([five_threes[0]] + transpose(five_threes[2:5]) + [five_threes[1]]),
]
layouts = []
# layout A
# two solutions:
# [bullseye, triangle] [pentagon, star, vortex]
# [triangle, pentagon, bullseye] [vortex] [star]
# [vortex] [star] [triangle] [pentagon] [bullseye]
# [pentagon] [vortex] [star] [bullseye] [triangle]
# [star] [bullseye] [vortex, triangle, pentagon]
#
# and, very similarly,
# [bullseye, triangle] [vortex, star, pentagon]
# [triangle, pentagon, bullseye] [vortex] [star]
# [vortex] [star] [triangle] [pentagon] [bullseye]
# [pentagon] [vortex] [star] [bullseye] [triangle]
# [star] [bullseye] [pentagon, triangle, vortex]
def layoutA(threes, twos):
return [
twos[0] + threes[0],
threes[1] + [threes[2][0], threes[3][0]],
[threes[4][0], threes[5][0], twos[1][0], threes[2][1], threes[3][1]],
[threes[4][1], threes[5][1], twos[1][1], threes[2][2], threes[3][2]],
[threes[4][2], threes[5][2]] + threes[6],
]
# layout B
# two solutions:
# [bullseye, triangle] [pentagon, star, vortex]
# [star] [bullseye] [vortex, triangle, pentagon]
# [pentagon] [vortex] [star] [bullseye] [triangle]
# [vortex] [star] [triangle] [pentagon] [bullseye]
# [triangle, pentagon, bullseye] [vortex] [star]
#
# and, very similarly:
# [bullseye, triangle] [vortex, star, pentagon]
# [star] [bullseye] [pentagon, triangle, vortex]
# [pentagon] [vortex] [star] [bullseye] [triangle]
# [vortex] [star] [triangle] [pentagon] [bullseye]
# [triangle, pentagon, bullseye] [vortex] [star]
def layoutB(threes, twos):
return [
twos[0] + threes[0],
[threes[1][0], threes[2][0]] + threes[3],
[threes[1][1], threes[2][1], twos[1][0], threes[4][0], threes[5][0]],
[threes[1][2], threes[2][2], twos[1][1], threes[4][1], threes[5][1]],
threes[6] + [threes[4][2], threes[5][2]],
]
# layout C
def layoutC(threes, twos):
return [
twos[0] + threes[0],
[threes[1][0], threes[2][0], threes[3][0]] + twos[1],
[threes[1][1], threes[2][1], threes[3][1], threes[4][0], threes[5][0]],
[threes[1][2], threes[2][2], threes[3][2], threes[4][1], threes[5][1]],
threes[6] + [threes[4][2], threes[5][2]],
]
# layout D
def layoutD(threes, twos):
return [
[threes[0][0], twos[0][0]] + threes[1],
[threes[0][1], twos[0][1]] + threes[2],
[threes[0][2]] + twos[1] + [threes[3][0], threes[4][0]],
threes[5] + [threes[3][1], threes[4][1]],
threes[6] + [threes[3][2], threes[4][2]],
]
# layout E
def layoutE(threes, twos):
return [
[threes[0][0], twos[0][0]] + threes[1],
[threes[0][1], twos[0][1]] + threes[2],
[threes[0][2]] + threes[3] + [threes[4][0]],
threes[5] + [twos[1][0], threes[4][1]],
threes[6] + [twos[1][1], threes[4][2]],
]
# layout F
def layoutF(threes, twos):
return [
twos[0] + [threes[0][0], threes[1][0], threes[2][0]],
[threes[3][0], threes[4][0], threes[0][1], threes[1][1], threes[2][1]],
[threes[3][1], threes[4][1], threes[0][2], threes[1][2], threes[2][2]],
[threes[3][2], threes[4][2]] + threes[5],
threes[6] + twos[1],
]
layouts += [layoutA, layoutB, layoutC, layoutD, layoutE, layoutF]
for five_by_three_layout in five_by_three_layouts:
def layoutG(threes, twos):
three_by_five = transpose(five_by_three_layout(threes[:5]))
return [
twos[0] + three_by_five[0],
twos[1] + three_by_five[1],
[threes[5][0], threes[6][0]] + three_by_five[2],
[threes[5][1], threes[6][1]] + three_by_five[3],
[threes[5][2], threes[6][2]] + three_by_five[4],
]
def layoutH(threes, twos):
five_by_three = five_by_three_layout(threes[:5])
return [
twos[0] + threes[5],
twos[1] + threes[6],
five_by_three[0],
five_by_three[1],
five_by_three[2],
]
def layoutI(threes, twos):
five_by_three = five_by_three_layout(threes[:5])
return [
twos[0] + threes[5],
threes[6] + twos[1],
five_by_three[0],
five_by_three[1],
five_by_three[2],
]
def layoutJ(threes, twos):
three_by_five = transpose(five_by_three_layout(threes[:5]))
return [
twos[0] + three_by_five[0],
[threes[5][0], threes[6][0]] + three_by_five[1],
[threes[5][1], threes[6][1]] + three_by_five[2],
[threes[5][2], threes[6][2]] + three_by_five[3],
twos[1] + three_by_five[4],
]
def layoutK(threes, twos):
five_by_three = five_by_three_layout(threes[:5])
return [
twos[0] + threes[5],
five_by_three[0],
five_by_three[1],
five_by_three[2],
twos[1] + threes[6],
]
def layoutL(threes, twos):
five_by_three = five_by_three_layout(threes[:5])
return [
twos[0] + threes[5],
five_by_three[0],
five_by_three[1],
five_by_three[2],
threes[6] + twos[1],
]
layouts += [layoutG, layoutH, layoutI, layoutJ, layoutK, layoutL]
def judge_square(square):
if len(square) != 5 or any([len(row) != 5 for row in square]):
print(f'Invalid square: {square}')
raise Exception('Invalid square')
for row in square:
if len(set(row)) != 5:
return False
for row in transpose(square):
if len(set(row)) != 5:
return False
return True
def generate_permutations(pieces):
if len(pieces) == 1:
yield [pieces[0]]
yield [pieces[0][::-1]]
return
permutation_length = len(pieces)
for sub_permutation in generate_permutations(pieces[1:]):
for index in range(permutation_length):
#print(f'inserting {pieces[0]} on either side of {sub_permutation[:index]} and {sub_permutation[index:]}')
yield sub_permutation[:index] + [pieces[0]] + sub_permutation[index:]
yield sub_permutation[:index] + [pieces[0][::-1]] + sub_permutation[index:]
def solve():
three_pieces_permutations = generate_permutations(three_pieces)
two_pieces_permutations = list(generate_permutations(two_pieces))
counter = 0
for three_pieces_permutation in three_pieces_permutations:
for two_pieces_permutation in two_pieces_permutations:
counter += 1
if counter % 10000 == 0:
print(f'Checked {counter}')
for layout in layouts:
square = layout(three_pieces_permutation, two_pieces_permutation)
if judge_square(square) is True:
print('found one')
print(three_pieces_permutation, two_pieces_permutation)
print(square)
print(layout)
if __name__ == '__main__':
solve()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.