用C语言模拟数独的人工解题思路.pdf

，…………………………………………………………” 实用第一／智慧密集 。．。。。。。．。．。。。．．。．。。．。。。。．．。。。．．。。。。…。。。。。。．。。…。。。。…。。。…。…。。， 摘要：以2006年首届世界数独大赛决赛题目为例，说明用C语言模拟数独的人工解题思 路。介绍了唯一法、排除法及尝试法三种解题方法。用c语言模拟数独的人工解题思路， 有利于学习C语言及相应的编程技巧，尝试着把人的思维方式转化成相应的计算机程序， 便于人工智能方面的研究。试验验证了程序的正确性。 关键词：数独；C语言；人工解题；候选数 和区。尝试法指的是首先选定一个候选数最少的空格，然后选 一、引言 择其中较小的一个候选数字，假定这个候选数字就是最终的答 数独是一种源自18世纪末的瑞士，后在美国发展、并在 案，然后再往下判定其它空格，如果最终解决问题当然万事大 日本得以发扬光大的数学智力拼图游戏。数独的玩法逻辑简 吉；如果发现在某一相同的行、列或区中一定会出现相同的两 单，数字排列方式千变万化。不少教育者认为数独是锻炼脑筋 个数字，那么可以断定前面的假设是错误的；这个时候，要重 的好方法。数独游戏成功的原因除了它的趣味性和挑战性之 新选择另一个候选数字进行尝试，直到解题。 外，更重要的原因其实是因为它很容易上手。玩这个游戏只需 当然唯一法、排除法及尝试法还可以扩展，这些在用C语 要认识1～9这九个数字，然后再需要一定的逻辑推理加上必 言实现时将做进一步探讨。从解题的顺序来看，优先使用唯一 要的耐心就可以了。 法。在唯一法无法实现解题的前提下，再使用排除法。一般入 数独游戏的规则是：在一个9×9的大正方形中，每一行 门级、中级、高级，甚至某些黄金级(骨灰级)的题目用这两种 和每一列都必须填入1至9的数字，不能重复也不能少；在每 方法是可以解题的。如果在前两者循环使用后，仍然不能解决 个由粗线隔开的3×3小九宫格(也被称为“区”)中，也必 问题，再使用尝试法。高级或黄金级(骨灰级)的题目通常要用 须填人1至9的数字，同样不能重复也不能少；每个数独游戏 到尝试法，有些难题甚至要多次尝试，对许多空格都要尝试。 只有一个解答方案。一般而言，一条数独题会给出1／3左右的 如果尝试过多，人工解题就失去了太多的乐趣。通常对某一个 数字作为初始条件，剩下的2／3空白处由读者完成。简单的数 空格使用尝试法之后，再结合唯一法、排除法可以顺利解题。 独题目初始时会有更多的数字。 三、C语言程序 用C语言模拟数独的人工解题思路，有利于学习C语言 及相应的编程技巧，不仅可以找寻计算机程序与人思维方式的 I．唯一法 差异，而且可以尝试着把人的思维方式转化成相应的计算机程 这里以2006年首届世界数独大赛决赛题目为例来说明用 序，便于今后人工智能方面的研究。 C语言模拟数独的人工解题思路。此题用C语言描述如下： ， intalxHx}tf|一。 二、数独解题思路 。| Q。 Q；蛰。§；。{_；i．5，Q；钱§l 数独游戏上手简单，但是随着难度的加大将会充满挑战。