Simple three steps validation in C#


  • 0
    P

    time complexity = O(N*N) where N = 9 so, constant. O(1)
    space complexity = O(N) where N = 9 so, constant O(1)

            /// <summary>
            /// Method to validate the sudoku only for how much it is filled. 
            /// if the it contains '.' that means, it is empty.
            /// </summary>
            /// <param name="s">9X9 matrix</param>
            /// <returns>validation result</returns>
            static public bool IsValidSudoku(char[,] s)
            {
                // need auxilary memory of 9 bit. 
                bool[] validateWith = new bool[9];
    
                // validating the sudoku row wise. 
                for (int i = 0; i < 9; i++)
                {
                    for (int j = 0; j < 9; j++)
                    {
                        char ch = s[i, j];
    
                        if (ch != '.')
                        {
                            // minus 1 to the value to make it index 
                            // (value from 1 to 9 and index from 0 to 8)
                            int val = int.Parse(ch.ToString()) - 1;
    
                            if (validateWith[val])
                            {
                                return false;
                            }
                            else
                            {
                                validateWith[val] = true;
                            }
                        }
                    }
    
                    // valid row. Re initialize the validating array. Set all false.
                    validateWith = new bool[9];
                }
    
                // validating the sudoku column wise. 
                for (int i = 0; i < 9; i++)
                {
                    for (int j = 0; j < 9; j++)
                    {
                        char ch = s[j, i];
    
                        if (ch != '.')
                        {
                            // minus 1 to the value to make it index 
                            // (value from 1 to 9 and index from 0 to 8)
                            int val = int.Parse(ch.ToString()) - 1;
    
                            if (validateWith[val])
                            {
                                return false;
                            }
                            else
                            {
                                validateWith[val] = true;
                            }
                        }
                    }
    
                    // valid column. Re initialize the validating array. Set all false.
                    validateWith = new bool[9];
                }
    
                // validating it blockwise starting from 0 to 8 blocks
                // 0, 1, 2,
                // 3, 4, 5,
                // 6, 7, 8
                for (int i = 0; i < 9; i++)
                {
                    int row = i / 3;
                    int block = i % 3;
                    for (int j = 0; j < 3; j++)
                    {
                        for (int k = 0; k < 3; k++)
                        {
                            char ch = s[j + (row * 3), k + (block * 3)];
                            if (ch != '.')
                            {
                                // minus 1 to the value to make it index 
                                // (value from 1 to 9 and index from 0 to 8)
                                int val = int.Parse(ch.ToString()) - 1;
    
                                // if already set, return false
                                if (validateWith[val])
                                {
                                    return false;
                                }
                                else
                                {
                                    // set it true. 
                                    validateWith[val] = true;
                                }
                            }
                        }
                    }
    
                    // valid block. Re initialize the validating array. Set all false.
                    validateWith = new bool[9];
                }
    
                // all test pass, return true.
                return true;
            }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.