在上海乘坐地鐵的朋友都知道 上海地鐵站免費贈閱的時代報上 經常會刊登有數獨這個益智遊戲 如果用紙和筆人工去算的話 恐怕妳要花上老半天功夫了 有時候還不壹定能解出來 心中壹定很郁悶吧？網上也有壹些數獨遊戲的求解計算器 不過我想與其直接拿來主義 還不如自己研究編壹個呢！所以 花了大概有壹個多月的時間來編寫了這樣壹個數獨求解軟件 由於不是利用所謂的窮舉算法 所以如果數獨遊戲非唯壹解的話 它就只提供最先找到的那個解 不過 請放心 肯定是正確的！下面我就來詳述壹下這個算法的精要
定義壹個類 代表數獨遊戲中的每壹個數 它有如下屬性 #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