# 37. 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 ‘.’.

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.

Difficulty: Hard

``````class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
if (board.size()==0 || board[0].size()==0) return;
solve(board);
}

bool solve(vector<vector<char> > &board)
{
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
if (board[i][j]=='.') {
//从1到9一个个尝试
for (char c = '1'; c <= '9'; c++) {
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (solve(board))
return true; //如果是解 就返回true
else
board[i][j] = '.'; //如果不是解,就返回
}
}
return false; //1-9 都尝试过了没解,返回false,说明上一层错误
}
}
}
return true;
}

bool isValid(vector<vector<char> > &board,int row,int col,char c)
{
for (int i=0; i<9; i++) {
if (board[i][col] != '.' && board[i][col] == c) return false; //验证行
if (board[row][i] != '.' && board[row][i] == c) return false; //验证列
//验证3x3的块.遍历这个board的这个3x3的块,看看是否有与c相同的字符,有的话就不合法.
if (board[3*(row/3)+i/3][3*(col/3)+i%3] != '.' && board[3*(row/3)+i/3][3*(col/3)+i%3] == c) return false;
}

return true;
}
};
``````