Leetcode 37: Sudoku Solver

Dec. 5, 2017

Introduction

It is the classical depth first algorithm called Sudoku solver. I had great time to practice mock interview and completed the code and passed all test cases in 28 minutes. The peer was very helpful, and I was told that there is a bug on line 29 and missing a function argument on line 58 after I did whiteboard testing.

Here is C# code.


Dec. 6, 2017

Two more comments after mock interview, one is to understand C# keyword const and static, and second one is to think carefully about const variable meaningful name.

Static vs Const

I wrote line 5 public static const int SIZE = 8; in mock interview, compile error, so I quickly removed const keyword in the mock interview. Need to look into the const in C# again.

Later I learned that const is static automatically, but static can be modified, not readonly. So I should write line 5 like the following:

public static readonly int SIZE = 8; 

or

public const int SIZE = 8; 

SIZE or LASTCOLUMN

It is good to name a variable using meaningful one. Let us discuss more here.

Board is 9 * 9 matrix, I added = sign after < on line 9 to make line 9 in the following:
board.GetLength(0) <= SIZE

better saying
board.GetLength(0) <= LASTCOLUMN


When I did whiteboard testing, I added equal = sign.The matrix's SIZE is 9, and LASTCOLUMN = 8. So the variable name on line 5 should
better be called LASTCOLUMN = 8

Line 5: public static int LASTCOLUMN = 8.

Actionable Items

1. Read C# Keywords/Modifiers/Access Modifiers/const, the link is here. There are around 12 access modifiers, plan to read one by one. Abstract, async, const, event, extern, in, out, override, readonly, sealed, static, unsafe, virtual, volatile.

2. C# static vs const on stackoverflow, link is here.

Plan to read 10 minutes on this discussion:

Argument or facts:


It is interesting to note that const members are always static, whereas a readonly member can be either static or not, just like a regular field.

3. One more thing is to review code review website the algorithm I asked about Sudoku solver, and understand the code review about complaints about const value 8 or 9 all over the code. 

The code review is called Sudoku solver recursive solution with clear structure, I posted it 30 days ago. 

Leetcode 37: Sudoku Solver

July 19, 2015

Problem statement:

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

Solution 1: 

Great blog to read:

http://blog.csdn.net/fightforyourdream/article/details/16916985

And then, start to implement the solution using C# code:

https://github.com/jianminchen/sudokuSolver/blob/master/Program.cs

Solution 2: 

Read the blog,
http://blog.csdn.net/linhuanmars/article/details/20748761

and then, implement the solution using c# code:

https://github.com/jianminchen/sudokuSolver/blob/master/Program2.cs

Solution 3: (good workout on C# KeyValuePair class)

and then, convert C++ code to C# code from the blog:
https://github.com/yinlinglin/LeetCode/blob/master/SudokuSolver.h

Excellent code in C++, using class for node on the board. Learn a few things, fun to play with the code

C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program3.cs

solution 4:
https://github.com/jianminchen/sudokuSolver/blob/master/Program4.cs
source code from the blog:
https://github.com/xiaoxq/leetcode-cpp/blob/master/src/SudokuSolver.cpp

Solution 5:
read the blog: (Good coding! practice more based on this blog)
https://github.com/zwxxx/LeetCode/blob/master/Sudoku_Solver.cpp

and convert the C++ code to C# code, (great workout on C# LinkedList for blank nodes)

https://github.com/jianminchen/sudokuSolver/blob/master/Program5.cs

Solution 6:
read the blog:
http://shanjiaxin.blogspot.ca/2014/04/sudoku-solver-leetcode.html

and convert Java code to C# code, great workout on C# and logic checking "return false"

https://github.com/jianminchen/sudokuSolver/blob/master/Program6.cs

Solution 7:
blog:
http://www.jiuzhang.com/solutions/sudoku-solver/
C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program7.cs

Solution 8:
Thanks for the blog's highlight line of code on back tracking; finally, I got it! My logic thinking has flaws on back tracking; extra backtracking is not a good. Minimize the back tracking, only do it when "return false". It makes sense to do that.

blog:
http://bangbingsyb.blogspot.ca/2014/11/leetcode-valid-sudoku-sudoku-solver.html
C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program8.cs

Solution 9:
blog:
http://www.cnblogs.com/TenosDoIt/p/3800485.html

C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program9.cs

Solution 10:
blog: (Excellent implementation! no extra line or number in the code! Best for memorization! Go through other solutions later. )
https://github.com/rffffffff007/leetcode/blob/master/Sudoku%20Solver.java

C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program10.cs

算法理解了, 代码可以记住了; 开始看不同的题解, 看看高手的代码; 从不同的题解中, 模仿模仿! 像打网球, 多接触不同的打法, 开阔眼界; 接着看这道题的题解. 试着从不同角度看一个问题, 多练习改代码; 看自己能不能有自己的看法, 去尝试一点更改, 玩一点花样; 增加练习C#编程的机会.

Also, the code written has been work on readability, learned through my favorite book reading:
http://shop.oreilly.com/product/9780596802301.do

Those favorite rules I like to learn, pick up and follow:
Big fan of DRY (Do not repeat yourself) principle, do one thing a time, break giant expression, using explaining variable or summary variable, and abstract the thing to a function, extract a subproblem to a function. The code is also modified to fit into short memory, less mental baggage to read through. 



Read solutions:

https://github.com/jordandong/myleetcodes/blob/master/SudokuSolver.cpp

https://github.com/Sayericplz/myleetcode/blob/master/isValidSudoku.cpp


BFS, using queue - try to convert it to C#
http://yucoding.blogspot.ca/2013/12/leetcode-question-sudoku-solver.html