Soudoku Solver

스도쿠 게임은 고전적인 게임이다.이제 나는 프로그램의 방법을 통과해야만 자동적으로 수독을 풀 수 있다.이 문제는'Puzzles for Programmers and Pros'라는 책에 설명되어 있다.
아이디어:
가장 직접적인 방법은 백트랙킹으로 귀속 시도를 할 수 있다는 것이다.일단 잘못을 탐지하면 거슬러 올라가면, 최종적으로 돌아가는 가장 깊은 곳에서 정해를 발견할 것이다.
백트랙킹은 인용 유형의 매개 변수로 귀속 깊이 들어갈 수 있지만 귀속 거슬러 올라갈 때 반드시 바뀐 값을 원상태로 되돌려야 다음 시도에 영향을 받지 않는다.
순수한 귀속 시도는 빈거법에 해당하며 속도가 매우 느리다.인간의 뇌가 스도쿠를 할 때 어떻게 진행되는지 생각해 보세요.위의 방법이 아닐 거야.가장 쉽게 쓸 수 있는 답을 먼저 찾아내는 거야.한 위치에 대해 동행, 동열, 동방격에서 9개 수의 8개를 모두 사용한 것을 발견하면 필연적으로 이 위치는 유일한 답안을 가지고 있다.이 방법에 따라 중복되면 먼저 수독을 약간 채울 수 있다.
유일하게 정답을 정할 수 있는 위치를 찾지 못할 때는 반드시 시도적인 추측을 해야 한다는 뜻이다.이때 나는 추측 범위가 가장 작은 위치를 찾아 시도해 보았다.범위가 좁을수록 성공할 확률이 높기 때문이다.이렇게 하면 잘못의 귀속 횟수를 최대한 줄일 수 있다.
코드:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<char> checker(vector<vector<char> > &board, int row, int col)
{
    vector<char> posibile;
    int bitmap[9];
    memset(bitmap, 0, sizeof(bitmap));
    int i;
    for(i=0;i<9;i++)
        if(board[row][i] != '.')
            bitmap[board[row][i] -'1'] = 1;
    
    for(i=0;i<9;i++)
        if(board[i][col] != '.')
            bitmap[board[i][col] - '1'] = 1;
    
    int row_base = (row/3)*3;
    int col_base = (col/3)*3;
    for(int i = 0;i<3;i++)
        for(int j=0;j<3;j++)
        {
            if(board[row_base + i][col_base + j] != '.')
                bitmap[board[row_base + i][col_base + j] - '1'] = 1;
        }

    for(i=0;i<9;i++)
        if(bitmap[i] == 0)
        {
            posibile.push_back(char('1' + i));
        }
    return posibile;
}

bool fun(vector<vector<char> > &board)
{
    size_t min = 10;
    vector<char> minoption;
    int mini, minj;
    //  
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
        {
            if(board[i][j] != '.')
                continue;
            
            vector<char> option = checker(board, i, j);
            if(option.size() < min)
            {
                min = option.size();
                minoption = option;
                mini = i;
                minj = j;
            }
        }
    
    if(min == 10)
        return true; //min ， 
    
    //  
    for(int k=0;k<minoption.size();k++)
    {
        board[mini][minj] = minoption[k];
        if(fun(board))
            return true;
        board[mini][minj] = '.';
    }
    return false; // ！！ option ， 

}

void solveSudoku(vector<vector<char> > &board)
{
    if(board.size() != 9)
        return;
    bool flag = true;

    while(flag)
    {
        flag = false;
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j] == '.')
                {
                    vector<char> tmp = checker(board, i, j);
                    if(tmp.size() == 1)
                    {
                        board[i][j] = tmp[0];
                        flag = true;
                    }
                }
            }
        }
    }
    
    fun(board);
}


void show(vector<vector<char> > &board)
{
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
            cout<<board[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
}


int main(int argc, const char * argv[])
{
    vector<vector<char> > board;
    vector<char> t;
    string s[9] = {"..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."};
    
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
            t.push_back(s[i][j]);
        board.push_back(t);
        t.clear();
    }
    show(board);
    cout<<"start..."<<endl;
    solveSudoku(board);
    cout<<"over"<<endl;
    show(board);
    return 0;
}