Java code with explanation


  • 0
    L

    This is a generic solution that should work on any nn board (where n is a perfect square). The idea is to imagine a section that is sqrt(9). So we need to check the uniqueness for a row, col and inside the section of 3x3 region. To traverse each region, we need to loop between 0-3 to cover reach region on row and col side. After that we run two loops for m and n to cover each row and col inside that region. It is easy to guess that m and n should be relative to i and j therefore. The formula will be
    m=3
    i to 3i + 3
    n = 3
    j to 3*j + 3

      public boolean isValidSudoku(char[][] board)
      {
        int section = (int) Math.sqrt(board.length);
        // validate rows.
        for (int i = 0; i < board.length; i++)
        {
          Set<Character> rows = new HashSet<>();
          for (int j = 0; j < board[i].length; j++)
          {
            if (board[i][j] != '.' && !rows.add(board[i][j]))
            {
              return false;
            }
          }
        }
        // validate cols.
        for (int i = 0; i < board[0].length; i++)
        {
          Set<Character> cols = new HashSet<>();
          for (int j = 0; j < board.length; j++)
          {
            if (board[j][i] != '.' && !cols.add(board[j][i]))
            {
              return false;
            }
          }
        }
        /**
         * We have board.length sections altogether.  Each section
         * is Math.sqrt(board.lenth)*Math.sqrt(board.length) long. To solve this
         * problem, we will break both rows and cols into Math.sqrt(board.length) 
         * regions and iterate over each one of them. One iteration of i and  j 
         * should cover one section. For example, for a 4*4 sukodo, we have 2 regions
         * each for for rows and cols. Here are the regions:
        
         * region#1: (0,0) to (1,1)
         * region#2: (0,2) to (1,3)
         * region# 3: (2,0) to (3,1)
         * region# 4: (3,1) to (3,3)
         * 
         * Use i an j to traverse to each region. We also need two variables
         * m and n to go through each element of a region. 
         * m = Math.sqrt(board.length) + Math.sqrt(board.length)*i 
         * n = Math.sqrt(board.length) + Math.sqrt(board.length)*j
         * 
        */
        for (int i = 0; i < section; i++)
        {
          for (int j = 0; j < section; j++)
          {
            Set<Character> cubeSet = new HashSet<>();
            for (int m = section * i; m < section + section * i; m++)
            {
              for (int n = section * j; n < section + section * j; n++)
              {
                if (board[m][n] != '.' && !cubeSet.add(board[m][n]))
                {
                  return false;
                }
              }
            }
          }
        }
        return true;
      }
    
    

Log in to reply
 

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