Terceira palavra cruzada com definições fora do quadro

Eis aqui minha terceira palavra cruzada com definições fora do quadro.

E eis aqui as definições:

Sem quadro preto - 6x6

Eis aqui, como prometido, um problema 6x6 sem quadro preto no meio.

Bônus 1: Um quadro 6x6, feito por mim, só com números romanos!

Bônus 2: Um quadro 4x4 também feito por mim, sem quadro preto no meio e com a característica especial de que todas as respostas são anagramas!

Problemas de palavras cruzadas sem "quadro preto"

Li na wikipedia que um brasileiro criou duas palavras cruzadas de 9x9 sem quadros pretos no meio. Obviamente tomei isso como um desafio, eu tinha que fazer algo nesse estilo. Como sou programador, nada mais natural do que escrever um programa para atacar esse problema.

Obviamente tinha que começar com um quadro menor, para testar o meu programa. Resolvi começar com um quadro de 4x4. Peguei a lista de palavras de quatro letras (mais de três mil palavras!) do site Todas as Palavras, coloquei-as num banco de dados e pus meu programa para rodar. Ele rodou, rodou, rodou e nada de dar uma solução...

O problema não era um bug no programa, mas sim a maneira como eu ataquei a questão: meu programa estava fazendo uma verificação por força bruta, quer dizer, estava tentando todas as três mil palavras em cada uma das quatro linhas do quadro. Ou seja, ele teria que verificar mais de oitenta trilhões de combinações antes de acabar!

Modifiquei meu programa, deixei-o um pouco mais inteligente (seria muito longo descrever aqui como foi; se você tiver interesse no assunto, me escreva à parte que eu terei prazer em conversar sobre isso) e ele começou a apresentar resultados.

Deixei o bichinho rodando por uma noite e quando fui ver o resultado na manhã seguinte, ele tinha encontrado quase um milhão de soluções possíveis! E isso com a primeira palavra sendo fixa! Quer dizer que se fosse verificar todas as três mil palavras na primeira posição ele iria encontrar provavelmente mais de um bilhão de quadros possíveis. Uau!

Anyway, parei o programa e em seguida comecei a trabalhar na versão 6x6 (pulei a 5x5 pois seria muito fácil). Enquanto espero os resultados dessa nova versão, coloco abaixo quatro problemas sem quadros pretos no meio, em quatro tamanhos diferentes. Eu os criei eu mesmo, não foram feitos por computador. Ah, e o problema de 5x5 é palíndromo, quer dizer, se você rodá-lo 180 graus vai ter o mesmo quadro. E se girar 90 graus, terá um quadro diferente, mas também com todas as palavras válidas!

Boas diversões! E semana que vem teremos um quadro 6x6!

Segunda palavra cruzada com definições fora do quadro

Primeira palavra cruzada com definições fora do quadro