As potências de 2 no Quadrado Mágico

[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:

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 March 3, 2013 at 06:16 PM by thoga31
Restrições alteradas

[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

[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?

[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;
}

[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.