Solving Sudoku Validity in Javascript - LC(#36)

1. Pre-requisites:

Before delving into the solution for validating a Sudoku board, it's essential to have a basic understanding of JavaScript, data structures, and the Sudoku puzzle itself. Familiarity with arrays, loops, and sets in JavaScript will be beneficial. Sudoku is a number puzzle where a 9x9 grid is filled with digits from 1 to 9. The puzzle is divided into 3x3 subgrids, and each row and column must contain unique digits.

2. Understanding the Problem:

The problem at hand is to determine whether a given Sudoku board is valid or not. A valid Sudoku board adheres to the following rules:

• Each row must have unique numbers from 1 to 9.

• Each column must have unique numbers from 1 to 9.

• Each of the 3x3 subgrids must have unique numbers from 1 to 9.

The provided JavaScript code addresses this problem by implementing three separate functions to check the validity of rows, columns, and subgrids.

3. Solution with Algorithm:

To solve this problem we will simply validate each row, column, and 3x3 subgrid, checking that they contain unique numbers or not, if one of the rows, columns, and subgrids has a duplicate number from 1-9, then we will return false, concluding it as invalid sudoku.

To validate all that, I have created separate functions and we will make a decision combining all three function's responses.

Here's the complete algorithm to get started with code.

1. For each row in the grid: a. Create an empty set to store numbers seen in the current row. b. For each element in the row:

   • If the element is not in the set, add it.

   • If the element is already in the set, return false (Sudoku is invalid).

2. For each column in the grid: a. Create an empty set to store numbers seen in the current column. b. For each element in the column:

   • If the element is not in the set, add it.

   • If the element is already in the set, return false (Sudoku is invalid).

3. For each 3x3 subgrid (box) in the grid: a. Create an empty set to store numbers seen in the current subgrid. b. For each element in the subgrid:

   • If the element is not in the set, add it.

   • If the element is already in the set, return false (Sudoku is invalid).

4. If all rows, columns, and subgrids are valid, return true (Sudoku is valid).

5. If any check in steps 1, 2, or 3 fails, return false (Sudoku is invalid).

4. Code in JavaScript:

function isValidRow(grid) {
  for (let i = 0; i < 9; i++) {
    let seen = new Set();

    for (let j = 0; j < 9; j++) {
      const currentNumber = grid[i][j];

      if (currentNumber !== "." && seen.has(currentNumber)) {
        return false; // Duplicate found, invalid Sudoku
      }

      seen.add(currentNumber);
    }
  }

  return true; // All rows are valid
}

function isValidColumn(grid) {
  for (let i = 0; i < 9; i++) {
    let seen = new Set();

    for (let j = 0; j < 9; j++) {
      const currentNumber = grid[j][i];

      if (currentNumber !== "." && seen.has(currentNumber)) {
        return false; // Duplicate found, invalid Sudoku
      }

      seen.add(currentNumber);
    }
  }
  return true; // All cols are valid
}

function isValidSudokuSubgrid(board) {
  for (let i = 0; i < 9; i++) {
    const set = new Set();
    for (let j = 0; j < 9; j++) {
      const row = Math.floor(i / 3) * 3 + Math.floor(j / 3);
      const col = (i % 3) * 3 + (j % 3);
      const cell = board[row][col];

      if (cell !== ".") {
        if (set.has(cell)) {
          return false;
        } else {
          set.add(cell);
        }
      }
    }
  }

  return true; // All subgrids are valid
}

function isValidSudoku(sudoku) {
  return (
    isValidRow(sudoku) && isValidColumn(sudoku) && isValidSudokuSubgrid(sudoku)
  );
}

// Example Sudoku board
board = [
  [".", ".", "4", ".", ".", ".", "6", "3", "."],
  [".", ".", ".", ".", ".", ".", ".", ".", "."],
  ["5", ".", ".", ".", ".", ".", ".", "9", "."],
  [".", ".", ".", "5", "6", ".", ".", ".", "."],
  ["4", ".", "3", ".", ".", ".", ".", ".", "1"],
  [".", ".", ".", "7", ".", ".", ".", ".", "."],
  [".", ".", ".", "5", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", ".", "."],
];

console.log(isValidSudoku(board));

In this code, the isValidSudoku function combines the results from checking rows, columns, and subgrids. If all conditions are met, the Sudoku board is deemed valid.

By understanding the problem and the provided code, you can use this JavaScript solution to check the validity of any given Sudoku puzzle. This code can be further optimized or extended for more complex Sudoku-related problems.

If you like this explanation and the given code, you should save this public repository where I will be uploading solutions to problems like this.

Repository: https://github.com/Meetmakwana7396/DSA-prep-JS

Leetcode problem link: https://leetcode.com/problems/valid-sudoku/description/

Happy Coding!