摘要:下面是希赛软考学院为大家提供的软考程序员教程重点提炼之数独求解算法,希望能帮助学友们
下面是希赛软考网为大家提供的软考程序员教程重点提炼之数独求解算法,希望能帮助学友们。
在上海乘坐地铁的朋友都知道,上海地铁站免费赠阅的时代报上,经常会刊登有数独这个益智游戏。如果用纸和笔人工去算的话,恐怕你要花上老半天功夫了,有时候还不一定能解出来,心中一定很郁闷吧?网上也有一些数独游戏的求解计算器,不过我想与其直接拿来主义,还不如自己研究编一个呢!所以,花了大概有一个多月的时间来编写了这样一个数独求解软件。由于不是利用所谓的穷举算法,所以如果数独游戏非解的话,它就只提供最先找到的那个解。不过,请放心,肯定是正确的!下面我就来详述一下这个算法的精要。
1、定义一个类,代表数独游戏中的每一个数。它有如下属性:#region属性
///
///数值
///
public int Num
{
set
{
if(UnFilled)
{
_num=value;
_unfilled=false;
Choices.Clear();
SetNumEvent(this);
}
}
get{return _num;}
}
///
///行坐标
///
public int Xpos
{
set{_x=value;}
get{return _x;}
}
///
///列坐标
///
public int Ypos
{
set{_y=value;}
get{return _y;}
}
///
///是否已填充的标记
///
public bool UnFilled
{
get{return _unfilled;}
}
///
///候选数列表
///
public List Choices
{
set{_choices=value;}
get{return _choices;}
}
#endregion
2、在求解的主类里,根据游戏的规则,设计这样一套算法。当某一个数值被设定以后,与它同行或同列的以及在同一个九宫里的数的候选数列里都要去掉这个数本身。数独游戏中出现的数为已知数,需要我们填补的则是未知数。未知数需要我们去试解,不过在试解之前先要备份初始化以后的数组矩阵,以备在前一次试解失败以后进行恢复再进行下一次试解,直到试解成功为止。
3、算法本身看上去不是太复杂,但是涉及到一个遍历和回滚的问题。所以,在编程的时候还是要注意一下的。
下面我就来简单介绍一下这个数独求解软件的操作和使用方法:
软件总体来说还是操作比较简单的,但是由于当时编写的时候只是想给自己用的,所以并没有设计菜单和帮助文档。用户在输入初始数据的时候可以用上下左右方向键或者ASDF来进行跳格。如果数错了,在按确定按钮以前可以按Back Space或Delete键进行修改;一旦按了确定按钮,就只得按F5清空后重新输入了。
希赛软考网,拥有十四年软考培训经验,希赛网一直坚持自主研发,将丰富的软考培训经验有效融入教程研发过程,自成体系的软考在线题库(软考历年真题)、软考培训教材和软考视频教程,多样的培训方式包括在线辅导、面授、和,使考生的学习更具系统性,辅导更具针对性。采用全程督学机制,,软考平均通过率在全国。
软考备考资料免费领取
去领取