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

# 37.Sudoku-Solver

## 37. Sudoku Solver

## 题目地址

<https://leetcode.com/problems/sudoku-solver/>

## 题目描述

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

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.

Note:
The given board contain only digits 1-9 and the character '.'.
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9x9.
```

## 代码

### Approach 1: Backtracking

`box_index = (row / 3) * 3 + column / 3`

```java
class Solution {
  // box size
  int n = 3;
  // row or column size
  int N = n * n;
  // index + value
  int [][] rows = new int[N][N + 1];
  int [][] columns = new int[N][N + 1];
  int [][] boxes = new int[N][N + 1];

  char[][] board;
  boolean sudokuSolved = false;

  public void solveSudoku(char[][] board) {
        this.board = board;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        char num = board[i][j];
        if (num != '.') {
          int d = Character.getNumbericValue(num);
          placeNumber(d, i, j);
        }
      }
    }
    backtrack(0, 0);
  }

  public boolean couldPlace(int d, int row, int col) {
    int idx = (row / n) * n + col / n;
    return rows[row][d] + columns[col][d] + boxes[idx][d] == 0;
  }

  public void placeNumber(int d, int row, int col) {
    int idx = (row / n) * n + col / n;
    //  Place a number d in (row, col) cell
    rows[row][d]++;
    columns[col][d]++;
    boxes[idx][d]++;
    board[row][col] = (char)(d + '0');
  }

  public void removeNumber(int d, int row, int col) {
    int idx = (row / n) * n + col / n;
    rows[row][d]--;
    columns[col][d]--;
    boxes[idx][d]--;
    board[row][col] = '.';
  }

  public void placeNextNumbers(int row, int col) {
    if ((col == N - 1) && (row == N - 1) {
      sudokuSolved = true;
    } else {
      if (col == N - 1) {
        backtrack(row + 1, 0);
      } else {
        backtrack(row, col + 1);
      }
    }
  }

  public void backtrack(int row, int col) {
    if (board[row][col] == '.') {
      for (int d = 1; d < 10; d++) {
        if (couldPlace(d, row, col)) { // constrained programming
          //backtrack
          placeNumber(d, row, col);
          placeNextNumbers(row, col);

          if (!sudokuSolved) removeNumber(d, row, col);
        }
      }
    } else {
      placeNextNumbers(row, col);
    }
  }
}
```