A try in CoffeeScript this weekend : Sudoku solver

sudoku-solver.coffee

class Board
  constructor: (@size = 9) ->
    @grid = []

  init: ->
    @grid = []

    for x in [0 .. @size - 1]
      @grid.push([])

      for [0 .. @size - 1]
        @grid[x].push(0)

  get: (x, y) ->
    return @grid[x][y]

  set: (x, y, value) ->
    @grid[x][y] = value

  isEnd: ->
    for x in [0 .. @size - 1]
      for y in [0 .. @size - 1]
        return false if 0 == @get(x, y)

    return true

  isValidLine: (line) ->
    numbers = []
    for y in [0 .. @size - 1]
      cellNumber = @grid[line][y]
      if 0 != cellNumber
        return false if -1 != numbers.indexOf(cellNumber)
        numbers.push(cellNumber)

    return true

  isValidColumn: (column) ->
    numbers = []
    for x in [0 .. @size - 1]
      cellNumber = @grid[x][column]
      if 0 != cellNumber
        return false if -1 != numbers.indexOf(cellNumber)
        numbers.push(cellNumber)

    return true

  clone: ->
    copy = new Board(@size)
    copy.init()

    for x in [0 .. @size - 1]
      for y in [0 .. @size - 1]
        copy.set(x, y, @get(x, y))

    return copy

  equal: (board) ->
    return false if @size != board.size

    for x in [0 .. @size - 1]
      for y in [0 .. @size - 1]
        return false if @get(x, y) != board.get(x, y)

    return true


class Grid1 extends Board
  constructor: ->
    super

    @grid.push([2, 0, 9, 0, 0, 0, 8, 0, 0])
    @grid.push([1, 7, 0, 8, 0, 9, 0, 4, 0])
    @grid.push([8, 0, 4, 1, 6, 0, 0, 0, 0])
    @grid.push([0, 4, 0, 0, 0, 0, 2, 0, 9])
    @grid.push([0, 0, 0, 9, 4, 5, 0, 0, 0])
    @grid.push([6, 0, 1, 0, 0, 0, 0, 7, 0])
    @grid.push([0, 0, 0, 0, 2, 6, 4, 0, 3])
    @grid.push([0, 6, 0, 5, 0, 1, 0, 2, 8])
    @grid.push([0, 0, 3, 0, 0, 0, 1, 0, 7])


class Grid2 extends Board
  constructor: ->
    super

    @grid.push([3, 7, 8, 5, 0, 4, 0, 0, 0])
    @grid.push([0, 0, 6, 0, 7, 0, 5, 0, 3])
    @grid.push([2, 0, 0, 0, 3, 6, 0, 0, 0])
    @grid.push([6, 0, 1, 3, 4, 0, 2, 0, 9])
    @grid.push([0, 0, 0, 0, 0, 0, 0, 0, 0])
    @grid.push([7, 0, 9, 0, 8, 2, 3, 0, 6])
    @grid.push([0, 0, 0, 2, 6, 0, 0, 0, 5])
    @grid.push([9, 0, 7, 0, 1, 0, 6, 0, 0])
    @grid.push([0, 0, 0, 7, 0, 9, 1, 2, 3])


class Grid3 extends Board
  constructor: ->
    super

    @grid.push([0, 0, 0, 0, 8, 0, 0, 7, 5])
    @grid.push([9, 5, 0, 0, 0, 7, 4, 0, 1])
    @grid.push([0, 0, 4, 5, 3, 0, 2, 0, 0])
    @grid.push([0, 4, 9, 0, 0, 0, 0, 5, 0])
    @grid.push([0, 3, 0, 9, 0, 8, 0, 6, 0])
    @grid.push([0, 8, 0, 0, 0, 0, 7, 9, 0])
    @grid.push([0, 0, 6, 0, 1, 5, 9, 0, 0])
    @grid.push([3, 0, 5, 2, 0, 0, 0, 1, 6])
    @grid.push([8, 2, 0, 0, 9, 0, 0, 0, 0])


class Grid4 extends Board
  constructor: ->
    super

    @grid.push([0, 0, 0, 7, 9, 0, 5, 0, 8])
    @grid.push([5, 0, 9, 0, 4, 8, 0, 7, 0])
    @grid.push([2, 0, 0, 6, 0, 0, 0, 0, 0])
    @grid.push([0, 0, 0, 0, 8, 0, 4, 5, 3])
    @grid.push([1, 8, 0, 9, 0, 5, 0, 6, 7])
    @grid.push([6, 5, 3, 0, 2, 0, 0, 0, 0])
    @grid.push([0, 0, 0, 0, 0, 2, 0, 0, 9])
    @grid.push([0, 6, 0, 5, 1, 0, 3, 0, 2])
    @grid.push([8, 0, 1, 0, 6, 9, 0, 0, 0])


class Solver
  constructor: (@board) ->
    @game = []
    @isUnableToSolve = false
    @init()

  init: ->
    for line, index in @board.grid
      @game.push([])

      for value in line
        @game[index].push(new SolverCell(value))

  solve: ->
    @solveIteration() until @board.isEnd() or @isUnableToSolve

  solveIteration: ->
    boardBeforeResolution = @board.clone()

    @genaratePossibilities()
    @updateSolverBoard()
    @updateBoard()

    @isUnableToSolve = true if @board.equal(boardBeforeResolution)

  genaratePossibilities: ->
    for x in [0 .. @board.size - 1]
      for y in [0 .. @board.size - 1]
        @game[x][y].possibilities = @getPossibilitiesForCell(x, y)

  getPossibilitiesForCell: (x, y) ->
    return [] if 0 != @board.get(x, y)

    numbers = [1 .. @board.size]

    # ligne/colonne direct
    for i in [0 .. @board.size - 1]
      numbers.splice(numbers.indexOf(@board.get(x, i)), 1) if 0 != @board.get(x, i) and i != y and -1 != numbers.indexOf(@board.get(x, i))
      numbers.splice(numbers.indexOf(@board.get(i, y)), 1) if 0 != @board.get(i, y) and i != x and -1 != numbers.indexOf(@board.get(i, y))

    # sous-carre
    x1 = x - (x % 3)
    y1 = y - (y % 3)

    for i in [x1 .. x1 + 2]
      for j in [y1 .. y1 + 2]
        numbers.splice(numbers.indexOf(@board.get(i, j)), 1) if 0 != @board.get(i, j) and i != x and j != y and -1 != numbers.indexOf(@board.get(i, j))

    # hypothese de placement
    iterator = []
    iterator.push(value) for value in numbers

    for possibleValue in iterator
      counter = 0
      for i in [x1 .. x1 + 2]
        for j in [y1 .. y1 + 2]
          counter++ if 0 == @board.get(i, j) and @isValidHypothesis(i, j, possibleValue)

      numbers.splice(numbers.indexOf(possibleValue), 1) if 1 < counter and -1 != numbers.indexOf(possibleValue)

    return numbers

  isValidHypothesis: (x, y, value) ->
    simulation = @board.clone()
    simulation.set(x, y, value)

    return simulation.isValidLine(x) and simulation.isValidColumn(y)

  updateSolverBoard: ->
    for x in [0 .. @board.size - 1]
      for y in [0 .. @board.size - 1]
        if not @game[x][y].initial and @game[x][y].possibilities.length == 1
          @game[x][y].value = @game[x][y].possibilities[0]

  updateBoard: ->
    for x in [0 .. @board.size - 1]
      for y in [0 .. @board.size - 1]
        @board.set(x, y, @game[x][y].value) if not @game[x][y].initial


class SolverCell
  constructor: (@value = 0) ->
    @initial = (@value != 0)
    @possibilities = []


# --- Execution --- #
obj = new Grid2()

solver = new Solver(obj)
solver.solve()
console.log obj.grid

console.log "==> game over " if obj.isEnd()
console.log "==> unable to find a solution " if solver.isUnableToSolve