fork download 
  1. #include <iostream>
  2. #include <set>
  3. using namespace std;
  4. #define SQUARE_SIZE 9
  5.  
  6. int anyLine = 0;
  7. int currLine = 0;
  8. int numSolutions = 0;
  9.  
  10. set<int> seen;
  11.  
  12. // swap two values in the square.
  13. void swap (int arr[], int idxa, int idxb)
  14. {
  15.   int tmp = arr[idxa];
  16.   arr[idxa] = arr[idxb];
  17.   arr[idxb] = tmp;
  18. }
  19.  
  20. int key(int arr[]) {
  21. 	return arr[0]
  22. 	+ 10 * arr[1]
  23. 	+ 100 * arr[2]
  24. 	+ 1000 * arr[3]
  25. 	+ 10000 * arr[4]
  26. 	+ 100000 * arr[5]
  27. 	+ 1000000 * arr[6]
  28. 	+ 10000000 * arr[7]
  29. 	+ 100000000 * arr[8];
  30. }
  31.  
  32.  void printArray(int arr[])
  33.  {
  34.  	if (!seen.insert(key(arr)).second) return;
  35.     numSolutions++;
  36.     for (int i = 0; i < SQUARE_SIZE; i++) {
  37.         cout << arr[i] << " ";
  38.         if((i+1) % 3 == 0)
  39.             cout << endl;
  40.     }
  41.     cout << endl;
  42.  }
  43.  
  44. bool checkArr(int arr[])
  45. {
  46.   anyLine = arr[0] + arr[1] + arr[2];
  47.   currLine = 0;
  48.   for (int i = 0; i < SQUARE_SIZE; i++)
  49.   {
  50.     currLine += arr[i];
  51.     if((i+1) % 3 == 0)
  52.     {
  53.         if (currLine != anyLine)
  54.         return false;
  55.         currLine = 0;
  56.     }
  57.   }
  58.   // check vertically
  59.   for (int col = 0; col <3; col++)
  60.  {
  61.     for (int row = 0; row <3; row++)
  62.     {
  63.         currLine += arr[col + 3 * row];
  64.     }
  65.     if (currLine != anyLine)
  66.         return false;
  67.         currLine = 0;
  68.   }
  69.  
  70.   // check the diagonals
  71.   if ((arr[2] + arr[4] + arr[6]) != anyLine)
  72.     return false;
  73.  
  74.   if ((arr[0] + arr[4] + arr[8]) != anyLine)
  75.     return false;
  76.  
  77.   return true;
  78.  }
  79.  
  80.  void solve(int arr[], int pos)
  81.  {
  82.  
  83.   if (pos == 8)
  84.  {
  85.  
  86.  if (checkArr(arr))
  87.  {
  88.     printArray(arr);
  89.  }
  90.  
  91. }else
  92. {
  93. for (int i = 0 ; i < 9; i++)
  94. { 
  95.     if (i == pos) continue;
  96.        swap(arr,pos,i);
  97.        solve(arr,pos +1);
  98.  
  99.     }
  100.   }
  101. }
  102.  
  103. int main()
  104. {
  105.  
  106. int arr[SQUARE_SIZE]= { 1,2,3,4,5,6,7,8,9 };
  107.  
  108. solve(arr,0);
  109. cout << "number of solutions is: " << numSolutions<< endl << seen.size() << endl;
  110.  
  111. return 0;
  112. }
Success #stdin #stdout 0.55s 3232KB
comments (?)
stdin 
Standard input is empty
stdout 
6 1 8 
7 5 3 
2 9 4 

8 1 6 
3 5 7 
4 9 2 

6 7 2 
1 5 9 
8 3 4 

2 9 4 
7 5 3 
6 1 8 

2 7 6 
9 5 1 
4 3 8 

4 3 8 
9 5 1 
2 7 6 

4 9 2 
3 5 7 
8 1 6 

8 3 4 
1 5 9 
6 7 2 

number of solutions is: 8
8
https://ideone.com/wtC7s6
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!