Sansu
National Olympiad — Municipal round (2009 season)
Submission name: sansu.cpp
Problem summary
Rearrange the digits 1 through 9 in a 3×3 board by swapping side-adjacent cells. Minimize swaps until every row, column and main diagonal forms a number divisible by three. Print the minimum and a resulting board.
Input
Three rows containing the nine digits, each once.
Output
The minimum swap count, then a valid final board on three rows.
Constraints
A 3×3 permutation of digits 1 through 9. The original contest awards partial credit for proximity to the optimum; this solution finds an optimum.
Worked example
Independent example: every required line has digit sum divisible by three already.
Input
1 2 3 4 5 6 7 8 9
Output
0 1 2 3 4 5 6 7 8 9
Solution analysis
- Divisibility by three depends only on digit residues. Replace each digit by its residue modulo three; there are exactly three cells of each residue, hence only 9!/(3!³)=1680 distinct residue boards.
- Run breadth-first search from the input residue board. Each edge swaps adjacent cells. A board is a goal when all eight required line sums are zero modulo three. Store parent pointers and the swapped cell indices.
- Replay the recovered shortest swap sequence on the original digits. For the independent example all rows, columns and both diagonals already have sums divisible by three, so the answer is zero. The actual identities of digits with equal residue never matter to validity.
Why it works
Every original-board swap projects to a residue-board edge or a redundant self-step; consequently the residue distance is a lower bound on the true optimum. Conversely, every residue path can be replayed on actual digits and reaches a valid board in the same number of swaps. BFS finds the shortest residue path, so the lower bound is attained.
Watch out. Diagonal constraints are required too.,Replay swaps on actual digits rather than printing residues.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every original-board swap projects to a residue-board edge or a redundant self-step;
// consequently the residue distance is a lower bound on the true optimum. Conversely, every residue
// path can be replayed on actual digits and reaches a valid board in the same number of swaps.
#include<algorithm>
#include<array>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int encode(const array<int,9>&a){
int code=0,p=1;
for(int x:a){
code+=x*p;
p*=3;
}
return code;
}
array<int,9>decode(int code){
array<int,9>a{};
for(int&x:a){
x=code%3;
code/=3;
}
return a;
}
bool valid(const array<int,9>&a){
for(int i=0;i<3;++i){
if((a[3*i]+a[3*i+1]+a[3*i+2])%3){
return false;
}
if((a[i]+a[i+3]+a[i+6])%3){
return false;
}
}
return (a[0]+a[4]+a[8])%3==0&&(a[2]+a[4]+a[6])%3==0;
}
int main(){
array<int,9>digits{},residues{};
for(int i=0;i<9;++i){
cin>>digits[i];
residues[i]=digits[i]%3;
}
vector<pair<int,int>>edges;
for(int i=0;i<9;++i){
if(i%3<2){
edges.push_back({i,i+1});
}
if(i/3<2){
edges.push_back({i,i+3});
}
}
vector<int>parent(19683,-1),move(19683,-1);
int start=encode(residues),goal=start;
queue<int>q;
q.push(start);
parent[start]=start;
while(!q.empty()){
int u=q.front();
q.pop();
auto a=decode(u);
if(valid(a)){
goal=u;
break;
}
for(int e=0;e<int(edges.size());++e){
auto[x,y]=edges[e];
swap(a[x],a[y]);
int v=encode(a);
if(parent[v]==-1){
parent[v]=u;
move[v]=e;
q.push(v);
}
swap(a[x],a[y]);
}
}
vector<int>path;
for(int u=goal;u!=start;u=parent[u]){
path.push_back(move[u]);
}
reverse(path.begin(),path.end());
for(int e:path){
swap(digits[edges[e].first],digits[edges[e].second]);
}
cout<<path.size()<<'\n';
for(int i=0;i<9;++i){
cout<<digits[i]<<(i%3==2?'\n':' ');
}
}