Problema del mosaico

El «Tiling Problem«, problema del mosaico o problema de recubrimiento es un desafío clásico en la informática y las matemáticas que consiste en determinar cómo cubrir completamente una región, generalmente un tablero, utilizando piezas geométricas específicas sin solapamientos ni espacios vacíos. Un ejemplo común es el problema de cubrir un tablero de 2^k x 2^k con una casilla defectuosa (es decir, una casilla que no se puede cubrir) utilizando piezas en forma de trominós en forma de «L».

Fundamentos del problema del mosaico

El problema se basa en la capacidad de dividir un tablero de tamaño 2^k x 2^k en subregiones más pequeñas, manteniendo siempre una casilla defectuosa en cada subdivisión. Un trominó en forma de «L» cubre exactamente tres casillas, lo que permite, mediante una estrategia adecuada, cubrir todo el tablero excepto la casilla defectuosa.

Resolución del problema del mosaico mediante divide y vencerás

La técnica de «Divide y Vencerás» es especialmente efectiva para este problema. Consiste en dividir el tablero en cuatro subtableros de igual tamaño, identificar la posición de la casilla defectuosa y colocar un trominó en el centro de manera que cada subtablero tenga exactamente una casilla ocupada o defectuosa. Este proceso se repite recursivamente hasta alcanzar subtableros de 2×22 \times 22×2, que son triviales de resolver.

Implementación en Java con representación gráfica

A continuación, se presenta una implementación en Java que resuelve el problema y muestra el resultado de manera gráfica utilizando la biblioteca Swing:

import javax.swing.*;
import java.awt.*;

public class TilingProblem extends JPanel {
    private static final int TILE_SIZE = 40; // Tamaño de cada casilla
    private static final int BOARD_SIZE = 8; // Debe ser una potencia de 2
    private int[][] board = new int[BOARD_SIZE][BOARD_SIZE];
    private int tileCounter = 1;

    public TilingProblem(int defectRow, int defectCol) {
        board[defectRow][defectCol] = -1; // Marca la casilla defectuosa
        tileBoard(0, 0, defectRow, defectCol, BOARD_SIZE);
    }

    private void tileBoard(int startX, int startY, int defectX, int defectY, int size) {
        if (size == 2) {
            // Coloca un trominó en las 4 casillas menos la defectuosa
            int tileNum = tileCounter++;
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    if (startX + i != defectX || startY + j != defectY) {
                        board[startX + i][startY + j] = tileNum;
                    }
                }
            }
            return;
        }

        int subSize = size / 2;
        int centerX = startX + subSize;
        int centerY = startY + subSize;

        // Determina en qué subtablero se encuentra la casilla defectuosa
        int defectRegion = (defectX < centerX ? 0 : 1) + (defectY < centerY ? 0 : 2);

        // Coloca un trominó en el centro, excepto en el subtablero con la casilla defectuosa
        int tileNum = tileCounter++;
        for (int i = 0; i < 4; i++) {
            if (i != defectRegion) {
                int dx = (i % 2 == 1) ? -1 : 0;
                int dy = (i / 2 == 1) ? -1 : 0;
                board[centerX + dx][centerY + dy] = tileNum;
            }
        }

        // Llama recursivamente para cada subtablero
        tileBoard(startX, startY, defectRegion == 0 ? defectX : centerX - 1, defectRegion == 0 ? defectY : centerY - 1, subSize);
        tileBoard(startX, centerY, defectRegion == 2 ? defectX : centerX - 1, defectRegion == 2 ? defectY : centerY, subSize);
        tileBoard(centerX, startY, defectRegion == 1 ? defectX : centerX, defectRegion == 1 ? defectY : centerY - 1, subSize);
        tileBoard(centerX, centerY, defectRegion == 3 ? defectX : centerX, defectRegion == 3 ? defectY : centerY, subSize);
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int j = 0; j < BOARD_SIZE; j++) {
                if (board[i][j] == -1) {
                    g.setColor(Color.RED); // Casilla defectuosa
                } else {
                    g.setColor(new Color((board[i][j] * 50) % 256, (board[i][j] * 80) % 256, (board[i][j] * 110) % 256));
                }
                g.fillRect(j * TILE_SIZE, i * TILE_SIZE, TILE_SIZE, TILE_SIZE);
                g.setColor(Color.BLACK);
                g.drawRect(j * TILE_SIZE, i * TILE_SIZE, TILE_SIZE, TILE_SIZE);
            }
        }
    }

    public static void main(String[] args) {
        JFrame frame = new JFrame("Tiling Problem");
        TilingProblem panel = new TilingProblem(0, 0); // Casilla defectuosa en (0,0)
        frame.add(panel);
        frame.setSize(BOARD_SIZE * TILE_SIZE + 15, BOARD_SIZE * TILE_SIZE + 40);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setVisible(true);
    }
}

Explicación del Código

Clase TilingProblem: Extiende JPanel para permitir la representación gráfica del tablero.

Constantes:

– TILE_SIZE: Define el tamaño de cada casilla en píxeles.

– BOARD_SIZE: Tamaño del tablero; debe ser una potencia de 2.

Variables:

– board: Matriz que representa el tablero; los valores indican el identificador del trominó que cubre cada casilla.

– tileCounter: Contador para asignar identificadores únicos a cada