As regras normais do sudoku são aplicáveis. Além disso, o setor em destaque é um quadrado mágico* e os números externos ao grid representam os divisores dos números de 9 dígitos, quando lidos naquela direção.
Exemplo:
2 é divisor de 843791652
1091 é divisor de 256197348
Qual o maior número primo que divide o número formado pelos 9 elementos da diagonal principal do grid?
*A soma dos números das colunas, linhas e diagonais é igual
Foram diversas estratégias de resolução diferentes submetidas e vamos resumir aqui algumas delas, demonstrando como pensar fora da caixa e de maneira criativa aproximou cada um da resolução correta do problema.
Resoluções Práticas
André Lorenzo
Comecei fazendo um programa para gerar e testar soluções candidatas. Ela preenche aleatoriamente com os números faltantes na linha/coluna e checa se as divisões são inteiras. Então fui para o quadrado mágico, que eu achei que teria um numero mais limitado de soluções e testei a linha central, limitando à dois quadrados. Segui para coluna 127/877 e continuei testando. Eventualmente segui a lógica de um jogo de Sudoku para conseguir mais quadrados e a testar as linhas/colunas. Até que, quase completando todo o Sudoku, cheguei num ponto em que as linhas/colunas tinham muitas soluções cada. Fui por outro caminho e vi que só tinham 3 quadrados completos possíveis, pelas regras do Sudoku. Testei cada um dos três no programa e felizmente só uma era aceitável. Depois foi só rodar uma rotina de fatoração.
João Vieira
O principal método foi programação inteira.
Lucas Dias
Utilizado algoritmo recursivo em Python + Numba
Lucas Sobrinho
Escrevi um código em Python para resolver o desafio do Sudoku. Consegui reduzir a uma única solução para a tabela: a diagonal sendo 219456894, que possui como fatores primos 2, 3, 61, 109, 5501. Logo, a resposta procurada é: 5501.
Raffaello Caser
Puzzle resolvido usando Python.
Vitor Santa Rosa
Fiz uma busca simples com umas heurísticas para otimizar o problema. Fiz um código que roda em 10 minutos.
Victor Seixas
Minha solução foi um híbrido de análise manual e automatizada. Eu fiz um script em Python que em que eu listava as restrições para uma linha e obtinha as opções. Uma vez que determinava mais células, manualmente modificava o código.
Resoluções Descritivas
Gabriel Sarkis
Valeu pelo puzzle, esse foi bem divertido solucionar. Anexei uma explicação da linha de pensamento que usei para resolver o problema.
Alexander Nunes
Usei Python e Jupyter Notebook com as bibliotecas itertools e pandas
Karina Awoki
a) Com os números externos obtive as seguintes informações:
– os múltiplos de 5 terminam em 5
– os múltiplos de 125 terminam em 25 ou 75
– os múltiplos de 2, 4, 8 terminam em par (diferente de zero)
– os múltiplos de 4 terminam em 4 ou 8 dado que, nesse sudoku, o penúltimo dígito…
Alexandre Cesar
Resolvi então usando MiniZinc, que é uma linguagem de constraint programming. Programei os requisitos de Sudoku, divisibilidade e quadrado mágico, com isso obtive a solução do Sudoku e depois foi só fatorar a diagonal.
Fabio Reale
Bom, de início observei que 3 dos 5s eram muito evidentes: o do meio pelo quadrado mágico, os outros 2 por divisibilidade por 5 (e não existência de 0s no Sudoku). Após esse breve início, segui uma estratégia de ver quais regras de divisibilidade criavam mais restrições e ir eliminando possibilidades dessa forma. Pude regras de divisibilidade para quaisquer números, mas com primos grandes é mais prático escrever um programa pra calcular, então escrevi um que me permitia acrescentar as restrições impostas pelo Sudoku nas regras de divisibilidade, devolvendo uma lista com as possibilidades. Eu então verificava se as soluções criavam novas restrições e atualizava as restrições até sobrar apenas uma opção.
Thiago Rissotto
Para resolver eu fiz um programa em Python para gerar todos os múltiplos de 9 dígitos dos números que estavam externos ao grid, e um outro programa para testar os números resolvendo o Sudoku. Fui filtrando os múltiplos que não serviam no problema até que encontrei uma solução final possível e estava realmente certa.
Felipe Moret
Em todo o processo, basicamente escrevi programas em C++ para computar certas restrições, e com isso ir descobrindo algumas linhas até a solução ser única. Para isso:
– Descobri todas as 8 possibilidades de quadrados mágicos 3×3;
– Usando a linha do 29 e 79 consegui determinar o unico quadrado mágico
compativel com o problema;
– Fiz um programa para gerar todas as permutações dos números de 1 a 9;
– Após, escrevi alguns programas auxiliares para filtrações as possíveis permutações para cada linha;
– A cada próximo passo e a cada novo quadradinho preenchido eu atualizava as permutações com uma restrição adicional, algumas acabavam por ter apenas uma única permutação possível;
– A linha do 11 e 5, e a linha do 127 e 877 foram mais fáceis, restando apenas poucos candidatos ao fim.
Paulo Lira
Não utilizei um algoritmo ou técnica específica. A chave foi o quadrado mágico. Na largada dá para saber que o centro é 5. O que demorei para perceber foi que as posições de “esquinas” são obrigatoriamente 2, 8, 4 e 6 e as adjacentes ao 5 são 1, 9, 3 e 7. Com isso, ficou mais fácil restringir a linha central dentre as possibilidades de múltiplos de 29 e 79. Em seguida ficou fácil encontrar a 7ª coluna dadas pequenas restrições. Depois fui trabalhando com os pequenos dados (múltiplo de 125, poucas possibilidades de primeira coluna, vários pontos do mapa terminam em pares, etc.). Para encontrar os possíveis valores de linha ou coluna com múltiplos fiz um pequeno código em Python. E adicionava restrições quando pertinentes.
Daniel Ramos
Eu não usei nenhum método específico. De início eu reduzi bastante o número de casos usando a informação do quadrado mágico e dos divisores dos números formados pelas linhas/colunas, mas sem ajuda de um Sudoku solver. Depois disso eu usei as informações que eu ainda não tinha usado antes dada pelos divisores para encontrar a solução adequada a todas as restrições usando um Sudoku solver.
Felipe Penna
Fiz um código em Python rápido para os testes dos divisores das linhas comparando os resultados entre as linhas com divisores mais óbvios (os maiores). Achei que já ia ter dado para pegar alguns dados, mas foi preciso rodar algumas modificações a mão para descobrir as possibilidades das outras colunas (com divisores menores, ou que só possuíam um divisor). Dessa forma comparei os resultados e fui “inputando” as regras do Sudoku de cabeça mesmo. Depois de algumas linhas/colunas, foi só combinar as regras do Sudoku com a de algumas colunas (divisor ser par) para fechar o Sudoku. Após foi só pegar os primos divisores.
Guilherme Echelmeier
Alguns números são óbvios, por conta da regra de divisibilidade por 5. O número do meio do grid também tem que ser 5, para que a soma das linhas, colunas e diagonais do quadrado do meio seja igual (quadrado mágico). E nesse quadrado mágico, a soma das linhas, colunas e diagonais tem que ser igual a 15. O passo seguinte foi testar as possibilidades para a 7ª coluna (da esquerda pra direita). A princípio, essa coluna teria 9! possibilidades diferentes (permutação dos números de 1 a 9). Dessas 9! possibilidades, imaginei que poucas conseguiriam satisfazer a condição de ser divisível por 877 em um sentido e 127 no outro sentido (e de não conter nenhum número 5 no quadrado do canto superior direito, pois já tinha um número 5 lá). Então testei as possibilidades com algumas linhas de código em Python e cheguei em poucas opções. Fazendo a mesma coisa para a 5ª linha (e inserindo as outras condições que eu já sabia: número do meio era 5 e soma dos 3 números do meio era 15), também cheguei em poucas opções. Cruzando os dois resultados (considerando que a 7ª coluna e a 5ª linha têm um número em comum), cheguei em uma única configuração possível. Com isso, também consegui resolver o quadrado mágico. Então basicamente essa foi a estratégia: eu tentava resolver o máximo possível do jeito “convencional” e, quando não conseguia mais avançar, escolhia alguma linha ou coluna e testava com Python as possibilidades para os divisores que eram fornecidos (e eliminando as opções em que repetia números na mesma linha, coluna ou dentro do mesmo quadrado). Depois, tentava mais um pouco do jeito “convencional” e eventualmente usava Python pra testar outra linha ou coluna, até que eventualmente achei todos os números.
João Chaves
Neste puzzle acabei utilizando um pouco de força bruta’, onde fiz um script em Python que me voltasse com todas combinações possíveis de números entre 123456789 e 987654321 que fossem divisíveis pelos números indicados e que seus inversos fossem divisíveis ao mesmo tempo pelo número na outra ponta da tabela (Ex: Na linha central peguei todas as combinações divisíveis por 29 e que seus inversos fossem divisíveis por 79). Depois desse primeiro filtro’, comecei a entrar mais no específico de cada linha, como nesse exemplo entre (29,79), dado que ele cruzava o centro do quadrado mágico, eu teria certeza que a linha correta teria nos seus números centrais uma das possíveis combinações [357’, 753’, 951’,’159]. Fazendo dessa forma, o programa acabava me dando como output poucas possibilidades, às vezes até me resultava em um único valor, ou me resultava um conjunto de números que possuíam algum número em comum em uma determinada posição. Foi assim que fui fazendo para o restante, porém em casos em que eu teria poucas combinações para filtrar, eu fazia listas de combinações de números que não poderiam ser em certas posições.