Quebra-cabeças - pensamentos e algoritmos

 Uma amiga (e vizinha) tem um hobby que a muito tempo eu não via ser feito: resolver quebra-cabeças. Em uma visita ela propôs resolvermos um que ela tem de 1500 peças. 

Eu, minha esposa, minha amiga e o marido dela começamos a montagem. Logo deu pra perceber que com tantas peças, é preciso ter alguns critérios pra começar a montagem, como por exemplo, encontrar as peças que tem bordas retas, pois obviamente, fazem parte das fronteiras laterais da imagem.

Só isso já se provou custoso. Mas após encontrar, os critérios de montagem começaram a ficar mais aleatórios, na base da tentativa e erro, ou na similaridade de cores e de partes da imagem... mesmo assim, critérios difíceis de evoluir, e muitas vezes impossíveis de distinguir se as soluções estavam plenamente certas ou erradas antes de testar peça com peça.

Aí entrou a minha mente tentando organizar um método/sistemática de solução e parece que, pelo menos no campo das ideias, eu fiz avanços (só a título de informação, pouco mais de uma semana depois, com mais visitas da minha esposa, o problema foi resolvido).

Eu percebi que preciso antes entender a maneira como o quebra cabeça foi construído. Cada peça oferece pequenas variações que são combinadas para compor a forma do recorte, isto é, a imagem não é a informação mais relevante que a peça carrega. E daí vem o desafio de compor uma estrutura de dados para representar uma peça, e todas essas informações que são necessárias.

Minha ideia básica é uma 4-upla, onde cada elemento armazena uma outra estrutura, que carrega os detalhes de um dos lados, conforme o ponto de vista de uma pessoa:

$$(L_{Esquerda}, L_{baixo}, L_{direita}, L_{cima})$$

Essas estruturas precisam ter dados específicos de cada lado, como raio da protuberância ou reentrância, comprimento de cada lado da peça. Apesar de pensar que normalmente uma análise da imagem da peça comparada com a imagem do quebra-cabeça completo pode ser importante, mas para quebra-cabeças de muitas peças isso parece ficar cada vez menos relevante.

Isso vai levar a algumas definições de operações com as peças bastante importantes, que por hora, julgo serem as fundamentais:

• Rotação de uma peça em sentido horário
• Critérios que definem encaixe de 2 peças
• Detecção de fronteira lateral (na peça, a que tem um lado reto, sem reentrâncias ou protuberância)

Quando isso for definido, uma peça pode ser manipulada de maneira mais precisa, e aí podemos pensar em um modelo/sistemática de solução. Minha proposta simplista:

1. Separam-se as peças as que tem 2 lados com fronteiras laterais. Estas serão os cantos do quebra-cabeça;
2. Para todas as peças que tem configurações de lado compatíveis, testa-se o encaixe com cada peça de canto. Esse processo deve garantir que pelo menos 1 peça seja encaixada em cada um dos 4 cantos
3. Repete o processo considerando cada uma das 4 peças recém encaixadas