Sudoku

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

#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 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED