Introduction
I start to practice coding in 2019 and try to push myself to finish another 200 medium level algorithm. I also follow others and write some comment based on my practice.
Sudoku solver
Here is my comment I wrote on the blog of a casual coder.
Jianmin ChenJanuary 11, 2019 at 11:49 AM
Thank you for sharing.
I really like the ideas in your implementation. I enumerate one by one in the following:
1. Preprocess all rows and columns and quadrants into data structure, O(1) to look up if the digit is available for next empty slot;
2. index variable from 0 to 80 is used to track the progress of depth first search, help to identify base case;
3. Step 1 is also very efficient since every element with digit values in the board will be added once at the beginning.
I make some minor changes and add some comment to help follow the calculation.
Hashtable -> HashSet
variable names:
rows -> rowDigits
cols -> colDigits
I rewrote the code and practice one more time, also I shared on Leetcode discuss.
https://leetcode.com/problems/sudoku-solver/discuss/217272/C-One-more-elegant-solution
One more comment
-
This comment has been removed by the author.
Very nice!!! This problem reminds me of the 8-queens problem doesn’t it? Same ideas. Cheers, Marcelo
///
/// The row and column should not include same digit more than once; quadrant as well.
///
private static bool AddNumber(int index,
int number,
HashSet[] rows,
HashSet[] cols,
HashSet[] quadrants)
{
// one row has 9 columns
int r = index / 9;
int c = index % 9;
// there are three rows and three columns quadrants.
// each row will have 27 elements
// each quadrant will have 9 elements
// First row quadrant
// Quadrant1 | Quadrant2 | Quadrant3
// by index
// 0 - 8 | 9 - 17 | 18 - 26
// by column
// 0 1 2 | 3 4 5 | 6 7 8
int q = (index / 27) * 3 + (index % 9) / 3;
if (!rows[r].Contains(number) &&
!cols[c].Contains(number) &&
!quadrants[q].Contains(number))
{
rows[r].Add(number);
cols[c].Add(number);
quadrants[q].Add(number);
return true;
}
return false;
}