Valid Sudoku, The JavaScript Solution

Pic from dictionary.com

When preparing for a Software Engineer job interview, one of the things we do is practice algorithms. For example, Leetcode has thousands of exercises we practice to keep our minds in shape and ready for technical questions. Those exercises often come across as puzzles, to the point some of those exercises are based on actual puzzles. The data structure exercise done recently was Valid Sudoku. A data structure exercise inspired by the logic-based, combinatorial number-placement puzzle.

In sudoku, the objective is to fill a 9 x 9 grid with digits so that each row, column, and 3 x 3 subgrids contain all of the digits, from number 1 to number 9. Variations of this popular puzzle started to publish in French newspapers in the 19th century. However, the modern version we know was published in 1986 by a Japanese company named Nikoli. Hence the Japanese name means “Single Number.”

In Leetcode’s Valid Sudoku, we must code a function that will determine if a board is valid or not. So let’s supposed this is our board composed of an array.

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

Sudoku’s description itself makes it very clear what we need to accomplish (not that it’s simple, but at least the instructions make it look like that).

Our goal when coding a Sudoku program:

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

Let’s start first by thinking about what we need:

1. A function that returns the result for the entire sudoku board.
2. The row function.
3. The column function.
4. The sub-boxes function.

Now, let’s do the code:

If we console log the sudoku function:

console.log(validSudoku(board))

The output of this code is true, as the board is a valid sudoku puzzle that contains all digits without repetition in the rows, columns, and 3 x 3 sub-boxes.

What if I say that there are even better solutions available? The next one I’ll show has only one function, and we’ll use Set to collect the values.

First, let’s start with a different board:

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

And now, let’s see if it’s a valid sudoku with the following function:

Not only the result for this board is false. It will also return each message from the variables row, column and box as requested in the console.log on line 11.

8 at row 0, 8 at column 0, 8 at box 0, 0
3 at row 0, 3 at column 1, 3 at box 0, 0
7 at row 0, 7 at column 4, 7 at box 0, 1
6 at row 1, 6 at column 0, 6 at box 0, 0
1 at row 1, 1 at column 3, 1 at box 0, 1
9 at row 1, 9 at column 4, 9 at box 0, 1
5 at row 1, 5 at column 5, 5 at box 0, 1
9 at row 2, 9 at column 1, 9 at box 0, 0
8 at row 2, 8 at column 2, 8 at box 0, 0
false

As you would observe, it’s pretty similar to the four functions approach. Using set helps do the same operation as the previous code. It’s even easier to set the message to display when it runs in each variable. Just be sure to leave the console.log or innerHTML if you’d like to make a small website at the same statement as this example, or it will return incorrect boolean results.

So this is it. Maybe you’d like to borrow your grandfather’s newspaper and try figuring out the sudoku puzzle. Or perhaps, even doing your Sudoku puzzle on JavaScript and this exercise will be a good start. Most importantly, have fun!

Overview:

1. Intro to Sudoku
2. Long Solution
3. Short Solution

References:

1. MDN Web Docs, Set