Valid Sudoku solution in JS
Tags: javascript, beginners, tutorial, webdev
Published: 2021-02-15 13:06:02

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

1. Check each row for duplicates. 
2. Check each column for duplicates. 
3. Check each 3x3 sub grid for duplicates.
4. 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:

```javascript
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:

1. 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
2. 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.

3. Check each of our arrays for duplicate values. If there are duplicates, `return false`, if there are no duplicates, `return true`.

4. Have a cuppa.

## Set Up

We’ll start by creating our 3 arrays:

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

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

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

The resulting code should look like the following:

```javascript
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:

```javascript
// 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:

```javascript
// 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:

```javascript
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.

```javascript
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:**
1. We loop through the rows and columns to traverse the board cell by cell
2. We store the cell in a variable `cell`
3. We check if `cell` has a value and if it does:
4. 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:

```javascript
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!