C++ very simple and easy understand. using bit operation


  • 79
    L
       bool isValidSudoku(vector<vector<char>>& board) {
        vector<short> col(9, 0);
        vector<short> block(9, 0);
        vector<short> row(9, 0);
        for (int i = 0; i < 9; i++)
         for (int j = 0; j < 9; j++) {
             if (board[i][j] != '.') {
                 int idx = 1 << (board[i][j] - '0');
                 if (row[i] & idx || col[j] & idx || block[i/3 * 3 + j / 3] & idx)
                    return false;
                row[i] |= idx;
                col[j] |= idx;
                block[i/3 * 3 + j/3] |= idx;
             }
         }
         return true;
      }

  • 0
    Y

    very nice solution!!


  • 0
    J

    Wow that's brilliant!!!
    Thank you so much for providing such a nice solution!


  • 0
    Z

    It can't be better one!


  • 0
    B

    You don't need the row vector, just a variable is OK, and reset row variable to zero after each inner loop.


  • 0
    C

    extremely smart answer!!!!!!!!!!!
    how can you figure it out!!???


  • 0
    I

    @zhouzhuofu :how it could be done ?


  • 0
    I

    @bng0517 :how it could be done?


  • 0

    The best solution!


  • 0
    H

    So similar with code. In fact,you needn't use vector to store row's result. This are my codes:

    class Solution {
    public:
        bool isValidSudoku(vector<vector<char>>& board) {
            vector<int> col_num(9);
            vector<int> grid(9);
            for(int row=0;row<9;row++) {
                int row_num=0;
                for(int col=0;col<9;col++) {
                    if(board[row][col]!='.') {
                        int num=1<<(board[row][col]-'1');
                        if(row_num&num || col_num[col]&num || grid[col/3+3*(row/3)]&num)
                            return false;
                        row_num|=num;
                        col_num[col]|=num;
                        grid[col/3+3*(row/3)]|=num;
                    }
                }   
            }
            return true;
        }
    };
    

  • 0

    Very nice solution! Could someone please explain how the formula for assigning the blocks block[i/3 * 3 + j / 3] works? I'm having a hard time understanding it. Thanks!


Log in to reply
 

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