循环暴力解数独
最近在玩数独，喜欢玩非常难的，有时候因为自己看漏了什么东西真花费很长时间(两三个小时)才能解出来，往往一个数独谜题要解好长时间，到了最后自己就累了，不想玩了，顺手写了一个循环暴力解数独的程序。
其实非常简单，速度比我预想的要快 !
思路就是先循环一遍，把空格子的位置（空格子我们用数字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;
}
结果截图，哈哈。
源码截图好似有一种大学课设的感觉
数独结果.png
