Advertisement
dmilicev

numbers_1-9_triangle_sum_17_v2.c

Apr 19th, 2020
1,428
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.47 KB | None
  1. /*
  2.  
  3.     numbers_1-9_triangle_sum_17_v2.c
  4.  
  5.     How to fill the triangle with 1, 2, 3, 4, 5, 6, 7, 8 and 9
  6.     to get the sum of each side equal to SUM ?
  7.  
  8.                 x4
  9.             x3      x5
  10.         x2              x6
  11.     x1      x9      x8      x7
  12.  
  13.     https://web.facebook.com/photo.php?fbid=130470831905101&set=gm.2637750503211777&type=3&theater
  14.  
  15.     Algorithm with permutations.
  16.  
  17.     https://www.codesdope.com/blog/article/generating-permutations-of-all-elements-of-an-arra/
  18.  
  19.  
  20.     You can find all my C programs at Dragan Milicev's pastebin:
  21.  
  22.     https://pastebin.com/u/dmilicev
  23.  
  24. */
  25.  
  26. #include <stdio.h>
  27.  
  28. #define SUM 17
  29.  
  30. int number_of_solutions=0;
  31. unsigned number_of_attempts=0;
  32.  
  33. //function to print the array of n integers
  34. void print_array(int arr[], int n)
  35. {
  36.     number_of_attempts++;
  37.  
  38.     if( arr[0] + arr[1] + arr[2] + arr[3] == SUM &&
  39.         arr[3] + arr[4] + arr[5] + arr[6] == SUM &&
  40.         arr[6] + arr[7] + arr[8] + arr[0] == SUM        )
  41.     {
  42.             number_of_solutions++;  // number_of_solutions and display them
  43.             printf("\n---%3d. solution: --------\n\n", number_of_solutions);
  44.             printf("............%d\n", arr[3]);
  45.             printf("........%d.......%d\n", arr[2],arr[4]);
  46.             printf("....%d...............%d\n", arr[1],arr[5]);
  47.             printf("%d.......%d.......%d.......%d\n", arr[0],arr[8],arr[7],arr[6]);
  48.     }
  49. } // print_array()
  50.  
  51. // function to swap the variables a and b
  52. void swap(int *a, int *b)
  53. {
  54.     int temp;
  55.     temp = *a;
  56.     *a = *b;
  57.     *b = temp;
  58. }
  59.  
  60. // recursive function to generate permutation
  61. void permutation(int *arr, int start, int end)
  62. {
  63.     int i;
  64.  
  65.     if(start==end)
  66.     {
  67.         print_array(arr, end+1);        // this is one permutation
  68.         return;
  69.     }
  70.  
  71.     for( i=start; i<=end; i++ )         // fixing one first digit,
  72.     {
  73.         swap((arr+i), (arr+start));     // swapping numbers
  74.         permutation(arr, start+1, end); // and calling permutation on the rest of the digits
  75.         swap((arr+i), (arr+start));     // swapping numbers
  76.     }
  77. } // permutation()
  78.  
  79.  
  80. int main(void)
  81. {
  82.     int i;
  83.  
  84.     int arr[9];                 // array of 9 permutation elements
  85.  
  86.     for (i = 0; i < 9; i++)     // fill in the array with integers from 1 to 9
  87.         arr[i] = i + 1;
  88.  
  89.     permutation(arr, 0, 8);     //calling recursive function to generate permutations
  90.  
  91.     printf("\n Number of attempts is %ld \n", number_of_attempts);
  92.     printf("\n There are %d solutions. \n", number_of_solutions);
  93.  
  94.     return 0;
  95. } // main()
Advertisement
RAW Paste Data Copied
Advertisement