Valid Sudoku solution in JS

#javascript #beginners #tutorial #webdev

Challenge 36 on Leetcode is ‘Valid Sudoku’. The logic behind the solution is very simple but applying it can be a bit tricky:

Check each row for duplicates. 
Check each column for duplicates. 
Check each 3x3 sub grid for duplicates.
Return false if any duplicates are found, and true if no duplicates are found.

Using a loop inside a loop, the first 2 checks are simple, but it was the sub grids that I stumbled over, getting lost in further loops knowing there had to be a simpler way.

I deleted all my code and started again, finally finding a solution which I will talk through now. When I looked online for other people's solutions (I highly recommend comparing your code to others’, especially if you’re self-taught), I couldn’t find many articles written with solutions in Javascript so figured that it might help some of you.

Problem

The Sudoku board is represented by a 2D array. Filled in squares are portrayed as a string with a number (e.g. “6”) and unfilled squares are represented by “.”. See below for an example:

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"]
];

We need to output true if all entries so far are valid and false if there are any invalid entries (duplicates in a row, column or sub grid).

Solution

The plan is as follows:

Set up 3 arrays, each of which contain 9 arrays
- An array for the columns to contain all 9 columns
- An array for the rows to contain all 9 rows
- An array for the sub grids to contain all 9 sub grids
Loop through the entire board and check each cell for a value. If the cell has a value add it to our appropriate row, column and sub grid arrays.
Check each of our arrays for duplicate values. If there are duplicates, return false, if there are no duplicates, return true.
Have a cuppa.

Set Up

We’ll start by creating our 3 arrays:

let rows = [];
let columns = [];
let boxes = [];

We’ll then add our 9 ‘sub arrays’ to each array:

for (let i = 0; i < 9; i++) {
    rows.push([]);
    columns.push([]);
    boxes.push([]);
}

The resulting code should look like the following:

rows = [[], [], [], [], [], [], [], [], []];
columns = [[], [], [], [], [], [], [], [], []];
boxes = [[], [], [], [], [], [], [], [], []];

Traversing the board

Next, we’ll set up our loops: a loop for the rows and an inner-loop for the columns:

// ROW LOOP
for (let i = 0; i < board.length; i++) {
    // COL LOOP
    for (let j = 0; j < board.length; j++) {

    }
}

Note: Because the size of our board is known and fixed, we could replace board.length with 9.

This will allow us to traverse the entire board where i is the index for the row co-ordinate and j is the index for the column co-ordinate (e.g. to access the top left Sudoku cell, the co-ordinates would be 0,0 and the bottom right cell co-ordinates would be 8,8).

The pattern for this loop would be as follows:

i = 0, j = 1
i = 0, j = 2
i = 0, j = 3
…
i = 0, j = 8
i = 1, j = 0
i = 1, j = 1
…
i = 8, j = 6
i = 8, j = 7
i = 8, j = 8

Check for a value and add to our arrays

Now that we’re traversing the entire Sudoku board, we want to first check if each cell has a value, and if it does, we need to add it to the appropriate arrays. Let’s do this for the column arrays and the row arrays first:

// ROW LOOP
for (let i = 0; i < board.length; i++) {
    // COL LOOP
    for (let j = 0; j < board.length; j++) {
        if(board[i][j] !== “.”) {
            rows[i].push(board[i][j]);
            columns[j].push(board[i][j]);
        }
    }
}

In English:

For each cell, check if the cell is not empty. If the cell is not empty, add the cell value to our appropriate row and column arrays.

After the loops have finished running, we should be left with our rows array that includes an array of values for each row on our board, and our columns array that includes an array of values for each column on our board.

It looks a little bit messy at the moment, so let’s add a variable to store our cell value in so we don’t have to write board[i][j] each time:

for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board.length; j++) {

        let cell = board[i][j];

        if(cell !== “.”) {
            rows[i].push(cell);
            columns[j].push(cell);
        }
    }
}

What about the sub grids?

Getting all the values for our columns and rows is a simple process, but getting each sub grid index is where it gets a bit tricky. Now, I have to confess: my original solution to this problem included a function that checked which 3x3 sub grid we were in based on the co-ordinates, but a much more elegant solution is the following formula:

(row / 3) x 3 + column / 3

Let’s add this to our code - I’ve commented each line so you can see what we’re doing.

for (let i = 0; I < board.length; i++) { // ROW CO-ORDINATE
    for (let j = 0; j < board.length; j++) { // COLUMN CO-ORDINATE

        let cell = board[i][j]; // STORE CELL IN VARIABLE

        if(cell !== “.”) { // IF CELL NOT EMPTY
            rows[i].push(cell); // ADD VALUE TO APPROPRIATE ROWS ARRAY
            columns[j].push(cell); // ADD VALUE TO APPROPRIATE COLUMNS ARRAY

            let boxIndex = Math.floor((i / 3)) * 3 + Math.floor(j / 3); // GET SUB-GRID (BOX) INDEX

            boxes[boxIndex].push(cell); // ADD VALUE TO BOXES ARRAY

        }
    }
}

To recap:

We loop through the rows and columns to traverse the board cell by cell
We store the cell in a variable cell
We check if cell has a value and if it does:
We add the value to the appropriate rows sub-array, columns sub-array and boxes sub-array

Validation

All that’s left to do now is check for duplicates. It might be logical to let the loops finish adding all the values to our arrays and then check each array for a duplicate. This would work, but it would mean that our code would have to traverse the entire board every time, regardless of how quickly a duplicate may appear. A sleeker way would be to check for duplicates ‘inline’, every time we find a new value.

The finished code is as follows:

function isValidSudoku(board) { 
  for (let i = 0; i < board.length; i++) { 
    for (let j = 0; j < board.length; j++) {

      let cell = board[i][j];

      if(cell !== “.”) {
        if (rows[i].includes(cell) {
          return false
        } else rows[i].push(cell);

        if (columns[j].includes(cell) {
          return false;
        } else columns[j].push(cell);

        let boxIndex = Math.floor((i / 3)) * 3 + Math.floor(j / 3);

        if (boxes[boxIndex].includes(cell) {
          return false;
        } else boxes[boxIndex].push(cell);

      }
    }
  } 

  return true;

}

This way, we’re checking first if cell has a value, then we’re checking if the value already exists in our arrays. If a duplicate is found, we return false without running through the rest of the code, otherwise, we keep going. At the bottom of our function, we return true which will only run if all of our tests have passed.

Outro

I hope this helped you in some way in traversing 2d arrays, and if it didn’t, I hope you at least found it interesting! I love these kinds of challenges, this was just one that I got a bit annoyingly lost in.. but hey, it happens!