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