Script to solve a pentomino jigsaw puzzle

puzzle.py

import time

all_pieces = [
    (0, [('-', 0, 0), ('|', 1, 0), ('-', 2, 0), ('|', 2, 1), ('|', 3, 0)]),
    (1, [('-', 1, 0), ('|', 1, 1), ('-', 0, 1), ('|', 0, 2), ('-', 0, 3)]),
    (2, [('|', 0, 0), ('-', 0, 1), ('|', 0, 2), ('-', 0, 3), ('|', 0, 4)]),
    (3, [('|', 0, 0), ('-', 0, 1), ('|', 1, 1), ('-', 2, 1), ('|', 2, 2)]),
    (4, [('-', 2, 0), ('|', 2, 1), ('-', 1, 1), ('|', 1, 2), ('-', 0, 2)]),
    (5, [('-', 0, 0), ('|', 0, 1), ('-', 0, 2), ('|', 0, 3), ('-', 0, 4)]),
    (6, [('-', 0, 0), ('|', 0, 1), ('-', 0, 2), ('-', 1, 1), ('|', 2, 1)]),
    (7, [('|', 0, 0), ('-', 1, 0), ('|', 1, 1), ('-', 1, 2), ('|', 2, 2)]),
    (8, [('-', 1, 0), ('-', 0, 1), ('|', 1, 1), ('-', 1, 2), ('|', 2, 2)]),
    (9, [('-', 0, 0), ('|', 0, 1), ('-', 1, 1), ('|', 2, 1), ('-', 2, 0)]),
    (10, [('|', 0, 0), ('-', 0, 1), ('|', 0, 2), ('-', 1, 0), ('|', 1, 1)]),
    (11, [('-', 0, 0), ('|', 0, 1), ('-', 0, 2), ('|', 0, 3), ('|', 1, 2)]),
    (12, [('-', 0, 0), ('|', 0, 1), ('-', 0, 2), ('|', 1, 2), ('-', 2, 2)]),
    (13, [('-', 0, 2), ('|', 0, 3), ('|', 1, 0), ('-', 1, 1), ('|', 1, 2)]),
    (14, [('|', 0, 0), ('-', 0, 1), ('|', 1, 1), ('-', 2, 1), ('-', 1, 2)]),
    (15, [('-', 0, 0), ('|', 1, 0), ('-', 2, 0), ('-', 1, 1), ('|', 1, 2)]),
    (16, [('-', 0, 0), ('|', 0, 1), ('|', 1, 0), ('-', 2, 0), ('|', 3, 0)]),
    (17, [('|', 0, 0), ('-', 0, 1), ('|', 1, 1), ('|', 2, 0), ('-', 2, 1)]),
    (18, [('|', 0, 0), ('-', 0, 1), ('-', 1, 0), ('|', 1, 1), ('-', 1, 2)]),
    (19, [('-', 0, 0), ('|', 1, 0), ('|', 0, 1), ('-', 0, 2), ('|', 0, 3)])
]

start_grid = []
grid_alignment = []
for i in range(5):
    start_grid.append([-1, -1, -1, -1, -1, -1, -1, -1, -1, -1])
    start_grid.append([-1, -1, -1, -1, -1, -1, -1, -1, -1, -1])
    grid_alignment.append(['-', '|', '-', '|', '-', '|', '-', '|', '-', '|'])
    grid_alignment.append(['|', '-', '|', '-', '|', '-', '|', '-', '|', '-'])

all_dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
solution_found = False

def add(a, b):
    return (a[0] + b[0], a[1] + b[1])

def is_free(grid, pos):
    return grid[pos[0]][pos[1]] == -1

def rev(s):
    return {'-': '|', '|': '-'}[s]

def get_placed_pieces(grid):
    placed = set()
    for row in grid:
        for c in row:
            placed.add(c)
    placed.remove(-1)
    return placed

def place_piece(grid, piece, pos):
    # First check if possible
    touched_other_piece = False
    piece_nr, pieces = piece
    for part in pieces:
        part_pos = add(pos, (part[1], part[2]))
        if not (0 <= part_pos[0] <= 9) or not (0 <= part_pos[1] <= 9):
            # Invalid coords
            return grid
        elif not is_free(grid, part_pos):
            # Already filled
            return grid
        elif grid_alignment[part_pos[0]][part_pos[1]] != part[0]:
            # Invalid alignment
            return grid
        for d in all_dirs:
            row, col = add(part_pos, d)
            if 0 <= row <= 9 and 0 <= col <= 9 and grid[row][col] != -1:
                touched_other_piece = True

    # If not touching other piece, invalid
    if not touched_other_piece and len(get_placed_pieces(grid)) > 0:
        return grid
        
    # If checks succeeded, update grid
    updated_grid = [g[:] for g in grid]
    for part in pieces:
        part_pos = add(pos, (part[1], part[2]))
        updated_grid[part_pos[0]][part_pos[1]] = piece_nr
    return updated_grid

def is_filled(grid):
    return all([all(c != -1 for c in row) for row in grid])

def rotate_piece180(piece):
    piece_id, parts = piece
    max_row = max(p[1] for p in parts)
    max_col = max(p[2] for p in parts)
    parts_reversed = [(p[0], -p[1]+max_row, -p[2]+max_col) for p in parts]
    return (piece_id, parts_reversed)

def rotate_piece90(piece):
    piece_id, parts = piece
    max_col = max(p[2] for p in parts)
    parts_reversed = [(rev(p[0]), -p[2]+max_col, p[1]) for p in parts]
    return (piece_id, parts_reversed)

def rotate_piece270(piece):
    piece_id, parts = piece
    max_row = max(p[1] for p in parts)
    parts_reversed = [(rev(p[0]), p[2], -p[1]+max_row) for p in parts]
    return (piece_id, parts_reversed)

def get_piece_variants(p):
    if piece_variants == 2:
        return [p, rotate_piece180(p)]
    elif piece_variants == 4:
        return [p, rotate_piece180(p), rotate_piece90(p), rotate_piece270(p)]
    else:
        raise Exception('unknown value for piece_variants')

def is_solvable(grid):
    # Check if all remaining space is still connected
    visited = set()
    for pos in [(row, col) for row in range(10) for col in range(10)]:
        if is_free(grid, pos) and pos not in visited:
            if len(visited) > 0:
                return False
            queue = [pos]
            i = 0
            while i < len(queue):
                current_pos = queue[i]
                for d in all_dirs:
                    new_pos = add(current_pos, d)
                    if 0 <= new_pos[0] <= 9 and 0 <= new_pos[1] <= 9 and new_pos not in queue and is_free(grid, new_pos):
                        queue.append((new_pos[0], new_pos[1]))
                i += 1
            
            if len(queue) < 5:
                return False
            else:
                visited.update(queue)
    return True

count = 0
seen_hashes = set()

def hash(grid):
    return tuple(tuple(row) for row in grid).__hash__()

def get_compactness_score(grid):
    """
    Calculates how many neighbor cells are free for placed cell.
    The lower, the more compact the current placement.
    """
    score = 0
    for pos in [(row, col) for row in range(10) for col in range(10)]:
        if not is_free(grid, pos):
            for d in all_dirs:
                new_pos = add(pos, d)
                if new_pos[0] < 0 or new_pos[0] > 9 or new_pos[1] < 0 or new_pos[1] > 9 or is_free(grid, new_pos):
                    score += 1
    return score

current_best = 16
start_time = time.time()

def get_char(c: int):
    if c == -1:
        return '.'
    elif c < 10:
        return str(c)
    else:
        return chr(c+55)

def print_grid(grid):
    for row in reversed(grid):
        print(''.join([get_char(c) for c in row]))
    print('t=', time.time()-start_time, 's')

def place_next(current_grid, level):
    global solution_found
    global count
    global current_best
    if hash(current_grid) in seen_hashes:
        return

    count += 1
    if solution_found:
        return
    
    placed = get_placed_pieces(current_grid)
    if len(placed) > current_best:
        print('New current best:', len(placed))
        current_best = len(placed)
        print_grid(current_grid)

    if count % 1000000 == 0:
        print(f'Count: {count}, {len(placed)} placed_pieces: {placed}')
        print_grid(current_grid)

    # Check next possible pieces
    possible_moves = []
    used_piece_indexes = get_placed_pieces(current_grid)
    for next_piece_raw in all_pieces:
        if next_piece_raw[0] in used_piece_indexes:
            continue
        for next_piece in get_piece_variants(next_piece_raw):
            for pos in [(row, col) for row in range(10) for col in range(10)]:
                updated_grid = place_piece(current_grid, next_piece, pos)
                if updated_grid == current_grid:
                    continue
                elif is_filled(updated_grid):
                    print('Found solution:', updated_grid)
                    print_grid(updated_grid)
                    solution_found = True
                    return
                elif check_solvable and not is_solvable(updated_grid):
                    continue
                score = get_compactness_score(updated_grid)
                possible_moves.append((score, next_piece, pos))
        
    # Place move by best score
    sorted_possibilities = sorted(possible_moves, key=lambda x: x[0])
    # print(f'Found {len(possible_moves)} possible moves', sorted_possibilities)
    for move in sorted_possibilities[:max_possibilities]:
        score, piece, pos = move
        updated_grid = place_piece(current_grid, piece, pos)
        if level <= 2:
            print(f'Placing next on {level}:', piece[0], pos)
        place_next(updated_grid, level+1)

    # Not solvable, add to index
    seen_hashes.add(hash(current_grid))


check_solvable = True
piece_variants = 4
max_possibilities = 5

if __name__ == '__main__':
    print('Starting, params:')
    print('- check_solvable:', check_solvable)
    print('- piece_variants:', piece_variants)
    print('- max_possibilities:', max_possibilities)
    print('- is_solvable: all remaining must be connected')
    place_next(start_grid, 0)