快捷導(dǎo)航

C#實現(xiàn)數(shù)獨解法

更新時間：2022年06月16日 11:03:42 作者：天方

這篇文章介紹了C#實現(xiàn)數(shù)獨解法的方法，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下

數(shù)獨簡介

數(shù)獨（shù dú）是源自18世紀(jì)瑞士的一種數(shù)學(xué)游戲。是一種運用紙、筆進行演算的邏輯游戲。玩家需要根據(jù)9×9盤面上的已知數(shù)字，推理出所有剩余空格的數(shù)字，并滿足每一行、每一列、每一個粗線宮（3*3）內(nèi)的數(shù)字均含1-9，不重復(fù) [1] 。
數(shù)獨盤面是個九宮，每一宮又分為九個小格。在這八十一格中給出一定的已知數(shù)字和解題條件，利用邏輯和推理，在其他的空格上填入1-9的數(shù)字。使1-9每個數(shù)字在每一行、每一列和每一宮中都只出現(xiàn)一次，所以又稱“九宮格”。

實現(xiàn)方式

今天晚上抽空把數(shù)獨的計算機求解也給實現(xiàn)了一下，由于時間有限，我這里追求的是簡潔而有效的解法，故用的是最原始而直觀的回溯算法。速度也還可以接受，解網(wǎng)上最難的數(shù)獨也大概就0.0X秒的樣子。最開始是一個面向過程的實現(xiàn)，考慮到用的是C#的實現(xiàn)，便把這個算法給OO化了一下。

class Sudoku
{
    public int[,] Numbers { get; set; }
    int x;
    int y;

    public Sudoku(int[,] num)
    {
        Numbers = num;

        for (x = 0; x < 9; x++)
        {
            for (y = 0; y < 9; y++)
            {
                if (Numbers[x, y] == 0)
                    return;
            }
        }
    }

    public bool IsCompleted { get { return x == 9 && y == 9; } }

    //計算數(shù)獨，返回null表示無法計算
    public Sudoku CaluSudoKu()
    {
        if (IsCompleted)
            return this;

        foreach (var num in GetAvaibleNumbers())
        {
            var tmpData = Numbers.Clone() as int[,];
            tmpData[x, y] = num;

            var sudouku = new Sudoku(tmpData);
            var ret = sudouku.CaluSudoKu();

            if (ret != null)
                return ret;
        }

        return null;
    }

    int[] GetAvaibleNumbers()
    {
        var set = new HashSet<int>(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 });
        for (int i = 0; i < 9; i++)
        {
            set.Remove(Numbers[x, i]);
            set.Remove(Numbers[i, y]);
        }

        int xStart = x - x % 3;
        int yStart = y - y % 3;

        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                set.Remove(Numbers[i + xStart, j + yStart]);
            }
        }

        return set.ToArray();
    }
}

算法非常簡單，大概就五六十行的樣子，這種簡單的算法自然談不上高效，那些討論數(shù)獨算法的時間復(fù)雜度和空間復(fù)雜度的話題不在本文討論范圍之列。

到此這篇關(guān)于C#實現(xiàn)數(shù)獨解法的文章就介紹到這了。希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: