Gostaríamos de parabenizar a todos que se desafiaram a solucionar o Giant Puzzle #3! Admiramos imensamente aqueles que se arriscam a pensar fora da caixa e a encontrar soluções criativas para problemas complexos.

Conseguiram resolver esse puzzle: Guilherme Sá, João Vieira, Lucas Gregolin Dias, Fabio Nassar, Lucas Sobrinho, Daniel Ramos, Guilherme Echelmeier, André Lorenzo Bittencourt, Vitor Santa Rosa, Gabriel Sarkis, Bruno Sphair, Fabio Reale, Felipe Buzato, Matheus Laranja, Hugo Ricardo Matarozzi, João Chaves, Raffaello Caser, Victor Abicalil, Felipe Moret, Luiz Castelo Branco, Alexander Costa Nunes, Paulo Ricardo Lira, João Pedro Candido, Caio Botelho Gomes, Felipe Penna, Erick Amaral Costa, Alexandre Cesar, Fabio Fernandes, Thiago Rissotto, Fabrizio Bernardi, Victor Seixas e Karina Suemi Awoki.

O problema

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

Resoluções

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.

Práticas

“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.”

– ANDRÉ LORENZO

Resolução completa >

Descritivas

“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… “

– KARINA AWOKI

Resolução completa >

“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.”

– FABIO REALE

“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.”

– THIAGO RISSOTTO

“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.”

– FELIPE MORET

“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.”

– PAULO LIRA

“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.”

– DANIEL RAMOS

“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.”

– FELIPE PENNA

“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.”

– GUILHERME ECHELMEIER

“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.”

– JOÃO CHAVES

Acesse o Giant Puzzle mais recente.

Puzzle,Artigos gerais

Solução do Giant Puzzle #3 – Sudoku

O problema

Resoluções

Giant Steps

Deixe um comentário Cancelar resposta

DOWNLOADS

FORMULÁRIO DE REFERÊNCIA

FALE CONOSCO

RECEBA NOSSAS ATUALIZAÇÕES E MATERIAIS

SIGA-NOS

NOSSOS FUNDOS TAMBÉM ESTÃO NAS CORRETORAS

AXIS

DARIUS

SIGMA

ZARA

GIANT PREV

SATOSHI

O problema

Resoluções

Giant Steps

Deixe um comentário Cancelar resposta

Selecione um dos fundos abaixo.

AXIS

DARIUS

SIGMA

ZARA

GIANT PREV

SATOSHI