POJ 2676 Sudoku

正月に帰省したとき暇だったので数独Solverを書いてたんだけど、最近POJやってみようかなーと思って眺めていたらこの問題を見つけ、通してみた。

問題

数独を解け！

解法

枝刈り探索。

ソースコード

#include <iostream>
#include <string>
#include <cstring>
#include <vector>

using std::vector;

int const n=9;
int const m=3;
typedef vector<int> vi;
typedef vector<vi> vvi;

namespace solver {
    bool column[n+1][n+1];
    bool raw[n+1][n+1];
    bool block[n+1][n+1];
    vector<vvi> ans;
    vvi g(n,vi(n));

    void rec(int x,int y){
        while(y!=n && g[y][x]){
            x++;
            if(x>=n){
                x=0;y++;
            }
        }
        if(y==n){
            ans.push_back(g);
            return;
        }
        for(int i=1;i<=n;i++){
            if(column[x][i]||raw[y][i]||block[x/m*m+y/m][i]){
                continue;
            }
            column[x][i]=raw[y][i]=block[x/m*m+y/m][i]=true;
            g[y][x]=i;
            rec(x,y);
            if(ans.size())return;
            column[x][i]=raw[y][i]=block[x/m*m+y/m][i]=false;
            g[y][x]=0;
        }
    }

    vector<vvi> solve(vvi const& g_){
        g.assign(n,vi(n,0));
        memset(column,0,sizeof(column));
        memset(raw,0,sizeof(raw));
        memset(block,0,sizeof(block));
        ans.clear();
        for(int y=0;y<n;y++){
            for(int x=0;x<n;x++){
                int t=g_[y][x];
                g[y][x]=t;
                column[x][t]=raw[y][t]=block[x/m*m+y/m][t]=true;
            }
        }
        rec(0,0);
        return ans;
    }
}

int main(){
    using std::cin;
    using std::cout;
    using std::endl;
    int _;cin>>_;
    while(_--){
        vvi g(n,vi(n));
        for(int y=0;y<n;y++){
            std::string s;cin>>s;
            for(int x=0;x<n;x++){
                g[y][x]=s[x]-'0';
            }
        }

        vector<vvi> ans=solver::solve(g);
        for(int y=0;y<n;y++){
            for(int x=0;x<n;x++){
                cout<<ans[0][y][x];
                if(x+1==n)cout<<endl;
            }
        }
    }
}