Quand c'est carré et c'est magique... c'est un carré magique

Cette semaine, c'est Yann qui vous propose un #KataOfTheWeek : Carré Magique

Briefing du Kata : Tu te souviens des carrés magiques qu'on faisait au primaire ?
Non ? Alors voici un petit rappel : Un carré magique est une matrice NxN contenant des nombres où :

• Toutes les lignes, colonnes et diagonales ont la même somme.
• Chaque nombre est unique

Le plus connu est le carré magique 3x3 avec les valeurs [1,2,3,4,5,6,7,8,9 ], et ou les sommes doivent être égales à 15.

Sais-tu trouver un programme qui résout ce carré magique ? Est-il extensible aux carrés NxN ?

Saurez-vous résoudre le problème ?

Bon courage !

Et voici une solution proposée par l'auteur en Python:

SIZE = 3
matrix = [[0 for i in range(SIZE)] for k in range(SIZE)] #Fill matrix with 0
current_i = 0
current_j = 0

remaining = [i for i in range(1, SIZE * SIZE + 1)]
tested = []
put = []
MAGIC_SUM = sum(remaining) / SIZE #Expected sum for lines/columns and diagonals

def run():
    global matrix

    if not remaining:
        previous_square()
        reset_left()
    else:
        put_remaining_value()
        if magic_broken():
            remove_value()
            if not remaining:
                previous_square()
                reset_left()
        else:
            next_square()
            reset_right()


def reset_left():
    """Reset tested/remaining values"""

    global tested, remaining
    current_val = matrix[current_i][current_j]
    remove_value()
    tested = [i for i in range(1, current_val + 1)]
    remaining = [i for i in range(1, SIZE * SIZE + 1) if i not in tested and i not in put]


def reset_right():
    """Reset tested/remaining values"""

    global tested, remaining
    tested = []
    remaining = [i for i in range(1, SIZE * SIZE + 1) if i not in tested and i not in put]


def remove_value():
    """Remove current placed value"""

    global tested, remaining
    val = matrix[current_i][current_j]
    matrix[current_i][current_j] = 0
    tested.append(val)
    put.remove(val)


def put_remaining_value():
    """Put in current position next available value"""

    global matrix
    val = remaining.pop(0)
    put.append(val)
    matrix[current_i][current_j] = val


def magic_broken():
    """Check if the magic square is broken (ie: any addition > MAGIC_SUM)"""

    # Return true if any line, column or diagonal is broken
    return len([line for line in matrix if direction_broken(line)]) != 0 \
           or direction_broken([matrix[i][i] for i in range(SIZE)]) \
           or direction_broken([matrix[i][SIZE - 1 - i] for i in range(SIZE)]) \
           or True in [direction_broken([matrix[i][j] for i in range(SIZE)]) for j in range(SIZE)]


def direction_broken(elements: list):
    """Check if the magic is broken for direction (line/col/diag)"""
    total = sum(elements)
    if total > MAGIC_SUM:
        return True
    return (total == MAGIC_SUM) == (0 in elements)


def previous_square():
    """Move to the previous square"""

    global current_i, current_j
    current_j -= 1
    if current_j < 0:
        current_j = SIZE - 1
        current_i -= 1


def next_square():
    """Move to the next square"""

    global current_i, current_j
    current_j += 1
    if current_j >= SIZE:
        current_j = 0
        current_i += 1


def display():
    for i in range(SIZE):
        print(matrix[i])


if __name__ == '__main__':
    while matrix[-1][-1] == 0:  # While last square is empty
        run()
    display()

Votre TakiVeille