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
