个人适合做跨境电商吗,seo排名哪家公司好,wordpress动态文章页模板下载,wordpress瓶颈起因
都说懒惰是第一生产力#xff0c;最近在玩数独游戏的时候#xff0c;总会遇到拆解数独比较复杂的情况#xff0c;就想着自己写个代码解题#xff0c;解放双手。所以很快就写了一个简单的代码求解经典数独。拿来跑了几个最高难度的数独发现确实很爽#xff01;虽说是…起因
都说懒惰是第一生产力最近在玩数独游戏的时候总会遇到拆解数独比较复杂的情况就想着自己写个代码解题解放双手。所以很快就写了一个简单的代码求解经典数独。拿来跑了几个最高难度的数独发现确实很爽虽说是比较暴力的 DFS但是由于数独中约束较多的性质实际上要找出唯一解并不复杂即使是最高难度的数独也可以在 0.04s 内解完可以说是非常的方便。
思路
经典数独游戏由 9*9 的方格组成每个方格可填 1~9 的数字一般都有三种约束同行同列同宫不可出现相同的数字。只要暴力时利用这些约束就可以快速剪枝。
考虑最简单的情况我们对于任何一个空位可以尝试去填 1~9 的数字并且检查三种约束是否满足。若满足就继续填下一个空位。
处理约束
实际上并不需要每个格子都去把 1~9 全部尝试。因为填的数字越多约束就越强我们就越容易发现之前填数时的错误。所以我们可以预先处理三种约束影响的格子范围
void initializeRelation() {memset(digitsUsed, 0, sizeof digitsUsed);// sub-gridsfor (int i 0; i 3; i) {for (int j 0; j 3; j) {int num i * 3 j;for (int k 0; k 3; k) {for (int l 0; l 3; l) {int idx calcIdx(i * 3 k, j * 3 l);group[2][idx] num;r[num].push_back(idx);}}}}// rowsfor (int i 0; i N; i) {for (int j 0; j N; j) {int idx calcIdx(i, j);group[0][idx] i N;r[i N].push_back(idx);}}// columnsfor (int i 0; i N; i) {for (int j 0; j N; j) {int idx calcIdx(j, i);group[1][idx] i N * 2;r[i N * 2].push_back(idx);}}
}预先处理完约束后下次要找一个格子到底应该对应哪些约束时就可以直接找到对应的 idx 序号了。
状态压缩
一个格子可以填 1~9 共九种数字那么到底哪些是可以填的呢就如同我们实际解数独时一样我们可以在格子上标记一下有哪些数字是符合约束的。一个简单的方法是把这个状态压缩成二进制数每个可用数字代表一个二进制位的 1若不可用则该位为 0。那么一个格子上的可用数字可用一个 9 位二进制数表示范围是0~2^9也即一个格子至多只有 512 种状态。
接下来 gcc 有一些方便的内建函数可以帮到我们它们都是以 __builtin 开头
__builtin_popcount(unsigned int x) 返回无符号整型x的二进制中 1 的个数__builtin_ctz(unsigned int x)返回无符号整型x的二进制的末尾有多少个 0
上述函数也可使用 std::bitsetN::count 等实现作用类似。
现在计算某个格子还有多少可用数字就可以这样
inline int calcUsable(int idx) {return 9 - __builtin_popcount(digitsUsed[idx]);
}DFS
当我们枚举数字时其实就是从当前状态中找到下一个可用数字并根据约束关系删除与其相关的格子中的可用数字。
那么搜索时如何快速判断当前填的数字否可行呢一个简单的思路是每次找到可用数字最少的格子这样的格子可以确定更多的约束搜索空间也更少一旦失败了我们可以迅速回滚。
那么把所有的空格子按照他们的[可用数字个数,可用数字状态]作为一个数对我们就可以利用std::set构造出一个暴力 DFS 方案
bool dfs() {if (grid.empty()) {return true;}pairint, int p *grid.begin();grid.erase(p);int idx p.second;int digitBit MASK ~digitsUsed[idx];for (int nextDigitBit digitBit; nextDigitBit; nextDigitBit ^ lowbit(nextDigitBit)) {int digit lowbit0Count(nextDigitBit);int currentDigitBit 1 digit;g[idx] digit 1;vectorint last;for (int j 0; j 3; j) {for (auto x: r[group[j][idx]]) {auto it grid.find(make_pair(calcUsable(x), x));if (it ! grid.end() (digitsUsed[x] | currentDigitBit) ! digitsUsed[x]) {grid.erase(it);digitsUsed[x] digitsUsed[x] | currentDigitBit;grid.insert(make_pair(calcUsable(x), x));last.push_back(x);}}}if (dfs()) {return true;}for (auto x: last) {grid.erase(make_pair(calcUsable(x), x));digitsUsed[x] digitsUsed[x] ~currentDigitBit;grid.insert(make_pair(calcUsable(x), x));}}grid.insert(p);return false;
}结语
由于只考虑经典数独代码还是非常简洁而且高效的。而对于各种各样的变形数独也可以考虑根据这种简化约束的方式去暴力求解。如果想要模仿人类解法对强弱链等逻辑进行推演而非简单暴力的话还需要更多的工作。
当然数独如果由机器暴力计算就会缺失很多乐趣但去寻找现有问题的一种代码实现也同样是另一种乐趣。我觉得能在数学游戏中找到自己喜欢的部分并发掘出其中的趣味其本身也是一种快乐的事情。
附录
最终代码如下输入重定向于sudoku.in输入格式中星号*代表空位可在代码最后注释中看到样例。 输出格式为先输出整体的解再输出只包含原数独中空位的解。
#include bits/stdc.husing namespace std;const int N 9;
const int R_NUM 27;
const int GRID_NUM 81;
const int MASK (1 N) - 1;char str[10][100];
int s[9][9];
int g[GRID_NUM];
int group[3][GRID_NUM]; // groups
vectorint r[R_NUM]; // relations
setpairint, int grid;
int digitsUsed[GRID_NUM];/**
group 0:
000000000
111111111
222222222
333333333
444444444
555555555
666666666
777777777
888888888group 1:
012345678
012345678
012345678
012345678
012345678
012345678
012345678
012345678
012345678group 2:
000111222
000111222
000111222
333444555
333444555
333444555
666777888
666777888
666777888
**/inline int calcX(int idx) {return group[0][idx];
}inline int calcIdx(int x, int y) {return x * N y;
}inline int lowbit(int x) {return x (-x);
}inline int lowbit0Count(int x) {return __builtin_ctz(x);
}inline int calcUsable(int idx) {return 9 - __builtin_popcount(digitsUsed[idx]);
}void initializeRelation() {memset(digitsUsed, 0, sizeof digitsUsed);// sub-gridsfor (int i 0; i 3; i) {for (int j 0; j 3; j) {int num i * 3 j;for (int k 0; k 3; k) {for (int l 0; l 3; l) {int idx calcIdx(i * 3 k, j * 3 l);group[2][idx] num;r[num].push_back(idx);}}}}// rowsfor (int i 0; i N; i) {for (int j 0; j N; j) {int idx calcIdx(i, j);group[0][idx] i N;r[i N].push_back(idx);}}// columnsfor (int i 0; i N; i) {for (int j 0; j N; j) {int idx calcIdx(j, i);group[1][idx] i N * 2;r[i N * 2].push_back(idx);}}
}void fail() {printf(IMPOSSIBLE\n);exit(0);
}void printResult() {printf(Result:\n);for (int i 0; i N; i) {for (int j 0; j N; j) {printf(%d, g[calcIdx(i, j)]);}printf(\n);}
}void printFillableResult() {printf(\nFillable Result:\n);for (int i 0; i N; i) {for (int j 0; j N; j) {printf(%c, (s[i][j] 0) ? g[calcIdx(i, j)] 0 : *);}printf(\n);}
}bool dfs() {if (grid.empty()) {return true;}pairint, int p *grid.begin();grid.erase(p);int idx p.second;int digitBit MASK ~digitsUsed[idx];for (int nextDigitBit digitBit; nextDigitBit; nextDigitBit ^ lowbit(nextDigitBit)) {int digit lowbit0Count(nextDigitBit);int currentDigitBit 1 digit;g[idx] digit 1;vectorint last;for (int j 0; j 3; j) {for (auto x: r[group[j][idx]]) {auto it grid.find(make_pair(calcUsable(x), x));if (it ! grid.end() (digitsUsed[x] | currentDigitBit) ! digitsUsed[x]) {grid.erase(it);digitsUsed[x] digitsUsed[x] | currentDigitBit;grid.insert(make_pair(calcUsable(x), x));last.push_back(x);}}}if (dfs()) {return true;}for (auto x: last) {grid.erase(make_pair(calcUsable(x), x));digitsUsed[x] digitsUsed[x] ~currentDigitBit;grid.insert(make_pair(calcUsable(x), x));}}grid.insert(p);return false;
}int main() {freopen(sudoku.in, r, stdin);initializeRelation();// Enter a sudoku puzzle: (9 lines with 9 characters on each line, use * for blank)for (int i 0; i N; i) {scanf(%s, str[i]);}for (int i 0; i N; i) {if (strlen(str[i]) ! N) {exit(0);}for (int j 0; j N; j) {int idx calcIdx(i, j);if (str[i][j] *) {g[idx] s[i][j] 0;digitsUsed[idx] 0;} else if (str[i][j] 1 str[i][j] 9) {g[idx] s[i][j] str[i][j] - 0;} else {exit(0);}}}for (int idx 0; idx GRID_NUM; idx) {if (g[idx] 0) {for (int j 0; j 3; j) {for (auto cur: r[group[j][idx]]) {if (g[cur] ! 0) {digitsUsed[idx] | 1 (g[cur] - 1);}}}// pair is (digitsLeftCount, idx)grid.insert(make_pair(calcUsable(idx), idx));}}if (dfs()) {printResult();printFillableResult();} else {printResult();fail();}return 0;
}/*
Sample Input*23456789
456789123
789123456
312645978
645978312
978312645
231564897
564897231
897231564**95*8*7*
23769***4
5**32**1*
8*1935**7
49*8*2*51
**3**6*2*
*1*2*4**6
6*8*****2
*7*1*38*******2***
2*4****7*
****5**49
**6**85**
******83*
57**4****
*3*7****6
*65*3**9*
7***9*1***/
文章转载自： http://www.morning.qlhkx.cn.gov.cn.qlhkx.cn http://www.morning.bmpjp.cn.gov.cn.bmpjp.cn http://www.morning.rqjfm.cn.gov.cn.rqjfm.cn http://www.morning.hwlmy.cn.gov.cn.hwlmy.cn http://www.morning.pjqxk.cn.gov.cn.pjqxk.cn http://www.morning.lggng.cn.gov.cn.lggng.cn http://www.morning.spftz.cn.gov.cn.spftz.cn http://www.morning.wztlr.cn.gov.cn.wztlr.cn http://www.morning.drcnn.cn.gov.cn.drcnn.cn http://www.morning.seoqun.com.gov.cn.seoqun.com http://www.morning.txgjx.cn.gov.cn.txgjx.cn http://www.morning.bfgpn.cn.gov.cn.bfgpn.cn http://www.morning.dbhnx.cn.gov.cn.dbhnx.cn http://www.morning.ldhbs.cn.gov.cn.ldhbs.cn http://www.morning.ckwrn.cn.gov.cn.ckwrn.cn http://www.morning.hsklc.cn.gov.cn.hsklc.cn http://www.morning.wdrxh.cn.gov.cn.wdrxh.cn http://www.morning.nrfqd.cn.gov.cn.nrfqd.cn http://www.morning.srbfp.cn.gov.cn.srbfp.cn http://www.morning.xq3nk42mvv.cn.gov.cn.xq3nk42mvv.cn http://www.morning.mjkqj.cn.gov.cn.mjkqj.cn http://www.morning.lwqst.cn.gov.cn.lwqst.cn http://www.morning.yqlrq.cn.gov.cn.yqlrq.cn http://www.morning.xhgcr.cn.gov.cn.xhgcr.cn http://www.morning.zrnph.cn.gov.cn.zrnph.cn http://www.morning.smzr.cn.gov.cn.smzr.cn http://www.morning.ycnqk.cn.gov.cn.ycnqk.cn http://www.morning.svrud.cn.gov.cn.svrud.cn http://www.morning.lbrrn.cn.gov.cn.lbrrn.cn http://www.morning.blqgc.cn.gov.cn.blqgc.cn http://www.morning.mzskr.cn.gov.cn.mzskr.cn http://www.morning.xnymt.cn.gov.cn.xnymt.cn http://www.morning.lcqrf.cn.gov.cn.lcqrf.cn http://www.morning.mggwr.cn.gov.cn.mggwr.cn http://www.morning.fbdkb.cn.gov.cn.fbdkb.cn http://www.morning.txkrc.cn.gov.cn.txkrc.cn http://www.morning.kxgn.cn.gov.cn.kxgn.cn http://www.morning.kqhlm.cn.gov.cn.kqhlm.cn http://www.morning.htfnz.cn.gov.cn.htfnz.cn http://www.morning.xnbd.cn.gov.cn.xnbd.cn http://www.morning.htfnz.cn.gov.cn.htfnz.cn http://www.morning.jbhhj.cn.gov.cn.jbhhj.cn http://www.morning.prgrh.cn.gov.cn.prgrh.cn http://www.morning.kgqww.cn.gov.cn.kgqww.cn http://www.morning.qyfrd.cn.gov.cn.qyfrd.cn http://www.morning.bpwdc.cn.gov.cn.bpwdc.cn http://www.morning.xpzrx.cn.gov.cn.xpzrx.cn http://www.morning.gmztd.cn.gov.cn.gmztd.cn http://www.morning.beeice.com.gov.cn.beeice.com http://www.morning.qmbgb.cn.gov.cn.qmbgb.cn http://www.morning.tqsmg.cn.gov.cn.tqsmg.cn http://www.morning.fgxws.cn.gov.cn.fgxws.cn http://www.morning.sbkb.cn.gov.cn.sbkb.cn http://www.morning.fldrg.cn.gov.cn.fldrg.cn http://www.morning.lylkh.cn.gov.cn.lylkh.cn http://www.morning.trbxt.cn.gov.cn.trbxt.cn http://www.morning.mrncd.cn.gov.cn.mrncd.cn http://www.morning.bnpcq.cn.gov.cn.bnpcq.cn http://www.morning.zhnpj.cn.gov.cn.zhnpj.cn http://www.morning.lfgql.cn.gov.cn.lfgql.cn http://www.morning.ktyww.cn.gov.cn.ktyww.cn http://www.morning.wrtsm.cn.gov.cn.wrtsm.cn http://www.morning.rxfgh.cn.gov.cn.rxfgh.cn http://www.morning.wkqrp.cn.gov.cn.wkqrp.cn http://www.morning.rkgyx.cn.gov.cn.rkgyx.cn http://www.morning.fbnsx.cn.gov.cn.fbnsx.cn http://www.morning.lfttb.cn.gov.cn.lfttb.cn http://www.morning.ryqsq.cn.gov.cn.ryqsq.cn http://www.morning.rwcw.cn.gov.cn.rwcw.cn http://www.morning.tgnr.cn.gov.cn.tgnr.cn http://www.morning.hjwkq.cn.gov.cn.hjwkq.cn http://www.morning.tssmk.cn.gov.cn.tssmk.cn http://www.morning.nlmm.cn.gov.cn.nlmm.cn http://www.morning.nclbk.cn.gov.cn.nclbk.cn http://www.morning.tnqk.cn.gov.cn.tnqk.cn http://www.morning.kmwbq.cn.gov.cn.kmwbq.cn http://www.morning.sogou66.cn.gov.cn.sogou66.cn http://www.morning.gkjnz.cn.gov.cn.gkjnz.cn http://www.morning.bwqr.cn.gov.cn.bwqr.cn http://www.morning.kjyhh.cn.gov.cn.kjyhh.cn
