backtrex

v0.1.2

backtrex v0.1.2 Backtrex behaviour

A backtracking behaviour for solving discrete computational problems.

Summary

Types

assignment()

Potential value assignment for some unknown

assignment_search()

An assignment with a list of values left to try

problem()

A puzzle with a set of unknowns, possible assignments for each, and an invariant property

result()
unknown()

Unique identifier for an unknown in a problem

value()

Value that could be assigned to an unknown

Callbacks

assign(problem, unknown, value)

Updated problem with value assigned to unknown

unknowns(problem)

Open questions in problem that a solution must answer

valid?(problem)

Return whether problem is in a valid state

values(problem, unknown)

Potential answers to an unknown in the context of a problem

Types

assignment() 
assignment() :: {unknown, value}

Potential value assignment for some unknown.

assignment_search() 
assignment_search() :: {assignment, [value]}

An assignment with a list of values left to try.

problem() 
problem() :: any

A puzzle with a set of unknowns, possible assignments for each, and an invariant property.

Each type of problem must have ways to:

  1. enumerate its unknowns (see Backtrex.unknowns/1),
  2. enumerate values that could be assigned to any particular unknown in a solution (see Backtrex.values/2).
  3. incorporate proposed assignments of values to unknowns (see Backtrex.assign/3), and
  4. check whether the invariant holds (see Backtrex.valid?/1).
result() 
result() :: {:ok, :solution, problem} | {:ok, :no_solution}
unknown() 
unknown() :: any

Unique identifier for an unknown in a problem.

value() 
value() :: any

Value that could be assigned to an unknown.

Callbacks

assign(problem, unknown, value) 
assign(problem, unknown, value) :: problem

Updated problem with value assigned to unknown.

Assignments may be wrong in the sense that they will not lead to a solution. Backtrex maintains a copy of the original problem, and uses the Backtrex.valid?/1 callback to ensure assignments are productive.

unknowns(problem) 
unknowns(problem) :: [unknown]

Open questions in problem that a solution must answer.

In Sudoku this would be the puzzle’s blank cells.

valid?(problem) 
valid?(problem) :: boolean

Return whether problem is in a valid state.

An invalid state means there’s no way to solve problem in its current state. This callback determines whether to march forward, tackling new unknowns, or backtrack, rewriting the provisional answers that led to this state.

values(problem, unknown) 
values(problem, unknown) :: Enum.t

Potential answers to an unknown in the context of a problem.

Every cell in Sudoku, for instance, must be a number between 1 and 9, inclusive, so a Sudoku solver would return 1..9. In this case the result doesn’t depend on puzzle or unknown, but for other problems it might.