Sudoku Validation with Javascript

How to master a Job Interview

A few days ago I was attending a technical interview hoping to score an exciting job. After the usual small talk and several basic questions I was handed a stack of paper, a pen and a tricky task.

“Write a Javascript program that validates a Sudoku game.“

After quite some struggling I ended up solving the task rather poorly. A quite unsatisfying code style and an if statement that covered nine lines have left a bad feeling behind. This article provides a more pleasing solution that is dedicated to rescue my guilty conscience.

Initial Thoughts

In Sudoku a game has been won if each row, each column and each sub-grid contain unique values from 1 to 9. The approach depends a lot on the set of data that represents the sudoku game.

The data structure of choice for this program is an array containing nine nested arrays, each representing a row of a sudoku board.

var sudoku_data = [
[5,3,4,6,7,8,9,1,2],
[6,7,2,1,9,5,3,4,8],
[1,9,8,3,4,2,5,6,7],
[8,5,9,7,6,1,4,2,3],
[4,2,6,8,5,3,7,9,1],
[7,1,3,9,2,4,8,5,6],
[9,6,1,5,3,7,2,8,4],
[2,8,7,4,1,9,6,3,5],
[3,4,5,2,8,6,1,7,9]
];

Validation of rows and columns is pretty straight forward. Sub-grids however seem to be tricky. It is necessary to reorganise the data into a new structure that makes validation easier.

Reorganizing Data

The idea is to use the same validation function for rows, columns and sub-grids. Therefore the values are being cached in different order.

Reorganizing column data, indexes of rows and columns are swapped for each value and saved into _cols.

_cols[col][row] = data[row][col];

The juicy part is figuring out which value belongs to which sub-grid. Therefore the whole 9x9 grid can be minimized into a 3x3 grid by dividing each row’s and column’s index by 3 and using Math.floor.

Now it is possible to match a sub-grid to each value. Finally the values are being pushed into the _grid array. Each nested array contains the values of one sub-grid and we can use the same validation function.

gridRow = Math.floor( row / 3 );
gridCol = Math.floor( col / 3 );
gridIndex = gridRow * 3 + gridCol;
_grid[gridIndex].push(data[row][col]);

Validating Arrays

A valid row has to contain nine unique values. The solution is to sort the array first. Each value is then being compared with its succeeding one.

data[row].sort()
for(var col = 0; col < 9; col++){
if (col !== 8 && data[row][col] === data[row][col + 1]){
return false;
}
}
Note: You would also want to check if values exist and if they are in the allowed range of 1 to 9.

Modules Rule!

Since this is supposed to answer an interview question it might be a good idea to show off some best practices. The whole program is being encapsulated into a module.

As a result all program logic is hidden inside the module. The returned closure keeps control of which functions are publicly available. This prevents naming conflicts with other code.

It is easy to add new functionality (like setValue(x, y)) and the code is quite easy to read and understand

var Sudoku = ( function (){
 // Variables to cache reorganized data
var _rows, _cols, _grid;
 // initialize the module with input data
init = function(data){
_transformData(data);
return this;
};
 // return true if sudoku is valid
isValid = function(){
return (_validate(_rows) &&
_validate(_cols) &&
_validate(_grid));
};

_validate = function(data){
// validate rows …
};

_reorganizeData = function(data){
// reorganize data into three structures …
};

// make functions public
return {
init: init,
isValid: isValid
};
})();

You can find the entire code here.


Alright, that’s it. I feel better now :-)