最近寫了好幾道DFS相關(guān)的題目，想起以前玩過(guò)的一個(gè)游戲：數(shù)獨(dú)，因?yàn)槎际且粋€(gè)類型的思想，所以很快就想到了用 DFS來(lái)求解 數(shù)獨(dú)，此文章來(lái)教你一步一步來(lái)實(shí)現(xiàn)一個(gè)數(shù)獨(dú)模擬器 . . .
.
相關(guān)文章：
藍(lán)橋杯DFS經(jīng)典題 —— 算式900、 寒假作業(yè)（告別枚舉法）

---

我們需要求解的數(shù)獨(dú)就是世界上最難的數(shù)獨(dú)：

這個(gè)數(shù)獨(dú)被當(dāng)時(shí)一個(gè) 69歲的爺爺花了三天時(shí)間給算出了，有這樣一個(gè)故事：

下面我將帶大家手把手寫出這樣的一個(gè)小程序，來(lái)快速的求解出世上最難的數(shù)獨(dú) . . .

首先，我們都知道數(shù)獨(dú)是有規(guī)則的，上面的數(shù)據(jù)不是隨便放的，規(guī)則如下：

一行九個(gè)數(shù)據(jù)，9個(gè)數(shù)字必須出現(xiàn)

一列九個(gè)數(shù)據(jù)，9個(gè)數(shù)字必須出現(xiàn)

一個(gè)九宮格，9個(gè)數(shù)字必須出現(xiàn)

比如下面這個(gè)情況才是允許存在的：

所以，我們需要寫一個(gè)方法，用來(lái)判斷當(dāng)前的這個(gè)數(shù)字是否允許存放在這個(gè)數(shù)獨(dú)之中，代碼如下：

bool JudgeIsNoWant(int n) // n 表示是當(dāng)前的第幾個(gè)數(shù) {int x = n / 9; // 定位當(dāng)前數(shù)的位置（數(shù)據(jù)在二維數(shù)組中的位置）int y = n % 9;for (size_t i = 0; i < 9; i++) // 橫豎 搜索{if (arr[x][i] == arr[x][y] && i != y) return false;if (arr[i][y] == arr[x][y] && i != x) return false;}// 九宮格 搜索 這里需要一個(gè)小小的算法，確定九宮格的位置for (size_t i = x / 3 * 3; i < x / 3 * 3 + 3; i++)for (size_t j = y / 3 * 3; j < y / 3 * 3 + 3; j++)if (arr[i][j] == arr[x][y] && (i != x || j != y))return false;return true; }

其中的九宮格位置確定算法如下所示：

其中，這個(gè) X 的值的位置是 （4，5），九宮格起始位置是（3，3），我們需要設(shè)計(jì)一個(gè)算法來(lái)打出這個(gè)點(diǎn)，而這個(gè)算法就是上面代碼上所述的：

• 4 / 3 * 3 = 3
• 5 / 3 * 3 = 3

.

下面我們就可以使用 DFS 來(lái)求解這個(gè)世上最難的數(shù)獨(dú)了，代碼如下所示：

void Dfs(int n) // 深搜思想 {// 判斷上一個(gè)數(shù)據(jù)是否滿足條件（ 橫、豎、九宮格 ）if (n > 0 && n <= 81) if (!JudgeIsNoWant(n - 1)) return;if (n >= 81) //　到最后則輸出數(shù)據(jù)并且返回{cout << endl << endl << "解為：" << endl << endl;for (size_t i = 0; i < 9; i++){for (size_t j = 0; j < 9; j++){ cout << arr[i][j] << " "; if (j % 3 == 2) cout << " ";}cout << endl;if (i % 3 == 2) cout << endl;}return;}int x = n / 9; // 定位當(dāng)前數(shù)的位置int y = n % 9;if (arr[x][y] != 0) // 只對(duì) 數(shù)字為 0 的元素進(jìn)行搜索Dfs(n + 1);else {// 每一個(gè)空位有 10 種可能性for (size_t i = 1; i < 10; i++) {arr[x][y] = i; // 當(dāng)前的數(shù)字放入到數(shù)組之中，Dfs(n + 1); // 進(jìn)行下一個(gè)位置的搜索arr[x][y] = 0; // 不滿足條件，重新清 0}} }

這里的關(guān)鍵點(diǎn)在于這一行代碼：

為什么我們需要判斷上一個(gè)數(shù)字是否滿足條件呢？而不是當(dāng)數(shù)組中有了新的數(shù)據(jù)就直接判斷呢？
如果是后一種思想求解將造成很多的問(wèn)題，且非常不方便，之前試過(guò)沒(méi)有成功 . . .

~

測(cè)試代碼就是讀取一個(gè)數(shù)獨(dú)，然后調(diào)用我們的 DFS方法（從 0開(kāi)始）：

/*世界上最難的數(shù)獨(dú):0 0 5 3 0 0 0 0 08 0 0 0 0 0 0 2 00 7 0 0 1 0 5 0 04 0 0 0 0 5 3 0 00 1 0 0 7 0 0 0 60 0 3 2 0 0 0 8 00 6 0 5 0 0 0 0 90 0 4 0 0 0 0 3 00 0 0 0 0 9 7 0 0*/ cout << "請(qǐng)輸入需要求解的數(shù)獨(dú)：" << endl << endl; for (size_t i = 0; i < 9; i++) for (size_t j = 0; j < 9; j++)cin >> arr[i][j];Dfs(0); // 從第一個(gè)開(kāi)始測(cè)試

這個(gè)世界上最難的解為：

我們可以用如下的方式來(lái)測(cè)試一下這個(gè) DFS 用了多少 ms ：

通過(guò)大量的測(cè)試后，我們發(fā)現(xiàn)要想求出這個(gè)解就要花費(fèi) 80ms 左右的時(shí)間 . . .

---

浪子花夢(mèng)

一個(gè)有趣的程序員 ~

總結(jié)

以上是生活随笔為你收集整理的80ms 求解世上最难数独 —— DFS的灵活运用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。