首页 > 代码库 > Sudoku Solver & Valid Sudoku
Sudoku Solver & Valid Sudoku
方法:采用递归的方式
class Solution { public: void solveSudoku(vector<vector<char>>& board) { solve(board); } bool solve(vector<vector<char>> &board) { for(int i=0; i<9; ++i) { for(int j=0; j<9; ++j) { if(board[i][j] == ‘.‘) { for(int k=0; k<9; ++k) { board[i][j] = k + ‘1‘; if(isValid(board, i, j) && solve(board)) return true; board[i][j] = ‘.‘; } return false; } } } return true; } bool isValid(vector<vector<char>> &board, int i, int j) { for(int k=0; k<9; ++k) if(i != k && board[i][j] == board[k][j]) return false; for(int k=0; k<9; ++k) if(j != k && board[i][j] == board[i][k]) return false; for(int m=3*(i/3); m<3*(i/3+1); ++m) for(int n=3*(j/3); n<3*(j/3+1); ++n) if(!(i == m && j == n) && board[i][j] == board[m][n]) return false; return true; } };
Valid Sudoku
判别方法同上
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { for(int i=0; i<9; ++i) for(int j=0; j<9; ++j) if(board[i][j] != ‘.‘ && !isValid(board, i, j)) return false; return true; } bool isValid(vector<vector<char>> &board, int i, int j) { for(int k=0; k<9; ++k) if(i != k && board[i][j] == board[k][j]) return false; for(int k=0; k<9; ++k) if(j != k && board[i][j] == board[i][k]) return false; for(int m = 3*(i/3); m<3*(i/3+1); ++m) for(int n = 3*(j/3); n<3*(j/3+1); ++n) if(!(m == i && n == j) && board[i][j] == board[m][n]) return false; return true; } };
Sudoku Solver & Valid Sudoku
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。