Brute force solver for a cat themed 'scramble squares' puzzle

puzzle.py

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

tiles.png