Simple and Clean Solution / C++


  • 27
    N
    bool check(vector<vector<char>> &board, int i, int j, char val)
    {
        int row = i - i%3, column = j - j%3;
        for(int x=0; x<9; x++) if(board[x][j] == val) return false;
        for(int y=0; y<9; y++) if(board[i][y] == val) return false;
        for(int x=0; x<3; x++)
        for(int y=0; y<3; y++)
            if(board[row+x][column+y] == val) return false;
        return true;
    }
    bool solveSudoku(vector<vector<char>> &board, int i, int j)
    {
        if(i==9) return true;
        if(j==9) return solveSudoku(board, i+1, 0);
        if(board[i][j] != '.') return solveSudoku(board, i, j+1);
    
        for(char c='1'; c<='9'; c++)
        {
            if(check(board, i, j, c))
            {
                board[i][j] = c;
                if(solveSudoku(board, i, j+1)) return true;
                board[i][j] = '.';
            }
        }
            
        return false;
    }
    

    public:
    void solveSudoku(vector<vector<char>>& board) {
    solveSudoku(board, 0, 0);
    }


  • 3
    D

    Like the solution.

    Just for function check , seems it can be compressed within 1 loop

       bool check(vector<vector<char>>& board, int i, int j, char val) {
    
        for( int h=0;h<9;h++)
            {
            if(board[i][h]==val) return false; /* check row */
            if(board[h][j]==val) return false; /* check col */
            if(board[i-i%3+h/3][j-j%3+h%3]==val)return false; /* check cube */
            }
            
        return true;
    }

  • 0
    S

    Please give the time complexity of this solution


  • 2
    S

    A more optimised check() using hashing ( 5 times faster execution -> 8 ms )

    The above code takes 44 ms.

    class Solution {
    private:
        int row[9][256], col[9][256], cube[3][3][256];
    public:
        void solveSudoku(vector<vector<char>>& board) {
            memset(row,0,sizeof(row));
            memset(col,0,sizeof(col));
            memset(cube,0,sizeof(col));
            
            // hash the already existing cell values
            for (int r = 0; r < 9; r++) {
                for (int c = 0; c < 9; c++) {
                    if (board[r][c] != '.') {
                        int d = board[r][c];
                        row[r][d] = 1; col[c][d] = 1; cube[r/3][c/3][d] = 1;
                    }
                }
            }
            
            solveSudoku(board, 0, 0);
        }
    private:
        bool check(vector<vector<char>>& board, int r, int c, char val)
        {
            if(row[r][val] == 1) return false;
            if(col[c][val] == 1) return false;
            if(cube[r/3][c/3][val] == 1) return false;
            return true;
        }
        bool solveSudoku(vector<vector<char>> &board, int i, int j)
        {
            if(i==9) return true;
            if(j==9) return solveSudoku(board, i+1, 0);
            if(board[i][j] != '.') return solveSudoku(board, i, j+1);
        
            for(char d='1'; d<='9'; d++)
            {
                if(check(board, i, j, d))
                {
                    board[i][j] = d;
                    row[i][d] = 1; col[j][d] = 1; cube[i/3][j/3][d] = 1;  // hash the digit 'd'
                    if(solveSudoku(board, i, j+1)) return true;
                    board[i][j] = '.';
                    row[i][d] = 0; col[j][d] = 0; cube[i/3][j/3][d] = 0;  // unhash the digit 'd'
                }
            }
        
            return false;
        }
    };

  • 0
    B
    This post is deleted!

  • 1
    X

    no need to store use [256], just store the digit from '1'-'9' is fine. BTW, nice solution!

    // leetcode 37, sudoku solver
    class Solution {
        int row[9][10], col[9][10], cube[3][3][10];
    public:
        void solveSudoku(vector<vector<char>>& board) {
            memset(row, 0, sizeof(row));
            memset(col, 0, sizeof(col));
            memset(cube, 0, sizeof(cube));
            for (int r = 0; r < 9; r++) {
                for (int c = 0; c < 9; c++) {
                    if (board[r][c] != '.') {
                        row[r][board[r][c] - '0'] = 1;
                        col[c][board[r][c] - '0'] = 1;
                        cube[r/3][c/3][board[r][c] - '0'] = 1;
                    } 
                }
            }
            dfs(0, 0, board);
        }
        
        bool dfs(int i, int j, vector<vector<char>>& board) {
            if (i == 9) return true;
            if (j == 9) return dfs(i + 1, 0, board);
            if (board[i][j] != '.') return dfs(i, j + 1, board);
            
            for (char c = '1'; c <= '9'; c++) {
                if (feasible(i, j, c)) {
                    board[i][j] = c;
                    row[i][c - '0'] = 1; col[j][c - '0'] = 1; cube[i/3][j/3][c - '0'] = 1;
                    if (dfs(i, j + 1, board)) return true;
                    row[i][c - '0'] = 0; col[j][c - '0'] = 0; cube[i/3][j/3][c - '0'] = 0;
                    board[i][j] = '.';
                }
            }
            return false;
        }
        
        bool feasible(int curRow, int curCol, char c) {
            if (row[curRow][c - '0'] == 1) return false;
            if (col[curCol][c - '0'] == 1) return false;
            if (cube[curRow/3][curCol/3][c - '0'] == 1) return false;
            return true;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.