Valid Sudoku | joeyreyes.dev

June 30, 2021

I'm still on a roll with LeetCode problems, so I'll walk through the solution for another problem that gave me a good amount of trouble. This one is called Valid Sudoku.

Prompt: Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.

Each column must contain the digits 1-9 without repetition.

Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note: A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input:

board =
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]

Output: true

Example 2:

Input:

board =
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]

Output: false

Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3 x 3 sub-box, it is invalid.

Stating the Problem in My Own Words

I will be given a Sudoku board with the name board. board will be an array of 9 sub-arrays. Each of these sub-arrays will have 9 items, which represent numbers and empty spaces on a partially filled Sudoku board (empty spaces will be represented with a period, .).

As with real life Sudoku, any repetition of a number within a row, or a column, or a 3 x 3 sub-box makes the solution invalid. This invalidity is what we're checking for in the provided numbers. If the solution is valid, the function will return true, if the solution is invalid, the function will return false.

Approach: Check Rows, Columns, and Sub-Boxes

Largely speaking, we're going to be checking for duplicates in three different dimensions/areas: rows, columns, and sub-boxes. We'll use a series of Sets to do this, as Sets allow us to store unique values. We can check for a value within a Set using the .has() method, and if that value isn't found, we can add it to the Set with the .add() method. If the value is found, we can return false.

We will begin with two loops, each counting from 0 to 9 -- we can use 9 because there will always be 9 rows and 9 columns in our board. These two loops, using the iterator variables i and j, will be used to traverse the board in each of the three dimensions.

I also found it helpful to map out the indices we're going to look at. I will refer to the following Index Board throughout this post:

Index Board

00 01 02 | 03 04 05 | 06 07 08
10 11 12 | 13 14 15 | 16 17 18
20 21 22 | 23 24 25 | 26 27 28
------------------------------
30 31 32 | 33 34 35 | 36 37 38
40 41 42 | 43 44 45 | 46 47 48
50 51 52 | 53 54 55 | 56 57 58
------------------------------
60 61 62 | 63 64 65 | 66 67 68
70 71 72 | 73 74 75 | 76 77 78
80 81 82 | 83 84 85 | 86 87 88

Each pair of numbers in the board represents one spot on the board. Starting with 00, you can think of this index matrix as [0][0], or row 0, column 0. Or 03 as [0][3], or row 0, column 3. Or 73 as [7][3], or row 7, column 3. We use different combinations of i and j to comprise these indices, depending on which dimension we're checking.

Step 1: Check Rows

The easiest place to start is to check each row of the board. With our two for Loops in place, we can iterate across each row horizontally by accessing items at board[i][j] indices. This can be a bit confusing, so let's just console.log() out what these values are.

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

    for (let j = 0; j < 9; j += 1) {
      let rowitem = board[i][j];
      console.log(i, j);
    }
  }
}

const board = [
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
];

isValidSudoku(board);
/*
  From the console.log() statement:
  00
  01
  02
  03
  04
  05
  06
  07
  08
  10
  11
  12
  13
  14
  15
  16
  17
  18
  20
  21
  ... (etc) ...
  86
  87
  88
 *.

If you look at these values on the Index Board above, you'll see that we're just going horizontally, row by row. Left to right on the first row, then the second row, then the third, all the way to the final row.

With this iteration in place, we can start adding values to the row Set. We don't need to worry about any values that are non-numeric (in these examples, they appear as a period, .). Instead, we need to check if any numbers we encounter are currently in the row Set. If they are, we'll return false and our function can stop running, since we'll know we have an invalid Sudoku solution. If the value isn't in the row Set then we can just add that value into the Set and continue iterating.

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

    for (let j = 0; j < 9; j += 1) {
      let rowitem = board[i][j];
      if (rowitem !== '.') {
        if (row.has(rowitem)) {
          return false;
        }
        row.add(rowitem);
      }
    }
  }

  return true;
}

Step 2: Check Columns

The next dimension we're going to check out is the columns of our board. This logic is almost identical to the Rows logic we did in Step 1, but rather than using the indices in the board[i][j] order that allows for horizontal iteration, we'll do the indices in the order board[j][i]. This allows us to iterate through the board vertically, looking at the first item in every array, then the second item in every array, then the third, and so on. Let's write out this iteration.

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

    for (let j = 0; j < 9; j += 1) {
      let colitem = board[j][i];
      console.log(j, i);
    }
  }
}

const board = [
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
];

isValidSudoku(board);
/*
  From the console.log() statement:
  00
  10
  20
  30
  40
  50
  60
  70
  80
  01
  11
  21
  31
  41
  51
  61
  71
  81
  02
  12
  ... (etc) ...
  68
  78
  88
 *.

If you look at these values on the Index Board above, you'll see that we're looking at the first item in the first array, then the first item in the second array, then the first item in the third array, all the way down the column. After we've looked at the first item in the eight arrays, then we move onto the second item in the first array, then the second item in the second array, and on and on.

Once we have this vertical iteration down, the rest of the logic for ignoring empty spots (.s), and then checking if a value is already in the col Set or not is exactly the same as what we did previously with the row Set.

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

    for (let j = 0; j < 9; j += 1) {
      let colitem = board[j][i];
      if (colitem !== '.') {
        if (col.has(colitem)) {
          return false;
        }
        col.add(colitem);
      }
    }
  }

  return true;
}

Step 3: Check Sub-Boxes

The last thing we need to do is check each of the 3 x 3 sub-boxes that make up the board. Up to now it's been pretty straightforward -- loop through a row or a column. But isolating these sub-boxes is a bit more difficult.

I'm going to start with the code that allows us to do this and then do my best to break down what's going on:

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

    for (let j = 0; j < 9; j += 1) {
      let boxitem = board[3 * Math.floor(i / 3) + Math.floor(j / 3)][3 * (i % 3) + (j % 3)];
      console.log((3 * Math.floor(i / 3) + Math.floor(j / 3)), (3 * (i % 3) + (j % 3)));
    }
  }
}

const board = [
  ["5", "2", ".", ".", "7", ".", ".", ".", "."],
  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
  [".", "9", "8", ".", ".", ".", ".", "6", "."],
  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
  [".", "6", ".", ".", ".", ".", "4", "8", "."],
  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
  [".", ".", ".", ".", "8", ".", ".", "0", "9"],
];

isValidSudoku(board);
/*
  From the console.log() statement:
  00
  01
  02
  10
  11
  12
  20
  21
  22
  03
  04
  05
  13
  14
  15
  23
  24
  25
  06
  07
  08
  16
  17
  18
  ... (etc) ...
  86
  87
  88
 */

We're still using the same two loops we used when checking rows and columns.

I'd first like to draw attention to this statement: 3 * Math.floor(i / 3) + Math.floor(j / 3), which calculates the first part of our index coordinates.

Let's say that i = 0 and j = 0.

The statement 3 * Math.floor(i / 3) + Math.floor(j / 3) translates to the following:

3 * Math.floor(0 / 3) + Math.floor(0 / 3)

This calculates out to 3 * 0 + 0, which gives us 0.

Now let's say that i = 0 and j = 1.

This calculates out to 3 * 0 + 1, which gives us 1.

And then now let's say that i = 0 and j = 2.

This calculates out to 3 * 0 + 2, which gives us 2. This series gives us the first coordinate for each item as we iterate through the first sub-box:

0, 0, 0, 1, 1, 1, 2, 2, 2.

This corresponds to the following index values in the first sub-box on the Index Board:

0x 0x 0x | .. .. .. | .. .. ..
1x 1x 1x | .. .. .. | .. .. ..
2x 2x 2x | .. .. .. | .. .. ..
------------------------------
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
------------------------------
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..

I won't continue stepping through iteration by iteration, but if we were to continue in this manner, then the second and third sub-boxes give us the same values for the first part of our index matrices:

0, 0, 0, 1, 1, 1, 2, 2, 2

As i and j each increment through the loop, this Math.floor() statement gives us the three items in a row at a time, followed by the same three items in the next row, then the three items in the row after that. For the next iteration, we get the following values:

3, 3, 3, 4, 4, 4, 5, 5, 5

This corresponds to the following index values in this sub-box on the Index Board:

.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
------------------------------
3x 3x 3x | .. .. .. | .. .. ..
4x 4x 4x | .. .. .. | .. .. ..
5x 5x 5x | .. .. .. | .. .. ..
------------------------------
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..

And so on. This gets us the first value in the index matrix for every 3 x 3 sub-box. However, we also need to get the second value in that index matrix. That's where the 3 * (i % 3) + (j % 3) statement comes in.

Let's say that i = 0 and j = 0.

The statement 3 * (i % 3) + (j % 3) translates to the following:

3 * 0 + 0, which gives us 0.

Now let's say that i = 0 and j = 1.

This translates to 3 * 0 + 1, which gives us 1.

Now let's say that i = 0 and j = 2.

This translates to 3 * 0 + 2 which gives us 2.

This loops through a few times, giving us a 0, 1, 2, 0, 1, 2, 0, 1, 2 pattern.

This corresponds to the following index values in the first sub-box on the Index Board:

x0 x1 x2 | .. .. .. | .. .. ..
x0 x1 x2 | .. .. .. | .. .. ..
x0 x1 x2 | .. .. .. | .. .. ..
------------------------------
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
------------------------------
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..

As j and i increase, we get a 3, 4, 5, 3, 4, 5, 3, 4, 5 pattern.

This corresponds to the following index values in this sub-box on the Index Board:

.. .. .. | x3 x4 x5 | .. .. ..
.. .. .. | x3 x4 x5 | .. .. ..
.. .. .. | x3 x4 x5 | .. .. ..
------------------------------
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
------------------------------
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..

Then 6, 7, 8, 6, 7, 8, 6, 7, 8:

.. .. .. | .. .. .. | x6 x7 x8
.. .. .. | .. .. .. | x6 x7 x8
.. .. .. | .. .. .. | x6 x7 x8
------------------------------
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
------------------------------
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..
.. .. .. | .. .. .. | .. .. ..

At this point, the numbers loop back around to give us another 0, 1, 2, 0, 1, 2, 0, 1, 2 pattern.

I'm probably not articulating this very well, but the point is that the 3 * Math.floor(i / 3) + Math.floor(j / 3) statement and the 3 * (i % 3) + (j % 3) statement work together to iterate through each 3 x 3 sub-box one at a time. We are isolating the 9 items that we're checking, and looking for repeating items. I know it can be a bit confusing, but ultimately it allows us to fall back on the same logic we used for the col and row sets.

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

    for (let j = 0; j < 9; j += 1) {
      let boxitem = board[3 * Math.floor(i / 3) + Math.floor(j / 3)][3 * (i % 3) + (j % 3)];
      if (boxitem !== '.') {
        if (box.has(boxitem)) {
          return false;
        }
        box.add(boxitem);
      }
    }
  }
  return true;
}

Solution: Valid Sudoku

I applaud you if you made it to this point and actually read all of my poor explanations above. At any rate, with the three pieces to the solution in place, at this point all we need to do is put them all together in the same function. If none of the dimensions return false, then we have a valid Sudoku solution, and we can simply return true at the end of the function.

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

    for (let j = 0; j < 9; j += 1) {
      let rowitem = board[i][j];
      if (rowitem !== '.') {
        if (row.has(rowitem)) {
          return false;
        }
        row.add(rowitem);
      }

      let colitem = board[j][i];
      if (colitem !== '.') {
        if (col.has(colitem)) {
          return false;
        }
        col.add(colitem);
      }

      let boxitem = board[3 * Math.floor(i / 3) + Math.floor(j / 3)][3 * (i % 3) + (j % 3)];
      if (boxitem !== '.') {
        if (box.has(boxitem)) {
          return false;
        }
        box.add(boxitem);
      }
    }
  }

  return true;
}

Big O of this Solution

I think that the Big O of this solution is O(n * m), where n is the number of sub-arrays in the matrix, and m is the length of each sub-array. Luckily there are always 9 sub-arrays in the matrix, and each sub-array has at most 9 items to check, so there is a ceiling we hit in terms of time complexity. However, checking the three different dimensions (rows, columns, and sub-boxes) is where things get difficult and we might wind up storing a lot of items into memory. If we have a fully filled out, valid Sudoku board, then that's 9 row Sets, 9 col Sets, and 9 box Sets. I don't think they all get stored at one time but it's still a lot of data to have to keep track of.