Backtracking: Solving Magic Squares

• Download source code - 3.5 KB

Introduction

Backtracking is a programming technique used to solve problems for which there are no known solutions. An example of a problem with a known solution is the computation of the sum of the first N integers, starting at 1. It is easily implemented as:

int sum = 0;

for ( int i = 1; i <= N; ++i )
{
   sum += i;
}

Of course, a more efficient way to compute the sum is to use the formula N * (N + 1) / 2, which can be proved by induction on N.

Magic Squares

A magic square is an N x N array of numbers in the range 1, 2, ..., N² such that each element of the array contains a unique number (no repetitions) and the sums in each row, column and both of the main diagonals are the same. The following figure, taken from Wikipedia, shows a 3 x 3 magic square where the sums equal 15:

The sum is called the magic number. This is a problem for which there is no ready-made solution, and it must be solved by trial and error.

A Naïve Approach to the Solution of Magic Squares: Permutations

One possible approach to solve magic squares is by generating permutations of the range 1, 2, ..., N² for an N x N square. The general idea is to generate a permutation, dump it into a square array row-by-row, and test whether the numbers in the array satisfy the row, column, and diagonal sum requirements for the given magic number. This idea looks reasonable, but the problem is that, in the worst case, ALL the permutations of the range will have to be generated, for it may well be the case that the solution of the magic square is the very last permutation of the range.

All the permutations of N² numbers are generated in N²! time, where “!” denotes the factorial function. As its argument becomes larger, the factorial function grows faster than exponential functions. For a 3 x 3 square,

9! = 362,880 permutations; for a 4 x 4 square, 16! = 20,922,789,888,000 permutations; and for a 5 x 5 square, 25! = 1.551121E25, where “E25” means that 1551121 is followed by 19 zeros. Clearly, the approach of generating permutations to solve magic squares must be replaced by another trial-and-error method, that is, backtracking.

A C# Program to Solve Magic Squares by Means of Bactracking

Given an N x N magic square and a magic number M, the general procedure is to place the numbers 1, 2, ..., N² in the array elements and to verify that the placement satisfies the requirements for the row, column and diagonal sums being all equal to M. If the requirements are met the problem is solved; if not, another arrangement must be attempted by undoing the last placement(s) and placing different number(s). Thus, by necessity, both the attempt to a solution and the backtracking steps are recursive in nature.

The modules of the program will be described in a piecewise fashion, that is, from the bottom up. The complete program, implemented as a C# console application, is in the ZIP file attached to the article. To begin with, all the data structures and variables to be used must be defined. The following class is defined within the MagicSquare namespace and is useful to define different magic squares simultaneously.

// Class to encapsulate the parameters of a magic square

public class Parameters
{
   // Properties

   public int N { get; set; }             // Size of the square.
   public int Nsquare { get; set; }       // Upper limit of the range of numbers.
   public int MagicNumber { get; set; }   // The magic number for the square.
   public bool ShowStep { get; set; }     // Control whether or not to display
                                          // the placement/removal of numbers

   // Standard constructor

   public Parameters( int n, int magicNumber, bool showStep = true )
   {
      N = n;
      Nsquare = N * N;
      MagicNumber = magicNumber;
      ShowStep = showStep;
   }

   // Abbreviated constructor

   public Parameters( int n, bool showStep = true )
   {
      N = n;
      Nsquare = N * N;
      // Compute magic number if not provided
      MagicNumber = N * ( Nsquare + 1 ) / 2;
      ShowStep = showStep;
   }

   // Function to validate the magic number

   public bool IsValidMagicNumber()
   {
      return MagicNumber == N * ( Nsquare + 1 ) / 2;
   }// IsValidMagicNumber
}// Parameters (class)

The following variables are defined within the class Program:

static int[ , ] square;      // Array to store the solution.
static int row,              // Row index into 'square'.
           col;              // Column index into 'square'.
static bool done;            // Flag to signal successful termination.
static ulong steps;          // Count of steps taken toward the solution.
static Queue<int> numbers;   // Queue to hold numbers that have not been placed
                             // and to recycle numbers that are removed.

// Variables to collect timing information.

static DateTime startTime, endTime;

All the functions to be described next are also within the class Program. When a magic square has been defined, the first function that comes to mind is one to attempt to solve the square if the magic number is valid.

static void SolveSquare( Parameters _params )
{
   if ( !_params.IsValidMagicNumber() )
   {
      Console.WriteLine( "\nNo solution for N = {0} and invalid Magic number = {1}\n",
                         _params.N, _params.MagicNumber );
   }
   else
   {
      square = new int[ _params.N, _params.N ];
      numbers = new Queue<int>();

      InitializeSquare( _params );

      // For no particular reason, insert the numbers in the range 1 .. N ^ 2
      // in reverse order.

      for ( int i = _params.Nsquare; i > 0; --i )
      {
         numbers.Enqueue( i );
      }
      steps = 0L;
      row = col = 0;
      done = false;
      startTime = DateTime.Now;

      PlaceNumber( _params );
      endTime = DateTime.Now;

      if ( !done )
      {
         Console.WriteLine( "\n\n{0} steps", steps );
         Console.WriteLine( "\nNo solution for N = {0} and Magic number = {1}\n",
                            _params.N, _params.MagicNumber );
      }
      ReportTimes( startTime, endTime );
   }
}// SolveSquare

Function InitializeSquare sets all the elements of the square to zero, to indicate that no numbers have been placed, and will not be reproduced here. The key function is PlaceNumber which is responsible for the placement of numbers when attempting a solution, the recycling of numbers already placed, and the removal of numbers during backtracking. If the field ShowStep in the parameters argument to function PlaceNumber is set to true, the notation ".{0} " in the call to the Console.Write statement indicates that a number has been placed in the square, while the notation "<{0} " indicates that a number has been removed from the square.

static void PlaceNumber( Parameters _params )
{
   int k, n, m, e;

   // As long as there are numbers to be placed, and the
   // (row, col) coordinates are within the limits of the
   // square (ValidPosition == true), attempt to place a number.

   if ( ( numbers.Count > 0 ) && ValidPosition( _params ) )
   {
      n = numbers.Count;
      k = 0;
      do
      {
         m = numbers.Dequeue();          // Remove number at the head.
         if ( ( e = square[ row, col ] ) != 0 )
         {
            numbers.Enqueue( e );        // Recycle the current number.
         }
         square[ row, col ] = m;         // Put the dequeued number in its place.
         if ( _params.ShowStep )
         {
            Console.Write( ".{0} ", m ); // number placed
         }
         ++k;
         ++steps;
         if ( SquareOK( _params ) )
         {
            if ( numbers.Count == 0 )
            {
               done = true;
               ShowSquare( _params );
            }
            else
            {
               NextPosition( _params );  // Compute next (row, col) coordinates.
               PlaceNumber( _params );   // Recursively place another number.
            }
         }
      } while ( k < n && !done );
      // k == n || done

      if ( !done )  // backtrack
      {
         numbers.Enqueue( square[ row, col ] ); // Recycle the number at the
                                                //  current position.
         if ( _params.ShowStep )
         {
            Console.Write( "<{0} ", square[ row, col ] ); // number removed
         }
         square[ row, col ] = 0;
         PreviousPosition( _params ); // Compute previous (row, col) coordinates.
      }
   }
   // numbers.Count == 0 || !ValidPosition( _params )
}// PlaceNumber

Function SquareOK checks whether the sums in all rows (HorizontalCheck), all columns (VerticalCheck) and the main diagonals (Diagonal_1_Check) and (Diagonal_2_Check) are equal to the magic number, that is whether the square is a magic square. If so, the variable done is set to true to signal termination, and the magic square is displayed by function ShowSquare. If the square is not magic, the last placement(s) of numbers are recursively undone (backtracked) to attempt placing other numbers at the front of the queue numbers.

static bool SquareOK( Parameters _params )
{
   int row = 0, col = 0, n = _params.N;

   while ( row < n && HorizontalCheck( _params, row ) )
   {
      ++row;
   }
   while ( col < n && VerticalCheck( _params, col ) )
   {
      ++col;
   }
   return row == n && col == n
          && Diagonal_1_Check( _params ) && Diagonal_2_Check( _params );
}// SquareOK

The four sum-checking functions return the result of calling function IndexAndSumOK, which determines whether there have been no placements of numbers, or placement is in progress or placement is complete in their respective direction.

static bool IndexAndSumOK( Parameters _params, int index, int sum )
{
   int n = _params.N, magicNr = _params.MagicNumber;

   return sum == 0 // No numbers have been placed in a particular direction
          ||
          ( index < n && sum < magicNr )    // Placement of numbers in progress
          ||
          ( index == n && sum == magicNr ); // Placement complete
}// IndexAndSumOK

As two examples, functions HorizontalCheck and Diagonal_1_Check are defined as follows:

static bool HorizontalCheck( Parameters _params, int row )
{
   int col = 0, e, s = 0;

   while ( col < _params.N && ( e = square[ row, col ] ) != 0 )
   {
      s += e;
      ++col;
   }
   return IndexAndSumOK( _params, col, s );
}// HorizontalCheck

static bool Diagonal_1_Check( Parameters _params )
{
   int row = 0, e, s = 0;

   while ( row < _params.N && ( e = square[ row, row ] ) != 0 )
   {
      s += e;
      ++row;
   }
   return IndexAndSumOK( _params, row, s );
}// Diagonal_1_Check

Functions NextPosition and PreviousPosition, called by function PlaceNumber, follow a row-major traversal of the square, respectively during placement of numbers and during backtracking of placements.

static void NextPosition( Parameters _params )
{
   if ( col == _params.N - 1 )
   {
      col = 0;
      ++row;
   }
   else // col < _params.N - 1
   {
      ++col;
   }
}// NextPosition

static void PreviousPosition( Parameters _params )
{
   if ( col == 0 )
   {
      col = _params.N - 1;
      --row;
   }
   else // col > 0
   {
      --col;
   }
}// PreviousPosition

All the functions that have not been reproduced here are easy to follow in the complete program in the ZIP file. To demonstrate the operation of the program, consider the definition of the following variables at the top of the class Program.

static Parameters _3x3_params_1 = new Parameters( 3, 15 );      // solution
static Parameters _3x3_params_2 = new Parameters( 3, 17 );      // no solution
static Parameters _4x4_params = new Parameters( 4, false );     // solution

Then, the execution of function SolveSquare on each of them by function Main:

static void Main( string[] args )
{
   SolveSquare( _3x3_params_1 );
   SolveSquare( _3x3_params_2 );
   SolveSquare( _4x4_params );
}// Main

produces the following output:

.9 .8 .7 .6 .5 .4 .3 .2 .1 .8 .7 .6 .4 .3 .2 .8 .7 .6 .2 <2 .7 .6 <6 .2 .8 .7 .6 .3 <3 
.8 .7 .6 <6 .3 .2 .8 .7 .6 .4 <4 .8 .7 .6 .4 .2 .8 .7 .6 .2 <2 .7 .6 <6 <4 .2 .8 .7 .6 
.4 .3 .8 .7 .6 <6 .3 .8 .7 .6 .4 <4 <3 <2 .8 .7 .6 <6 .4 .3 .2 .1 .8 .7 .6 .5 .3 .8 .7 
.6 <6 .3 .8 .7 .6 .5 <5 <3 .8 .7 .6 .5 .3 .1 .8 .7 .6 .1 .8 <8 .6 <6 .1 .8 .7 .6 .3 <3 
.8 .7 .6 <6 .3 .1 .8 .7 .6 .5 <5 .8 .7 .6 .5 .1 .8 .7 .6 .1 .8 <8 .6 <6 <5 <3 .1 .8 .7 
.6 .5 <5 .3 .2 .1 .8 .7 .6 .5 .4 <4 .2 .1 .8 .7 .6 .5 .4 .3 .1 .8 .7 .6 .5 <5 .8 .7 .6 
.5 .1 .8 .7 .6 .1 .8 <8 .6 <6 <5 .1 .8 .7 .6 .5 .3 .8 .7 .6 <6 .3 .8 .7 .6 .5 <5 <3 .8 
.7 .6 .5 .3 .1 .8 .7 .6 .1 .8 <8 .6 <6 .1 .8 .7 .6 .3 <3 .8 .7 .6 <6 <5 .3 <3 .1 .8 .7 
.6 .5 .4 .3 .2 .8 .7 .6 .2 <2 .7 .6 <6 .2 .8 .7 .6 .3 <3 .8 .7 .6 <6 .3 .2 .8 .7 .6 .4 
<4 .8 .7 .6 .4 .2 .8 .7 .6 .2 <2 .7 .6 <6 <4 .2 .8 .7 .6 .4 .3 .8 .7 .6 <6 .3 .8 .7 .6 
.4 <4 <3 .8 .7 .6 <6 .4 .3 .2 <2 <1 .8 .7 .6 .5 .4 .3 .2 .1 .9 .7 .5 .4 .3 .2 .9 .7 <7 
.3 .2 .9 .7 .4 .2 .9 <9 .4 <4 .2 .9 .7 .4 .3 <3 .9 .7 <7 .4 .3 .2 .9 .7 .5 <5 .2 .9 .7 
.5 .3 <3 .7 .5 .3 <3 .9 .7 .5 .3 .2 .9 .7 <7 <5 .3 .2 .9 .7 .5 .4 <4 .9 .7 .5 .4 .2 .9 
.7 .4 .2 .9 <9 <7 .4 .2 .9 .7 .5 <5 <4 .2 .9 .7 .5 .4 .3 .9 .7 <7 .4 .3 .9 .7 .5 .3 <3 
.7 .5 <5 .3 .9 .7 .5 .4 <4 <3 <2 .9 .7 <7 .5 .4 .3 .2 .1 .9 .7 .6 .4 .3 .9 .7 <7 .4 .3 
.9 .7 .6 <6 .3 .9 .7 .6 .4 <4 <3 .9 .7 .6 .4 .3 .1 .9 .7 <7 .3 .1 .9 .7 .4 <4 .1 .9 .7 
.4 .3 <3 .9 .7 <7 .4 .3 .1 .9 .7 .6 <6 .1 .9 .7 .6 .3 <3 .9 .7 .6 .3 .1 .9 .7 <7 <6 .3 
.1 .9 .7 .6 .4 <4 .9 .7 .6 .4 .1 .9 .7 <7 .4 .1 .9 .7 .6 <6 <4 <3 .1 .9 .7 .6 <6 .4 .3 
.2 .1 .9 .7 .6 .5 <5 .9 .7 .6 .5 .1 .9 .7 .5 .1 .9 <9 <7 .5 .1 .9 .7 .6 <6 <5 .1 .9 .7 
.6 .5 .2 .9 .7 <7 .5 .2 .9 .7 .6 .2 <2 .7 .6 <6 .2 .9 .7 .6 .5 <5 <2 .9 .7 .6 .5 .2 .1 
.9 .7 <7 .2 .1 .9 .7 .5 .1 .9 <9 .5 <5 .1 .9 .7 .5 .2 <2 .9 .7 <7 .5 .2 .1 .9 .7 .6 <6 
.1 .9 .7 .6 .2 <2 .7 .6 .2 <2 .9 .7 .6 .2 .1 .9 .7 <7 <6 <5 .2 .1 .9 .7 .6 .5 <5 .3 .2 
.1 .9 .7 .6 .5 .4 .2 .1 .9 .7 .6 .5 <5 .9 .7 .6 .5 .1 .9 .7 .5 .1 .9 <9 .1 .9 <9 <7 .5 
.1 .9 .7 .6 <6 <5 .1 .9 .7 .6 .5 .2 .9 .7 <7 .5 .2 .9 .7 .6 .2 .7 .2

N = 3

Magic number = 15

8 3 4
1 5 9
6 7 2

567 steps

End time: 7:09:04 AM

Start time: 7:09:04 AM

Elapsed time: 0 0:0:0 136 ms

No solution for N = 3 and invalid Magic number = 17

N = 4

Magic number = 34

16 15  2  1
 6  3 14 11
 8  9  5 12
 4  7 13 10

237,300 steps

End time: 7:09:04 AM
Start time: 7:09:04 AM

Elapsed time: 0 0:0:0 455 ms

Press any key to continue . . .

Solving Magic Squares by Generating Permutations

Just for the sake of comparison against backtracking, this section describes the implementation of the solution of magic squares by generating permutations of the numbers in the range of a magic square. All the code dealing with permutations is after function ReportTimes. The variables required to generate permutations are as follows:

static ulong count;             // Count of permutations generated.
static int[] source;            // Array to generate permutations in-situ.
static ulong countAtSolution;   // Value of 'count' when first solution found.
static DateTime timeAtSolution; // Time when first solution found.

static bool abort;              // Flag to stop recursive function 'Permute'.

Similar to the driver function SolveSquare in the case of backtracking, function Permutations drives the generation of permutations. It initializes the variables used, in particular, the array to store the permutations, and then calls function Permute.

static void Permutations( Parameters _params )
{
   int n = _params.N;

   count = 0L;
   InitializeSource( _params.Nsquare );
   square = new int[ n, n ];
   abort = false;

   startTime = DateTime.Now;

   Permute( _params, source, 0, _params.Nsquare );

   endTime = DateTime.Now;

   Console.WriteLine( "\n{0} permutations\n", count );

   ShowSquare( _params );
   ReportTimes( startTime, endTime );
}// Permutations

Function Permute uses the array source to generate in-situ (that is, in place) all the permutations of the numbers stored in the array if it is not stopped. Since the objective is to find the first solution to the magic square, variable abort is used to stop the function.

// Function 'Permute', if not stopped, recursively generates ALL the
// permutations of the elements in its 'array' argument.

static void Permute( Parameters _params, int[] array, int k, int n )
{
   int i;

   if ( k == n ) // Permutation complete.
   {
      ++count;
      PrintArray( array, n );

      ArrayToSquare( _params, array, n );
      if ( SquareOK( _params ) )
      {
         countAtSolution = count;
         timeAtSolution = DateTime.Now;
         abort = true;              // Only one solution is necessary.
      }
   }
   else // k < n
   {
      for ( i = k; i < n; ++i )
      {
         Iswap( array, i, k );      // swap array[ i ] and array[ k ]
         Permute( _params, array, k + 1, n );
         Iswap( array, i, k );      // restore array[ i ] and array[ k ]
         if ( abort )
         {
            goto end;               // Abort the recursive process.
         }
      }
   }
end: ;
}// Permute

Functions PrintArray, ArrayToSquare, and Iswap are straightforward and are not reproduced here. The Main function can now be modified to find the solution for 3x3 and 4x4 magic squares, one at a time.

static void Main( string[] args )
{
   /*
   SolveSquare( _3x3_params_1 );
   SolveSquare( _3x3_params_2 );
   SolveSquare( _4x4_params );
   */

   Permutations( _3x3_params_1 );
   // Permutations( _4x4_params );
}// Main

In the case of a 3x3 magic square, the program produces the following output (only the end of the command-prompt window is shown):

68292: 2 7 6 9 5 1 4 3 8

68292 permutations

N = 3

Magic number = 15

2 7 6
9 5 1
4 3 8

End time: 6:54:52 AM

Start time: 6:52:55 AM

Elapsed time: 0 0:1:56 610 ms

Press any key to continue . . .

The elapsed time is 1 minute, 56 seconds and 610 milliseconds, which is much greater than the 136 milliseconds taken by the backtracking code. Observe that this solution is the backtracking solution flipped vertically (either up or down) and then horizontally to the left.

Using the Code

In Visual Studio, create a Windows console application named MagicSquare, which will be the namespace in the file Program.cs. Unzip the file attached to this article into some directory and open the file Program.cs. In that file, highlight the entire MagicSquare namespace and copy it. In the Program.cs file of your solution, highlight the entire MagicSquare namespace and paste the copied code. Build the solution and start it without debugging.

A Cautionary Note

The execution of the backtracking code for a 5x5 or higher-dimension square, and of the permutations code for a 4x4 or higher-dimension square will take a very long time, on the order of days. The program was run on a Toshiba Satellite L75D-A7283 laptop with an AMD A4-5000 APU x64 processor. The operating system was 64-bit Windows 10.

History

• 1^st November, 2020: Initial version