Hashiwokakero Bicolor

Infelizmente, não é possível inferir a resolução do tabuleiro baseado apenas em algumas propriedades do mesmo. Para resolver esse problema, é necessário criar um algoritmo que resolve o tabuleiro, e para nossa sorte, nesse caso, o problema não é NP-completo como no puzzle original.

Antes de tudo, podemos dizer que um tabuleiro não possui solução possível se o número de quadrados azuis e quadrados laranjas não é igual. Também podemos tirar de jogo todas as soluções onde o número de quadrados adjacentes é menor que o número encontrado no quadrado dividido por dois.

De toda forma, ultimamente não vamos poder escapar de ter que resolver os tabuleiros que respeitam ambas essas regras. Para tal, o uso de duas cores para representar os quadrados insinua que esse é um problema de grafo bipartido. A ideia é que um quadrado de cor azul seja representado por alguns vértices de um lado, enquanto que quadrados de cor laranja sejam representados por alguns vértices do outro lado. Um tabuleiro resolvido é aquele onde todos as arestas de todos os quadrados sejam cobertas, isto é, obtemos um emparelhamento bipartido máximo.

Para fazer tal modelagem, tratamos cada quadrado como sendo representado por dois vértices em cada uma de suas extremidades, representando cada uma de suas pontes possíveis. Ligamos esses dois vértices com outros dois vértices de quadrados adjacentes de forma paralela. Para satisfazer o emparelhamento de arestas extras, criamos vértices extras com arestas para todos os outros vértices que precisarão ser escolhidas caso o emparelhamento máximo exista.

Note que é possível otimizar o conjunto de vértices e arestas dos quadrados com digito 1. A solução do juiz não escolhe fazer isso, e opta por um padrão uniforme de vértices extras em todos os quadrados.

Assim, aplicamos o algoritmo de Kuhn para emparelhamento mínimo em grafo bipartido e verificamos se todos os vértices foram cobertos. Se eles foram todos cobertos, o tabuleiro tem solução, e o emparelhamento mostra uma resposta possível. Se não, não existe solução possível.