SUPER BLOCKS GilKER puzzle solver

superblocks.py

import numpy as np

YELLOW = 'yellow'
BLUE = 'blue'
RED = 'red'
GREEN = 'green'

# ANSI color codes
COLOR_CODES = {
    YELLOW: '\033[93m',  # Light yellow
    BLUE: '\033[94m',  # Light blue
    GREEN: '\033[92m',  # Light green
    RED: '\033[91m',  # Light red
    'RESET': '\033[0m'  # Reset to default terminal color
}


class PuzzlePiece:
    def __init__(self, shape, color, identifier):
        self.shape = shape
        self.color = color
        self.identifier = identifier  # Unique identifier for each piece
        self.unique_rotations = self.calculate_unique_rotations()
        self.rotations = [np.rot90(shape, k=i) for i in range(self.unique_rotations)]

    def calculate_unique_rotations(self):
        # Improved calculation of unique rotations
        unique_shapes = []
        for i in range(4):
            rotated_shape = np.rot90(self.shape, k=i)
            if not any(np.array_equal(rotated_shape, us) for us in unique_shapes):
                unique_shapes.append(rotated_shape)
        return len(unique_shapes)

    def get_rotation(self, rotation_index):
        # Return the shape for a given rotation index
        return self.rotations[rotation_index % self.unique_rotations]

def fits(grid, piece_shape, row, col):
    nrows, ncols = piece_shape.shape
    if row + nrows > grid.shape[0] or col + ncols > grid.shape[1]:
        return False  # Piece would go out of bounds
    for i in range(nrows):
        for j in range(ncols):
            if piece_shape[i, j] == 1 and grid[row + i, col + j] != 1:
                return False
    return True

def place_piece(grid, piece_shape, identifier, row, col):
    nrows, ncols = piece_shape.shape
    new_grid = np.copy(grid)
    for i in range(nrows):
        for j in range(ncols):
            if piece_shape[i, j] == 1:
                new_grid[row + i, col + j] = identifier
    return new_grid


def solve_puzzle(grid, pieces, index=0):
    if not np.any(grid == 1):
        return grid

    if index >= len(pieces):
        return None

    piece = pieces[index]

    for rotation_index in range(piece.unique_rotations):
        rotated_shape = piece.get_rotation(rotation_index)
        for row in range(grid.shape[0]):
            for col in range(grid.shape[1]):
                if fits(grid, rotated_shape, row, col):
                    new_grid = place_piece(grid, rotated_shape, piece.identifier, row, col)
                    result = solve_puzzle(new_grid, pieces, index + 1)
                    if result is not None:
                        return result

    # If none of the positions and rotations work, try the next piece
    return solve_puzzle(grid, pieces, index + 1)

ALL_YELLOW = [
    PuzzlePiece(np.array([
        [0, 1, 0],
        [1, 1, 1],
        [0, 1, 0],
    ]), YELLOW, "A"),
    PuzzlePiece(np.array([
        [1, 1, 1, 0],
        [0, 1, 1, 1],
    ]), YELLOW, "B"),
    PuzzlePiece(np.array([
        [0, 1, 0],
        [1, 1, 1],
        [1, 0, 1],
    ]), YELLOW, "C"),
    PuzzlePiece(np.array([
        [1, 1, 1, 1],
    ]), YELLOW, "D")
]

ALL_BLUE = [
    PuzzlePiece(np.array([
        [1, 0, 0],
        [1, 0, 0],
        [1, 1, 1],
    ]), BLUE, "E"),
    PuzzlePiece(np.array([
        [0, 1, 1, 0],
        [1, 1, 1, 1],
    ]), BLUE, "F"),
    PuzzlePiece(np.array([
        [0, 1, 1],
        [1, 1, 0],
    ]), BLUE, "G"),
    PuzzlePiece(np.array([
        [0, 1, 0],
        [1, 1, 1],
        [0, 1, 0],
        [0, 1, 0],
    ]), BLUE, "H"),
]

ALL_GREEN = [
    PuzzlePiece(np.array([
        [1, 1, 0],
        [1, 1, 1],
    ]), GREEN, "I"),
    PuzzlePiece(np.array([
        [1, 0, 0],
        [1, 1, 0],
        [0, 1, 1],
    ]), GREEN, "J"),
    PuzzlePiece(np.array([
        [1, 0, 0, 1],
        [1, 1, 1, 1],
    ]), GREEN, "K"),
    PuzzlePiece(np.array([
        [0, 1, 0],
        [0, 1, 0],
        [1, 1, 1],
    ]), GREEN, "L"),
]

ALL_RED = [
    PuzzlePiece(np.array([
        [1, 0, 0],
        [1, 1, 0],
        [1, 1, 1],
    ]), RED, "M"),
    PuzzlePiece(np.array([
        [0, 1, 0],
        [1, 1, 1],
        [1, 1, 0],
    ]), RED, "N"),
    PuzzlePiece(np.array([
        [1, 0, 0, 0],
        [1, 1, 1, 1],
    ]), RED, "O"),
    PuzzlePiece(np.array([
        [1, 0, 1],
        [1, 1, 1],
    ]), RED, "P"),
]


def print_colored_grid(solution_grid, input_pieces):
    piece_color_map = {piece.identifier: COLOR_CODES[piece.color] for piece in input_pieces}
    print()
    for row in solution_grid:
        for cell in row:
            if cell in piece_color_map:
                print(f"{piece_color_map[cell]}{cell}{COLOR_CODES['RESET']}", end=" ")
            else:
                print('.', end=" ")  # Empty cells
        print()  # Newline for the next row




def run(grid, pieces):
    res = solve_puzzle(grid, pieces)
    print_colored_grid(solution_grid=res, input_pieces=pieces)

 ### TESTS:

def test_real_case_8_pieces():
    res = solve_puzzle(
        np.array([
            [1, 1, 1, 1, 0, 0, 0, 0],
            [1, 1, 1, 1, 0, 0, 0, 0],
            [1, 1, 1, 1, 1, 0, 0, 0],
            [0, 1, 0, 1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 1, 1, 1, 1, 1, 0],
            [0, 0, 0, 1, 1, 1, 1, 1],
            [0, 1, 1, 1, 1, 1, 1, 0],
        ], dtype=object),
        ALL_YELLOW + ALL_BLUE
    )
    print_colored_grid(solution_grid=res, input_pieces=ALL_YELLOW + ALL_BLUE)
    assert res is not None


def test_real_case_12_piece_300():
    input_pieces = ALL_BLUE + ALL_GREEN + ALL_RED
    res = solve_puzzle(
        np.array([
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0],
            [1, 1, 1, 1, 0, 1, 1, 0],
            [1, 1, 1, 1, 1, 1, 1, 0],
            [1, 1, 1, 1, 1, 1, 1, 0],
            [1, 1, 1, 1, 1, 1, 1, 0],
            [0, 0, 0, 1, 1, 1, 1, 1],
            [0, 0, 0, 1, 1, 1, 1, 0],
        ], dtype=object),
        input_pieces
    )
    print_colored_grid(res, input_pieces)
    assert res is not None


@pytest.mark.skip
def test_real_case_all_pieces_max_hard():
    input_pieces = ALL_YELLOW + ALL_BLUE + ALL_GREEN + ALL_RED
    res = solve_puzzle(
        np.array([
            [0, 0, 0, 0, 1, 1, 1, 1],
            [1, 1, 0, 0, 0, 1, 1, 1],
            [1, 1, 1, 1, 0, 1, 1, 1],
            [1, 1, 1, 1, 0, 0, 0, 1],
            [1, 1, 1, 1, 1, 1, 0, 0],
            [1, 1, 1, 1, 1, 1, 1, 0],
            [1, 1, 1, 1, 1, 1, 1, 1],
            [1, 1, 1, 1, 1, 1, 1, 1],
        ], dtype=object),
        input_pieces
    )
    print_colored_grid(res, input_pieces)
    assert res is not None