C# solution: space(3 * n) transformation of coordinates with explanation


  • 0
    B

    We need to check row, col and block in for-loop. If we can transform j = 0 ~ 9 into the correct coordinate, the problem can be solved.

    for (int i ....)
    {
    for (int j ...)
    {
    // For row:
    // when i = 0, j = 0 ~ 9
    // we check: [0, 0], [1, 0], [2, 0], [3, 0]....
    // just reverse i, j to solve it.

         // For col:
         // when i = 0, j = 0 ~ 9
         // we check: [0, 0], [0, 1].....
         // there is no need to change
    
         // For block: see below
    }
    

    }
    when i = 0, j = 0 ~ 9
    we need to check:
    0,0 0,1 0,2
    1,0 1,1 1,2
    2,0 2,1 2,2

    we can see:
    rowIndex = i / 3
    colIndex = j % 3

    when i = 1, j = 0 ~ 9
    we need to check:
    0,3 0,4 0,5
    1,3 1,4 1,5
    2,3 2,4 2,5

    we need to change colIndex to
    colIndex = j % 3 + (i * 3)

    when i = 3, j = 0 ~ 9
    we need to check:
    3,0 3,1 3,2
    4,0 4,1 4,2
    5,0 5,1 5,2

    we need to change colIndex to
    colIndex = j % 3 + (i % 3 * 3)

    Row index is similar as col index.

    public class Solution 
    {
        public bool IsValidSudoku(char[,] board) 
        {
            var n = board.GetLength(0);
    
            for(int i = 0; i < n; i++)
            {
                var isVisitedForRow = new bool[n];
                var isVisitedForCol = new bool[n];
                var isVisitedForBlock = new bool[n];
    
                for(int j = 0; j < n; j++)
                {
                    // row - reverse i, j
                    if (!IsValid(board, isVisitedForRow, j, i)) return false;
                    
                    // col - do not need to change
                    if (!IsValid(board, isVisitedForCol, i, j)) return false;
    
                    // isVisitedForBlock - rowIndex = j / 3 + (i / 3 * 3); colIndex = j % 3 + (i % 3 * 3)
                    
                    //Console.WriteLine("i:" + i + "  j:" + j);
                    //Console.WriteLine("rowIndex:" + (j / 3 + (i / 3 * 3)) + "  colIndex:" + (j % 3 + (i % 3 * 3)));
                    
                    if (!IsValid(board, isVisitedForBlock, j / 3 + (i / 3 * 3), j % 3 + (i % 3 * 3))) return false;
                }
                
                //Console.WriteLine("------------------------------");
            }
    
            return true;
        }
    
        private bool IsValid(char[,] board, bool[] isVisited, int rowIndex, int colIndex)
        {
            var cell = board[rowIndex, colIndex];
            
            if (Char.IsNumber(cell))
            {
                var index = cell - '0' - 1;
                
                if (isVisited[index]) return false;
                else                  isVisited[index] = true;
            }
            return true;
        }
    }
    

Log in to reply
 

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