Sudoku Solver in Elixir using pure functions and backtracking

sudoku_solver.exs

# Sudoku Solver
#
# Go to the SudokuSolver module at the bottom to see the main module.
# To run the solver on a example input board, call `SudokuSolver.run/0`.
# The high-level backtracking logic is in the `SudokuSolver.solve/2` function;
# the other modules and their functions provide the supporting code for representing
# the board and performing simple tasks or providing utility functionality.


defmodule SudokuSolver.Cell do
  defstruct [value: 0, possibilities: ""]
end

defmodule SudokuSolver.Board do
  alias SudokuSolver.Cell

  def new(board_list) do
    board =
      board_list
      |> coord_tuples()
      |> cell_tuples()
      |> Enum.into(%{})

    Enum.reduce(board, board, fn({coords, cell}, board) ->
      if cell.value != 0 do
        propagate_changes(board, coords)
      else
        board
      end
    end)
  end

  def print(board) do
    for i <- 0..8 do
      row =
        Enum.reduce((0..8), [], fn(j, list) ->
          value = board[{i, j}].value
          if rem(j, 3) == 2 do
            [" ", value | list]
          else
            [value | list]
          end
        end)
        |> Enum.reverse()
        |> Enum.join(" ")

      IO.puts(row)
      if rem(i, 3) == 2, do: IO.puts("")
    end
  end

  def peers({i, j} = coords) do
    row = MapSet.new(for t <- 0..8, do: {i, t})
    column = MapSet.new(for t <- 0..8, do: {t, j})

    start_row = 3 * div(i, 3)
    start_col = 3 * div(j, 3)
    square =MapSet.new(
      for r <- (start_row..(start_row + 2)),
          c <- (start_col..(start_col + 2)), do: {r, c}
    )

    row
    |> MapSet.union(column)
    |> MapSet.union(square)
    |> MapSet.delete(coords)
  end

  def propagate_changes(board, position) do
    value = board[position].value

    position
    |> peers()
    |> Enum.reduce(board, fn(peer_position, board) ->
      update_in(board[peer_position].possibilities, &(
        String.replace(&1, to_string(value), "")
      ))
    end)
  end

  def next_position(board) do
    board
    |> Enum.filter(fn {_pos, cell} -> cell.value == 0 end)
    |> Enum.min_by(fn {_pos, cell} -> String.length(cell.possibilities) end)
    |> elem(0)
  end

  def assign(board, position, value) do
    board[position]
    |> put_in(%Cell{value: value, possibilities: ""})
    |> propagate_changes(position)
  end

  def possible_numbers(board, coords) do
    board[coords].possibilities
    |> String.codepoints()
    |> Enum.map(&String.to_integer/1)
  end




  defp coord_tuples(board_list) do
    board_list
    |> Enum.with_index()
    |> Enum.map(fn {row, i} ->
      row
      |> Enum.with_index()
      |> Enum.map(fn {value, j} -> {{i, j}, value} end)
    end)
    |> List.flatten()
  end

  defp cell_tuples(coord_tuples) do
    Enum.map(coord_tuples, fn {coords, value} ->
      {coords, %Cell{
          value: value,
          possibilities: (if value == 0, do: "123456789", else: "")}
      }
    end)
  end
end


defmodule SudokuSolver do
  alias SudokuSolver.Board

  def run() do
    board_list = [
      [9, 0, 0, 0, 8, 0, 0, 0, 1],
      [0, 0, 0, 4, 0, 6, 0, 0, 0],
      [0, 0, 5, 0, 7, 0, 3, 0, 0],
      [0, 6, 0, 0, 0, 0, 0, 4, 0],
      [4, 0, 1, 0, 6, 0, 5, 0, 8],
      [0, 9, 0, 0, 0, 0, 0, 2, 0],
      [0, 0, 7, 0, 3, 0, 2, 0, 0],
      [0, 0, 0, 7, 0, 5, 0, 0, 0],
      [1, 0, 0, 0, 4, 0, 0, 0, 7]]

      count = board_list |> List.flatten() |> Enum.count(& &1 != 0)
      board = Board.new(board_list)

      solve(board, count)
      :ok
  end


  def solve(board, 81 = _count) do
    Board.print(board)
    board
  end
  def solve(board, count) do
    position = Board.next_position(board)
    possible_nums = Board.possible_numbers(board, position)

    Enum.reduce_while(possible_nums, nil, fn(number, _) ->
      new_board = Board.assign(board, position, number)

      case solve(new_board, count + 1) do
        nil ->  {:cont, nil}
        solved_board ->  {:halt, solved_board}
      end
    end)
  end

end