數(shù)據(jù)結(jié)構(gòu)算法:數(shù)獨求解算法

在上海乘坐地鐵的朋友都知道，上海地鐵站免費贈閱的時代報上，經(jīng)常會刊登有數(shù)獨這個益智游戲。如果用紙和筆人工去算的話，恐怕你要花上老半天功夫了，有時候還不一定能解出來，心中一定很郁悶吧？網(wǎng)上也有一些數(shù)獨游戲的求解計算器，不過我想與其直接拿來主義，還不如自己研究編一個呢！所以，花了大概有一個多月的時間來編寫了這樣一個數(shù)獨求解軟件。由于不是利用所謂的窮舉算法，所以如果數(shù)獨游戲非解的話，它就只提供最先找到的那個解。不過，請放心，肯定是正確的！下面我就來詳述一下這個算法的精要。
    1、定義一個類，代表數(shù)獨游戲中的每一個數(shù)。它有如下屬性： #region 屬性
    ///
    /// 數(shù)值
    ///
    public int Num
    {
    set
    {
    if (UnFilled)
    {
    _num = value;
    _unfilled = false;
    Choices.Clear();
    SetNumEvent(this);
    }
    }
    get { return _num; }
    }
    ///
    /// 行坐標(biāo)
    ///
    public int Xpos
    {
    set { _x = value; }
    get { return _x; }
    }
    ///
    /// 列坐標(biāo)
    ///
    public int Ypos
    {
    set { _y = value; }
    get { return _y; }
    }
    ///
    /// 是否已填充的標(biāo)記
    ///
    public bool UnFilled
    {
    get { return _unfilled; }
    }
    ///
    /// 候選數(shù)列表
    ///
    public List Choices
    {
    set { _choices = value; }
    get { return _choices; }
    }
    #endregion
    2、在求解的主類里，根據(jù)游戲的規(guī)則，設(shè)計這樣一套算法。當(dāng)某一個數(shù)值被設(shè)定以后，與它同行或同列的以及在同一個九宮里的數(shù)的候選數(shù)列里都要去掉這個數(shù)本身。數(shù)獨游戲中出現(xiàn)的數(shù)為已知數(shù)，需要我們填補的則是未知數(shù)。未知數(shù)需要我們?nèi)ピ嚱?，不過在試解之前先要備份初始化以后的數(shù)組矩陣，以備在前一次試解失敗以后進(jìn)行恢復(fù)再進(jìn)行下一次試解，直到試解成功為止。
    3、算法本身看上去不是太復(fù)雜，但是涉及到一個遍歷和回滾的問題。所以，在編程的時候還是要注意一下的。
    下面我就來簡單介紹一下這個數(shù)獨求解軟件的操作和使用方法：
    軟件總體來說還是操作比較簡單的，但是由于當(dāng)時編寫的時候只是想給自己用的，所以并沒有設(shè)計菜單和幫助文檔。用戶在輸入初始數(shù)據(jù)的時候可以用上下左右方向鍵或者ASDF來進(jìn)行跳格。如果數(shù)錯了，在按確定按鈕以前可以按Back Space或Delete鍵進(jìn)行修改；一旦按了確定按鈕，就只得按F5清空后重新輸入了。
    軟件下載地址：http://download.csdn.net/source/512093
    源碼下載地址：http://download.csdn.net/source/512102