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