sudoku ver.1

sudoku.cpp

#include <stdio.h>
#include <algorithm>

namespace sudoku {
    const char UNKNOWN = '_';
    char board[90];
    void input(){
        for(int row=0; row<9; row++){
            scanf("%s",board + 9*row);
        }
    }
    const int ALL = 0b111'111'111;
    int candidate[81];
    const int blockpos[9] = {0, 3, 6, 27, 30, 33, 54, 57, 60};
    const int blockdiff[9] = {0, 1, 2, 9, 10, 11, 18, 19, 20};
    bool dfs(){
        if(std::count(board, board+81, UNKNOWN) == 0){
            return true;
        }
        std::fill(candidate, candidate+81, ALL);
        // row condition
        for(int row=0; row<9; row++){
            int cand = ALL;
            for(int col=0; col<9; col++){
                if(board[9*row + col] != UNKNOWN){
                    cand ^= 1<<(board[9*row + col] - '1');
                }
            }
            for(int col=0; col<9; col++){
                candidate[9*row + col] &= cand;
            }
        }
        // col condition
        for(int col=0; col<9; col++){
            int cand = ALL;
            for(int row=0; row<9; row++){
                if(board[9*row + col] != UNKNOWN){
                    cand ^= 1<<(board[9*row + col] - '1');
                }
            }
            for(int row=0; row<9; row++){
                candidate[9*row + col] &= cand;
            }
        }
        // block condition
        for(int block=0; block<9; block++){
            int cand = ALL;
            for(int idx=0; idx<9; idx++){
                int pos = blockpos[block] + blockdiff[idx];
                if(board[pos] != UNKNOWN){
                    cand ^= 1<<(board[pos] - '1');
                }
            }
            for(int idx=0; idx<9; idx++){
                int pos = blockpos[block] + blockdiff[idx];
                candidate[pos] &= cand;
            }
        }
        // least candidate
        int pos = -1;
        {
            int least = 10;
            for(int idx=0; idx<81; idx++){
                if(board[idx] != UNKNOWN)continue;
                int cnt = __builtin_popcount(candidate[idx]);
                if(cnt < least){
                    least = cnt;
                    pos = idx;
                }
            }
        }
        int cand = candidate[pos];
        // dfs
        for(int num=0; num<9; num++)if(cand>>num&1){
            board[pos] = num + '1';
            if(dfs())return true;
        }
        board[pos] = UNKNOWN;
        return false;
    }
    void solve(){
        dfs();
    }
    void output(){
        for(int row=0; row<9; row++){
            for(int col=0; col<9; col++){
                putchar(board[9*row + col]);
            }
            putchar('\n');
        }
    }
}

int main(){
    sudoku::input();
    sudoku::solve();
    sudoku::output();
    return 0;
}