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

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

Monday, November 1, 2021

37. Sudoku Solver: C# | DFS algorithm | 2018 practice | Warmup

Nov. 1, 2021

Here is the link. 

C# | DFS algorithm | 2018 practice | Warmup

Nov. 1, 2021
Introduction
It is the most important experience to learn how to write a perfect DFS algorithm by solving Sudoku algorithm. I also came cross this algorithm since my college classmate back in 1984 to 1988 worked on Sudoku algorithm on paper and wondered how it is designed.

DFS algorithm | Back tracking | Available digits to keep row, column, 3 x 3 matrixs unique numbers

It is kind of brute force solution. Go through all possible digits and then call the DFS function sudokuSolveHelper recursively.

Back tracking is also important to keep allow space efficient as well.

Performance | 15 minutes to write perfect code | Pramp 30 mock interview experience

I had 30 mock interviews experience to work on Sudoku with various engineers in Canada over 12 months. So many tips came in from my experience to work with talent engineers in the world. I learn how to write bug free code in less than 15 minutes and then the code should be able to run without any debugging.

The following code passes online judge.

public class Solution {
    public void SolveSudoku(char[][] board) {
        sudokuSolveHelper(board, 0, 0);
    }      
    
    private static bool sudokuSolveHelper(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 sudokuSolveHelper(board, nextRow, nextCol);  
            }
           
            foreach (var digit in getAvaiableDigits(board, row, col))
            {
                board[row][col] = digit; 

                if (sudokuSolveHelper(board, nextRow, nextCol))
                {
                    return true;
                }

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

            return false;
        }

        private static IEnumerable<char> getAvaiableDigits(char[][] board, int currentRow, int currentCol)
        {
            var hashSet = new HashSet<char>("123456789".ToCharArray());

            for (int index = 0; index < 9; index++)
            {
                // remove current row used char
                hashSet.Remove(board[currentRow][index]);
                hashSet.Remove(board[index][currentCol]);
            }

            // small 3 x 3 matrix 
            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;
        }   
}

Comments: 0

Sunday, December 6, 2020

Algorithm practice: FANG onsite

 coding1: 利口意思而散,做完没问followup直接出了一道挺经典的背包dp。常规的问了复杂度,最开始脑抽了说错,面试官提示之后赶紧改正。两道题都bug-free,所以自我感觉还好。


coding2: 不是LC原题,但是是道典型的backtracking题,蛮类似sudoku solver,就不复述具体题目细节了。bug-free

coding3: 依然不是LC原题?(是真的背,我看很多rp好的面经全是高频题怎么回事emm),在一个排好序的数组中找到出现次数超过总数1/4的数字。一开始只想到brute-force的做法,没想到怎么logN。面试官提示了一下,想到基于二分查找就可以。然后写完有个小bug赶在面试官发现之前先改过来了。这一轮的面试官无精打采呵欠连连,搞得我也一头雾水不知道自己答的如何,再加上没问followup,就很虚。但考虑到最后几分钟面试官让我给code加了一些注释,还让我把复杂度啥的都明确注释在了doc里,个人猜测应该至少是个baseline的评价吧,如果是负面的那应该不用花时间让我的doc看起

1423. Maximum Points You Can Obtain from Cards

Thursday, November 14, 2019

Easy level algorithms - My party with 15 algorithms

Nov. 14, 2019

Introduction

It is so important for me to stay on track to push myself advance as a software programmer. There are so many projects I can choose to work on, but I have to think about for myself. How to stay longer as a software programmer? I still do not develop the love of crafting an algorithm, still afraid, problem to understand the requirement, and feel exhaust after 20 minutes problem solving. 

Let me party with easy level algorithms

I did solve 15 easy level algorithm. Each easy level algorithm just reminds me to slow down, work on basics of problem solving. Stay on track, continue to work on crafting skills. 
Oct. 21 - Oct. 25, 2019
1170. Compare Strings by Frequency of the Smallest Character C# Sort first and then get count of smallest character
985. Sum of Even Numbers After Queries C# Using dynamic programming to track sum of even numbers
1128. Number of Equivalent Domino Pairs C# Learn from three failed test cases
999. Available Captures for Rook C# work on directions and also boundary check carefully
1122. Relative Sort Array C# Good learning experience
509. Fibonacci Number C# optimal time and space complexity
1160. Find Words That Can Be Formed by Characters C# Counting sort technique
1051. Height Checker C# Solve 60 easy level algorithms - No 1 of 60
Oct. 29, 2019
1238. Circular Permutation in Binary Representation Design algorithm using DFS similar to Sudoku solver
989. Add to Array-Form of Integer C# Learn IEnumerable Skip and Take API
989. Add to Array-Form of Integer C# iterative solution
1239. Maximum Length of a Concatenated String with Unique Characters C# A solution with readable code using DFS
Nov. 4, 2019
1247. Minimum Swaps to Make Strings Equal C# learn from two test cases
1248. Count Number of Nice Subarrays C# - preprocess the array first
Nov., 12, 2019
1103. Distribute Candies to People C# Work on basics - while loop

Nov. 14, 2019
884. Uncommon Words from Two Sentences C# Fail three times to succeed
299. Bulls and Cows C# digit count and comparison count of same digit same position

Reference:

My 2019 Leetcode practice webpage is here. 

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


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, October 24, 2018

1000 submissions

Oct. 24, 2018

Introduction


It is time for me to work on one easy level algorithm, so I can have 1000 submissions. I am so excited to work on my 1000th submission in short future.


What it takes


It takes a lot of hard work, time and also wisdom to reach 1000 submissions. It is much hard to compare to get a gold medal on Hackerrank.com, and also any course work I had in mathematics major in Florida Atlantic University, all courses work together in my bachelor degree and master degree, include Ph.D. study.

I also have to learn so many things in order to make a successful submission sometimes.

The Leetcode community is different from Hackerrank, some of us are ready to share just after the contest. The discuss ratio compared to all submissions is not that high, for example, over 300,000 submissions in 39 Sudoku solver only less than 400 discuss.

This is also time for me to learn how to write code; I am so glad to read ideas and then write code for various ideas.

I learn from my own experience, last month I worked on easy level algorithm binary watch, I felt nervous as I did in the phone screen. But once I started to read various ideas, I felt so relax and enjoyable to work on those ideas. I learn to deal with my own emotions, I have to push myself hard to think independently more often, before I read the discuss. I will have to get used to figure out things by myself. Hopefully next 1000 submissions I can train myself to overcome this nervousness issue.

Those 1000 submissions also help me to have the chance to be get two phone screens and one onsite interview this year. Without those encouragements from Amazon and Facebook, a few of local companies, I will not be smart enough to work on so many submissions. I also had thanks to my ex-coach, I have to stay humble and work on those easy level algorithms first, without those 200 easy level algorithms practice, I will not have chance to reach 1000 submission mark.

My personality is kind of over confident sometimes, and sometimes low on confidence. I have to learn how to make good judgement where I am in terms of confidence level.

I have to stay humble, start from easy level, and work on the foundation skills. I also overcome my shyness, first time in those easy level practice, I decided to share my practice on Leetcode discuss. I started from August 11, now it is two months experience with over 100 sharing 20 reputations.

Also through those easy level algorithm practice, I started again to play Leetcode weekly contest, I have played over 8 contest last two months. It is so good journey for last two months. I read one blog I wrote in August 31, at that time, I solved 177 algorithm with 679 submission. Based on the facts written in the blog two month ago, I can easily find out that I solved 88 algorithms with 321 submissions from August 31 to Oct. 26, 2018.


Saturday, October 13, 2018

Does my failure on Leetcode 150 easy level algorithms has a name?

Oct. 13, 2018

Introduction


It is time for me to spend 10 to 30 minutes to go over those failed submissions on 150 easy level algorithms. I like to identify what I should be careful, the growth pain of the algorithm and data structure problem solving. Like a baby growing up in the first year, there are numerous stages an infant can continuously develop. This is the first time I intensely work with the online judge, and work with those problem statements and problem setters, and also work with those hidden test cases which may never be released but may explode any time.

Common mistakes 


I make common mistakes very often. I just could not believe that I learn so much and so quickly through those easy level algorithms.

Sometimes the algorithms are labelled by the mistake as an easy level, but then I just fell in love with the algorithms and continue to learn from my experience. I choose the algorithm to be my mock interview algorithms more than five times.

Most surprisingly I learn a few solution with such elegant solution. I just could not believe that I need to refine my thinking process, and then rework the problem after my first submission by working independently.

I will list over 5 mistakes and lessons I learn in the following later.

687. Longest univalue path with design flaw, pass 43 out of 68 test cases
687. Longest univalue path copy the idea from most popular post
Array easy level algorithms (solved 44, shared 24)

867. Transpose matrix - pass 29/36 test cases
Math easy level algorithms (solved 27/ 32, shared 12)

415. Add Strings recursive version - memory limit exceeded
415. Add Strings Iterative solution - learn to use for loop creatively
String easy level algorithms (solved 32, shared 15) 
680. Valid Palindrome II 418/460 test cases passed Time limit exceeded
686. Repeated String Match memory limit exceeded for last test case
686. Repeated String Match memory limit exceeded for last test case
Hashtable easy level algorithm (solved 25, shared 21)

204. Count Primes verbose code
204. Count Primes elegant version

242. Valid Anagram One more mistake to remind me to work on easy level

500. Keyboard Row do it myself
500. Keyboard Row use HashSet API IsSubsetOf

645. Set Mismatch first submission - XOR
645. Set Mismatch elegant one using XOR two places
645. Set Mismatch use bit manipulation trick

720. Longest Word in Dictionary use hashset
720. Longest Word in Dictionary use Trie data structure
720. Longest Word in Dictionary use Trie data structure
720. Longest Word in Dictionary use Queue data structure
720. Longest Word in Dictionary use recursive function
Medium level (solved 53, shared 4)


915. Partition Array into Disjoint Intervals use three iterations
915. Partition Array into Disjoint Intervals one pass idea discuss
916. Word Subsets using counting sort
916. Word Subsets discuss
918. Maximum Sum Circular Subarray pass 98/108, in the contest
918. Maximum Sum Circular Subarray after the contest, working code
919. Complete Binary Tree Inserter O(1) insert
919. Complete Binary Tree Inserter Using Queue
919. Complete Binary Tree Inserter Using Queue
923. 3Sum With Multiplicity
923. 3Sum With Multiplicity dynamic programming solution 
Medium level tree algorithms (solved 14, total 39, shared 12)

102. Binary Tree Level Order Traversal submitted in 2015
102. Binary Tree Level Order Traversal submitted in 2018
Hard level (solved 33, shared 5)

37. Sudoku Solver
76. Minimum Window Substring One thing a time
85. Maximal Rectangle
239. Sliding Window Maximum optimal solution using LinkedList
239. Sliding Window Maximum All submissions, SortedSet, timeout

A name


I like to give those mistakes a name to encourage myself to work hard, work on more algorithm problem solving.

The name is called in Chinese, "这需要托大家的福,托大家的福就要吃百家饭、穿百家衣". The custom is to help raise a healthy child to eat and wear in so many families. The link is here.