Leetcode 37解数独c++
1347 ワード
考え方:2つのサブ関数を書き、1つは9*9の宮格に1つの数を追加した後、その宮格が有効な数独であるかどうかを検出することです.もう1つの関数は、スペースの空白に数値を追加し、最初の関数を使用して追加後に有効な数独であるかどうかを検出します.
class Solution {
public:
void solveSudoku(vector>& board) {
solvesudokuDFS(board,0,0);
}
bool solvesudokuDFS(vector >&board,int i,int j)
{
if(i==9) return true;
if(j>=9) return solvesudokuDFS(board,i+1,0);
if(board[i][j]=='.')
{
for( int k=1;k<=9;++k)
{
board[i][j]=(char)k+'0';
if(isvalid(board,i,j))
{
if(solvesudokuDFS(board,i,j+1)) return true;
}
board[i][j]='.';
}
}
else
{
return solvesudokuDFS(board,i,j+1);
}
return false;
}
bool isvalid (vector >&board,int i,int j)
{
for(int col=0;col<9;++col)
{
if(col!=j&&board[i][j]==board[i][col]) return false;
}
for(int row=0;row<9;++row)
{
if(row!=i&&board[i][j]==board[row][j]) return false;
}
for(int l=i/3*3;l