Task: | Sudoku |
Sender: | |
Submission time: | 2015-08-15 22:27:44 +0300 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 100 |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.06 s | details |
#2 | ACCEPTED | 0.07 s | details |
#3 | ACCEPTED | 0.07 s | details |
#4 | ACCEPTED | 0.07 s | details |
#5 | ACCEPTED | 0.07 s | details |
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 constraintsfor(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 constraintsfor(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 constraintsfor(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?, gridpair<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 guessG2 = propagate(G2); // Fill the rest, does not make immediately inconsistent choices// G2 will always be consistentif(done(G2)) return {true,G2};auto asd = guess(G2,depth+1); // Was not done yetif(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 ... |