Magic Squares from a Multiset
National Olympiad — Municipal round (2014 season)
Submission name: magic.cpp
Problem summary
Arrange all nine supplied numbers in a 3×3 square. Count distinct arrangements whose three row sums, three column sums and two diagonal sums are all equal.
Input
Nine positive integers, each less than 100.
Output
The number of distinct magic squares, or 0 if impossible.
Constraints
Exactly nine numbers; repetitions are allowed.
Worked example
An independently prepared example for this explanation.
Input
1 3 2 4 5 8 7 6 9
Output
8
Solution analysis
- Sort the multiset and enumerate its distinct permutations with next_permutation. Map each permutation to the square in row-major order.
- Use the first row sum as the target and compare all remaining rows, all columns and both diagonals. Increment the answer only if all match. Starting from the sorted order makes next_permutation skip duplicate arrangements automatically.
- The numbers 1 through 9 form the eight orientations of the usual 3×3 magic square, giving the first sample answer 8. Nine copies of 1 have only one distinct permutation, which is magic, so the second sample gives 1.
Why it works
Every distinct arrangement occurs exactly once in lexicographic permutation enumeration. The eight checked sums are exactly the defining conditions of a magic square, so an arrangement is counted if and only if it qualifies.
Watch out. Do not count permutations of equal-valued copies separately. Both diagonals are required, and rotations are distinct arrangements.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<array>
#include<algorithm>
// Algorithm: Sort the multiset and enumerate its distinct permutations with next_permutation.
using namespace std;
int main(){
array<int,9>values;
for(int&value:values){
cin>>value;
}
sort(values.begin(),values.end());
int answer=0;
do{
int target=values[0]+values[1]+values[2];
bool valid=true;
for(int row=0;row<3;row++){
valid=valid&&values[row*3]+values[row*3+1]+values[row*3+2]==target;
}
for(int column=0;column<3;column++){
valid=valid&&values[column]+values[column+3]+values[column+6]==target;
}
valid=valid&&values[0]+values[4]+values[8]==target;
valid=valid&&values[2]+values[4]+values[6]==target;
if(valid){
answer++;
}
}
while(next_permutation(values.begin(),values.end()));
cout<<answer<<'\n';
}