数独问题求解

2020年6月8日16:53:44 发表评论

数独问题求解

1.数独介绍

数独是一种数学逻辑游戏,游戏由9×9个格子组成,玩家需要根据格子提供的数字推理出其他格子的数字。游戏设计者会提供最少17个数字使得解答谜题只有一个答案。

这种游戏只需要逻辑思维能力,与数字运算无关。虽然玩法简单,但提供的数字却千变万化,所以不少教育者认为数独是锻炼脑筋的好方法。数独游戏由日本出版商Nikoli于1986年发展,意思为“独身最适数字”。经过多年的发展,数独游戏现已发扬到全世界。

游戏规则:

游戏一般由9个3×3个的九宫格组成。

每一列的数字均须包含 1~9,不能缺少,也不能重复。

每一行的数字均须包含 1~9,不能缺少,也不能重复。

每一宫(粗黑线围起来的区域,通常是 3*3 的九宫格)的数字均须包含 1~9,不能缺少,也不能重复。

2.数独求解

本文介绍的是回溯法求解数独,参考《 数独问题的求解评价与生成算法的研究 》一文编程写出能够求解数独的程序。程序流程图如下所示。

数独问题求解

原理:首先计算所有空格的候选字并统计其数目,选择候选字数目最少空格开始代入,依次代入每个候选字,如果还有空格则递归代入,没有空格则判断是否求解成功。

因此,所需要的函数就有:

1.判断是否为终盘

2.判断是否为死盘

3.计算候选字并统计候选字数目

其中,判断是不是为终盘的条件是空格数和最小候选字数是不是都等于0。而判断是否死盘则是空格数是否大于最小候选字数。计算候选字时要根据行、列、宫来一一排除。

程序代码

代码和编译后的程序我都放在一个文件下了,解压后查看说明即可食用。一年没写代码了,有点粗糙,还请大家见谅。点击即可下载。提取码:nnbs。

flyingsheep

发表评论