# [LeetCode 37] Sudoku Solver

### Question

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.

A sudoku puzzle...

...and its solution numbers marked in red.

### Stats

 Frequency 2 Difficulty 4 Adjusted Difficulty 5 Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Solution

This is a very classic DFS search problem, and it is not easy.

The solution simply brute force DFS. Read more at this blog.

### My code

``````public class Solution {
public void solveSudoku(char[][] board) {
if (board == null || board.length == 0) {
return;
}
int N = board.length;
board = helper(board, N, 0, 0);
}

private char[][] helper(char[][] board, int N, int x, int y) {
if (x == N) {
return board;
} else if (y == N) {
return helper(board, N, x + 1, 0);
} else if (board[x][y] != '.') {
return helper(board, N, x, y + 1);
} else {
// put in from 1 to 9, and then check validation
for (int i = 1; i <= 9; i++) {
board[x][y] = (char) ('0' + i);
if (isValid(board, x, y)) {
// if the number we just put in is valid inside the board
char[][] ans = helper(board, N, x, y + 1);
if (ans != null) {
return ans;
} else {
// putting in this number (i) will not work, so...
// put in next number and try, until 9
}
}
// this is important for backtarcking - set the char back to its original value!!!
board[x][y] = '.';
}
}
// in fact, we can just return true/false for this question.
return null;
}

// this validation method we borrowed from my old code
private boolean isValid(char[][] board, int i, int j) {
boolean[] map = new boolean[9];
for (int k = 0; k < 9; k++)
if (k != j && board[i][k] == board[i][j])
return false;
for (int k = 0; k < 9; k++)
if (k != i && board[k][j] == board[i][j])
return false;
for (int row = i / 3 * 3; row < i / 3 * 3 + 3; row++)
for (int col = j / 3 * 3; col < j / 3 * 3 + 3; col++)
if ((row != i || col != j) && board[row][col] == board[i][j])
return false;
return true;
}
}
``````