Vi o puzzle a seguir, e parecia interessante. Por falta de um nome melhor, chamá-lo-ei de “quadrado mágico esburacado”.
Se o leitor quiser tentar resolver, aviso que há spoilers à frente.
Como eu já tinha feito uma rotina que resolve quadrados mágicos de qualquer tamanho, achei que poderia aproveitar algum padrão já existente.
Vide https://asgunzi.github.io/QuadradoMagicoD3/index.html
Entretanto, não foi possível partir para uma solução que utilizasse quadrados mágicos comuns. E também não consegui chegar numa fórmula matemática fechada, que chegue a uma solução.
O jeito foi apelar para os computadores. Mesmo assim, não é tarefa fácil.
O jeito “força bruta” pura chega a 20! (fatorial) combinações. Isso dá o número astronômico de 2,4*10^18 combinações. Computador algum no mundo consegue resolver.
O que fiz foi usar a estrutura do problema para diminuir drasticamente o número de combinações. Uma “força bruta” refinada…
Imagine fatiar o problema. Resolver somente a primeira linha.
Se olhar só para a primeira linha, há 20 números possíveis, e a combinação de 4 delas tem que somar 42.
O Python tem algumas rotinas de combinações e permutações que vêm bem a calhar. Elas geram todas as combinações possíveis.
#Passo 0:
comb = itertools.combinations(setNumbers,4)
for c in comb:
if sum(c)==42:
#Faz alguma coisa
Esse código vai descartar uma combinação errada (digamos, [1,2,3,4]) e vai ficar com uma combinação correta (ex. [1, 2, 20,19]).
Dada essa combinação correta, ainda assim há todas as permutações possíveis dela (ex. [1,20, 19, 2], [20,19,2,1] ) a checar.
permut1 = list(itertools.permutations(c)) #Código para gerar permutações
Isso dá comb(20,4)*permut(4) = 116 mil
Para cada combinação possível da primeira linha, agora vamos tentar encaixar a primeira coluna:
São três espaços vazios, para encaixar 16 números (ou seja, 20 iniciais – 4 da primeira linha). A soma da coluna tem que dar 42.
O resto do procedimento é igual. Dá comb(16,3)*permut(3) = 3360.
Uma nota importante. Das 116 mil, somente uma fração preenche o critério da soma ser 42. Portanto, esses 3360 testes não são aplicados aos 116 mil, somente ao que passou. Ainda assim, dá um número enorme, mas dessa forma, vamos restringindo o problema.
A seguir, tento preencher a diagonal. Isso porque ela tem só duas casas vazias. É um espaço menor de busca de combinações, mais fácil. Vamos restringindo o problema aos poucos.
A seguir, a segunda coluna.
E assim, sucessivamente.
Com isso, a rotina chegou à diversas soluções:
| 6 | 9 | 10 | 0 | 17 |
| 0 | 20 | 2 | 13 | 7 |
| 18 | 5 | 0 | 16 | 3 |
| 14 | 8 | 19 | 1 | 0 |
| 4 | 0 | 11 | 12 | 15 |
Ou:
| 1 | 2 | 19 | 0 | 20 |
| 0 | 18 | 12 | 3 | 9 |
| 11 | 16 | 0 | 10 | 5 |
| 17 | 6 | 4 | 15 | 0 |
| 13 | 0 | 7 | 14 | 8 |
Ou:
| 2 | 4 | 17 | 0 | 19 |
| 0 | 20 | 5 | 8 | 9 |
| 10 | 15 | 0 | 16 | 1 |
| 18 | 3 | 14 | 7 | 0 |
| 12 | 0 | 6 | 11 | 13 |
Na verdade, a rotina mostrou mais de 30 mil soluções (tinha várias permutações simples das soluções mostradas, e até repetidas).
Mesmo não tendo a elegância de ter solução única, é um desafio computacional interessante.
Download do código (em Python): https://github.com/asgunzi/QuadradoMagicoEsburacado
Veja também:
