Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- Solution() {
- mBoardLen = 9;
- }
- void solveSudoku(vector<vector<char>>& board) {
- solveByDFS(0, 0, board);
- }
- bool solveByDFS(const int &row, const int &col, vector<vector<char>>& board) {
- //> ending criteria
- if(row == mBoardLen) {
- return true;
- }
- else if(col == mBoardLen) {
- return solveByDFS(row+1, 0, board);
- }
- //> solve sudoku
- if(board[row][col] == '.') {
- for(int i = 0; i < 9; i++) {
- char ch = static_cast<char>('1' + i);
- board[row][col] = ch;
- if(isValid(row, col, board)) {
- if(solveByDFS(row, col+1, board)) {
- return true;
- }
- }
- //> current number is either non-valid
- //> or non-solvable
- board[row][col] = '.';
- }
- }
- else {
- return solveByDFS(row, col+1, board);
- }
- return false;
- }
- bool isValid(const int &row, const int &col, vector<vector<char>>& board) {
- //> check row
- for(int c = 0; c < mBoardLen; c++) {
- if(c != col && board[row][c] == board[row][col]) {
- return false;
- }
- }
- //> check col
- for(int r = 0; r < mBoardLen; r++) {
- if(r != row && board[r][col] == board[row][col]) {
- return false;
- }
- }
- //> check cube
- int rStart = 3 * (row / 3);
- int cStart = 3 * (col / 3);
- for(int r = rStart; r < rStart + 3; r++) {
- for(int c = cStart; c < cStart + 3; c++) {
- if(r != row && c != col && board[r][c] == board[row][col]) {
- return false;
- }
- }
- }
- return true;
- }
- private:
- int mBoardLen;
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement