> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/37.-sudoku-solver.md).

# 37. Sudoku Solver

## 1.問題

*

![](/files/-LO33hOfyNg4xRC4PhYS)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 時間複雜度與可用空間是否有限制?&#x20;
* function header, parameter
* test input
* 說明想法
  * 可以用ray tracking的方式: 在空的地方放置有可能的(不違規)數字, 再繼續填下一個空位
  * 要注意的是, 這種試誤法, 目的是從許多可能中只有都是true的路徑才會持續走下去, type要用bool
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        if (board.empty() ||
            board.size() < 9 ||
            board[0].size() < 9) {
            return;
        }
        trySolveSudoku(board, 0, 0);
    }
private:
    bool trySolveSudoku(vector<vector<char>>& board, int startX, int startY) {
        if (startX == 9) {
            return true;
        } 
        
        if (startY >= 9) {
            return trySolveSudoku(board, startX + 1, 0);
        }
        if (board[startX][startY] == '.') {
            for (int i = 1; i <= 9; i++) {
                board[startX][startY] = char(i + '0');
                if(isValid(board, startX, startY)) {
                    //當下一步這樣ok時, 返回true
                    //因此從許多可能中只有都是true的路徑才會持續走下去, type要用bool
                     if (trySolveSudoku(board, startX, startY + 1)) {
                         return true;
                     }
                }
                board[startX][startY] = '.';
            }
        } else {
            return trySolveSudoku(board, startX, startY + 1);
        }
        return false;
    }
    
    bool isValid(vector<vector<char>>& board, int startX, int startY) {
        //row
        for (int j = 0; j < 9; ++j) {
            if (j != startY &&
                board[startX][startY] == board[startX][j]) {
                return false;
            }
        }
        
        //row
        for (int i = 0; i < 9; ++i) {
            if (i != startX &&
                board[startX][startY] == board[i][startY]) {
                return false;
            }
        }
        
        //9 * 9
        for (int i = startX / 3 *3; i < startX / 3 *3 + 3; ++i) {
            for (int j = startY / 3 *3; j < startY / 3 *3 + 3; ++j) {
                if ((i != startX || j != startY) &&
                    board[startX][startY] == board[i][j]) {
                    return false;
                }
            }    
        }

        return true;
    }
};
```