Sudo-ku!
National Olympiad — Municipal round (2010 season)
Submission name: sudoku.cpp
Problem summary
Complete a nearly solved Sudoku. It is guaranteed that repeatedly filling the sole missing entry of a row, column or 3×3 box can solve the puzzle.
Input
Nine rows of nine space-separated digits; zero is an empty cell.
Output
The completed nine rows.
Constraints
A 9×9 Sudoku with a valid completion obtainable by the stated single-missing-entry rule.
Worked example
Official statement example.
Input
5 3 4 6 7 8 9 1 2 6 0 2 0 9 5 3 4 8 1 9 8 3 4 2 5 0 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 0 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9
Output
5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9
Solution analysis
- Build the 27 units: nine rows, nine columns and nine boxes. For each unit count empty cells and sum the known entries. If exactly one cell is empty, fill it with 45 minus that sum.
- Repeat passes until no unit changes. Every successful fill decreases the number of zeros, so there are at most 81 successful fills. The input guarantee ensures a non-complete board always admits a fill.
- In the sample, column two first forces 7; row two then forces 1. Row three forces 6, and the remaining missing entry is 7. No guessing or general Sudoku search is necessary.
Why it works
Every unit must contain the digits 1 through 9, whose sum is 45. A sole missing entry is therefore forced in every completion. Such fills preserve the valid completion. The stated guarantee ensures progress until every cell is filled, yielding the required Sudoku.
Watch out. Apply the box rule as well as row and column rules.,A unit with multiple zeros cannot be completed just from its sum.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every unit must contain the digits 1 through 9, whose sum is 45. A sole missing entry is
// therefore forced in every completion.
#include<array>
#include<iostream>
#include<vector>
using namespace std;
int main(){
array<int,81>board{};
for(int&x:board){
cin>>x;
}
vector<vector<int>>units;
for(int r=0;r<9;++r){
vector<int>row,column;
for(int c=0;c<9;++c){
row.push_back(9*r+c);
column.push_back(9*c+r);
}
units.push_back(row);
units.push_back(column);
}
for(int r=0;r<9;r+=3){
for(int c=0;c<9;c+=3){
vector<int>box;
for(int i=0;i<3;++i){
for(int j=0;j<3;++j){
box.push_back(9*(r+i)+c+j);
}
}
units.push_back(box);
}
}
bool changed=true;
while(changed){
changed=false;
for(const auto&unit:units){
int missing=0,position=-1,sum=0;
for(int p:unit){
sum+=board[p];
if(board[p]==0){
++missing;
position=p;
}
}
if(missing==1){
board[position]=45-sum;
changed=true;
}
}
}
for(int i=0;i<81;++i){
cout<<board[i]<<(i%9==8?'\n':' ');
}
}