magic_square_sum_15_v1.c

/*

    magic_square_sum_15_v1.c

    Sum of the 3 numbers in each row, column and diagonal should be 15.
    All numbers are different, from range 1 to 9.
    In the middle of square is number 5.

    x5 = 5 .

    15                15                indexes of array:

        x1  x2  x3  =   15              0   1   2

        x4  x5  x6  =   15              3   4   5

        x7  x8  x9  =   15              6   7   8

        "   "   "
  15    15  15  15     15

https://web.facebook.com/groups/nitesh1991mathematics/permalink/1401624773361031/?comment_id=1401700693353439

    Algorithm with permutations.

    https://www.codesdope.com/blog/article/generating-permutations-of-all-elements-of-an-arra/


    You can find all my C programs at Dragan Milicev's pastebin:

    https://pastebin.com/u/dmilicev

*/

#include <stdio.h>

#define SUM 15

int number_of_solutions=0;
unsigned number_of_attempts=0;

//function to print the array of n integers
void print_array(int arr[], int n)
{
    number_of_attempts++;

    if( arr[0] + arr[1] + arr[2] == SUM &&
        arr[3] + arr[4] + arr[5] == SUM &&
        arr[6] + arr[7] + arr[8] == SUM &&
        arr[0] + arr[3] + arr[6] == SUM &&
        arr[1] + arr[4] + arr[7] == SUM &&
        arr[2] + arr[5] + arr[8] == SUM &&
        arr[0] + arr[4] + arr[8] == SUM &&
        arr[2] + arr[4] + arr[6] == SUM &&
        arr[4] == 5                         )
    {
            number_of_solutions++;  // number_of_solutions and display them
            printf("\n---%3d. solution: --------\n\n", number_of_solutions);
            printf(" %3d %3d %3d \n", arr[0], arr[1], arr[2] );
            printf(" %3d %3d %3d \n", arr[3], arr[4], arr[5] );
            printf(" %3d %3d %3d \n", arr[6], arr[7], arr[8] );
    }
} // print_array()

// function to swap the variables a and b
void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

// recursive function to generate permutation
void permutation(int *arr, int start, int end)
{
    int i;

    if(start==end)
    {
        print_array(arr, end+1);        // this is one permutation
        return;
    }

    for( i=start; i<=end; i++ )         // fixing one first digit,
    {
        swap((arr+i), (arr+start));     // swapping numbers
        permutation(arr, start+1, end); // and calling permutation on the rest of the digits
        swap((arr+i), (arr+start));     // swapping numbers
    }
} // permutation()


int main(void)
{
    int i;

    int arr[9];                 // array of 9 permutation elements

    for (i = 0; i < 9; i++)     // fill in the array with integers from 1 to 9
        arr[i] = i + 1;

    permutation(arr, 0, 8);     //calling recursive function to generate permutations

    printf("\n Number of attempts is 9! = %ld \n", number_of_attempts);
    printf("\n There are %d solutions. \n", number_of_solutions);

    return 0;
} // main()

/*

---  1. solution: --------

   2   7   6
   9   5   1
   4   3   8

---  2. solution: --------

   2   9   4
   7   5   3
   6   1   8

---  3. solution: --------

   4   3   8
   9   5   1
   2   7   6

---  4. solution: --------

   4   9   2
   3   5   7
   8   1   6

---  5. solution: --------

   6   1   8
   7   5   3
   2   9   4

---  6. solution: --------

   6   7   2
   1   5   9
   8   3   4

---  7. solution: --------

   8   3   4
   1   5   9
   6   7   2

---  8. solution: --------

   8   1   6
   3   5   7
   4   9   2

 Number of attempts is 9! = 362880

 There are 8 solutions.

*/