《数独游戏的解题算法》由会员分享,可在线阅读,更多相关《数独游戏的解题算法(4页珍藏版)》请在金锄头文库上搜索。
1、实用第一智慧密集?沪摘要关健词本文实现了求解数独游戏的解题算法,通过排斥法、唯一 法及排除法并结合递归算法达到解题目的。数独,位操作,递归调 用数独游戏是一种时下很流行的数学智力拼图游戏。拼图由!的九宫格组成,每个格子又分为一个小九宫格。其布局如下图所示。其规则很简单,在已经给定的数字基础上填出空白处的数字,使得每一行、每一列、每个小九宫格中的数字包含数字到#,且不重复。数独游戏可以很好地锻炼逻辑推理能力。一、分析为了说明方便规定一行、一列或一个九宫格为一组。在空白格子里 可能会坡的数字为候选项。候选项可以有多个,但不能为个,为视为无解。将有两个或两个以上候选项的格子称为空位。对于格子上已经确
2、定的数称为确项。解题方法如下!?相斥法数独游戏规定每一组中的#个数字不能重复。根据这个规则可以用组中确项来限定空位的候选项范围。例如某组中存在确项为 ,则该组中的其他位不能再有数字 。%?唯一法数独游戏规定每一组中必须出现到#各一次。根据这个规则,如果 空位候选项 中的某个数字在组中其他空位的候选项中没有出现,那么这个数字就是该空位应填的数字88; 7=?=;7 ?= 叮47=?=.3 【)49表示行、列、九宫格三种,共4个组,全部初始化为 +输人数字后,置为表达式 !组中所有确项# 的值。可以规定第一维的,1分别表示行、列、九宫格三种组,第二维为组的顺序值。九宫格的组内编号顺序为从左到右,从上到下。经过前述的准备,现在可以很容易地将解数独的技巧表示为程序语言。&?排斥法空位的候选项应为数字&一4去除其所在三个组的所有确项,表示为?候选项二! 行内确项#! 组内确项#!九宫格内确项#! (#其中“表示位操作异或,。1?唯一法空位的确项可以是其所在组中其他空位候选项不包含的数字,表示为?确项二空位的候选项! !组内其他空位的候选项#!空位的候选项#其中扭表示位操作与 。)?排膝法