Array

Question 1

2-D Array
Validate Sudoku (row, column, sub-box) using string

Answer 1

Collect the set of things we see, encoded as strings. For example:
‘4’ in row 7 is encoded as “(4)7”.
‘4’ in column 7 is encoded as “7(4)”.
‘4’ in the top-right block is encoded as “0(4)2”.
Scream false if we ever fail to add something because it was already added (i.e., seen before).

public boolean isValidSudoku(char[][] board) {
Set seen = new HashSet();
for (int i=0; i<9; ++i) {
for (int j=0; j<9; ++j) {
if (board[i][j] != ‘.’) {
String b = “(“ + board[i][j] + “)”;
if (!seen.add(b + i) || !seen.add(j + b) || !seen.add(i/3 + b + j/3))
return false;
}
}
}
return true;
}

Question 2

2-D Array
Validate Sudoku (row, column, sub-box) using char

Answer 2

public boolean isValidSudoku(char[][] board) {
for(int i = 0; i<9; i++){
HashSet<Character> rows = new HashSet<Character>();
HashSet<Character> columns = new HashSet<Character>();
HashSet<Character> cube = new HashSet<Character>();
for (int j = 0; j < 9;j++){
if(board[i][j]!='.' && !rows.add(board[i][j]))
return false;
if(board[j][i]!='.' && !columns.add(board[j][i]))
return false;
int RowIndex = 3*(i/3);
int ColIndex = 3*(i%3);
if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !cube.add(board[RowIndex + j/3][ColIndex + j%3]))
return false;
}
}
return true;
}</Character></Character></Character></Character></Character></Character>

Question 3

Explanation why using / and % for 2d matrix traversal specifically for sudoku

Answer 3

Just trying to explain how to think about % and /. These two operators can be helpful for matrix traversal problems.

For a block traversal, it goes the following way.

0,0, 0,1, 0,2; < — 3 Horizontal Steps followed by 1 Vertical step to next level.

1,0, 1,1, 1,2; < — 3 Horizontal Steps followed by 1 Vertical step to next level.

2,0, 2,1, 2,2; < — 3 Horizontal Steps.

And so on…
But, the j iterates from 0 to 9.

But we need to stop after 3 horizontal steps, and go down 1 step vertical.

Use % for horizontal traversal. Because % increments by 1 for each j : 0%3 = 0 , 1%3 = 1, 2%3 = 2, and resets back. So this covers horizontal traversal for each block by 3 steps.

Use / for vertical traversal. Because / increments by 1 after every 3 j: 0/3 = 0; 1/3 = 0; 2/3 =0; 3/3 = 1.

So far, for a given block, you can traverse the whole block using just j.

But because j is just 0 to 9, it will stay only first block. But to increment block, use i. To move horizontally to next block, use % again : ColIndex = 3 * i%3 (Multiply by 3 so that the next block is after 3 columns. Ie 0,0 is start of first block, second block is 0,3 (not 0,1);

Similarly, to move to next block vertically, use / and multiply by 3 as explained above. Hope this helps.

Question 4

Example for how this works in real life for each iteration (when I = 0 and j runs [0,8])

Answer 4

i j RowIdx ColIdx RowIdx + j/3 ColIdx + j%3
0 0 0 0 0 0
0 1 0 0 0 1
0 2 0 0 0 2
0 3 0 0 1 0
0 4 0 0 1 1
0 5 0 0 1 2
0 6 0 0 2 0
0 7 0 0 2 1
0 8 0 0 2 2