Backtracking Algorithm – Magic Square Solver

The purpose of this Python challenge is to demonstrate the use of a backtracking algorithm to solve a Magic Square puzzle.

Did You Know?

A 3×3 magic square is an arrangement of the numbers from 1 to 9 in a 3 by 3 grid, with each number occurring exactly once, and such that the sum of the entries of any row, any column, or any main diagonal is the same.

Backtracking Algorithm

A backtracking algorithm is a recursive algorithm that attempts to solve a given problem by testing all possible paths towards a solution until a solution is found. Each time a path is tested, if a solution is not found, the algorithm backtracks to test another possible path and so on till a solution is found or all paths have been tested.

The typical scenario where a backtracking algorithm is when you try to find your way out in a maze. Every time you reach a dead-end, you backtrack to try another path until you find the exit or all paths have been explored.

Backtracking algorithms can be used for other types of problems such as solving a Magic Square Puzzle or a Sudoku grid.

Backtracking algorithms rely on the use of a recursive function. A recursive function is a function that calls itself until a condition is met.

Note that there are other approaches that could be used to solve the magic square puzzle. The Backtracking approach may not be the most effective but is used in this challenge to demonstrate how a backtracking algorithm behaves and how it can be implemented using Python.

Python Code

Extension Task

Adapt this challenge to implement a backtracking algorithm used to solve a Sudoku grid!