numbers_1-9_triangle_sum_17_v2.c

/*

    numbers_1-9_triangle_sum_17_v2.c

    How to fill the triangle with 1, 2, 3, 4, 5, 6, 7, 8 and 9
    to get the sum of each side equal to SUM ?

                x4
            x3      x5
        x2              x6
    x1      x9      x8      x7

    https://web.facebook.com/photo.php?fbid=130470831905101&set=gm.2637750503211777&type=3&theater

    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 17

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] + arr[3] == SUM &&
        arr[3] + arr[4] + arr[5] + arr[6] == SUM &&
        arr[6] + arr[7] + arr[8] + arr[0] == SUM        )
    {
            number_of_solutions++;  // number_of_solutions and display them
            printf("\n---%3d. solution: --------\n\n", number_of_solutions);
            printf("............%d\n", arr[3]);
            printf("........%d.......%d\n", arr[2],arr[4]);
            printf("....%d...............%d\n", arr[1],arr[5]);
            printf("%d.......%d.......%d.......%d\n", arr[0],arr[8],arr[7],arr[6]);
    }
} // 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 %ld \n", number_of_attempts);
    printf("\n There are %d solutions. \n", number_of_solutions);

    return 0;
} // main()