c++recursionbacktrackingrecursive-backtracking

Sudoku Solver code gives unexpected result


Question Link: https://leetcode.com/problems/valid-sudoku/description/

Below is my code for Sudoku Solver. I am expected to return true if the sudoku is solvable else false.

class Solution {
public:
    bool solveSudoku(vector<vector<char>> &board, int row, int col) {
        // If the position is now at the end of the 9*9 grid
        if(row == 8 and col == 9) return true;
        // if column has reached upper bound
        if(col==9)  {
            row++;
            col=0;
        }
        // For characters other than dot move to the next position
        if(board[row][col]!='.') return solveSudoku(board,row,col+1); 
        for(int i=1; i<=9; i++) {
            char num='0'+i;
            if(isValid(board, row, col, num)) {
                board[row][col]=num;
                if(solveSudoku(board,row,col+1)) return true;
            }
            board[row][col]='.';
        }
        return false;
    }
    bool isValid(vector<vector<char>> &board, int row, int col, char num) {
        int i,j;
        /* Checking if its duplicated on the same row */
        for(i=0; i<9; i++) {
            if(i!=col && board[row][i] == num) {
                return false;
            }
        }
        /* Checking if its duplicated on the same col */
        for(i=0; i<9; i++) {
            if(i!=row && board[i][col] == num) {
                return false;
            }
        }
        /* Checking if its duplicated inside the 3*3 grid */
        int rowOffset=row-(row%3);
        int colOffset=col-(col%3);
        for(i=0; i<3;i++) {
            for(j=0;j<3;j++) {
                if((rowOffset+i)!=row && (colOffset+j)!=col && board[rowOffset+i][colOffset+j] == num) {
                    return false;
                }
            }
        }
        return true;
    }
    bool isValidSudoku(vector<vector<char>>& board) {
        if(solveSudoku(board, 0, 0)) return true;
        return false;
    }
};

for the below test input

[[".","8","7",  "6","5","4",  "3","2","1"],
 ["2",".",".",  ".",".",".",  ".",".","."],
 ["3",".",".",  ".",".",".",  ".",".","."],

 ["4",".",".",  ".",".",".",  ".",".","."], 
 ["5",".",".",  ".",".",".",  ".",".","."],
 ["6",".",".",  ".",".",".",  ".",".","."],

 ["7",".",".",  ".",".",".",  ".",".","."],
 ["8",".",".",  ".",".",".",  ".",".","."],
 ["9",".",".",  ".",".",".",  ".",".","."]]

Note: This is a leetcode question

It returns false which I feel is correct but the expected answer is true. How is this supposed to be a wrong Answer. Could anyone pls explain.

Thanks in advance


Solution

  • You are misinterpreting the task.

    Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

    The filled cells do NOT violate Sudoku's rules.