36. Valid Sudoku

Link: https://leetcode.com/problems/valid-sudoku

Description: We need to check if a 9x9 Sudoku board is valid.

Solution:

/**
 * @param {character[][]} board
 * @return {boolean}
 */

var isValidSudoku = function (board) {
  for (let i = 0; i < 9; i++) {
    let row = new Set()
    let col = new Set()
    let box = new Set()

    for (let j = 0; j < 9; j++) {
      let _row = board[i][j]
      let _col = board[j][i]
      let _box =
        board[3 * Math.floor(i / 3) + Math.floor(j / 3)][3 * (i % 3) + (j % 3)]

      if (_row !== '.') {
        if (row.has(_row)) return false
        row.add(_row)
      }
      if (_col !== '.') {
        if (col.has(_col)) return false
        col.add(_col)
      }
      if (_box !== '.') {
        if (box.has(_box)) return false
        box.add(_box)
      }
    }
  }
  return true
}

A valid Sudoku puzzle must satisfy these rules:

Each row contains the digits 1-9 without repetition. Each column contains the digits 1-9 without repetition. Each of the nine 3x3 sub-boxes of the grid contains the digits 1-9 without repetition. The provided function isValidSudoku checks a Sudoku board to ensure it meets these criteria. Here's how it works:

Outer Loop

The outer for-loop iterates through each row and column index from 0 to 8. This loop allows us to check every row, column, and 3x3 sub-box on the board.

Sets for Validation

For each iteration of the outer loop, three Set objects are created: row, col, and box. These sets are used to track the numbers found in the current row, column, and 3x3 sub-box, respectively. Set is chosen because it automatically ensures uniqueness of its elements.

Inner Loop

The inner for-loop also iterates from 0 to 8, allowing us to check each cell in the current row, column, and 3x3 sub-box.

Checking Rows and Columns

_row represents the current element in the row being checked, and _col represents the current element in the column being checked.
If _row or _col is not '.' (indicating a filled cell), the function checks whether the value already exists in the respective set (row or col). If it does, the board is invalid (return false). If not, the value is added to the set for future checks.

Checking 3x3 Sub-boxes

_box calculates the current element in the 3x3 sub-box being checked. This calculation might seem a bit complex, but it's essentially converting the row and column loops into a single loop that covers each 3x3 sub-box.

let _box =
  board[3 * Math.floor(i / 3) + Math.floor(j / 3)][3 * (i % 3) + (j % 3)]

This expression determines the element to check in the current 3x3 sub-box based on the current row (i) and column (j) being iterated over in the loops. To understand how this works, remember that a Sudoku board is divided into nine 3x3 sub-boxes:

[ 0 1 2 | 3 4 5 | 6 7 8 ]
[ 0 1 2 | 3 4 5 | 6 7 8 ]
[ 0 1 2 | 3 4 5 | 6 7 8 ]
-------------------------
[ 0 1 2 | 3 4 5 | 6 7 8 ]
[ 0 1 2 | 3 4 5 | 6 7 8 ]
[ 0 1 2 | 3 4 5 | 6 7 8 ]
-------------------------
[ 0 1 2 | 3 4 5 | 6 7 8 ]
[ 0 1 2 | 3 4 5 | 6 7 8 ]
[ 0 1 2 | 3 4 5 | 6 7 8 ]

1. Determining the Sub-box Row (3 * Math.floor(i/3) + Math.floor(j / 3))

Math.floor(i/3): Since i iterates over rows, dividing it by 3 and then applying Math.floor gives the index of the vertical group of 3x3 sub-boxes (0 for rows 0-2, 1 for rows 3-5, and 2 for rows 6-8). Multiplying this by 3 gets the starting row index of the sub-box.
Math.floor(j / 3): Similar to rows, this expression calculates the sub-box's column grouping. However, since we're still determining the row index within the sub-box, this part adjusts the row within the sub-box based on the column being accessed.

2. Determining the Sub-box Column (3 * (i % 3) + (j % 3))

i % 3: The modulus operator here finds the row's position within its sub-box group (0, 1, or 2). Multiplying by 3 adjusts for the fact that each sub-box has 3 rows.
(j % 3): This calculates the column's position within the sub-box, similarly using the modulus operator.

Putting It Together

Combining these two parts allows us to index directly into any of the nine 3x3 sub-boxes and then iterate over each cell within those sub-boxes. This works because:

The first part [3 * Math.floor(i/3) + Math.floor(j / 3)] moves down the rows of sub-boxes, ensuring we're in the correct 3x3 sub-box vertically.
The second part [3 * (i % 3) + (j % 3)] then moves across the columns within a sub-box, ensuring we're in the correct position horizontally.

As the loops iterate, this calculation ensures that each element in every 3x3 sub-box is checked precisely once, making it a very efficient way to validate the sub-boxes of a Sudoku board.

Valid Board

If the function completes both loops without finding any duplicate numbers in any row, column, or 3x3 sub-box, it returns true, indicating the board is valid according to Sudoku rules.