Last active
January 8, 2023 19:40
-
-
Save cibomahto/31e0ec014bedcd39242265e333535809 to your computer and use it in GitHub Desktop.
Brute force solver for a cat themed 'scramble squares' puzzle
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Brute force solver for a cat themed 'scramble squares' puzzle. Attempts to find all | |
# possible solutions to the puzzle. | |
import math | |
def number_to_order(number, items): | |
# Create a unique ordering of the values in items, based on an integer number. | |
# This alows all possible combinations of the items to be calculated by looping | |
# through the numbers 0 - len(items)! | |
# | |
# For instance, for a set of three items: | |
# | number | items | output | | |
# | --- | --- | --- | | |
# | 0 | ['a','b','c'] | ['a','b','c'] | | |
# | 1 | ['a','b','c'] | ['a','c','b'] | | |
# | 2 | ['a','b','c'] | ['b','a','c'] | | |
# | 3 | ['a','b','c'] | ['b','c','a'] | | |
# | 4 | ['a','b','c'] | ['c','a','b'] | | |
# | 5 | ['a','b','c'] | ['c','b','a'] | | |
# | |
f = math.factorial(len(items))//len(items) | |
pos = math.floor(number//f) | |
new_items = items.copy() | |
del new_items[pos] | |
if(len(new_items) > 1): | |
ret = [items[pos]] | |
ret.extend(number_to_order(number%f, new_items)) | |
return ret | |
else: | |
ret = [items[pos]] | |
ret.extend(new_items) | |
return ret | |
def grid_33_matches(tiles, matches): | |
# Each tiles is described by a list, which describes its edges starting at the north | |
# and working clockwise. For example, ['A2', 'B1', 'D1', 'C1'] represents: | |
# ____________ | |
# | A2 | | |
# | | | |
# | C1 B1 | | |
# | | | |
# | D1 | | |
# |____________| | |
# | |
# This function determines if a 3x3 grid of tiles 'matches' on each edge. Tiles match | |
# if their edges fit together (as defined in the 'matches' dict), for instance: | |
# ____________ ____________ ____________ | |
# | A2 | | A2 | | A2 | | |
# | | | | | | | |
# | C1 B1 | | B2 C2 | | C1 B1 | | |
# | | | | | | | |
# | D1 | | A1 | | B1 | | |
# |____________| |____________| |____________| | |
# ____________ ____________ ____________ | |
# | D2 | | A2 | | B2 | | |
# | | | | | | | |
# | C1 B1 | | B2 B1 | | B2 B1 | | |
# | | | | | | | |
# | A1 | | D1 | | B1 | | |
# |____________| |____________| |____________| | |
# ____________ ____________ ____________ | |
# | A2 | | D2 | | B2 | | |
# | | | | | | | |
# | C1 B1 | | B2 B1 | | B2 B1 | | |
# | | | | | | | |
# | D1 | | D1 | | D1 | | |
# |____________| |____________| |____________| | |
return (matches[tiles[0][1]] == tiles[1][3]) \ | |
and (matches[tiles[1][1]] == tiles[2][3]) \ | |
and (matches[tiles[3][1]] == tiles[4][3]) \ | |
and (matches[tiles[4][1]] == tiles[5][3]) \ | |
and (matches[tiles[6][1]] == tiles[7][3]) \ | |
and (matches[tiles[7][1]] == tiles[8][3]) \ | |
and (matches[tiles[0][2]] == tiles[3][0]) \ | |
and (matches[tiles[1][2]] == tiles[4][0]) \ | |
and (matches[tiles[2][2]] == tiles[5][0]) \ | |
and (matches[tiles[3][2]] == tiles[6][0]) \ | |
and (matches[tiles[4][2]] == tiles[7][0]) \ | |
and (matches[tiles[5][2]] == tiles[8][0]) | |
def search_neighbor_rotations_horizontal(tile_0, tile_1, matches): | |
# Search for any rotation combinations that allow two tiles to match horizontally. For | |
# example, these tiles only match in one orientation: | |
# ____________ ____________ | |
# | A1 | | B2 | | |
# | | | | | |
# | D2 B1 | | C1 D2 | | |
# | | | | | |
# | C1 | | A1 | | |
# |____________| |____________| | |
# | |
# [0,270] => [0,3] | |
# These match in three orientations: | |
# ____________ ____________ | |
# | D1 | | A1 | | |
# | | | | | |
# | A2 A2 | | B2 B2 | | |
# | | | | | |
# | C1 | | C2 | | |
# |____________| |____________| | |
# | |
# [0,270] => [0,3] | |
# [180,270] => [2,3] | |
# [270,90] => [3,1] | |
# | |
# These are then the maximum set of rotations that each piece can be in | |
rotations = [] | |
for rot_0 in range(0,4): | |
for rot_1 in range(0,4): | |
if matches[tile_0[(4-rot_0+1)%4]] == tile_1[(4-rot_1+3)%4]: | |
rotations.append([rot_0, rot_1]) | |
return rotations | |
def search_neighbor_rotations_vertical(tile_0, tile_1, matches): | |
# Search for any rotation combinations that allow two tiles to match vertically. For | |
# example, these tiles only match in one orientation: | |
# ____________ | |
# | A1 | | |
# | | | |
# | D2 B1 | | |
# | | | |
# | C1 | | |
# |____________| | |
# ____________ | |
# | B2 | | |
# | | | |
# | C1 D2 | | |
# | | | |
# | A1 | | |
# |____________| | |
# | |
# [90,0] => [1,0] | |
# These match in three orientations: | |
# ____________ | |
# | A2 | | |
# | | | |
# | A2 D2 | | |
# | | | |
# | C1 | | |
# |____________| | |
# ____________ | |
# | A1 | | |
# | | | |
# | B2 B2 | | |
# | | | |
# | C2 | | |
# |____________| | |
# | |
# [0,180] => [0,2] | |
# [180,0] => [2,0] | |
# [270,0] => [3,0] | |
# | |
# These are then the maximum set of rotations that each piece can be in | |
rotations = [] | |
for rot_0 in range(0,4): | |
for rot_1 in range(0,4): | |
if matches[tile_0[(4-rot_0+2)%4]] == tile_1[(4-rot_1+0)%4]: | |
rotations.append([rot_0, rot_1]) | |
return rotations | |
def rotate_tile(tile, rotation): | |
return [tile[(4 + 0 - rotation) % 4], | |
tile[(4 + 1 - rotation) % 4], | |
tile[(4 + 2 - rotation) % 4], | |
tile[(4 + 3 - rotation) % 4] | |
] | |
# print(rotate_tile(['D2','D1','C1','B1'],0)) | |
# print(rotate_tile(['D2','D1','C1','B1'],1)) | |
# print(rotate_tile(['D2','D1','C1','B1'],2)) | |
# print(rotate_tile(['D2','D1','C1','B1'],3)) | |
# exit(0) | |
def rotate_tileset(tileset, rotations): | |
return [rotate_tile(tile, rotation) for tile, rotation in zip(tileset, rotations)] | |
def search_rotations(tiles, matches): | |
# Tile positions: | |
# | |
# 0 1 2 | |
# 3 4 5 | |
# 6 7 8 | |
# | |
# Try rotating each tile in the set, to see if it can match its neighbor. This function returns early if | |
# any two neighbor tiles can't be rotated to match each other, to prevent needing to search the entire | |
# space. | |
horizontal_tileset = [ | |
[0,1],[1,2], | |
[3,4],[4,5], | |
[6,7],[7,8] | |
] | |
vertical_tileset = [ | |
[0,3],[3,6], | |
[1,4],[4,7], | |
[2,5],[5,8] | |
] | |
# Union of all allowed rotations, for each tile | |
allowed_rotations = [ | |
[0,1,2,3], | |
[0,1,2,3], | |
[0,1,2,3], | |
[0,1,2,3], | |
[0,1,2,3], | |
[0,1,2,3], | |
[0,1,2,3], | |
[0,1,2,3], | |
[0,1,2,3] | |
] | |
# Check if each horizonal neighbor has a valid fit (in isolation) | |
for tileset in horizontal_tileset: | |
rotations = search_neighbor_rotations_horizontal(tiles[tileset[0]], tiles[tileset[1]], matches) | |
if rotations == []: | |
return False, [] | |
allowed_0 = [] | |
allowed_1 = [] | |
for rotation in rotations: | |
allowed_0.append(rotation[0]) | |
allowed_1.append(rotation[1]) | |
allowed_rotations[tileset[0]] = list(set(allowed_rotations[tileset[0]]) & set(allowed_0)) | |
allowed_rotations[tileset[1]] = list(set(allowed_rotations[tileset[1]]) & set(allowed_1)) | |
# Check if each vertical neighbor has a valid fit (in isolation) | |
for tileset in vertical_tileset: | |
rotations = search_neighbor_rotations_vertical(tiles[tileset[0]], tiles[tileset[1]], matches) | |
if rotations == []: | |
return False, [] | |
allowed_0 = [] | |
allowed_1 = [] | |
for rotation in rotations: | |
allowed_0.append(rotation[0]) | |
allowed_1.append(rotation[1]) | |
allowed_rotations[tileset[0]] = list(set(allowed_rotations[tileset[0]]) & set(allowed_0)) | |
allowed_rotations[tileset[1]] = list(set(allowed_rotations[tileset[1]]) & set(allowed_1)) | |
# Check if all of the isolated sets still allow a potential rotation | |
for rotation in allowed_rotations: | |
if rotation == []: | |
return False, [] | |
# Probably a recursive solution would be cleaner here | |
valid_solutions = [] | |
for rot0 in allowed_rotations[0]: | |
for rot1 in allowed_rotations[1]: | |
for rot2 in allowed_rotations[2]: | |
for rot3 in allowed_rotations[3]: | |
for rot4 in allowed_rotations[4]: | |
for rot5 in allowed_rotations[5]: | |
for rot6 in allowed_rotations[6]: | |
for rot7 in allowed_rotations[7]: | |
for rot8 in allowed_rotations[8]: | |
rotated_tileset = rotate_tileset( | |
#[tile_set[i] for i in tiles], | |
tiles, | |
[rot0, rot1, rot2, rot3, rot4, rot5, rot6, rot7, rot8] | |
) | |
#print(rotated_tileset) | |
if grid_33_matches(rotated_tileset, matches): | |
valid_solutions.append([rot0, rot1, rot2, rot3, rot4, rot5, rot6, rot7, rot8]) | |
if valid_solutions == []: | |
return False, [] | |
return True, valid_solutions | |
# seta = [1,2,3,4] | |
# setb = [2,2,4] | |
# print(list(set(seta) & set(setb))) | |
# exit(0) | |
def tile_repr(tiles): | |
# This function prints a tile grid, for example: | |
# ____________ ____________ ____________ | |
# | A2 | | A2 | | A2 | | |
# | | | | | | | |
# | C1 B1 | | B2 C2 | | C1 B1 | | |
# | | | | | | | |
# | D1 | | A1 | | B1 | | |
# |____________| |____________| |____________| | |
# ____________ ____________ ____________ | |
# | D2 | | A2 | | B2 | | |
# | | | | | | | |
# | C1 B1 | | B2 B1 | | B2 B1 | | |
# | | | | | | | |
# | A1 | | D1 | | B1 | | |
# |____________| |____________| |____________| | |
# ____________ ____________ ____________ | |
# | A2 | | D2 | | B2 | | |
# | | | | | | | |
# | C1 B1 | | B2 B1 | | B2 B1 | | |
# | | | | | | | |
# | D1 | | D1 | | D1 | | |
# |____________| |____________| |____________| | |
text = [] | |
for row in [tiles[0:3], tiles[3:6],tiles[6:9]]: | |
text.extend([' ____________ ____________ ____________ ']) | |
text.extend(['| {:} | | {:} | | {:} |'.format(row[0][0],row[1][0],row[2][0])]) | |
text.extend(['| | | | | |']) | |
text.extend(['| {:} {:} | | {:} {:} | | {:} {:} |'.format(row[0][3],row[0][1],row[1][3],row[1][1],row[2][3],row[2][1])]) | |
text.extend(['| | | | | |']) | |
text.extend(['| {:} | | {:} | | {:} |'.format(row[0][2],row[1][2],row[2][2])]) | |
text.extend(['|____________| |____________| |____________|']) | |
return text | |
tile_set = [ | |
['A1','B1','C1','D2'], | |
['B2','D2','A1','C1'], | |
['A1','B2','C2','B2'], | |
['D1','A2','C1','A2'], | |
['A2','C1','D2','B1'], | |
['C2','D2','B2','A1'], | |
['D2','D1','C1','B1'], | |
['A1','B2','D1','C2'], | |
['A2','B1','D1','C1'] | |
] | |
matches = { | |
'A1':'A2', | |
'A2':'A1', | |
'B1':'B2', | |
'B2':'B1', | |
'C1':'C2', | |
'C2':'C1', | |
'D1':'D2', | |
'D2':'D1', | |
} | |
good_match = [ | |
['A2','B1','D1','C1'], | |
['A2','C2','A1','B2'], | |
['A2','B1','B1','C1'], | |
['D2','B1','A1','C1'], | |
['A2','B1','D1','B2'], | |
['B2','B1','B1','B2'], | |
['A2','B1','D1','C1'], | |
['D2','B1','D1','B2'], | |
['B2','B1','D1','B2'], | |
] | |
# print('\n'.join(tile_repr(good_match))) | |
# print(grid_33_matches(good_match,matches)) | |
# exit(0) | |
# print(search_neighbor_rotations_horizontal(['A1','B1','C1','D2'], ['B2','D2','A1','C1'], matches)) | |
# print(search_neighbor_rotations_horizontal(['D1','A2','C1','A2'], ['A1','B2','C2','B2'], matches)) | |
# print(search_neighbor_rotations_vertical(['A1','B1','C1','D2'], ['B2','D2','A1','C1'], matches)) | |
# print(search_neighbor_rotations_vertical(['A2','D2','C1','A2'], ['A1','B2','C2','B2'], matches)) | |
# exit(0) | |
rot_possible_count = 0 | |
total = math.factorial(len(tile_set)) | |
for number in range(0,math.factorial(len(tile_set))): | |
order = number_to_order(number, list(range(0,len(tile_set)))) | |
tiles = [tile_set[i] for i in order] | |
#good = grid_33_matches(tiles, matches) | |
rotation_possible, allowed_rotations = search_rotations(tiles, matches) | |
#print('{:3.0f}%'.format(number/total*100), number, order, tiles, rotation_possible) | |
if rotation_possible: | |
print('{:3.0f}%'.format(number/total*100), number, order, tiles, allowed_rotations) | |
rot_possible_count = rot_possible_count + 1 | |
for line in tile_repr(tiles): | |
print(line) | |
print(rot_possible_count, total) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment