循环暴力解数独

最近在玩数独，喜欢玩非常难的，有时候因为自己看漏了什么东西真花费很长时间(两三个小时)才能解出来，往往一个数独谜题要解好长时间，到了最后自己就累了，不想玩了，顺手写了一个循环暴力解数独的程序。

其实非常简单，速度比我预想的要快 !

思路就是先循环一遍，把空格子的位置（空格子我们用数字0来表示）存到vector<pair<unsigned,unsigned>里面，然后对vector的每个格子从1试到9，检测每行每列该九宫格内有没有冲突，符合要求填下一个格子，不符合该格子+1，如果该格子的数值超过了9，那就该格子清零，对上一个格子进行+1,然后进行冲突检测，如此循环，直到全部循环完毕。

废话不多说，直接上源代码

sudoku.hpp

class Sudoku    //  shu du
{
public:
    // declary
    using question= unsigned int [9][9];
    // functions
    static bool solve(question& q)
    {
        static std::vector<pair<unsigned,unsigned>> steps;
        steps.resize(0);
        // get the empty position
        for(unsigned int r=0;r<9;++r)
            for(unsigned int c=0;c<9;++c)
                if(q[r][c]!=0)
                    continue;
                else
                    steps.push_back(make_pair(r,c));
        // fill the position
        for( auto each=steps.begin(); each!=steps.end(); each++ )
        {
            for (;;)
            {
                if(q[each->first][each->second]<9)
                    q[each->first][each->second]++;
                else
                {
                    q[each->first][each->second]=0;
                    if(each==steps.begin())
                    {
                        cout<<"Error: sudo can't find result !"<<endl;
                        return false;
                    }
                    else
                    {
                        each--;
                        continue;
                    }
                }
                if(check(q,*each))
                    break;
            }
        }
        stringstream output;
        output<<"Sudo Result:\n-------------------\n";
        for(unsigned r=0;r<9;++r)
        {
            output<<"|";
            for(unsigned c=0;c<9;++c)
                output<<q[r][c]<<"|";
            output<<"\n";
        }
        output<<"-------------------\n";
        cout<<output.str()<<endl;
        return true;
    }
private:
    static bool check(question& q,pair<unsigned,unsigned> p)
    {
        pair<unsigned,unsigned> block; // nine blocks
        block.first=p.first/3;
        block.second=p.second/3;
        // check the block
        for(unsigned int r=0;r<3;++r)
            for(unsigned int c=0;c<3;++c)
                if(p.first==r+block.first*3&&p.second==c+block.second*3)
                    continue;
                else
                    if(q[p.first][p.second]==q[r+block.first*3][c+block.second*3])
                       return false;
        // check the line
        for(unsigned int i=0;i<9;++i)
        {
            if(p.second!=i)
            if(q[p.first][p.second]==q[p.first][i])
                return false;
            if(p.first!=i)
            if(q[p.first][p.second]==q[i][p.second])
                return false;
        }
        return true;
    }

};

main.cpp 调用sudoku.hpp

#include <sstream>
#include <funny_code/sudoko.hpp>

using namespace std;
using namespace LB;

int main()
{
    Sudoku::question q={
                         7,0,0,  0,0,0,  0,0,4,
                         0,4,1,  0,0,6,  0,0,0,
                         0,5,0,  7,0,3,  1,9,0,

                         0,0,0,  0,2,0,  0,7,0,
                         0,1,8,  6,0,7,  0,0,0,
                         0,0,0,  0,3,0,  0,5,0,

                         0,7,0,  3,0,1,  2,6,0,
                         0,8,6,  0,0,5,  0,0,0,
                         2,0,0,  0,0,0,  0,0,8,
                     };
    Sudoku::solve(q);

    return 0;
}