Formatted question description: https://leetcode.ca/all/37.html

# 37. Sudoku Solver

Hard

## Description

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

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. 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 '.'.

A sudoku puzzle…

…and its solution numbers marked in red.

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.

# Algorithm

Similar to this question, there are Permutations, Combinations, N-Queens, etc., especially the N-Queens’s problem-solving idea is very similar.

For each grid that needs to be filled with numbers, enter 1 to 9, and every time a number is substituted Determine whether it is legal. If it is legal, continue to the next recursion, and set the number back to’.’ at the end. When judging whether the newly added number is legal, you only need to determine whether the current number is legal, not whether the array is a Sudoku array. Because the numbers added before are all legal, this can make the program more efficient.

The overall idea is this, but it can be implemented in different forms. One form of implementation is to recursively bring the horizontal and vertical coordinates. Since it is filled with numbers line by line, and starts from line 0, when i reaches 9, it means that all the numbers have been successfully filled in and return to true directly. When j is greater than or equal to 9, the current line is filled, and you need to switch to the next line to continue filling, then continue to call the recursive function, and the abscissa will bring i+1. Otherwise, if the current number is not a point, it means that the current position does not need to fill in a number, so call recursion on the right position.

If you need to fill in a number at the current position, you should try to fill in all the numbers from 1 to 9 and let c traverse from 1 to 9. Whenever you try to fill in a number, you need to check whether there is a conflict, and use another sub-function isValid To check whether it is legal, if not legal, skip the current number.

• If it is valid, assign the current position to this number, and call recursion on the right position. If the recursive function returns true, it means that it can be filled successfully and returns true directly.
• If it doesn’t work, you need to reset the state to restore the current position to a point. If all numbers are tried, but still fails, it will eventually return false.

The principle of checking whether the current array is valid is very similar to the previous Valid Sudoku, but it is simpler, because here we only need to check whether the newly added number will conflict with other positions, and detect the ranks and positions of the newly added numbers. Whether there are repeated numbers in the interval.

# Code

Java

• 
public class Sudoku_Solver {

public class Solution {

boolean found = false;

public void solveSudoku(char[][] b) {

if (b == null || b.length == 0)     return;

dfs(b, 0, 0);
}

public void dfs (char[][] b, int row, int col) {

if (row == b.length) {
found = true;
return;
}

for (int i = row; i < b.length; i++) {
for (int j = col; j < b[0].length; j++) {
if (b[i][j] != '.') {
continue;
}

// try from 1 to 9
int num = 1;
while (num <= 9) {

if (isValid(b, i, j, num)) {
b[i][j] = (char)('0' + num); // @note@note: must add cast

if (col < b[0].length - 1) {
dfs(b, row, col + 1);

if (found) {
return;
}

} else {
// dfs(b, row + 1, col);
dfs(b, row + 1, 0); // @note@note: index-0 of next row

if (found) {
return;
}
}

b[i][j] = '.'; // reset
}

num++;
}
}
}
}

public boolean isValid (char[][] b, int row, int col, int num) {

// search row
for (int i = 0; i < b[0].length; i++) {
if (b[row][i] == '0' + num)     return false;
}

// search column
for (int i = 0; i < b.length; i++) {
if (b[i][col] == '0' + num)     return false;
}

// search sub-square
int rowSub = row / 3;
int colSub = col / 3;
for (int i = rowSub; i < rowSub + 3; i++) {
for (int j = colSub; j < colSub + 3; j++) {
if (b[i][j] == '0' + num)     return false;
}
}

return true;
}
}

public class Solution_2 {

// +1 is for index simplicity
boolean[][] row = new boolean[9][9 + 1];
boolean[][] col = new boolean[9][9 + 1];
boolean[][] sub = new boolean[9][9 + 1];

// hard code number 9 is not good practise BTW
public void solveSudoku(char[][] board) {
if(board == null || board.length == 0) {
return;
}

solve(board, 0, 0);
}

public boolean solve(char[][] b, int i, int j) { // r: row, c: col

if(i == 8 && j == 9) { // reaching end of this matrix
return true;
}

if(b[i][j] != '.') {
char currentChar = b[i][j];
row[i][currentChar - '0'] = true;
col[j][currentChar - '0'] = true;
sub[i - i % 3 + j / 3][currentChar - '0'] = true;

if(i < 9) {
solve(b, i + 1, j);
} else {
solve(b, i, j + 1);
}

} else {

for(int test = 1; test <= 9; test++) {
if(row[i][test] == false && col[j][test] == false && sub[i - i % 3 + j / 3][test] == false) {
// set this test in marking map to be true
row[i][test] = true;
col[j][test] = true;
sub[i - i % 3 + j / 3][test] = true;

boolean isFound = false;
if(i < 9) {
isFound = solve(b, i + 1, j);
} else {
isFound = solve(b, i, j + 1);
}

if(isFound) {
return true;
}

// reset test value
row[i][test] = false;
col[j][test] = false;
sub[i - i % 3 + j / 3][test] = false;

}
}
}

return false;
}
}
}

• // OJ: https://leetcode.com/problems/sudoku-solver/
// Time: O((9!)^9)
// Space: O(81)
class Solution {
int row[9][9] = {}, col[9][9] = {}, box[9][9] = {};
bool valid(int x, int y, int i) {
return row[x][i] == 0 && col[y][i] == 0 && box[x / 3 * 3 + y / 3][i] == 0;
}
bool dfs(vector<vector<char>> &A, int x, int y) {
if (y == 9) {
++x;
y = 0;
}
if (x == 9) return true;
if (A[x][y] == '.') {
for (int i = 0; i < 9; ++i) {
if (!valid(x, y, i)) continue;
A[x][y] = '1' + i;
row[x][i] = col[y][i] = box[x / 3 * 3 + y / 3][i] = 1;
if (dfs(A, x, y + 1)) return true;
row[x][i] = col[y][i] = box[x / 3 * 3 + y / 3][i] = 0;
A[x][y] = '.';
}
return false;
}
return dfs(A, x, y + 1);
}
public:
void solveSudoku(vector<vector<char>>& A) {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (A[i][j] == '.') continue;
row[i][A[i][j] - '1'] = 1;
col[j][A[i][j] - '1'] = 1;
box[i / 3 * 3 + j / 3][A[i][j] - '1'] = 1;
}
}
dfs(A, 0, 0);
}
};

• class Solution(object):
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
cacheBox = [[0] * len(board) for _ in range(len(board))]
cacheRow = [[0] * len(board) for _ in range(len(board))]
cacheCol = [[0] * len(board) for _ in range(len(board))]

def helper(board, i, j, cacheRow, cacheCol, cacheBox):
if board[i][j] == ".":
for k in range(1, 10):
if i < 0 or i >= len(board) or j < 0 or j >= len(board):
continue
ib = (i / 3) * 3 + j / 3
if cacheRow[i][k - 1] == 1 or cacheCol[j][k - 1] == 1 or cacheBox[ib][k - 1] == 1:
continue

cacheRow[i][k - 1] = cacheCol[j][k - 1] = cacheBox[ib][k - 1] = 1
board[i][j] = str(k)
if i == j == len(board) - 1:
return True
if i + 1 < len(board):
if helper(board, i + 1, j, cacheRow, cacheCol, cacheBox):
return True
elif j + 1 < len(board):
if helper(board, 0, j + 1, cacheRow, cacheCol, cacheBox):
return True
board[i][j] = "."
cacheRow[i][k - 1] = cacheCol[j][k - 1] = cacheBox[ib][k - 1] = 0
else:
if i == j == len(board) - 1:
return True
if i + 1 < len(board):
if helper(board, i + 1, j, cacheRow, cacheCol, cacheBox):
return True
elif j + 1 < len(board):
if helper(board, 0, j + 1, cacheRow, cacheCol, cacheBox):
return True
return False

for i in range(len(board)):
for j in range(len(board)):
if board[i][j] != ".":
ib = (i / 3) * 3 + j / 3
k = int(board[i][j]) - 1
cacheRow[i][k] = cacheCol[j][k] = cacheBox[ib][k] = 1
print
helper(board, 0, 0, cacheRow, cacheCol, cacheBox)