037 Sudoku Solver[H]

03-06

1 題目描述

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character ..

You may assume that there will be only one unique solution.

難度：Hard

2 題目樣例

空白的數獨

被填好的數獨

3 題意分析

上一道題目要求判斷數獨是否合法，這次是要求解數獨了。

第一思路就是用搜索實現。深度優先搜索是最佳選擇。

（PS：我記得我在大一上學期好像就做過類似的題目了......）

4 思路分析

爆搜即可。

注意想要解數獨必須要先判斷數獨是否合法，我在這裡直接使用了上一道題解里對於數獨是否合法的判斷。

代碼如下

class Solution { public: void solveSudoku(vector<vector<char>>& board) { DFS(board,0,0); } bool isValidSudoku(vector<vector<char>>& board) { bool column[9][9]={0}; bool row[9][9]={0}; bool square[9][9]={0}; int k=0; int tp; for(int i=0;i<9;i++) for(int j=0;j<9;j++) { tp = board[i][j]; if(tp!=.) { tp = tp - 0 - 1; k = (i/3)*3 + j/3; if(row[i][tp] || column[j][tp] || square[k][tp]) return false; row[i][tp] = true; column[j][tp] = true; square[k][tp] = true; } } return true; } bool DFS(vector<vector<char>>& board,int i,int j) { if(j>=9) return DFS(board,i+1,0); if(i==9) return true; if(board[i][j]==.) { for(int k=1;k<=9;k++) { board[i][j]=char(k+0); if(isValidSudoku(board)) { if(DFS(board,i,j+1)) return true; } board[i][j]=.; } } else return DFS(board,i,j+1); return false; }};

由於整個數獨的大小是固定的9x9，所以其實時間複雜度和空間複雜度都是 $O(1)$ ，當然如果是n*n的話時間複雜度是 $O(n^2)$ ，空間複雜度依然是 $O(1)$ 。

5 後記

如果剛剛學習過搜索的話，可以嘗試著寫一寫這道題。

PS：今天是返校的日子......渾身酸痛不知道有沒有法子可治。