Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como resolver um quadrado mágico 4x4 utilizando algoritmos?

0 votos
103 visitas
perguntada Set 15, 2020 em Ciência da Computação por Rodrigo Stuckert (66 pontos)  
reclassificado Set 24, 2020 por Rodrigo Stuckert

O problema refere-se ao exercício 10, da página 36, do livro The Art of Computer Programming, Volume 4A: Combinatorial Algorithms – Donald E. Knuth.

Compartilhe

1 Resposta

0 votos
respondida Set 15, 2020 por Rodrigo Stuckert (66 pontos)  
editado Dez 15, 2020 por Rodrigo Stuckert

Quadrados mágicos são matrizes quadradas, cuja soma de cada uma de suas linhas, colunas ou diagonais resulte sempre em um mesmo número. De origem remota, o quadrado mágico é um problema que aparece em diferentes culturas, como a chinesa, a árabe e a indiana. Ele é também o símbolo adotado pela Editora 34, conhecida por suas traduções de clássicos da literatura europeia.

A imagem será apresentada aqui.

Curiosamente, estamos interessados na resolução de quadrados mágicos de ordem 4x4 resultando no número 34.

Uma solução bem ineficiente, baseada em busca exaustiva, seria testar todas as permutações possíveis entre os números de 1 a 16 para encontrar quais se enquadram nas regras especificadas. No entanto, teríamos \(P_{16} = 16! \approx 20 \) trilhões de possibilidades para testar, de modo que um computador que realize um milhão de operações por segundo demoraria cerca de 240 dias para encontrar todas as respostas, no pior dos casos! Uma alternativa seria utilizar backtracking.

O que faremos aqui será construir soluções a partir do primeiro dígito, verificando se, até então, a soma de cada linha e coluna não supera o limite máximo estabelecido de 34. A função magic_square cria um vetor que contém todos os números factíveis, bem como uma matriz "possible_solution", que receberá os valores a serem checados.

import numpy as np


def magic_square(n = 4):
    """ Finds one solution to magic squares. 

    n: square side
    """ 
    n_square = n**2 # Max number
    target = ((n_square)*(n_square + 1)/2) / n # Row's / column's target sum
    possible_solution = np.zeros((n, n), dtype = int) # Will receive the tested values

    values = [x for x in range(1, n_square + 1)] # List with all the numbers

    # Does the trick
    solve(possible_solution, values, target, n, level = 0)

    return(None)

A função solve, por sua vez, resolverá o problema de maneira recursiva, interrompendo sua execução quando a variável level atingir o valor 16, ie, quando preenchermos o último espaço disponível. Note que colocaremos um número na matriz somente se sua adição não violar as condições pré-estabelecidas.

def solve(possible_solution, values, target, n, level):
    """ Solves the problem.

    possible_solution: each attempt
    values: all possible values
    target: row's / column's / diagonal's target sum.
    level: tree node level (max level == n_square)
    """
    if level == n**2:
        print("We've found a solution!\n", possible_solution)
        return True
    else:
        for i in values:

            # Gets level's row/column equivalents to fill the "possible_solution" matrix
            row = level // n
            col = level % n

            # Checks whether certain possibity is valid so far or not
            if not(i in possible_solution):
                if is_valid(possible_solution, n, target, row, col, next_number = i):                    
                    possible_solution[row, col] = i

                    # PS: enable the following two lines of code if you want a better understanding of what's going on at each step
                    #print("i:",i,"level:",level,"row:",row,"col:",col)
                    #print(possible_solution)

                    if solve(possible_solution, values, target, n, level + 1):
                        return True

            possible_solution[row, col] = 0 # Backtracking

        return False

Por fim, a função is_valid fará a verificação. O pulo do gato aqui é que ela testará as linhas apenas no momento em que elas forem completamente preenchidas, valendo o mesmo para as colunas e diagonais.

def is_valid(possible_solution, n, target, row, col, next_number):
    """ Checks wheter certain input will be a valid magic square, so far. If so,
    we're allowed to add "next_number" to possible_solution[row, col].

    n: square's side
    row/col: current testing row/col.
    next_number: next number we'll input to possible_solution.
    """                    
    possible_solution[row, col] = next_number

    # Checks rows (If you've reached the end of a row and its sum != target, return FALSE)
    if (col == n - 1) and sum(possible_solution[row,:]) != target:
        return False

    # Checks columns
    if (row == n - 1) and sum(possible_solution[:,col]) != target:
        return False

    # Checks secondary diagonal (does the checking when you reach 1st entry of last line)
    if (row == n - 1) and (col == 0):
        my_sum = 0 
        for i in range(n):
            my_sum += possible_solution[i, n - 1 - i]

        if my_sum != target:
            return False


    # Checks main diagonal (only when you've reached the very last entry)
    if (row == n - 1) and (col == n - 1):
        my_sum = 0
        for i in range(n):
            my_sum += possible_solution[i, i]

        if my_sum != target:
            return(False)


    return(True)


if __name__ == '__main__':    
    n = 4
    magic_square(n)

É possível, ainda, encontrar a solução para qualquer quadrado mágico de tamanho \(n >= 3\) por meio desse código, bastando alterar o valor de \(n\).

Alternativa: todas as soluções

Note, ainda, que é fácil adaptarmos o código para encontrarmos todos os quadrados mágicos possíveis para um n qualquer, bastando remover os valores booleanos atribuídos aos retornos da função solve:

import numpy as np


def magic_square(n = 4):
    """ Finds ALL solutions to magic squares. 

    n: square side
    """ 
    n_square = n**2 # Max number
    target = ((n_square)*(n_square + 1)/2) / n # Row's / column's target sum
    possible_solution = np.zeros((n, n), dtype = int) # Will receive the tested values

    values = [x for x in range(1, n_square + 1)] # List with all the numbers

    # Does the trick
    solve(possible_solution, values, target, n, level = 0)

    return(None)


def solve(possible_solution, values, target, n, level):
    """ Solves the problem.

    possible_solution: each attempt
    values: all possible values
    target: row's / column's / diagonal's target sum.
    level: tree node level (max level == n_square)
    """
    if level == n**2:
        print("We've found a solution!\n", possible_solution)
        pass
    else:
        for i in values:

            # Gets level's row/column equivalents to fill the "possible_solution" matrix
            row = level // n
            col = level % n

            # Checks whether certain possibity is valid so far or not
            if not(i in possible_solution):
                if is_valid(possible_solution, n, target, row, col, next_number = i):                    
                    possible_solution[row, col] = i
                    solve(possible_solution, values, target, n, level + 1)

            possible_solution[row, col] = 0 # Backtracking

    return None


def is_valid(possible_solution, n, target, row, col, next_number):
    """ Checks wheter certain input will be a valid magic square, so far. If so,
    we're allowed to add "next_number" to possible_solution[row, col].

    n: square's side
    row/col: current testing row/col.
    next_number: next number we'll input to possible_solution
    """                    
    possible_solution[row, col] = next_number

    # Checks rows (If you've reached the end of a row and its sum != target, return FALSE)
    if (col == n - 1) and sum(possible_solution[row,:]) != target:
        return False

    # Checks columns
    if (row == n - 1) and sum(possible_solution[:,col]) != target:
        return False

    # Checks secondary diagonal (does the checking when you reach 1st entry of last line)
    if (row == n - 1) and (col == 0):
        my_sum = 0 
        for i in range(n):
            my_sum += possible_solution[i, n - 1 - i]

        if my_sum != target:
            return False


    # Checks main diagonal (only when you've reached the very last entry)
    if (row == n - 1) and (col == n - 1):
        my_sum = 0
        for i in range(n):
            my_sum += possible_solution[i, i]

        if my_sum != target:
            return(False)


    return(True)


if __name__ == '__main__':    
    magic_square(n = 4)
comentou Dez 1, 2020 por Andrei Leite (21 pontos)  
Oá Rodrigo!
Muito didática sua resolução.  Consegui compreender seu código sem muita dificuldade.
Achei interessante a forma como você estruturou a função solve(possible_solution, values, target, n, level). Ficou bastante evidente na sua resolução os passos que o professor cita como resumo da abordagem de Busca Exaustiva para resolução dos problemas: gerar cada elemento do domínio (que você fez criando a lista values = [x for x in range(1, n_square + 1)]); selecionar os elementos que satisfazem as restrições do problema (que são encontrados nesta resolução utilizando a função is_valid); e encontrar o elemento de interesse (que será, no caso, a matriz possible_solution).
A forma como você estruturou esses passos na sua resolução ficou bastante clara, o que me ajudou na compreensão.
Muito interessante também a forma como você estruturou a função is_valid()  com objetivo de testar as linhas apenas no momento em que elas forem completamente preenchidas, valendo o mesmo para as colunas e diagonais.
Como forma de visualizar como você estruturou o loop da função solve, incluí as seguintes linhas de comando na função solve:
            if not(i in possible_solution):
                if is_valid(possible_solution, n, target, row, col, next_number = i):
                    print("i:",i,"level:",level,"row:",row,"col:",col)                    
                    possible_solution[row, col] = i
                    print(possible_solution)
Poder ver em que posição cada i que retornava True na função is_valid entrava na matriz possible_solution e também perceber a variável level sendo acrescida de uma unidade à medida que o loop acontece me ajudou a visualizar a forma que você pensou para resolver a questão. Talvez seja uma boa ideia para outros leitores também.
comentou Dez 15, 2020 por Rodrigo Stuckert (66 pontos)  
Obrigado pela sugestão, Andrei! Adicionei essa observação ao meu código. Abraço!
...