數獨（Sudoku，記憶中這個游戲也叫九宮格，可能是我記錯了，應該叫數獨比較準確）

數獨百度百科：http://baike.baidu.cn/view/961.htm

九宮格百度百科：http://baike.baidu.cn/view/230179.htm#sub5038177

?

前兩天看到 @萬倉一黍 關于數獨解法算法實踐的一篇文章（http://www.cnblogs.com/grenet/archive/2013/06/19/3138654.html），突然想起去年的時候，因為微博上一篇關于某個外國學者花費3個月，研究出一道只有一種答案的數獨題，然后自己一時熱血涌上，花了3個鐘寫了個程序解了這道題。

原微博地址：http://weibo.com/2305049812/z0k9MciY7?type=repost

我的程序結果：http://weibo.com/1974539725/z0mBU0AtX?type=repost

這道數獨題是這樣的：

?

接下來說說我當時寫程序時的想法是怎樣的：

先拋開這道題，數獨的規則很簡單，就是要每一行、每一列、每一個九宮格中都含有1-9九個數字，且不重復。那就可以根據這一規則來制定解題的流程、邏輯。

用程序來解題的好處就是，我們有“循環”、“遞歸”這兩個概念，而且計算機的計算速度遠比人腦要快多了。

?

大概邏輯是：

1、先判斷每一格空格可能填寫的數字，取數量最少的那一格。

2、循環它可能的數字列，取第一個填入該格，再重復執行該邏輯（遞歸調用）。

3、若得到的數字列為空，則跳回上一格，取下一個數字填入，繼續執行查詢；若已跳回第一格，且已取完最后一個數字，則宣布該題無解；若已執行到最后一個，且得到數字列（理論上來將該數字列只有一個item），則宣布得到該題的解。

?

?

這里我使用Winform（C#）來做這個程序。

先設計好界面：

在后臺用一個數組變量保存這（9x9）81個格子

private static int _x = 9, _y = 9; private TextBox[,] _tbs = new TextBox[_x, _y];

?

當點擊“開始計算”按鈕后，后臺啟動一個線程開始計算。

private bool Find() {// 循環每一格，找出各自可能情況數var count = 10;int[] indexs = null;IList<int> numbers = null;for (var i = 0; i < _x; ++i)for (var j = 0; j < _y; ++j){int val;if (string.IsNullOrEmpty(_tbs[i, j].Text.Trim()) || !int.TryParse(_tbs[i, j].Text.Trim(), out val)){var ns = GetNums(i, j);if (ns.Count == 0)return false;else if (ns.Count < count){count = ns.Count;indexs = new int[2] { i, j };numbers = ns;}}}// 選擇最少可能情況的那一格if (numbers == null)return true;else{var tb = _tbs[indexs[0], indexs[1]];do{tb.Text = numbers[0].ToString();if (Find())return true;elsenumbers.RemoveAt(0);}while (numbers.Count > 0);tb.Text = "";return false;} }// 獲取這一格所有可能的情況 private IList<int> GetNums(int x, int y) {// 獲取該格所在九宮格var cells = new List<TextBox>();int xstart = x / 3 * 3,ystart = y / 3 * 3;for (int i = xstart, iend = xstart + 3; i < iend; ++i)for (int j = ystart, yend = ystart + 3; j < yend; ++j)cells.Add(_tbs[i, j]);int val;var nums = new List<int>();for (var num = 1; num <= 9; ++num){if (nums.Contains(num)) continue;var isIn = false;// 橫行for (var index = 0; index < _y; ++index){if (index != y &&!string.IsNullOrEmpty(_tbs[x, index].Text.Trim()) &&int.TryParse(_tbs[x, index].Text.Trim(), out val) &&val == num){isIn = true;break;}}if (isIn) continue;// 豎行for (var index = 0; index < _x; ++index){if (index != x &&!string.IsNullOrEmpty(_tbs[index, y].Text.Trim()) &&int.TryParse(_tbs[index, y].Text.Trim(), out val) &&val == num){isIn = true;break;}}if (isIn) continue;// 九宮格var tb = _tbs[x, y];foreach (var c in cells){if (c != tb &&!string.IsNullOrEmpty(c.Text.Trim()) &&int.TryParse(c.Text.Trim(), out val) &&val == num){isIn = true;break;}}if (isIn) continue;// 可選數值 nums.Add(num);}return nums; }

?

兩個大的方法已完成，接下來計算花費的時間。以這道題為例，最后得出結果為：

???

?

這個可能不是最優的邏輯算法，之前試過另一種方法，同樣可以得出這個結果，但花費了70多秒，這個方法只花費了19秒多。

貼出這篇文章只是為了學習，希望各位前輩多多指教。

?

PS：貌似這道題的答案不止一種，之前做程序的時候至少得到兩種答案，不過結果沒保存下來。誰知道呢，就讓其他人去研究吧 ...

轉載于:https://www.cnblogs.com/SugarLSG/p/3149113.html

總結

以上是生活随笔為你收集整理的用程序来解数独的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。