Showing posts sorted by relevance for query sudoku solver. Sort by date Show all posts
Showing posts sorted by relevance for query sudoku solver. Sort by date Show all posts

Sunday, July 19, 2015

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





Tuesday, April 11, 2017

Sudoku solver talk

April 11, 2017

Introduction


Sudoku solver is such interesting problem and Julia wrote more than 3 solution in her practice back in 2015. Here is one of the blogs, and also Leetcode 37: sudoku solver is also very good material to review the algorithm.

Sudoku solver talk 


Here is the C# code written in 30 minutes mocking experience.

Transcript is compiled to make it work. C# code is here.

Highlights of a few corrections:

3 nested for loops. The first 2 for loops is to find the first cell with value -1 to do search, try numbers from 1 to 9 and start a DFS search, if all of them are failed, then return false; otherwise return true.

Need to talk about optimization, use the first one with value -1 to start DFS or other cell?


Follow up

Sept. 6, 2017

It is very important to learn the algorithm. Start from code review and learn from the important message in the review.




Tuesday, December 5, 2017

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. 

Monday, October 28, 2019

1238. Circular Permutation in Binary Representation

Here is the discussion post.

C# Design algorithm using DFS similar to Sudoku solver

It is a medium level algorithm which can be solved using depth first search. The challenge part is to work on bit manipulation, how to change one bit from index = 0 to index = 15?
Case study:
I need to warmup bit manipulation to learn to solve two problems in the following:
  1. Change one bit - how to change it?
    Use bit operator XOR. As we know, 0 ^ 0 = 0, 0 ^1 = 1, 1 ^ 1 = 0; and there are 16 bits to alter, and we can use left shift operator to generate an integer to set nth bit to 1 whereas n is from 0 to 15. In other words, I have to come out the express 1 << i.
    So, the answer is last ^ (1 << i), whereas is from 0 to 15.
  2. How to prove two numbers are the same except one bit?
    Assume that m and n only have one bit different, so m ^ n = 2^p, p is from p to 15. And p & (p - 1) = 0 <=> all bits from 0 to p should be 0.
Here are highlights:
  1. Understand how to run DFS to search all possible paths until one path is found.
  2. Work on DFS search - base case, backtracking, mark visited using HashSet to avoid deadloop;
  3. Time complexity and space analysis is similar to my favorite algorithm Sudoku solver.
Actionable Items
I could not solve the algorithm in weekly contest 160 on Oct. 26, 2019. I spent over 20 minutes to analyze, but I could not come out using DFS algorithm to work on all bits from 0 to 15.
I have to practice more often in weekdays, solve more medium algorithms.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1238_circular_permutation
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// 1238 Circular Permutation in Binary Representation
        /// The idea is similar to Sudoku solver; Each step using DFS to search all options. 
        /// </summary>
        /// <param name="n"></param>
        /// <param name="start"></param>
        /// <returns></returns>
        public IList<int> CircularPermutation(int n, int start)
        {
            var result = new List<int>();

            var set = new HashSet<int>();
            result.Add(start);
            set.Add(start);

            runDFS(n, set, result, start);
            return result; 
        }

        /// <summary>
        /// similar to Sudoku solver
        /// backtracking 
        /// DFS path - mark visited
        /// </summary>
        /// <param name="n"></param>
        /// <param name="hashSet"></param>
        /// <param name="result"></param>
        /// <param name="start"></param>
        /// <returns></returns>
        private static bool runDFS(int n, HashSet<int> hashSet, IList<int> result, int start)
        {
            if (hashSet.Count == (int)Math.Pow(2, n))
            {
                int x = result[result.Count - 1] ^ start; // XOR operator - first and last are different
                return (x & (x - 1)) == 0; 
            }

            var length = result.Count;
            int last = result[length - 1];

            for (int i = 0; i < 16; i++)
            {
                int next = last ^ (1 << i); // XOR operator - change ith bit 
                if (next <= (Math.Pow(2, n) - 1) && !hashSet.Contains(next))
                {
                    hashSet.Add(next);
                    result.Add(next); 

                    if(runDFS(n, hashSet, result, start))
                    {
                        return true; 
                    }

                    hashSet.Remove(next);
                    result.RemoveAt(result.Count - 1);
                }
            }

            return false; 
        }
    }
}


Tuesday, May 23, 2017

Leetcode 37: Sudoku Solver

May 23, 2017

Introduction


Sudoku solver is the most classical algorithm to apply Depth First Search (DFS) using recursion and also use back tracking as well. Julia had a very good experience in May 22, 2017, she had chance to learn to write a short version of depth first search coached by her mocking peer.

Most important design is about base case. To make the implementation as simple as possible, DFS algorithm can start from the matrix left top corner, and then scan from left to right, top to bottom, if the row is bigger than 8, then it finds a solution.


Algorithm Study 



Problem statement is here.

The C# code practice is here.

Algorithm talk 


May 25, 2017

It is also very good experience to use Sudoku Solver algorithm to conduct mocking experience. Julia did her first mocking experience using the algorithm as an interviewer.

June 13, 2017

It is very good experience to write sudoku in mocking experience, this is the third time Julia worked on Sudoku for mocking experience.

Julia put the code into Visual Studio to compile and here is her C# practice code.

Here are two mistakes in writing through mocking experience:

One compiler error in mocking writing, line 61,
add type conversion by adding (char), and also (number + '0')

line 61  board[row, col] = (char)(number + '0'); // add '0'

One compiler error, duplicate variable inside for loop on line 82, change col to column; line 91, row is changed to rowIndex.

Try to pass online judge, and then find the bug on line 84, 93, 111. C# code is here.

line 84 if (board[row, column] - number == '0') // should be '0', not 0



Actionable Item



Julia still remembered that she got some great advice on her second mocking experience using Sudoku, and then she was coached by the peer to use DFS starting from (0, 0) and set the base case to row > 8.

Wednesday, September 6, 2017

Leetcode 37: Sudoku solver

Sept. 6, 2017


Introduction



It is so enjoyable to write sudoku solver as a depth first solution and also walk through each step called "thinking out loud". The conversation after the mocking this evening starting from 10:00 pm until 11:30 pm is also rewarding experience, I try to contribute my two cents for a young person to prepare for an important trial. Although I have written sudoku solver solution over 5 times last 3 months, I still found that this time I wrote a different style.


Algorithm practice 


Here is my C# practice. No bug in the first writing, only fix two compiler errors, pass all test cases the first time.

I forgot that I need to visit current node instead of using two loops to scan the matrix to find the first empty element. After 1 - 2 minutes, I noticed the issue, and then I corrected my thought process and continue to write from line 25.

I wrote line 38 and thought out loud saying that it is kind of stupid to write '1', '2' to '9', actually I am thinking that it is better to split from string "123456789" instead of declaring a char array.

After the mocking interview 


I spent over 20 minutes to share my past 80 interviews with the peer, what I have learned through the mocking practice, specially how I learn to write sudoku algorithm through more than three practices.

One thing I like to say is that if you take it slow, you have a lot of time to write code in 30 minutes mocking interview; but if you write in a rush, then you end up with issues. I am getting more comfortable to stay on one node at a time.

The fact is that in my solution there is no need to write a double for loop at all. Avoid scan from top to down by row, left to right by column to find the first empty element all the time.

The peer gave me the feedback saying that I did very good to explain the algorithm by going over the example to find options 1, 2, 4, 7 ( see line 117 - line 124).

Saturday, May 21, 2016

Leetcode 37: Sudoku solver - a warm up practice

May 21, 2016

Introduction


It is time to warm up Leetcode 37: Sudoku solver algorithm. The problem statement is here. I reviewed the blog written in July, 2015 first, the blog link is here.

I also like to review one blog written by fightforyourdream, the link is here.

Analysis about Sudoku solver in Chinese


I like to translate the analysis from Chinese to English. The analysis from the above Chinese blog:

典型 DFS/递归/回溯/深搜题。对于 DFS,说白了

1. 什么时候返回?
在本题中,
    1. 当 x > 8 或 y > 8 表示已经遍历完所有的格子,因此成功完成,返回 true。
    2. 当下一个搜索(子搜索)返回true,说明已经找到,返回 true。  
    3. 如果测试过本轮的所有可能解,但无一是对的,说明无解,返回false。  
    4. 如果当前空格不是空格,则改变x,y坐标后,继续下一个空格的尝试

2)DFS 就是针对本轮的所有可能解进行逐一尝试,找到本轮的一个可能解后,这时要调用递归,基于本轮的解对下一轮(子问题)进行求解。如果下一轮(子问题)求解成功,则说明大功告成,及时返回true,停止之后的尝试。
否则如果下一轮(子问题)求解失败,则说明本轮的解不适合子问题,因此,必须换一个本轮的解,然后基于本轮的新解,继续尝试子问题。如果已经本轮所有的解都尝试过了,也都失败了,说明本问题无解,返回false。

当然在每次尝试子问题前和如果失败返回后,都要恢复原来的环境(撤销动作)。

所以,要想使 DFS 成功返回, 条件就是找到满足本轮的解和这个解也要满足下一轮(子问题)。


Analysis in English 


Plan to write down English translation on Nov. 3, 2017.


Warm up practice


May 21, 2016

Try to finish in 30 minutes, here is Julia's C# practice, based on past practice - C# code. 





Friday, November 3, 2017

Leetcode 37: Sudoku solver

Nov. 2, 2017

Introduction


It is the time again to write a Sudoku solver. Here is my C# practice, the peer told me that I do not need to run the code using web browser compiler.

The mock interview was supposed to end in one hour to 11:00 PM, but it actually ended at 11:50 PM. I spent more time to chat with the peer until the session terminated due to timeout.

After that, I started to run the code, first I fixed the grammar error line 62. The Split function of string will have an array of string, not an array of char. The line 62 has compile error. It is the easy and quick fix. But I came cross the index out of range run time error. This one I could not pinpoint the error.

I was troubled and tried to set up test case until 1:00 AM, and then I called it a day. I did not do whiteboard testing, instead I tried to guess what is possible places to go wrong for index-out-of range error. With whiteboard testing, it should be a quick fix. But without it, I wasted almost one hour but I still could not find the issue until 1:00 AM.

Whiteboard testing


The whiteboard testing is to use a test case and go over the code line by line, write down the value for each variable, and run the code virtually with results.

If I do whiteboard testing, I should have found the bug on line 91. Here is line 91 with the bug:

for(int row = startRow; row < row + 3; row++)

actually when I run the whiteboard testing, startRow = 0, then row is from 0 to 2. The statement should be written in the following:

for(int row = startRow; row < startRow + 3; row++)


Nothing beats whiteboard testing 


In terms of bug fixing, nothing beats whiteboard testing. Go over a simple test case, go over each line of code, put the result next to the code.

Actionable Item


C# code is updated and it passes all test cases after mock interview. The C# code is here. 

Review sudoku algorithm on code review website, and I studied the question:

Solving Sudoku using backtracking

Plan to write C# code based on the above code review. I feel that there are a few things I can apply to my mock practice code. 


Plan to write a blog to review algorithm of longest common subsequence written in Chinese. The link is here.

Tuesday, June 20, 2017

Can mock interview make difference? Continued

June 20, 2017


Introduction



"It takes a village to raise a child". Related to improve algorithm and data structure, Julia learned that it also takes the hundred people to help her learn depth first search using recursive function.

As a classical depth first search algorithm, Julia worked on the Sudoku algorithm in 2015, she collected over 10 solutions; She thought that she mastered the sudoku algorithm in 2015, actually not! How did Julia find out the fact?

Julia practised Sudoku solver in April and May of 2017. First experience is in April, the peer complained that Julia forgot to write a base case in her first writing and gave a rating of 3 with comment "Do not know how to write code", and then second one is in May, the peer coached Julia to set base case first thing in the design, do not write any small function, keep it short as possible, quick as possible. From those two hours to work with two different people, Julia learned to stay humble, learn and quickly fix her learning issues. With those two mock interview experience, Julia learned the Sudoku solver in totally surprising ways. Learn from people from recent graduate and senior developer, recent graduate explained what to work on through Google onsite experience, and the senior developer showed her later in second meeting with more tips.

June 18 and 19 weekend, Julia worked on the expert level algorithm called path matching, she scored 0.46 out of maximum score 100, she worked on over 5 hours but she learned depth first search again through the problem solving. Julia likes to solve the problem first, it does not matter if she scored less than 0.5%. She likes to get expert level algorithm problem solved first.

Julia starts to meet a person a day to work on algorithm problem solving, she also pays attention to peer's curiosity level on algorithm and problem solving, how good the peer can influence her through one hour conversation. Today she was surprised that the peer shared her link to solve C# problem from stackoverflow.com. Also the peer also typed the test case for her, and then Julia found out that her code had a bug, wrong output.

Julia learns how to do whiteboard testing and she did one today as well. But she missed the bug. So she felt that the peer is much better a tester and maybe she is a project manager working somewhere. It is the second time Julia worked on the algorithm.

A research talk 



The mocking experience is short, only one hour, the peer chose to turn off the video. But the quality of the work is very impressing, Julia found out that she is lacking of this kind of preparation for the mocking experience. 

Julia worked on extra 10 minutes to use Microsoft visual studio to find the bug. It is an excellent experience. 

C# code is here. 

In the line of 44, the new variable should be declared for each key value pair of dictionary. It is called nextPrefix. Do not change the function argument prefix, based on the least astonishment principle.

So share the advice Julia got today.

-very good communication, i liked how you explained your thought process thoroughly -got to the answer fast but still made sure to test before writing code

it's ok to ask the interviewer if you can look up inbuilt/library functions for the language if you need to, that might be helpful sometimes.


Wednesday, May 2, 2018

Why I work on mock interview and choose to be an interviewer?

May 2, 2018

Introduction


I had a mock interview this 10:00 PM. At the end of interview, the peer asked me why I choose to be an interviewer on mock interview. So I like to write a small research on this topic.

Will continue to work on it.

Sudoku solver algorithm 


Learning one algorthm very well. It takes determination to learn one algorithm over years since I could not believe that I am too busy and I have to constantly remind me to work on the same algorithm and get better and better. This will make my life as a software programmer much easy.

It is very important for me to learn the algorithm very well in order to sustain my career as a software programmer. I like the mock interview since I love learning and teaching, and also I do see the opportunities to improve through each mock interview.

I like to write down my experience of learning Suodku solver algorithm. I started to work on the algorithm and documented my practice in a few of blogs in 2015. I thought that I did very well to master the algorithm.

I got to know the truth once I start to practice mock interviews.  To work on the sudoku solver algorithm in mock interview, one time a senior developer who works for fortune 500 gave me a rating of 1 out of 4, and later in mock interview the peer told me that I should work on the structure of depth first search algorithm. I have worked on 10 rounds of mock interview, so I have chance to work on the mock interview over 20 times. I also asked the question on code review website.

It is very important for me to learn the algorithm very well in order to sustain my career as a software programmer. I like the mock interview since I love learning and teaching, and also I do see the opportunities to improve through each mock interview.

Learning and teaching 



I remember that I used to read a post by a high school teacher in early 2006 when I worked on computer science Ph.D. in Florida, who is my second elder sister Jianhua's friend. My sister Jianhua has over 30 years teaching experience. Basically the friend wrote in her post is that learning and teaching is kind of repetition. You got so many feedbacks coming in, bad or good. You have to work on those feedback, integrate them to next teaching or learning.

Learning algorithm is kind of the same thing. You practice the algorithm through mock interview, work with different people who is also hard working. And then you will get a lot of things to work on.

Do not stop. Keep continue. Work on the same algorithm again and again. You will find things to work on besides memorizing the solution. There are a lot of challenging issues.

My mental toughness


I had a mock interview with a friend on May 2, 2018. After more than one hour mock interview, the peer gave me honest feedback. I should memorize the common solution for those algorithms. If the competitor makes it in five minutes, I take 20 minutes, I will be in trouble. I will not have chance to get the second question.

Also here is the quote:"Must do interview questions
Each topic has some building block questions which end up being used by a lot of solutions. It is important that you already know solutions to all these problems so you don't waste time thinking up the solution to these problems and focus on the question interviewer has given you because you will be judged on that. I have included some of  these questions but if you go through Interview Bit in detail you would eventually come across/cover most of these questions"


I gave my thoughts as well. Here is my argument:

I always watch those tennis professional player up and down, so that I will not get disappointed too long if I fail. I used to hit rackets to the net but opponent complained to me. I like to practice better than real interview.


I like to practice than real interview



I like to write a few sentences for this argument. I do think that the more I meet peers through mock interview, I know better to do current job. My achievement is tremendous and make me grounded. I am not trying to achieve unachieveable target, serve others if need, teach or learn.

Share the experience


I like to document my own practice. It looks like that I am the luckiest one to be able to document my algorithm practice more than a few years. I treat the code like commodity. I can produce and consume any time. I do not need to worry too much how good my code is. If it is not, I will get better next blog or next practice. If it is good, then it will be such a fascinating marketing tool for me to get connected to more people.

Love to code every day


It is like sports activity. To maintain the physical health and mental health, I always play sport and also matches to encourage myself to get in teams, and continuously learn new things.

I got feedback from binary tree level order traversal from my mock interview performance on May 2, 2018 9:40 PM. I use extra node null to mark the end of level, but there is more popular trick to use a nested loop for the current level, and leave the outside loop for the level update. I missed that part, and the peer told me the truth, honest feedback. He asked if I like honest feedback or nice sayings. I chose the honest feedback.

I practiced the algorithm over 2 years ago. I just reviewed my past practice, and also spent hours to go over Leetcode discussion first time on this algorithm called binary tree level order traversal.

Here is my C# code written for binary tree level order traversal.

Here is my C# code written for zigzag level traversal.

Sunday, January 7, 2018

Sudoku solver

January 7, 2018

Introduction


It is another mock interview, Sunday 10:00 AM. I had the chance to work on sudoku solver, and then I spend 30 minutes exactly to solve the problem, first few minutes to explain the problem, my solution, and then I wrote the code and pass all test cases.


Code review


Here is my C# code.


Saturday, January 12, 2019

Being a good blogger and also learn from others as well

January 12, 2019

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


  1. One more comment, I took some time to figure out the calculation and add some comment to help people to read the code of function AddNumber(...)
    ///
    /// 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;
    }
    REPLYDELETE
  2. This comment has been removed by the author.
  3. Very nice!!! This problem reminds me of the 8-queens problem doesn’t it? Same ideas. Cheers, Marcelo

Wednesday, March 14, 2018

Sudoku solver

March 14, 2018


Introduction


It is my most favorite algorithm in the world. I could not believe that I practiced today with an engineer in Oregon and also I did learn a few things through mock interview. I took extra 30 minutes to discuss with the peer about algorithm practice and exchange ideas. The peer recommended me to practice on codefights.com, consider the purchase of interviewcake.com algorithms with the answers.

I remembered that in 2015 I did study over 5 solution on Sudoku solver algorithm, I spent over 40 hours to practice the algorithm. At that time, I thought that I was the expert on the algorithm. It was so naive and here is the blog link for those practices.

Code practice


I spent less than 10 minutes to analyze the algorithm, and then the peer asked me if I can improve the efficiency to get available numbers to replace '.' char. So I plan to use a hashset to store available numbers.

After I finished the code, I ran the test cases, I only passed one of test cases. So I found out that the hashset should be digits from 1 to 9 excluding those number showing in the same row or column or 3 x 3 small matrix. I just naively got those numbers and put into the hashset instead.

Here is the code. It took me exactly 30 minutes to pass all test cases. I spent around 5 minutes to fix all bugs.


Monday, November 6, 2017

Code Review: Sudoku solver recursive solution with clear structure

Nov. 6, 2017

Introduction


It only takes less than one hour to post the question on code review. The algorithm is Leetcode 37: Sudoku solver, the most classical depth first search algorithm. My practice is documented here.

It is a wise decision to ask a question on code review website, this time I learn a few things from code review.


Code Review


Code review link is here.

I got very good review. My most favorite advice is Code to interface. Use IEnumrable<char> instead of using HashSet<char>.

Saturday, April 21, 2018

Being an interviewer: Sudoku solver

April 21, 2018

Introduction


It is my 10:00 AM mock interview. The peer worked on Sudoku solver, and then he chose swift language. What he did is to check given numbers on the board are following the rules - row/ column, small grid 3 x 3 matrix not duplicate.

The code he wrote for preprocessing is kind of buggy, so we started to talk and communicate on this piece of code. And then I told him that most of people do not do this preprocessing.

The interviewee wrote code but could not pass the test case, and then I walked through the code, and pointed out on line 18, variable name i is used the second time.

Code review 


Here is the swift code I reviewed for the peer as well. The code passed all test cases.

I gave the advice to write readable code, use meaningful variable names, and also I advised the peer to communicate more with the interviewer. I told him that I met a young master graduate, who was preparing Google onsite, and then he got offer. When I mocked interview him, he kept asking me "am I in right check", "do you think that my coding looks ok", he has determined goal, to write code to pass all test cases he prepared, he likes to develop a complete solution in less than 30 minutes.

I had a small chat with the peer who is preparing Uber phone screen. The peer got the Amazon offer but chose another offer a few years ago. Interesting story, a small world, stay anonymous, smart and hard working young programmer.



Monday, April 2, 2018

Sudoku solver

April 2, 2018

Introduction


It is such great experience to work on Sudoku solver in mock interview. I wrote the algorithm in less than 30 minutes.

Code review


Here is my analysis with C# code.


Wednesday, November 3, 2021

Leetcode discuss: 37. Sudoku Solver | My practice and sharing

Nov. 3, 2021

Here is the link. 


C# | Depth first search | DFS with Backtracking - space efficiency | Warmup practice in 2021

Nov. 3, 2021
Introduction
It is so important for me to warm up my coding skills, and then I choose to write a C# solution to solve Sudoku solver 37.

Depth first search | Back tracking | Run a test case
The problem asked is to gurantee that there is a solution, so I choose to add a test case to run the code, and make sure that the code will return true if DFS is run to try to find first working solution.

I spent a few minutes to add the test case using given matrix in the problem statement.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _37_sudoku_solver
{
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase();
        }

        public static void RunTestcase()
        {
            var board = new char[9][];

            int index = 0;
            board[index++] = "53..7....".ToCharArray();
            board[index++] = "6..195...".ToCharArray();
            board[index++] = ".98....6.".ToCharArray();
            board[index++] = "8...6...3".ToCharArray();
            board[index++] = "4..8.3..1".ToCharArray();
            board[index++] = "7...2...6".ToCharArray();
            board[index++] = ".6....28.".ToCharArray();
            board[index++] = "...419..5".ToCharArray();
            board[index++] = "....8..79".ToCharArray();

            SolveSudoku(board);
        }

        /// <summary>
        /// warmup algorithm - need more practice to write C# code 
        /// board.length == 9
        /// board[i].length == 9
        /// board[i][j] is a digit or '.'.
        /// It is guaranteed that the input board has only one solution.
        /// </summary>
        /// <param name="board"></param>
        public static void SolveSudoku(char[][] board)
        {
            var result = RunDepthFirstSearch(board, 0, 0);
            //Debug.Assert(result);
        }

        /// <summary>
        /// classical DFS algorithm to work on
        /// </summary>
        /// <param name="board"></param>
        /// <param name="row"></param>
        /// <param name="col"></param>
        /// <returns></returns>
        private static bool RunDepthFirstSearch(char[][] board, int row, int col)
        {
            //base case
            if (row > 8)
            {
                return true; 
            }

            var isLastColumn = col == 8;
            int nextRow = isLastColumn ? (row + 1) : row;
            int nextCol = isLastColumn ? 0 : (col + 1);

            var current = board[row][col];
            bool isDot = current == '.';
            bool isNumber = (current - '0') >= 0 && (current - '0') <= 9;

            if (isNumber)
            {
                return RunDepthFirstSearch(board, nextRow, nextCol);
            }

            foreach (var digit in getAvailableDigits(board, row, col))
            {
                board[row][col] = digit;
                if(RunDepthFirstSearch(board, nextRow, nextCol))
                {
                    return true; 
                }

                board[row][col] = '.';
            }

            return false; 
        }

        /// <summary>
        /// Given a position in the matrix, check current row and current column, and also it's small matrix 3 x 3
        /// Idea is to remove existing chars from given string "123456789" which has all chars
        /// </summary>
        /// <param name="board"></param>
        /// <param name="currentRow"></param>
        /// <param name="currentCol"></param>
        /// <returns></returns>
        private static IEnumerable<char> getAvailableDigits(char[][] board, int currentRow, int currentCol)
        {
            var hashSet = new HashSet<char>("123456789".ToCharArray());

            for (int index = 0; index < 9; index++)
            {
                hashSet.Remove(board[currentRow][index]);
                hashSet.Remove(board[index][currentCol]);
            }

            // small 3 x 3 matrix - one of 9 3 x 3 matrixes
            var smallRow = currentRow / 3 * 3; // 0, 3, 6
            var smallCol = currentCol / 3 * 3; // 0, 3, 6
            
            for (int row = smallRow; row < smallRow + 3; row++)
            {
                for (int col = smallCol; col < smallCol + 3; col++)
                {
                    hashSet.Remove(board[row][col]);
                }
            }

            return hashSet; 
        }
    }
}

Saturday, January 20, 2018

Sudoku solver

January 20, 2018

Introduction


It is another 10:00 PM mocking interview. At the very beginning, I always say that my name is Julia. I am in the city of Vancouver. I have been working on C# last eight years, web programmer. And then the peer told me that he is xxx and then he has been working for yyy last 5 years.

I was so surprised to learn that the mock interview has such great machine learning algorithm. I just got another senior developer with one of top four software companies and then we will spend one hour together to discuss the algorithm.

Code review


The algorithm I had to work on is called Sudoku solver. What I have to do is to write down the problem, constraints, and also explain the depth first search and idea to apply backtracking algorithm.

The peer did ask me how to optimize the function getAvailableChars, there are 27 searches.

Here is the C# code with analysis as well. I start to pay attention to the analysis in mock interview, make sure that I can write very clearly about problem, given constraints, and the problem to solve, the idea to solve the algorithm problem.

I went over the constraint in the matrix first, and the write down Constraint, and then write down the main idea of the algorithm: DFS + backtracking, and go over the first row three elements in depth first search, and then the peer told me that he understood the algorithm and I can write the code.

I continue to write down the time complexity and space complexity. The time complexity is 981 at most, but I wrote it wrong 819. The peer asked me and then I corrected it.

The only thing I found in whiteboard testing is line 32, I forgot to add !, it should be if(!isDot).