Interview Question
Share Lesson

Valid Sudoku Board

6 4
5 1 8
4 3
2
41 8 9
7
6 1

This problem has a lot of detail, so take a breath and walk through it step-by-step. If this is too complex to solve now, come back after you level up and work through more of the course.

Given a Sudoku board that is either partially or completely filled, determine if it is a valid board based on the numbers that are in each cell. A valid Sudoku board means there are no duplicate integers within a given row, column, or sub-square.

There’s a catch — we want our Sudoku validator to work for any k x k size board, not just the standard 9 x 9 board.

The question input will be a two-dimensional array that corresponds to the rows and columns of the board. The values of the array will be 0-k where 0 means it is an empty cell and 1-k are values in a cell.

To be valid, the board must be a square of n = k x k where k is the length of each side and n is the total number of cells. Let's also call j = sqrt(k) — a valid board must consist of sub-squares that are j x j.

A standard 9 x 9 Sudoku board would have n = 81 cells, k = 9 row and column length, and each sub-square would have a row and column length of j = 3.

A valid board must meet the following criteria:

  1. The board must be a square of k x k, and it must be composed of j x j size sub-squares.
  2. Rows: inside a given row, a value 1-k cannot appear more than once
  3. Columns: inside a given column, a value 1-k cannot appear more than once
  4. Sub-squares: inside a given sub-square, a value 1-k cannot appear more than once

Write a function isValidSudokuBoard which returns a boolean indicating if the board is valid.

Keep in mind that we only want to determine that the board is valid and do not care if it is solvable. To be considered valid, the input only needs to match the outlined criteria. We do not care if the board is mathematically solvable and could reach a completed state from the initial board.

Example 1:

 

Example 2:

 

Example 3:

 

Breakdown

Loading...
Follow teacher
Share:

Table of Contents

Validate My Answer

  1. View your solution in 2 parts — does it handle checking for a valid board shape and also valid cell content?

  2. You can check for a valid board shape in constant time and space O(1).

  3. You can check for valid cell content in linear time and space O(n).

  4. This question has some edge cases. Have you considered any in your solution?

  5. Does your solution ensure the board is square?

  6. Does your solution ensure the sub-squares are square?

  7. Does your solution check for an empty board input (n=0)?

  8. Does your solution work if all the cells are empty (all values are 0)?

Loading...
Follow teacher
Share:

Table of Contents

Test Results

Run your code and see results here...

/**
* @param {List[List[int]]} board
* @return {boolean}
*/
function isValidSudokuBoard(board) {
  // Your solution here
}
// Upgrade for full course access
// Upgrade for full course access

Valid Sudoku Board

Given a Sudoku board that is either partially or completely filled, determine if it is a valid board based on the numbers that are in each cell. A valid Sudoku board means there are no duplicate integers within a given row, column, or sub-square.

There’s a catch — we want our Sudoku validator to work for any k x k size board, not just the standard 9 x 9 board.

The question input will be a two-dimensional array that corresponds to the rows and columns of the board. The values of the array will be 0-k where 0 means it is an empty cell and 1-k are values in a cell.

To be valid, the board must be a square of n = k x k where k is the length of each side and n is the total number of cells. Let's also call j = sqrt(k) — a valid board must consist of sub-squares that are j x j.

A standard 9 x 9 Sudoku board would have n = 81 cells, k = 9 row and column length, and each sub-square would have a row and column length of j = 3.

A valid board must meet the following criteria:

  1. The board must be a square of k x k, and it must be composed of j x j size sub-squares.
  2. Rows: inside a given row, a value 1-k cannot appear more than once
  3. Columns: inside a given column, a value 1-k cannot appear more than once
  4. Sub-squares: inside a given sub-square, a value 1-k cannot appear more than once

Write a function isValidSudokuBoard which returns a boolean indicating if the board is valid.

Keep in mind that we only want to determine that the board is valid and do not care if it is solvable. To be considered valid, the input only needs to match the outlined criteria. We do not care if the board is mathematically solvable and could reach a completed state from the initial board.

Example 1:

 

Example 2:

 

Example 3:

 
/**
* @param {List[List[int]]} board
* @return {boolean}
*/
function isValidSudokuBoard(board) {
  // Your solution here
}
// Upgrade for full course access
// Upgrade for full course access