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

# 37. Sudoku Solver

![](/files/-MhcnP0tB91EGpZD1pbP)

![](/files/-MhcnSTRV3FA3Q41Kc-u)

![](/files/-MhcnVNiyjYYu__ERmki)

## backtracking

```java
/*

    time complexity: O(9^m), m represents the number of blanks to be filled in
    space complexity: O(1)

*/
class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0) return;
        solve(board);
    }

    private boolean solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {

                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) { //每個位置一一放入去try
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c; //set value

                            if (solve(board)) return true; // resursive, find unique solution, ealry stop

                            board[i][j] = '.'; // backtrack
                        }

                    }
                    return false;
                }
            }
        }
        return true;
    }

    
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) { //判斷9個格子
            char rowVal = board[row][i];
            if (rowVal != '.' && rowVal == c) return false;

            char colVal = board[i][col];
            if (colVal != '.' && colVal == c) return false;

            // 因為沒有用set, 所以判斷式是這樣, 這裡再針對(i,j) 去判斷9宮格內是否有c了
            char boxVal = board[3*(row/3) + i/3][3*(col/3) + i%3];
            if (boxVal != '.' && boxVal == c) return false;
        }
        return true;
    }
}
```

![](/files/5H3sUHZQz3yaUB94JCr0)

T: O(9!^9),  每列有 9! 的放入可能, 9 列, 所以是 O(9!^9)

S: O(9\*9) = O(81)

更好懂的寫法

```java
class Solution {
    public void solveSudoku(char[][] board) {
        dfs(board);
    }
    private boolean dfs(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                
                if (board[i][j] != '.') { // not empty, pass, do dfs from '.'
                    continue;
                }
                for (char c = '1'; c <= '9'; c++) {
                    if (isValid(board, i, j, c)) { // validate
                        board[i][j] = c; // try '1' to '9'
                        
                        if (dfs(board)) { // dfs
                            return true;
                        }
                        
                        board[i][j] = '.'; // backtracking
                    }
                }
                return false;
            }
        }
        return true;
    }
    
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] != '.' && board[row][i] == c) {
                return false;
            }
            if (board[i][col] != '.' && board[i][col] == c) {
                return false;
            }
        }
        
        int startRow = 3*(row/3);
        int startCol = 3*(col/3);
        for (int i = startRow; i < startRow+3; i++) {
            for (int j = startCol; j < startCol+3; j++) {
                if (board[i][j] != '.' && board[i][j] == c) {
                    return false;
                }
            }
        }
        return true;
    }
}

/*
最後用 startRow, startCol 來推 box 內 9 個座標
取的某點, ex 45, 3*(4/3), 3*(5/3) 取得起始座標=> 3,3

33.  3,4  35
43.  44.  45
53.  54.  55  => startRow, startCol = 3,3
ex 45, 3*(4/3), 3*(5/3) => 3,3

*/
```

````java
```java
class Solution {
    public void solveSudoku(char[][] board) {
        dfs(board, 0, 0);
    }
    private boolean dfs(char[][] board, int i, int j) {
        int m = board.length;
        int n = board[0].length;
        if (i == m) {
            return true;
        }
        if (j == n) { //col j reach n, so do next row, and col = 0
            return dfs(board, i+1, 0);
        }
        if (board[i][j] != '.') {
            return dfs(board, i, j+1);
        }
        for (char c = '1'; c <= '9'; c++) { // try to put each char into it
            if (isValid(board, i, j, c)) {
                board[i][j] = c;
                if (dfs(board, i, j+1)) {
                    return true;
                }
                board[i][j] = '.';
            }
        }
        return false;
    }
    private boolean isValid(char[][] board, int r, int c, char newChar) {
        for (int i = 0; i < 9; i++) {
            if (board[r][i] == newChar) {
                return false;
            }
            if (board[i][c] == newChar) {
                return false;
            }
        }
        int startR = r/3*3;
        int startC = c/3*3;
        for (int i = startR; i < startR+3; i++) {
            for (int j = startC; j < startC+3; j++) {
                if (board[i][j] == newChar) {
                    return false;
                }
            }
        }
        return true;
    }
}

/*
how to check it is valid?

if (board[r][i] == n) return false;
        // 判断列是否存在重复
        if (board[i][c] == n) return false;
        // 判断 3 x 3 方框是否存在重复
        if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)
            return false;


            3, 0

            3,0 4,0 5,0
            3,1.4,1 5,1  
            3,2 4,2.5,2



if j == n
dfs(i+1, 0)

not '.'
dfs(i, j+1)

if valid
dfs(i, j+1)

*/
```
````


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/dfs/tips/37.-sudoku-solver.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.