CSES - Putka Open 2015 – 2/6 - Results
Submission details
Task:Sudoku
Sender:
Submission time:2015-08-15 22:27:44 +0300
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED100
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#2ACCEPTED0.07 sdetails
#3ACCEPTED0.07 sdetails
#4ACCEPTED0.07 sdetails
#5ACCEPTED0.07 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:162:9: warning: unused variable 'ans' [-Wunused-variable]
     int ans = 0;
         ^

Code

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <utility>
/* Copy paste ratkaisu project euler problem 96:sta :Dd */
using namespace std;
typedef vector<vector<int> > Grid;
Grid readGrid(){
string s; getline(cin,s);
Grid G(9,vector<int>(9));
for(int c = 0; c < 9; c++){
G[0][c] = s[c] - '0';
}
return G;
}
vector<vector<set<int> > > getCandidates(Grid G){
vector<vector<set<int> > > candidates;
for(int r = 0; r < 9; r++){
vector<set<int> > V;
candidates.push_back(V);
for(int c = 0; c < 9; c++){
set<int> all = {1,2,3,4,5,6,7,8,9};
candidates[r].push_back(all);
}
}
// Row constraints
for(int r = 0; r < 9; r++){
set<int> used;
for(int c = 0; c < 9; c++){
used.insert(G[r][c]);
}
for(int c = 0; c < 9; c++){
for(auto x : used)
candidates[r][c].erase(x);
}
}
// column constraints
for(int c = 0; c < 9; c++){
set<int> used;
for(int r = 0; r < 9; r++){
used.insert(G[r][c]);
}
for(int r = 0; r < 9; r++){
for(auto x : used)
candidates[r][c].erase(x);
}
}
// square constraints
for(int topleft_row = 0; topleft_row < 9; topleft_row += 3){
for(int topleft_col = 0; topleft_col < 9; topleft_col += 3){
set<int> used;
for(int r = topleft_row; r < topleft_row + 3; r++){
for(int c = topleft_col; c < topleft_col + 3; c++){
used.insert(G[r][c]);
}
}
for(int r = topleft_row; r < topleft_row + 3; r++){
for(int c = topleft_col; c < topleft_col + 3; c++){
for(auto x : used)
candidates[r][c].erase(x);
}
}
}
}
return candidates;
}
Grid propagate(Grid G){
bool update = true;
while(update){
update = false;
auto cand = getCandidates(G);
for(int r = 0; r < 9; r++){
for(int c = 0; c < 9; c++){
if(cand[r][c].size() == 1 && G[r][c] == 0){
G[r][c] = *(cand[r][c].begin());
cand = getCandidates(G);
update = true;
}
}
}
}
return G;
}
bool done(Grid G){
for(int r = 0; r < 9; r++){
for(int c = 0; c < 9; c++){
if(G[r][c] == 0) return false;
}
}
return true;
}
bool consistent(Grid G){
auto cand = getCandidates(G);
for(int r = 0; r < 9; r++){
for(int c = 0; c < 9; c++){
if((cand[r][c].size() == 0 && G[r][c] == 0)){
return false;
}
}
}
return true;
}
// Try all guesses, and if any gives a solution, return it
// If all guesses lead to inconsistencies, return an inconsistent grid
// Return: branch good?, grid
pair<bool,Grid> guess(Grid G, int depth){
auto cand = getCandidates(G);
for(int r = 0; r < 9; r++){
for(int c = 0; c < 9; c++){
if(G[r][c] == 0){
for(int x : cand[r][c]){
auto G2 = G;
G2[r][c] = x; // Make the guess
G2 = propagate(G2); // Fill the rest, does not make immediately inconsistent choices
// G2 will always be consistent
if(done(G2)) return {true,G2};
auto asd = guess(G2,depth+1); // Was not done yet
if(asd.first == true) return asd;
}
return {false, G};
}
}
}
return {true, G}; // Was already done
}
int solve(Grid G){
G = propagate(G);
G = guess(G,0).second;
for(int r = 0; r < 9; r++){
for(int c = 0; c < 9; c++){
cout << G[r][c];
} cout << endl;
}
return G[0][0]*100 + G[0][1]*10 + G[0][2];
}
int main(){
int ans = 0;
Grid G = readGrid();
solve(G);
}

Test details

Test 1

Verdict: ACCEPTED

input
592836471

correct output
592836471
836471592
471592836
928364715
364715928
...

user output
592836471
134257689
678149235
213465798
456798123
...

Test 2

Verdict: ACCEPTED

input
672935418

correct output
672935418
935418672
418672935
729354186
354186729
...

user output
672935418
134268579
589147236
213456897
456789123
...

Test 3

Verdict: ACCEPTED

input
329174658

correct output
329174658
174658329
658329174
291746583
746583291
...

user output
329174658
145268379
678359124
213485796
456791283
...

Test 4

Verdict: ACCEPTED

input
376958421

correct output
376958421
958421376
421376958
769584213
584213769
...

user output
376958421
124367589
589124367
213475698
457689132
...

Test 5

Verdict: ACCEPTED

input
875694321

correct output
875694321
694321875
321875694
756943218
943218756
...

user output
875694321
123578469
469123578
214356897
356789142
...