37. Sudoku Solver

题目描述

37. Sudoku Solver

回溯

class Solution {vector<vector<bool>> row_used;vector<vector<bool>> col_used;vector<vector<bool>> box_used;public:void solveSudoku(vector<vector<char>>& board) {row_used.resize(9,vector<bool>(9,false));col_used.resize(9,vector<bool>(9,false));box_used.resize(9,vector<bool>(9,false));for(int row= 0;row < 9;row++){for(int col = 0;col < 9;col++){if(board[row][col] != '.'){int digit = board[row][col] - '0' -1;row_used[row][digit] = true;col_used[col][digit] = true;box_used[(row/3)*3 + col/3][digit] = true;}}}backtrack(board);}bool backtrack(vector<vector<char>>& board){for(int row = 0;row < 9;row++){for(int col = 0;col < 9;col++){if(board[row][col] != '.')continue;for(int digit = 0;digit<9;digit++){if(row_used[row][digit])continue;if(col_used[col][digit])continue;if(box_used[(row/3)*3+ col/3][digit])continue;row_used[row][digit] = true;col_used[col][digit] = true;box_used[(row/3)*3+ col/3][digit] = true;board[row][col] = '0'+ digit + 1;if(backtrack(board)) return true;board[row][col] = '.';row_used[row][digit] = false;col_used[col][digit] = false;box_used[(row/3)*3+ col/3][digit] = false;}return false;}}return true;}
};

可以事先把需要填数的空格存起来

class Solution {vector<vector<bool>> row_used;vector<vector<bool>> col_used;vector<vector<bool>> box_used;vector<pair<int,int>> spaces;//事先把需要填数的空格存起来
public:void solveSudoku(vector<vector<char>>& board) {row_used.resize(9,vector<bool>(9,false));col_used.resize(9,vector<bool>(9,false));box_used.resize(9,vector<bool>(9,false));for(int row= 0;row < 9;row++){for(int col = 0;col < 9;col++){if(board[row][col] != '.'){int digit = board[row][col] - '0' -1;row_used[row][digit] = true;col_used[col][digit] = true;box_used[(row/3)*3 + col/3][digit] = true;}else{spaces.emplace_back(row,col);}}}backtrack(board,0);}//每次调用，处理一个需要填数的空格bool backtrack(vector<vector<char>>& board,int space_idx){if(space_idx == spaces.size())return true;auto [row,col] = spaces[space_idx];for(int digit = 0;digit<9;digit++){if(row_used[row][digit])continue;if(col_used[col][digit])continue;if(box_used[(row/3)*3+ col/3][digit])continue;row_used[row][digit] = true;col_used[col][digit] = true;box_used[(row/3)*3+ col/3][digit] = true;board[row][col] = '0'+ digit + 1;if(backtrack(board,space_idx+1)) return true;board[row][col] = '.';row_used[row][digit] = false;col_used[col][digit] = false;box_used[(row/3)*3+ col/3][digit] = false;}return false;}
};