A Sudoku solver in NodeJS using ES6 classes

Question

As part of a challenge with one of my colleagues, I developed a NodeJS Sudoku solver. It takes an array of all the values of the grid as input (with zeros for absent values), and outputs the same array with zeros filled with the missing numbers.

I choose to use ES6 classes because it helped me to reason about the code. NodeJS is the de-facto environment for writing and debugging JavaScript libraries.

Here is a showcase of the library:

const Grid = require('./grid.js')
const Solver = require('./solver.js')

const grid_data = [
  0, 0, 2,   9, 0, 8,   0, 1, 0,
  7, 0, 0,   0, 6, 0,   5, 0, 0,
  0, 0, 9,   5, 0, 0,   0, 0, 7,

  0, 4, 1,   0, 2, 6,   0, 5, 0,
  0, 8, 7,   0, 0, 0,   3, 4, 0,
  0, 6, 0,   4, 8, 0,   1, 9, 0,

  1, 0, 0,   0, 0, 5,   2, 0, 0,
  0, 0, 8,   0, 4, 0,   0, 0, 5,
  0, 7, 0,   6, 0, 2,   8, 0, 0,
]

let grid = new Grid(grid_data)
let solver = new Solver(grid)
let solved_grid = solver.solve()

solved_grid === ([
  6, 5, 2,   9, 7, 8,   4, 1, 3,
  7, 1, 4,   2, 6, 3,   5, 8, 9,
  8, 3, 9,   5, 1, 4,   6, 2, 7,

  9, 4, 1,   3, 2, 6,   7, 5, 8,
  2, 8, 7,   1, 5, 9,   3, 4, 6,
  5, 6, 3,   4, 8, 7,   1, 9, 2,

  1, 9, 6,   8, 3, 5,   2, 7, 4,
  3, 2, 8,   7, 4, 1,   9, 6, 5,
  4, 7, 5,   6, 9, 2,   8, 3, 1,
])

I created two classes, Grid and Solver.

The Grid constructor takes an array of 81 numbers. The Solver constructor takes a Grid.

Here is the code of the classes:

grid.jd

class Grid {

  /**
   * @param {number[]} grid An array of 81 numbers representing the Sudoku grid.
   */
  constructor(grid) {
    if (!(grid instanceof Array)) {
      throw new TypeError('grid must be an array')
    }

    if (grid.length !== 81) {
      throw new RangeError('grid must be 81 numbers long')
    }

    this.grid = grid
  }

  /**
   * @param {number} row A number between 0 and 8 included.
   * @param {number} column A number between 0 and 8 included.
   * @returns {number} A number representing the start index for a 3x3 sub-grid grid.
   */
  static getStartIndex(row, column) {
    return (row * 27) + (column * 3)
  }

  /**
   * @param {number} grid_index The index of a cell in the grid, from 0 up to 80 included.
   * @returns {number} The sub-grid index for the given grid index.
   */
  static getSubGridIndexForGridIndex(grid_index) {
    return Math.floor(Grid.getRowIndexForGridIndex(grid_index) / 3) * 3 +
      Math.floor(Grid.getColumnIndexForGridIndex(grid_index) / 3)
  }

  /**
   * @param {number} grid_index The index of a cell in the grid, from 0 to 80 included.
   * @returns {number} The row index, from 0 to 8, for the given grid index.
   */
  static getRowIndexForGridIndex(grid_index) {
    return Math.floor(grid_index / 9)
  }

  /**
   * @param {number} grid_index The index of a cell in the grid, from 0 to 80 included.
   * @returns {number} The column index, from 0 to 8, for the given grid index.
   */
  static getColumnIndexForGridIndex(grid_index) {
    return grid_index % 9
  }

  /**
   * @param {number} index A number between 0 and 8 included.
   * @returns {number[]} The sub-grid at index.
   */
  getSubGrid(index) {
    if (typeof index !== 'number') {
      throw new TypeError('index must be a number')
    }

    if (index < 0 || index >= 9) {
      throw new RangeError('index must be >= 0 and < 9')
    }

    let grid_row = Math.floor(index / 3)
    let grid_column = index % 3
    let grid_start_index = Grid.getStartIndex(grid_row, grid_column)

    let sub_grid = []

    for (let i = 0, grid_index = grid_start_index; i < 9; i++ , grid_index++) {
      if (i !== 0 && i % 3 === 0) {
        grid_index += 6
      }

      sub_grid.push(this.grid[grid_index])
    }

    return sub_grid
  }

  /**
   * @param {number} index A number between 0 and 8 included.
   * @returns {number[]} The row at index.
   */
  getRow(index) {
    if (typeof index !== 'number') {
      throw new TypeError('index must be a number')
    }

    if (index < 0 || index >= 9) {
      throw new RangeError('index must be >= 0 and < 9')
    }

    let grid_start_index = index * 9
    let row = []

    for (let grid_index = grid_start_index; grid_index < grid_start_index + 9; grid_index++) {
      row.push(this.grid[grid_index])
    }

    return row
  }

  /**
   * @param {number} index A number between 0 and 8 included.
   * @returns {number[]} The row at index.
   */
  getColumn(index) {
    if (typeof index !== 'number') {
      throw new TypeError('index must be a number')
    }

    if (index < 0 || index >= 9) {
      throw new RangeError('index must be >= 0 and < 9')
    }

    let column = []

    for (let grid_index = index; grid_index < 81; grid_index += 9) {
      column.push(this.grid[grid_index])
    }

    return column
  }

  /**
   * @description Reads all numbers in the sub-grid, row and column to compute the possible values of a cell.
   * @param {number} index The index of a cell in the grid, from 0 up to 80 included.
   * @returns {number[]} An array of all possible value for the requested cell.
   */
  getPossibleValues(index) {
    let values = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    // Removes all values in the { from: values } array that are present in the { present_in: array } array.
    function removeValues({ from: values, present_in: array }) {
      for (var index = 0; index < array.length && values.length > 0; index++) {
        let _number = array[index]
        if (_number === 0) { continue }

        let value_index
        if ((value_index = values.indexOf(_number)) !== -1) {
          values.splice(value_index, 1)
        }
      }
    }

    let sub_grid = this.getSubGrid(Grid.getSubGridIndexForGridIndex(index))
    removeValues({ from: values, present_in: sub_grid })

    if (values.length === 0) {
      return values
    }

    let grid_row = this.getRow(Grid.getRowIndexForGridIndex(index))
    removeValues({ from: values, present_in: grid_row })

    if (values.length === 0) {
      return values
    }

    let grid_column = this.getColumn(Grid.getColumnIndexForGridIndex(index))
    removeValues({ from: values, present_in: grid_column })

    return values
  }

}

module.exports = Grid

solver.js

const Grid = require('./grid.js')

class Solver {

  /**
   * @param {Grid} grid A Grid object.
   */
  constructor(grid) {
    if (!(grid instanceof Grid)) {
      throw new TypeError('grid must be an instance of Grid')
    }

    this.grid = grid
  }

  /**
   * @returns {number[]} The solved grid.
   */
  solve() {
    let sudoku = this.grid.grid
    let solved = false

    while (!solved) {
      solved = true

      for (let index = 0; index < 81; index++) {
        if (sudoku[index] !== 0) { continue }

        let possible_values = this.grid.getPossibleValues(index)

        if (possible_values.length === 1) {
          sudoku[index] = possible_values[0]
        } else if (possible_values.length > 1) {
          solved = false
        }
      }
    }

    return sudoku
  }

}

module.exports = Solver

By separating the solver and the grid, I can implement logic where it belong. The Solver.solve method is the only logic that actually tries to solve the Sudoku. The rest of the code is simple functions for accessing the Grid's cells.

Does anyone has something to say to improve the performance, the logic of the solver or the general code quality?

EDIT Here is the project on GitHub: https://github.com/ThomasKerbrat/sudoku-solver A lot has changed since this post.

Answer 1

I love Sudoku solvers.

One thing that struck me, is that you calculate for every single spot the possible values, which means you have about 3^4 * 3 * 8 = 1944 array accesses per solving cycle.

If you had a 2d array with 1d accesses, you would have n * 3 * 8 accesses (with n being the count of non zero values in the matrix ) and writes. You would simply remove for each non-zero that value from the full line, full row, and the zone that number is in. This should give better performance. Plus, every time you find a number, you then only need to update the cache of the matching row/col/zone.

Another thing that struck me is that you checked if (values.length === 0) twice. If this condition were to happen, then it should stop solving right there, because the Sudoku is impossible. In the calling function, you actually do not check for (possible_values.length === 0) which is where I would have checked, and then abandoned the solving.

Passing the grid as a parameter to the constructor makes the variable a throw away variable in my mind. I would much rather see

let grid = new Grid(gridData)
let solver = new Solver()
let solvedGrid = solver.solve(grid)

Also, lowerCamelCase is the way of JavaScript.

Another thing is that a good solver must be able to guess; hard Sudoku's require guessing while still having a single possible solution. A hard Sudoku puzzle would create an infinite loop with your approach since you would end up with a number of positions that have multiple possible values.

Finally, I think it should be possible to adapt your code to any size of grid. I would change the code with 1 hardcoded size ( 3 ), and the make your other constants (like 81, 27 etc.) named constants based of the 1 hardcoded size.