C++实现的简单数独计算器

发表于:2013-6-04 16:26

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:qq499194341    来源:51Testing软件测试网采编

  平时挺喜欢写小程序的,但是不知道写啥,偶然看到关于数独的新闻,觉得用小程序实现再合适不过了,网上一搜,有原理,有程序,但是没有找到优秀的代码,干脆自己写了一个,虽然也不优秀,起码自己看得懂。

  原理:

  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呢?因为速度太慢。

  结果截图:

21/212>
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号