Leetcode discuss: 36. Valid Sudoku

 April 25, 2022

C# | Validation process | HashSet

Here is the link. 

April 18, 2022
Introduction
The algorithm is to verify the given matrix is valid based on given digits and a few rules - check each row, each column, and then 8 small matrixes 3 x 3.

Rules to check

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
   Note:
   A Sudoku board (partially filled) could be valid but is not necessarily solvable.
   Only the filled cells need to be validated according to the mentioned rules.

Test cases to verify

1. If there is digit 0 in given matrix, it will return false; Since "123456789" specifies the digits in the hashset, 0 is not in HashSet.
2. If there is a duplicate 1 in one row, then it will return false; By checking the given row, first '1' will invokde removal of '1' from HashSet, second one will find that '1' is not in HashSet, return false;
3. Same as step 2 applies to one column, and one small matrix - 9 matrixes - define the left top corner, and then use count variable 0 - 9 to map the value of left top corner, and then two loops for row and col in size of 3 each.

I will study discuss post and write a few more solutions.

The following C# code passes online judge.

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

namespace _36_valid_sudoku
{
    class Program
    {
        static void Main(string[] args)
        {
            //[[".","8","7","6","5","4","3","2","1"],
            //["2",".",".",".",".",".",".",".","."],
            //["3",".",".",".",".",".",".",".","."],
            //["4",".",".",".",".",".",".",".","."],
            //["5",".",".",".",".",".",".",".","."],
            //["6",".",".",".",".",".",".",".","."],
            //["7",".",".",".",".",".",".",".","."],
            //["8",".",".",".",".",".",".",".","."],
            //["9",".",".",".",".",".",".",".","."]]
            var board = new char[9][];
            board[0] = new char[]{'.','8','7','6','5','4','3','2','1'};
            board[1] = new char[] { '2', '.', '.', '.', '.', '.', '.', '.', '.' };
            board[2] = new char[] { '3', '.', '.', '.', '.', '.', '.', '.', '.' };
            board[3] = new char[] { '4', '.', '.', '.', '.', '.', '.', '.', '.' };
            board[4] = new char[] { '5', '.', '.', '.', '.', '.', '.', '.', '.' };
            board[5] = new char[] { '6', '.', '.', '.', '.', '.', '.', '.', '.' };
            board[6] = new char[] { '7', '.', '.', '.', '.', '.', '.', '.', '.' };
            board[7] = new char[] { '8', '.', '.', '.', '.', '.', '.', '.', '.' };
            board[8] = new char[] { '9', '.', '.', '.', '.', '.', '.', '.', '.' };

            var result = IsValidSudoku(board);

            // Failed test case: 478 / 507 test cases passed.
            //[[".",".",".",".","5",".",".","1","."],
            //[".","4",".","3",".",".",".",".","."],
            //[".",".",".",".",".","3",".",".","1"],
            //["8",".",".",".",".",".",".","2","."],
            //[".",".","2",".","7",".",".",".","."],
            //[".","1","5",".",".",".",".",".","."],
            //[".",".",".",".",".","2",".",".","."],
            //[".","2",".","9",".",".",".",".","."],
            //[".",".","4",".",".",".",".",".","."]]
        }

        /// <summary>
        /// code review on April 18, 2022
        /// rules to follow:
        /// 1. Each row must contain the digits 1-9 without repetition.
        /// 2. Each column must contain the digits 1-9 without repetition.
        /// 3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
        /// Note:
        /// A Sudoku board (partially filled) could be valid but is not necessarily solvable.
        /// Only the filled cells need to be validated according to the mentioned rules.
        /// </summary>
        /// <param name="board"></param>
        /// <returns></returns>
        public static bool IsValidSudoku(char[][] board)
        {
            if (board == null || board.Length != 9 || board[0].Length != 9)
                return false;

            var rows = board.Length;
            var columns = board[0].Length;
            var digits = "123456789".ToCharArray();
            for (int row = 0; row < 9; row++)
            {
                var set = new HashSet<char>(digits);
                for (int col = 0; col < 9; col++)
                {
                    var c = board[row][col];
                    if (c != '.' && !set.Contains(c))
                    {
                        return false; 
                    }

                    set.Remove(c);
                }               
            }

            for (int col = 0; col < 9; col++)
            {
                var set = new HashSet<char>(digits);
                for (int row = 0; row < 9; row++)
                {
                    var c = board[row][col];
                    if (c != '.' && !set.Contains(c))
                    {
                        return false; 
                    }

                    set.Remove(c);
                }
            }
            
            // check 3 * 3 matrix 
            // first row - 3 corners, next is fourth row, next is 7th row
            for (int count = 0; count < 9; count++)
            {
                var startRow = 3 * (count / 3);
                var startCol = 3 * (count % 3);

                var set = new HashSet<char>(digits);
                for (int row = 0; row < 3; row++)
                {
                    for (int col = 0; col < 3; col++)
                    {
                        var c = board[startRow + row][startCol + col];
                        if (c != '.' && !set.Contains(c))
                        {
                            return false;
                        }

                        set.Remove(c);
                    }
                }
            }

            return true;
        }        
    }
}