当前位置：首页 > 窍门 > 科技数码

算法实践数独的基本解法

来源： 最后更新：22-03-29 12:10:45

数独（Sudoku）是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9乘以9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1到9，不重复。 每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

　　

　　数独的基本解法就是利用规则的摒弃法。每一行称为数独的行，每一列称为数独的列，每一个小九宫格称为数独的宫。数独的基本规则就是每一行、每一列、每一宫中，1到9这9个数字都只出现一次。那些只能填一个数字的空白单元格，我们称之为唯一数单元格。

　　

　　解题的顺序，就是从唯一数单元格开始，由于唯一数单元格只能填一个数，故先在这个单元格里填数。在这个单元格里填数，由于规则的定义，那么这个单元格所在的行、所在的列、所在的宫的其他单元格就不能再填这个数了。这些单元格能填的数的可能性就少了。有可能会产生新的唯一数单元格。

　　

　　在相当的一些的数独题目中，从唯一数单元格开始填数，不停的在唯一数单元格填数就可以把数独解出来。如果在解题的过程中，发现某些空白单元格没有数字能填这样的单元格称之为无解单元格，那就说明：要么这个数独没有解；要么之前的解题过程有问题，需要返回检查之前的解题过程查看。

　　

　　但是还有不少的数独的题目，在解题的过程中，在还有空白单元格的情况下，却找不到唯一数单元格，也就是意味着每个空白单元格中能填的数字至少有2个。而出现无唯一数单元格的这种状况，我们可以找到其中一个可能数最少的空白单元格（这个没有定论，可以是可能数最少的空白单元格；

　　

　　也可以是第一个空白单元格；也可以是可能数最多的空白单元格，选哪个空白单元格对后面的解题是否有影响，没有证明过，不好妄下定论。凭感觉选可能数最少的空白单元格是最好的选择），由于能填的数字不止一个，先把当前的状态保存起来，再在能选的数字中选择一个数字填写（从小到大选择），然后继续求解下去。如果能解出最后的结果，说明当前的选择是正确的；如果后面的求解过程有问题，说明当前的数字的选择有问题，那么再挑选另一个数填写，继续求解。

　　

　　如果，所有的选择都求不出最后的结果，还是说明：要么这个数独没有解；要么之前的解题过程有问题，需要返回检查之前的解题过程查看。如此反复，直到求出最终的答案。会有种极端的情况（可能性不大）。那就是在当前的空白单元格的所有可能的数字都选择了一遍，都没有解。而之前又没有出现无唯一数单元格的状况。那就说明这个数独根本就无解。

　　

　　

标签: 算法  标签  简介  

免责声明：本文系转载，版权归原作者所有；旨在传递信息，其原创性以及文中陈述文字和内容未经本站证实。

本文地址:http://www.zuomama.com/qiaomen/youxi/187797.html

随机分配算法

网站首页 返回栏目

算法工程师是程序员吗