Jump to content
thoga31

As potências de 2 no Quadrado Mágico

Recommended Posts

thoga31

Este é mais um desafio simples mas que acho divertido. Tem resolução por brute force ou por métodos matemáticos.

Descrição: são vários os exercícios e jogos que envolvem os chamados quadrados mágicos. Estes são quadrados, geralmente 3x3, cujos elementos, em determinada ordem, cumprem determinados requisitos. Por exemplo:

200px-Magicsquareexample.svg.png

Objectivo: Considere-se as primeiras 9 potências de 2: [1,2,4,8,16,32,64,128,256]. Considere-se um quadrado mágico de 3x3. Pretende-se saber qual o quadrado mágico que, quando preenchido com estes números, os produtos das linhas, colunas e diagonais sejam iguais.

Restrições: Não podem partir do quadrado mágico dito "convencional" (imagem anterior) para dar a solução. Isso é considerado fraude. Se querem evitar brute force, apliquem raciocínio matemático.

Devem-se excluir repetições e quadrados invertidos. Para ser mais claro com exemplos:

Invertidos:
2 7 6  |  8 3 4
9 5 1  |  1 5 9
4 3 8  |  6 7 2

Linhas vs colunas:
2 7 6  |  2 9 4
9 5 1  |  7 5 1
4 3 8  |  6 1 8

Espelho:
2 7 6  |  6 7 2
9 5 1  |  1 5 9
4 3 8  |  8 3 4

Tudo isto são consideradas repetições. Isto porque existe uma solução única e que, se o output inicial não for "tratado", poderá dar umas 8 soluções possíveis mas que são o mesmo.

Verifiquem que outras situações podem existir que levam à multiplicidade de soluções. Analisem bem o caso e vejam a forma mais eficaz de os eliminar.

Edited by thoga31
Restrições alteradas

Knowledge is free!

Share this post


Link to post
Share on other sites
thoga31

import Data.List (permutations)

magicSquare = head . filter condition . map setTri . permutations . map (2^) $ [0..8]
 where
 setTri [] = []
 setTri (a:b:c:xs) = [[a, b, c]] ++ setTri xs

 condition xs = line xs && row xs && diagonal xs
   where
   line (x:[]) = True
   line (x:xs) = (product x) == (product . head $ xs) && (line xs)

   row ((x:[]):(y:[]):(z:[]):_) = True
   row (x:y:z:_) = (product . map head $ [x, y, z]) == (product . map middle $ [x, y, z]) && (row . map tail $ [x, y, z])

   diagonal (a:b:c:_) = product [head a, middle b, last c] == product [last a, middle b, head c]

   middle = head . tail


main = mapM_ print magicSquare

http://ideone.com/3jSRro


Knowledge is free!

Share this post


Link to post
Share on other sites
polska

Eu não estou a perceber uma coisa.. Ao usarmos essas restrições encontramos apenas uma solução certo? Então o nosso programa mal encontre a primeira solução imprime e termina, não é necessário continuar pois só vai encontrar a mesma solução em repetições.. Ou estou há algo que me está a escapar?


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
HappyHippyHippo

Tem resolução por brute force ou por métodos matemáticos.

desta vez decidi em vez de apresentar os cálculos matemáticos, apresentar por aplicação:

#include <stdio.h>

int main()
{
 char magic[3][3] = {{2, 7, 6},
                     {9, 5, 1},
                     {4, 3, 8}}; // quadrado mágico convencional
 int i, j;

 for (i = 0; i < 3; i++)
 {
   for (j = 0; j < 3; j++)
   {
     printf("%3d ", 1 << (magic[i][j] - 1));
   }
   printf("\n");
 }

 return 0;
}


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
thoga31

Se assim o pedem...

Restrições: Não podem partir do quadrado mágico dito "convencional" (imagem anterior) para dar a solução. Isso é considerado fraude. Se querem evitar brute force, apliquem raciocínio matemático.

Eu não estou a perceber uma coisa.. Ao usarmos essas restrições encontramos apenas uma solução certo? Então o nosso programa mal encontre a primeira solução imprime e termina, não é necessário continuar pois só vai encontrar a mesma solução em repetições.. Ou estou há algo que me está a escapar?

É exactamente esse o ponto: tu irias encontrar 8 soluções, e essas 8 são todas equivalentes. Logo, o truque está em parar a análise assim que se encontra uma solução.

É por isso que na minha solução utilizei a função head: aproveitando a característica do Haskell de ser lazy, assim que o processo devolva uma solução, ele pára, pois essa primeira solução é a "cabeça" da lista total de soluções.


Knowledge is free!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.