Leetcode discuss: 36. Valid Sudoku

 April 25, 2022

Here is the link. 

C# | Encode string - three ideas to map same row, same column, same 3 x 3 matrix

April 18, 2022
Introduction
I worked on the discuss post called 30 days to Meta onsite, and I chose to work on more algorithms on day 18, and I chose to work on top-voted algorithm by this profile Stefan Pochmann:

My practice
I just worked on the algorithm and put together a few test cases to make sure that my solution will work. Here is my first practice.

Next step | Learn how to write an elegant solution | prepare Meta onsite 4th time in May 2022
I also chose to learn to write an elegant solution based on Stefan Pochamann's solution.
How to encode a string to make sure that all digits in the same row will not have duplicate digit?
Hint: Inorder to separate row number from column number, row number is added after digit, whereas column integer is added before digit; In order to separate digit from row number or column number, put left and right parentheses around digit, for example, 1 -> (1), first row check rules - no duplicate, each digit in the first row will be (1)0, (2)0, ..., (9)0. But if the first row has digit 0, then it can not be detected and report error.

The challenge one is 3 x 3 matrix, how to identify 9 of those 3 x 3 matrixes? We can use left-top corner as start position to uniquely identify.
So first row to thir row, first column to third column 3 x 3 matrix
'.','8','7',
'2','.','.'
'3',',','.'
Encode those chars which are not '.'
0(8)0
0(7)0
0(2)0
0(3)0
So it is easy to tell that there is no duplicated char to represent digit from 1 to 9.

It is easy to figure out how to encode second row of 3 x 3 matrix, second column, the right-top corner is (3, 3). All digits will be represented in 3(?)3, ? is to represent any digit from 1 to 9.

If one digit is added to same row or same column or same 3 x 3 matrix more than once, then second HashSet.Add API will return false. HashSet variable is defined as seen, so it is easy to check if seen.Add return value is false using expression:

!seen.Add(b + row)

It takes 10 minutes to write down the idea how to encode, and also coding is easy to write, since two loops, one hashset, C# HashSet.Add API has return value - true or fale to represent result.

If needed, it is easy to add logic checking to check digit is not 0, and it is one of digits from 1 to 9.

My algorithms to work on | Stefan Pochamann's solution
It is hard for me to practice and have submission more than 800 submissions in one year. So I plan to work on top-voted algorithms written by Stefan Pochamann, and I think that it is important to be a good thinker like Stefan Pochamann to work on this algorithm using encoded string to quickly draft a solution in a few minutes.

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___encode_as_strings
{
    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);
        }

        /// <summary>
        /// study code:
        /// https://leetcode.com/problems/valid-sudoku/discuss/15472/Short%2BSimple-Java-using-Strings
        /// Collect the set of things we see, encoded as strings. For example:
        /// '4' in row 7 is encoded as "(4)7".
        /// '4' in column 7 is encoded as "7(4)".
        /// '4' in the top-right block is encoded as "0(4)2".
        /// </summary>
        /// <param name="board"></param>
        /// <returns></returns>
        public static bool IsValidSudoku(char[][] board)
        {
            var seen = new HashSet<string>();

            for (int row = 0; row < 9; ++row)
            {
                for (int col = 0; col < 9; ++col)
                {
                    if (board[row][col] != '.')
                    {
                        var b = "(" + board[row][col] + ")";

                        if (!seen.Add(b + row) || !seen.Add(col + b) || !seen.Add(row / 3 + b + col / 3))
                        {
                            return false;
                        }
                    }
                }
            }

            return true;
        }
    }
}