Backtrex

Logic puzzles and similar problems can be solved by exploring the space of possible solutions. By enumerating potential answers to open questions like "what should go in this cell?" or "which direction should I go now?", checking whether a given set of those answers is valid, and revising answers whenever you reach an invalid state you'll eventually find the solution (assuming one exists and the problem is finite). This strategy is known as backtracking and has a surprising range of applications. A few simple callbacks are all Backtrex needs to get to work.

Getting Started

Backtrex is an Elixir project, and these directions assume you are using the mix tool. However, it should be possible to use this project in Erlang as well.

Installing

Add backtrex to your list of dependencies in mix.exs:

def deps do
  [{:backtrex, "~> 0.1.2"}]
end

Then run mix do deps.get.

Backtrex currently makes a lot of Logger.debug calls. To avoid seeing them, add the following to config/config.exs:

config :logger, level: :warn

Usage

Suppose you want to make a Sudoku solver, and you already have ways to represent, update, and validate puzzles. Here's roughly what the solver, a Backtrex behaviour, would look like:

defmodule SudokuSolver do
  use Backtrex
  
  def unknowns(puzzle) do
    SudokuPuzzle.empty_cells(puzzle)
  end
  
  def values(_puzzle, _cell), do: 1..9
  
  def assign(puzzle, cell, value) do
    SudokuPuzzle.put_cell(puzzle, cell, value)
  end

  def valid?(puzzle) do
    SudokuPuzzle.valid?(puzzle)
  end
end

In return for implementing these callbacks, Backtrex gives you a SudokuSolver.solve/1 function for free.

The documentation at https://hexdocs.pm/backtrex explains what Backtrex expects from these callbacks.

Similar Sudoku solver code is available in lib/examples/sudoku. For now those modules are even shipped with the package. Try it out in your project:

defmodule Sandbox do
  alias Backtrex.Examples.Sudoku.Puzzle
  alias Backtrex.Examples.Sudoku.Solver

  def hello_backtrex do
    {:ok, puzzle} = Puzzle.from_list([
      [5,   3, :_, :_,  7, :_, :_, :_, :_],
      [6,  :_, :_,  1,  9,  5, :_, :_, :_],
      [:_,  9,  8, :_, :_, :_, :_,  6, :_],
      [8,  :_, :_, :_,  6, :_, :_, :_,  3],
      [4,  :_, :_,  8, :_,  3, :_, :_,  1],
      [7,  :_, :_, :_,  2, :_, :_, :_,  6],
      [:_,  6, :_, :_, :_, :_,  2,  8, :_],
      [:_, :_, :_,  4,  1,  9, :_, :_,  5],
      [:_, :_, :_, :_,  8, :_, :_,  7,  9]])

    {:ok, expected_solution} = Puzzle.from_list([
      [5, 3, 4, 6, 7, 8, 9, 1, 2],
      [6, 7, 2, 1, 9, 5, 3, 4, 8],
      [1, 9, 8, 3, 4, 2, 5, 6, 7],
      [8, 5, 9, 7, 6, 1, 4, 2, 3],
      [4, 2, 6, 8, 5, 3, 7, 9, 1],
      [7, 1, 3, 9, 2, 4, 8, 5, 6],
      [9, 6, 1, 5, 3, 7, 2, 8, 4],
      [2, 8, 7, 4, 1, 9, 6, 3, 5],
      [3, 4, 5, 2, 8, 6, 1, 7, 9]])

    {:ok, :solution, solution} = puzzle |> Solver.solve

    solution == expected_solution
  end
end

Sandbox.hello_backtrex/0 should return true within 5 seconds or so.

Other applications

Sudoku makes for a good introductory demo, but it doesn't showcase the flexibility of Backtrex's design. Here's some other applications I suspect it could handle.

• incomplete information
  • corn maze of unknown size; visibility limited to what's nearby.
• don't know until you get there
  • finding a string of 5 characters that hashes to a certain value.
• programming language features
  • pattern matching engine
  • type checker

License

Backtrex is licensed under Apache 2.0. See the LICENSE file.