Complete N-doku
National Olympiad — Municipal round (2015 season)
Submission name: ndoku.cpp
Problem summary
Complete an N² by N² grid so every row, column, and aligned N by N box contains each of N² distinct symbols exactly once. The upper-left box is supplied and must remain unchanged.
Input
N, then N rows of N different symbols.
Output
Any valid completed grid.
Constraints
2 ≤ N ≤ 6; symbols are digits or uppercase Latin letters and are all distinct.
Worked example
Official sample; other valid outputs may exist.
Input
2 Z1 3F
Output
Z13F 3FZ1 13FZ FZ13
Solution analysis
- Flatten the supplied box into a string S in row-major order. Let L=N². Construct row r by cyclically shifting S left by (r mod N)N+floor(r/N).
- Within a band of N rows, shifts differ by N, so every aligned N-column box sees all the symbols. Different bands add offsets 0 through N−1, ensuring every column also sees every symbol.
- For N=2 the shifts are 0,2,1,3. Applied to Z13F they produce the sample and preserve the initial 2 by 2 box.
Why it works
Each row is a permutation of S. The row shifts enumerate all residues modulo N², so each column is a permutation too. In a box with band b and stack c, indices are b+(c+t)N+j modulo N², with t,j independently ranging from 0 to N−1; these are all distinct. For r,c<N, the index is rN+c, preserving the given box.
Watch out. Ordinary Sudoku shifts would not necessarily preserve the entire supplied box. Output any valid completion.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Each row is a permutation of S. The row shifts enumerate all residues modulo N², so each
// column is a permutation too.
#include<iostream>
#include<string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
string symbols,row;
for(int i=0;i<n;++i){
cin>>row;
symbols+=row;
}
int size=n*n;
for(int r=0;r<size;++r){
int shift=(r%n)*n+r/n;
for(int c=0;c<size;++c){
cout<<symbols[(c+shift)%size];
}
cout<<'\n';
}
}