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.
class Solution {
public:
void solveSudoku(vector<vector<char>> &board) {
int line=,column=-;
findNextEmpty(board,line,column);
backtracking(board,line,column);
}
bool backtracking(vector<vector<char>> &board,int line, int column)
{
int i=line, j = column;
for(int k = ; k<=; k++)
{
if(!isValid(board,line,column,k+'')) continue;
board[line][column] = k+'';
if(!findNextEmpty(board,line,column)) return true; //if no empty cell is found
if(backtracking(board,line,column)) return true;
//backTracking
line = i;
column = j;
}
//backTracking
board[line][column] = '.';
return false; //if no valid number is found
}
//为回溯法写一个独立的check函数
bool isValid(vector<vector<char>> &board, int line, int column, char value)
{
//check九宫格的一个格
int upperBoard = line/ * ;
int leftBoard = column/ * ;
for(int i = ; i<; i++)
{
for(int j = ; j<; j++)
{
if(board[upperBoard+i][leftBoard+j] == value) return false;
}
}
//check 列
for(int i = ; i<; i++)
{
if(board[line][i] == value) return false;
}
//check行
for(int i = ; i<; i++)
{
if(board[i][column] == value) return false;
}
return true;
}
bool findNextEmpty(vector<vector<char>> &board, int &line, int &column){
int i,j;
for(j = column+; j < ; j++){
if(board[line][j]!='.') continue;
column=j;
return true;
}
for(i = line+; i < ; i++){
for(j = ; j < ; j++){
if(board[i][j]!='.') continue;
line = i;
column=j;
return true;
}
}
return false;
}
};