Solving a magic square using recursion in C

Question

Hi I want to make a 3 x 3 magic square in C using backtracking (as in the 4 queens exercise) with recursivity.

In addition, I must enter the maximum value that this magic square will have inside, for example if I enter m = 26, my table should look something like this:

[22,8,21]
[16,17,18]
[13,26,12]

as it should be done by backtracking, that is one possible solution of many, currently I have a simple code of 3 loops to perform all the possible combinations by entering the value of M.

attached code:

#include <stdio.h>
#include <string.h>
#define N 10

void print (int * num, int n)
{
    int i;
    for (i = 0; i <n; i ++)
        printf ("% d", num [i]);
    printf ("\ n");
}

int main ()
{
    int num [N];
    int * ptr;
    int temp;
    int i, m, j;
    int n = 3;
    printf ("\ nlimite:");
        scanf ("% d", & m);
    for (int i = 1; i <= m; ++ i)
    {
        for (int j = 1; j <= m; ++ j)
        {
            for (int k = 1; k <= m; ++ k)
            {
                permutations ++;
                printf ("%i,%i,%i\n", i, j, k);
            }
        }
    }
}

How can I transform this code to be recursive? and without repeating the first values, for example [1,1,1] [16,16,16] since this will allow me to create the possible rows and columns to elaborate the magic square.

and finally to be able to print all the possible solutions that are correct.

solution 1     solution N
[4,9,2]        [22,8,21]
[3,5,7]        [16,17,18]
[8,1,6]   ...  [13,26,12]

for compilation I use MingGW - gcc on windows, in advance thanks a lot for the help

Answer 1

so, nowhere in your current code do you actually test that the solution is a perfect square. Let's rectify that.

Now this solution is realllllllly slow, but it does show how to advance recursively in this kind of problem.

#include <stdio.h>

void magic_square(int *grid, int next_slot, int max_value) {
  // Maybe recurse
  if (next_slot < 9) {
    for (int i = 1; i < max_value; i++) {
      grid[next_slot] = i;
      magic_square(grid, next_slot + 1, max_value);
    }
  // Test magic square.
  } else {
    const int sum = grid[0] + grid[1] + grid[2];
    // Horizontal lines
    if (grid[3] + grid[4] + grid[5] != sum) return;
    if (grid[6] + grid[7] + grid[8] != sum) return;
    // Vertical lines
    if (grid[0] + grid[3] + grid[6] != sum) return;
    if (grid[1] + grid[4] + grid[7] != sum) return;
    if (grid[2] + grid[5] + grid[8] != sum) return;
    // Diagonal lines
    if (grid[0] + grid[4] + grid[8] != sum) return;
    if (grid[2] + grid[4] + grid[6] != sum) return;
    // Guess it works
    printf("%3d %3d %3d\n%3d %3d %3d\n%3d %3d %3d\n\n",
          grid[0], grid[1], grid[2],
          grid[3], grid[4], grid[5],
          grid[6], grid[7], grid[8]);
  }
}

int main(void) {
  int grid[9];
  int max_value = 5;
  magic_square(grid, 0, max_value);
}

You'll also need to add the restriction that no number is used multiple times.