熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> .NET編程 >> 正文

數獨求解算法

2013-11-13 10:33:11  來源: .NET編程 

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

  定義一個類代表數獨游戲中的每一個數它有如下屬性          #region 屬性
        /// <summary>
        /// 數值
        /// </summary>
        public int Num
        {
            set
            {
                if (UnFilled)
                {
                    _num = value;
                    _unfilled = false;
                    ChoicesClear();
                    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清空後重新輸入了

  軟件下載地址

  源碼下載地址

  下載所要的資源分可能是高了點不過絕對是原創作品前後花了一個多月才完成的本人自我感覺應該是物有所值的謝謝大家支持原創作品!


From:http://tw.wingwit.com/Article/program/net/201311/13980.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.