Valid Sudoku - LeetCode

Hi ,

I want to implement the JAVA solution to the valid sudoku problem on LeetCode in C++. It uses hashset<hashset> form . I understand std::unordered_set<std::unordered_set<int>> would be the ideal DS but I am struggling to default initialize it . You can see the snippet of the JAVA solution below ,
Java:
public boolean isValidSudoku(char[][] board) {
        int N = 9;

        // Use hash set to record the status
        HashSet<Character>[] rows = new HashSet[N];
        HashSet<Character>[] cols = new HashSet[N];
        HashSet<Character>[] boxes = new HashSet[N];
        for (int r = 0; r < N; r++) {
            rows[r] = new HashSet<Character>();
            cols[r] = new HashSet<Character>();
            boxes[r] = new HashSet<Character>();
        }
        
        .....
        
        }

Any help would be much appreciated !
Thanks :)
 

Daniel Duffy

C++ author, trainer
What problems are you trying to solve?
Scary code and it is JAVA!!!!

The term cargo cult programmer may apply when anyone inexperienced with the problem at hand copies some program code from one place to another with little understanding of how it works or whether it is required.


Of course, I might be missing some vital information.
 
Last edited:
What problems are you trying to solve?
Scary code and it is JAVA!!!!

The term cargo cult programmer may apply when anyone inexperienced with the problem at hand copies some program code from one place to another with little understanding of how it works or whether it is required.


Of course, I might be missing some vital information.
This is the problem statement :

I realized I did start a thread when I solved this question for the first time using vectors Java Data Structure in C++
 
But I want to replicate the HashSet<> code above using unordered_set ...
This is one solution to the problem using vectors ,

C++:
bool isValidSudoku(vector<vector<char>>& board)
    {
       int N = 9;
        std::vector<int> row(N);
        std::vector<int> col(N);
        std::vector<int> box(N);
        
      
        for(int r = 0; r < N ; ++r)
        {
            for(int c = 0; c < N ; ++c)
            {
                if(board[r][c] == '.')
                    continue;
                int val = board[r][c] - '0';
                int pos = 1 << (val -1);
                if((row[r] & pos) > 0)
                    return false;
                row[r] |= pos;
                    
                if((col[c] & pos) > 0)
                    return false;
                col[c] |= pos;
                    
                int idx = (r/3) * 3 + c/3;
                if((box[idx] & pos) > 0)
                    return false;
                box[idx] |= pos;
            }
        }
        
        return true;
    }
 

Daniel Duffy

C++ author, trainer
This is the problem statement :

I realized I did start a thread when I solved this question for the first time using vectors Java Data Structure in C++
The specification is ambiguous

1. Is Example 1 an example of a valid board?'OK, yes it is.

2. "Each row must contain the digits 1-9 without repetition."
is ambiguous

"Each row must contain non-repeating subset digits 1-9 without repetition. Blanks are alowed."
3. It is a compile-time matrix really, yes.

//

I would use a compile-time matrix based onn std::array<std::array<int, NCols>, NRows> + multithreadin environment, e.g.

A. 1 thread to process rows
B. 1 thread to process columns
C. 2(or 4?) to process sub-matrices

The final challenge is to check uniqueness. C++ has not std::is_unique but C++20 has std::unique_copy. Check sizes of original and "uniqued" containers.

// it's a great way to learn parallel programming, BTW. The pattern is called Geometric Decomposition.
 
Last edited:

Daniel Duffy

C++ author, trainer
But I want to replicate the HashSet<> code above using unordered_set ...
This is one solution to the problem using vectors ,

C++:
bool isValidSudoku(vector<vector<char>>& board)
    {
       int N = 9;
        std::vector<int> row(N);
        std::vector<int> col(N);
        std::vector<int> box(N);
  
 
        for(int r = 0; r < N ; ++r)
        {
            for(int c = 0; c < N ; ++c)
            {
                if(board[r][c] == '.')
                    continue;
                int val = board[r][c] - '0';
                int pos = 1 << (val -1);
                if((row[r] & pos) > 0)
                    return false;
                row[r] |= pos;
              
                if((col[c] & pos) > 0)
                    return false;
                col[c] |= pos;
              
                int idx = (r/3) * 3 + c/3;
                if((box[idx] & pos) > 0)
                    return false;
                box[idx] |= pos;
            }
        }
  
        return true;
    }
I don't see why you need those 3 vectors row, col, box. They are just views of board.
And where are they initialised?

maybe std::array better than std::vector here?

// the original Java HashSet is so wrong. And "char"....
 
Last edited:
I don't see why you need those 3 vectors row, col, box. They are just views of board.
And where are they initialised?

maybe std::array better than std::vector here?

// the original Java HashSet is so wrong. And "char"....
Well I can't comment on the leetcode solution :)
I used std::array<std::unordered_set<int>, N> for the solution ..
 
I believe we don’t need ordering here thats why I chose unordered_set .. also its very frustrating that these websites don’t provide C++ solutions . I have premium membership still all the questions have Java/Python implementation!
 

Daniel Duffy

C++ author, trainer
I believe we don’t need ordering here thats why I chose unordered_set .. also its very frustrating that these websites don’t provide C++ solutions . I have premium membership still all the questions have Java/Python implementation!
In the old days there were no sites, so you had to do it yourself.
We are in a new phase of software ... the copy and paste generation.

I have heard this criticism from at least 6 experienced project leaders /architects in the last months. It's a big problem.

I give my first face-to-face course in 3 years (there was a lockdown you know) and I experienced it first-hand.

The focus is rather skewed at the moment.

Just a remark.
 
Last edited:

Daniel Duffy

C++ author, trainer
I believe we don’t need ordering here thats why I chose unordered_set .. also its very frustrating that these websites don’t provide C++ solutions . I have premium membership still all the questions have Java/Python implementation!
Because Java and Python are much easire than C++. Does Leetcode Inc. have the necessary C++ skills?
 
In the old days there were no sites, so you had to do it yourself.
We are in a new phase of software ... the copy and paste generation.

I have heard this criticism from at least 6 experienced project leaders /architects in the last months. It's a big problem.

I give my first face-to-face course in 3 years (there was a lockdown you know) and I experienced it first-hand.

The focus is rather skewed at the moment.

Just a remark.
So what would be your recommendation ? Should I pickup a standard Algorithms book like Introduction to Algorithms by Cormen (used at MIT) and try to implement solutions from scratch. You are absolutely right about the "copy paste" culture !!
I am doing this as part of my quant trader/developer job interview prep. I manage to solve the pure C++ questions, thanks to your courses here on Quantnet :) but I struggle with Algorithms ..
 

Daniel Duffy

C++ author, trainer
So what would be your recommendation ? Should I pickup a standard Algorithms book like Introduction to Algorithms by Cormen (used at MIT) and try to implement solutions from scratch. You are absolutely right about the "copy paste" culture !!
I am doing this as part of my quant trader/developer job interview prep. I manage to solve the pure C++ questions, thanks to your courses here on Quantnet :) but I struggle with Algorithms ..

Doing/knowing algorithms is important. Why not start with 1) understanding and b) applying industry standard STL algorithms. Use them on a need-be basis.

Writing your own b-tree ADT is nice but very 90s. Leave it to C++ and other experts, just like we don't (usually) write our own matrix solvers.

I haven't given an algo course since late 1990s.

Better to learn how to write maintainable code. Desing Patterns are good, if done correctly.

And LOTS of real programming.
 
Last edited:

Daniel Duffy

C++ author, trainer
Doing/knowing algorithms is important. Why not start with 1) understanding and b) applying industry standard STL algorithms. Use them on a need-be basis.

Writing your own b-tree ADT is nice but very 90s. Leave it to C++ and other experts, just like we don't (usually) write our own matrix solvers.

I haven't given an algo course since late 1990s.

Better to learn how to write maintainable code. Desing Patterns are good, if done correctly.

And LOTS of real programming.
Thank you :)
I guess all of this I can follow this if I work on a project . I am exploring a few ideas , hopefully I will find something interesting this summer !!
 
Top