数独问题'高级数独没有更快捷的解答方式吗?
答案:2 悬赏:50 手机版
解决时间 2021-03-20 11:20
- 提问者网友:萌卜娃娃
- 2021-03-19 16:37
现在开始玩高级数独但是要一步一步的推敲'一步错了要从新来过'非常麻烦'请问有什么公式什么的方法帮助我吗?如果可以的话请留下联系方式。
最佳答案
- 五星知识达人网友:迟山
- 2021-03-19 16:52
计算机算法简介
本文所讨论的算法是一种通用算法,虽然不能说是最快的算法,但却可以求解所有的数独游戏。
算法准备:
1、一个可能性:表示某个格子可能填写的数字。
2、可能性数目:表示某个格子可能性的数量。为0表示已经确定。
3、区域标志:表示某个格子所在区域(小九宫)的ID,所有区域标志都是预定义的。
4、确定数量:表示所有数字已经确定的格子的数量,为81时则表示已经找到解。
5、整个九宫格用三个矩阵表示:可能性矩阵,数目矩阵,区域标志矩阵
算法的基本思想:
步骤1、将所有未确定的格子的可能性定义为0xFFFF(即所有数字都可能),可能数目为9。
步骤2、寻找所有确定的格子A(可能数目为0),在所有与A同行、同列和同区域的未确定的格子的可能性中减去与A相同的可能性。例如:A确定为9,则与A同行、同列和同区域(区域标志相同)的未确定的格子的可能性与0xFEFF按位与(除去可能性9),并将其可能性数目减少。
在除去可能性的过程中如果发现某个格子B的可能性数目由1减小为0,说明B和A只能取相同的数字,这可能是题目本身无解引起,也肯能是由于步骤3中搜索方向不对引起的,可认为此方向的搜索无解,退出这一方向的搜索。定义这个检查为唯一性检查。
步骤3、寻找所有未确定格子中可能性数目最少的格子M,如果M的可能性数目为1,则确定M:将M的可能性数目定义为0,并把确定数量加1,如果此时确定数量达到81,则报告找到解,否则,在所有与M同行、同列和同区域的未确定的格子的可能性中减去与M相同的可能性,并进行唯一性检查。然后重复步骤3。
如果M的可能性大于1,则把M假设为所有M的可能性,分多个方向进行搜索,在每一个搜索方向重复步骤3(这个可以用递归来实现)。
算法性能
本算法可以在50毫秒以内求解任意有解的数独游戏。
本文所讨论的算法是一种通用算法,虽然不能说是最快的算法,但却可以求解所有的数独游戏。
算法准备:
1、一个可能性:表示某个格子可能填写的数字。
2、可能性数目:表示某个格子可能性的数量。为0表示已经确定。
3、区域标志:表示某个格子所在区域(小九宫)的ID,所有区域标志都是预定义的。
4、确定数量:表示所有数字已经确定的格子的数量,为81时则表示已经找到解。
5、整个九宫格用三个矩阵表示:可能性矩阵,数目矩阵,区域标志矩阵
算法的基本思想:
步骤1、将所有未确定的格子的可能性定义为0xFFFF(即所有数字都可能),可能数目为9。
步骤2、寻找所有确定的格子A(可能数目为0),在所有与A同行、同列和同区域的未确定的格子的可能性中减去与A相同的可能性。例如:A确定为9,则与A同行、同列和同区域(区域标志相同)的未确定的格子的可能性与0xFEFF按位与(除去可能性9),并将其可能性数目减少。
在除去可能性的过程中如果发现某个格子B的可能性数目由1减小为0,说明B和A只能取相同的数字,这可能是题目本身无解引起,也肯能是由于步骤3中搜索方向不对引起的,可认为此方向的搜索无解,退出这一方向的搜索。定义这个检查为唯一性检查。
步骤3、寻找所有未确定格子中可能性数目最少的格子M,如果M的可能性数目为1,则确定M:将M的可能性数目定义为0,并把确定数量加1,如果此时确定数量达到81,则报告找到解,否则,在所有与M同行、同列和同区域的未确定的格子的可能性中减去与M相同的可能性,并进行唯一性检查。然后重复步骤3。
如果M的可能性大于1,则把M假设为所有M的可能性,分多个方向进行搜索,在每一个搜索方向重复步骤3(这个可以用递归来实现)。
算法性能
本算法可以在50毫秒以内求解任意有解的数独游戏。
全部回答
- 1楼网友:动情书生
- 2021-03-19 17:32
没有
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯