審題：

本題需要我們找出數獨的解，并打印出來

時間復雜度分析：

本題是9*9的數獨格子，所以數據量小于25，可以使用2^n的算法

思路：

方法一：深度優先搜索

首先確定搜索及插入策略：

我們采用逐個搜索插入數字1~9的策略，所以dfs的參數需要包括行數和列數。而插入需要滿足的條件是行，列，九宮格都沒有該數字。我們采用bool類型的row[行數][num]，col[列數][num]，matrix[行數/3][列數/3][num]來記錄是否插入。

注意：

matrix表示的就是3*3的九宮格，而我們利用行數/3以及列數/3的方法可以使九宮格內的數據都被歸類到一塊，然后即可表示該num在九宮格內的插入狀態

圖示：

確定遞歸進入前提：

由于本題初始矩陣存在著一些給定的非0數據，所以我們遇到初始數據就直接進行下一個格子的dfs搜索即可

確定遞歸深入邏輯：

我們對1~9的數在當前坐標插入是否合法依次判斷，若合法就將數字插入到結果數組上，并更新行，列，九宮格的bool數組狀態。

不合法就繼續判斷下一個數字是否合法，直到循環退出了我們就返回false（因為此時所有數字都無法插入）

確定遞歸回溯邏輯：

由于數獨只存在一個正確解法，所以我們不是對于每一次回溯都要回退插入狀態的，只有當

dfs返回的是false才要回退，返回true說明找到了，不進行回退

確定遞歸退出邏輯：

當行數超出9時，說明全部插入成功了，直接返回true。

解題：

#include<iostream>
using namespace std;
int v[9][9];
bool row[10][10], col[10][10], matrix[10][10][10];

（1）main函數邏輯

int main()
{//錄入數據for (int i = 0; i < 9; i++){for (int j = 0; j < 9; j++){cin >> v[i][j];int num = v[i][j];//記錄已有數字格子if (v[i][j] != 0){row[i][num] = col[j][num] = matrix[i / 3][j / 3][num] = true;}}}//搜索dfs(0, 0);//基0//輸出for (auto& a : v){for (auto& b : a){cout << b << " ";}cout << endl;}return 0;
}

在錄入數據的時候記得把已有數據的行/列/九宮格狀態更新。

（2）dfs

//深度優先搜索
bool dfs(int rows, int cols)
{//結束條件if (rows > 8){return true;}//跳過已有數字的格子if (v[rows][cols] != 0){if (cols < 8){return dfs(rows, cols + 1);}else{return  dfs(rows + 1, 0);}}//遞歸for (int i = 1; i <= 9; i++){if (row[rows][i] || col[cols][i] || matrix[rows / 3][cols / 3][i]){}else{v[rows][cols] = i;matrix[rows / 3][cols / 3][i] = col[cols][i] = row[rows][i] = true;bool judge;if (cols < 8){judge = dfs(rows, cols + 1);}else{judge = dfs(rows + 1, 0);}//回溯數據if (!judge){v[rows][cols] = 0;matrix[rows / 3][cols / 3][i] = col[cols][i] = row[rows][i] = false;}else{return true;}}}return false;
}

（1）由于我們是一個個搜索，所以我們進入深層遞歸前需要進行判斷，若列數沒到9就可以進入行數不變，列數++的位置搜索，若列數超了，那就進入行數++，列數為1搜索。

（2）本題之所以從0索引開始，是為了支持行數/3和列數/3的算法，因為從1索引開始的話，我們的第三行/第三列就無法歸為0九宮格，而是3/3==1歸為1九宮格了

P1784 數獨 - 洛谷