# Valid Sudoku - LeetCode

#### Shashank_Choudhary

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:

#### Shashank_Choudhary

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++

#### Shashank_Choudhary

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;
}

#### Shashank_Choudhary

we need an array of unordered_Sets here not set of sets .. its solved now

#### 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:

#### Daniel Duffy

##### C++ author, trainer
Analogy

The Ariane 5 reused the code from the inertial reference platform from the Ariane 4, but the early part of the Ariane 5's flight path differed from the Ariane 4 in having higher horizontal velocity values. This caused an internal value BH (Horizontal Bias) calculated in the alignment function to be unexpectedly high.

#### Shashank_Choudhary

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 ..

#### Daniel Duffy

##### C++ author, trainer
Well I can't comment on the leetcode solution
I used std::array<std::unordered_set<int>, N> for the solution ..
That's a nice one; fixed array + embedded set. Even std::set is good I reckon.

#### Shashank_Choudhary

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?

#### Shashank_Choudhary

Because Java and Python are much easire than C++. Does Leetcode Inc. have the necessary C++ skills?
No they don't provide help for C++ . I google to find the corresponding data structure in C++ after reading their recommended solution

#### Shashank_Choudhary

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
Not much has changed in the grey matter of software since the 60s.

#### Shashank_Choudhary

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 !!

#### Daniel Duffy

##### C++ author, trainer
Here is a possible project

"Reproduce and/or improve the results in this thesis by doing it in C++20 (+ Python pybind11)"

V1: standard Heston
V2: rough Heston

Replies
14
Views
1K
Replies
0
Views
2K
Replies
2
Views
11K
Replies
18
Views
38K
Replies
32
Views
9K