数独求解算法
在上海乘坐地铁的朋友都知道 上海地铁站免费赠阅的时代报上 经常会刊登有数独这个益智游戏 如果用纸和笔人工去算的话 恐怕你要花上老半天功夫了 有时候还不一定能解出来 心中一定很郁闷吧？网上也有一些数独游戏的求解计算器 不过我想与其直接拿来主义 还不如自己研究编一个呢！所以 花了大概有一个多月的时间来编写了这样一个数独求解软件 由于不是利用所谓的穷举算法 所以如果数独游戏非唯一解的话 它就只提供最先找到的那个解 不过 请放心 肯定是正确的！下面我就来详述一下这个算法的精要
定义一个类 代表数独游戏中的每一个数 它有如下属性 #region 属性 /// <summary> /// 数值 /// </summary> public int Num { set { if (UnFilled) { _num = value; _unfilled = false; Choices Clear(); SetNumEvent(this); } } get { return _num; } } /// <summary> /// 行坐标 /// </summary> public int Xpos { set { _x = value; } get { return _x; } } /// <summary> /// 列坐标 /// </summary> public int Ypos { set { _y = value; } get { return _y; } } /// <summary> /// 是否已填充的标记 /// </summary> public bool UnFilled { get { return _unfilled; } } /// <summary> /// 候选数列表 /// </summary> public List<int> Choices { set { _choices = value; } get { return _choices; } } #endregion
在求解的主类里 根据游戏的规则 设计这样一套算法 当某一个数值被设定以后 与它同行或同列的以及在同一个九宫里的数的候选数列里都要去掉这个数本身 数独游戏中出现的数为已知数 需要我们填补的则是未知数 未知数需要我们去试解 不过在试解之前先要备份初始化以后的数组矩阵 以备在前一次试解失败以后进行恢复再进行下一次试解 直到试解成功为止
算法本身看上去不是太复杂 但是涉及到一个遍历和回滚的问题 所以 在编程的时候还是要注意一下的
下面我就来简单介绍一下这个数独求解软件的操作和使用方法
软件总体来说还是操作比较简单的 但是由于当时编写的时候只是想给自己用的 所以并没有设计菜单和帮助文档 用户在输入初始数据的时候可以用上下左右方向键或者ASDF来进行跳格 如果数错了 在按确定按钮以前可以按Back Space或Delete键进行修改 一旦按了确定按钮 就只得按F 清空后重新输入了
软件下载地址
源码下载地址
lishixinzhi/Article/program/net/201311/13980
