Solving the Five Squared puzzle (חמש בריבוע)

solve.py

# 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()