Sudoku Solver

¶

Sudoku Solver

A sudoku solver that solves abitrary size grids using a simple backtracking algorithm.

Grid dimensions. The solver itself can handle a grid of any size, but currently this isn't exposed in the UI. As a result, dimensions are currently set as constants.

The grid is made up of groups which are rectangular, although the overall grid is always square.
```
GROUPWIDTH = 3;
GROUPHEIGHT = 3;
BOARDSIZE = GROUPWIDTH * GROUPHEIGHT
```
¶

TODO: move away from undefined to this for consistency (currently this only used in the frontend)
```
BLANK = ""
```

A random integer between min and max, inclusive.

randomInt = (min, max) ->
  Math.floor(Math.random() * (max - min + 1) + min)

¶

The Sudoku model. The grid itself is a 2D array, so it can be accessed with @grid[x][y]. Previously there were @get and @set methods, but profiling suggested they were affecting performance. Further benchmarking is needed, particulary after more heuristics are added.
```
class SudokuGrid
```

Create an empty grid.

  constructor: () ->
    @grid = for x in [0...BOARDSIZE]
      for y in [0...BOARDSIZE]
        undefined

    @legalValues = [1..BOARDSIZE]

Set this grid based on the text inputs in this selector

  setFromSelector: (selector) ->
    selector.each (index, element) =>
      x = index % BOARDSIZE
      y = Math.floor(index / BOARDSIZE)

      value = $(element).val()
      if value != ""
        @grid[x][y] = parseInt(value, 10)

¶

Set this table based on a string of characters specifying it

e.g. ".......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6..."
```
  setFromString: (string) ->
    for i in [0...string.length]
      value = parseInt(string.charAt i, 10)
```

skip '.'

      if value in @legalValues
        x = i % BOARDSIZE
        y = Math.floor(i / BOARDSIZE)
        @grid[x][y] = value

Get a string of the current grid values, in the same format as setFromString.

  getAsString: () ->
    string = ""
    for x in [0...BOARDSIZE]
      for y in [0...BOARDSIZE]
        string = string + (@grid[x][y] or ".")

    string

  clear: () ->
    for i in [0...BOARDSIZE]
      for j in [0...BOARDSIZE]
        @grid[i][j] = undefined

Get row at height y, where 0 is the top.

  getRow: (y) ->
    for i in [0...BOARDSIZE]
      @grid[i][y]

¶

Get column which is x across, where 0 is leftmost.
```
  getColumn: (x) ->
    @grid[x]
```

Get the group which is x groups across and y groups down, returning a 1-D array.

  getGroup: (x, y) ->
    group = []
    for i in [x * GROUPWIDTH...(x+1) * GROUPWIDTH]
      for j in [y * GROUPHEIGHT...(y+1) * GROUPHEIGHT]
        group.push(@grid[i][j])

    group

Get an array of co-ordinates of all the blank squares. We deliberately iterate over x in the inner loop, as it produces more attractive results when 'solving' an empty grid.

  getEmptyPositions: () ->
    emptyPositions = []

    for y in [0...BOARDSIZE]
      for x in [0...BOARDSIZE]
        if @grid[x][y] == undefined
          emptyPositions.push {x, y}

    emptyPositions

Does every position on this grid have a value?

  isFull: () ->
    for x in [0...BOARDSIZE]
      for y in [0...BOARDSIZE]
        if @grid[x][y] == undefined
          return false

    true

Get all the possible values that can go in this position, based on neighbours.

  getPossibilities: (x, y) ->
    possibilities = []

    for value in @legalValues
      groupX = Math.floor(x / GROUPWIDTH)
      groupY = Math.floor(y / GROUPHEIGHT)

      if value not in @getRow(y)
        if value not in @getColumn(x)
          if value not in @getGroup(groupX, groupY)
            possibilities.push(value)

    possibilities

Check that a given array contains no duplicates (other than empty regions).

  isRegionValid: (region) ->
    seenSoFar = {}

    for value in region
      if value == undefined
        continue

      if value of seenSoFar
        return false
      else
        seenSoFar[value] = true

    return true

¶

Could this table be a valid solution, or part of one? We tolerate blanks.

Note that we only check for obvious errors in a row, column or group, so it is still possible for an invalid grid to return true here.
```
  isValid: () ->
```

Check rows.

    for i in [0...BOARDSIZE]
      row = @getRow i
      if not @isRegionValid row
        return false

Check columns.

    for j in [0...BOARDSIZE]
      column = @getColumn j
      if not @isRegionValid column
        return false

Check groups.

    for i in [0...GROUPWIDTH]
      for j in [0...GROUPWIDTH]
        group = @getGroup i, j

        if not @isRegionValid group
          return false

    return true

¶

UI utilities
```
ui =
```

Set the table in the DOM to be blank.

  clearTable: () ->
    ui.removeUserValuesClass()
    $("#invalid_table").hide()

    blankTable = new SudokuGrid()
    ui.setTable blankTable

¶

Add an additional class to user-provided cells, so we can style them differently.
```
  addUserValuesClass: () ->
```

the user's input is the non-empty cells

    $("#sudoku td input[value!='']").addClass "user_value"

Undoes addUserValuesClass.

  removeUserValuesClass: () ->
    $(".user_value").removeClass "user_value"

  checkTableIsValid: () ->
    currentTable = new SudokuGrid()
    currentTable.setFromSelector $("#sudoku input")

    if not currentTable.isValid()
      $("#invalid_table").show()
    else
      $("#invalid_table").hide()

  getTable: () ->
    grid = new SudokuGrid()
    grid.setFromSelector $('#sudoku input')

    grid

  setTable: (table) ->

go over every row

    $("#sudoku tr").each (y, element) ->

then go over ever input in that row

      $("input", $(element)).each (x, element) ->

¶

set this input to the table value at this point
```
        $(element).val(table.grid[x][y])
```
¶

Solver

Our solver uses a backtracking cross-off algorithm.
```
solver =
```

Given a sudoku grid, find the position with the fewest possibilities.

Note that an invalid grid has positions with no possibilities.

  getMostContstrainedPosition: (grid) ->
    mostConstrainedPosition = null

    for {x: x, y: y} in grid.getEmptyPositions()
      possibilitiesHere = grid.getPossibilities x, y

      if possibilitiesHere.length == 0

¶

We will never find a more constrained position, so terminate early.
```
        return {x: x, y: y, possibilities: []}
```

If this position is more constrained, update mostConstrainedPosition.

      if not mostConstrainedPosition or possibilitiesHere.length < mostConstrainedPosition.possibilities.length
        mostConstrainedPosition = {x: x, y: y, possibilities: possibilitiesHere}

    mostConstrainedPosition

Given a sudoku grid, find a soution with a backtracking brute-force algorithm, starting with the most constrained positions.

  findSolution: (grid) ->
    if grid.isFull()
      return {isSolution: true, table: grid}

    {x: x, y: y, possibilities: possibilities} = solver.getMostContstrainedPosition grid

Try each of the possible values in this empty square until we find the correct one.

    for possibility in possibilities
      grid.grid[x][y] = possibility

      result = solver.findSolution grid
      if result.isSolution

¶

Found a solution on this branch! hurrah!
```
        return result
```

If we get here, this table is now unsolvable since there's a position with no possibilities. So we reset this square to blank for backtracking.

    grid.grid[x][y] = undefined

    return {isSolution: false, table: grid}

init = () ->

  $('#solve').click ->
    ui.addUserValuesClass()

    currentTable = ui.getTable()

    startTime = new Date().getTime()

    result = solver.findSolution currentTable

    endTime = new Date().getTime()
    console?.log "Solved in #{endTime - startTime} milliseconds."

    if result.isSolution
      solvedTable = result.table
      ui.setTable solvedTable
    else
      ui.removeUserValuesClass

  $('#demo').click ->
    ui.clearTable()

    grid = new SudokuGrid()
    
    for i in [1..BOARDSIZE]
      grid.grid[randomInt(0, BOARDSIZE - 1)][randomInt(0, BOARDSIZE - 1)] = i

    ui.setTable(grid)

    $('#demo').removeClass('info')
    $('#solve').removeClass('info').addClass('primary')

  $('#clear_table').click ->
    ui.clearTable()

  $('#import_puzzle').click ->
    ui.clearTable()

    puzzleString = prompt("Enter a puzzle string:")

    table = new SudokuGrid()
    table.setFromString(puzzleString)
    ui.setTable(table)
    ui.checkTableIsValid()

  $('#export_puzzle').click ->
    alert ui.getTable().getAsString()

¶

Monitor table for changes, and warn immediately if the grid is invalid.
```
  $("#sudoku input").keyup ->
    ui.checkTableIsValid()

init()
```
¶

We attach our objects to the global object so it's easy to fiddle with things in the browser console.
```
window.ui = ui
window.solver = solver
window.SudokuGrid = SudokuGrid
```

Sudoku Solver

UI utilities

Solver