平时挺喜欢写小程序的,但是不知道写啥,偶然看到关于数独的新闻,觉得用小程序实现再合适不过了,网上一搜,有原理,有程序,但是没有找到优秀的代码,干脆自己写了一个,虽然也不优秀,起码自己看得懂。
原理:
1、每个格子可以是1-9的数,n行m列的数确定后,则第n行,第m列,nm所在的”宫“里其他的格子就不能是这个数了。
2、刚开始每个格子都有9个”候选数“,逐步把初始数据添加到最终的格子中,并把相应的格子中的候选数更新,如1所说。
3、开始计算,选出候选数最少的格子,对这些数迭代测试,如把候选数中的第1个添加到最终的格子中。和2一样更新其他格子的候选数列表。
4、3之后自然还是3,所以把3实现为递归要简单一些。而且考虑到本题实际情况最多递归81层,不会栈溢出。而且递归本身还保存了后续所需数据,简化了操作。
代码注释:
g_currentIndex:格子中已经确定结果的个数(添加到格子中的数的个数,递归的深度),索引表示的,所以0代表已添加1个。
g_affectedFlags:位标志,某次添加数据是否对格子产生影响,回退操作要使用。
g_candidate:每个格子的候选列表,用bitset的索引表示。第n位为1,代表n是候选数。
g_candidateNum:每个格子的候选个数,为什么不用bitset的count呢?因为速度太慢。
结果截图: