• # 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 ->

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')

\$('#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 ->
```  \$("#sudoku input").keyup ->
```window.ui = ui