jmitchell

Introducing Backtrex: solve discrete problems by brute force

I mentioned the project in “Logging: a silent performance killer”, but I’d like to formally present it. Backtrex is a behaviour that makes it easy to brute force any discrete problem.

The project currently includes a sample Sudoku solver, though it will probably get pulled out into a separate project later.

These callbacks are all Backtrex needs to get to work.

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

Since this is my first published package I’d sincerely appreciate feedback on its design. Cheers.

10 comments

#behaviours #library

5 2641 10

2017-01-17 18:33:26 UTC

First Post!

jmitchell

I plan to make Backtrex scale across multiple processes and even nodes. This issue talks more about that.

It mentions the need to research existing OTP and Elixir tools that would simplify the implementation. I’ve implemented a couple GenServers and Supervisors from tutorials, but haven’t done much with them or Agents, Tasks, and GenStage yet. Some combination of them or other tools would probably help a lot here.

Any advice on where to focus my search?

Post #1

Most Liked

michalmuskala

This does look interesting. How does it compare to prolog? From what I saw, this is in some ways similar to working with clpfd (“Constraint Logic Programming over Finite Domains”).

There’s an erlang implementation of prolog, GitHub - rvirding/erlog: Prolog interpreter in and for Erlang · GitHub, but it does not come with a clpfd library. I think this would also be an interesting area to explore.

Post #4

jmitchell

AFAIK Backtrex could be used as the basis for a Prolog engine or other unification systems. I’ve made toy projects in Prolog to solve constraint satisfaction problems like Sudoku, but I can’t claim to understand all its semantics. For example, it has impure features to prematurely stop searching part of the tree (known as a “cut”), but I don’t have any experience using it. Backtrex’s API would allow somebody to prematurely prune the search; they could simply stop returning as many unknowns and values. It’s not a recommended use case, but could be worth exploring, and I don’t know if this maps well to the “cut” semantics.

A while back I studied *kanren languages and implemented microKanren in Idris (may not compile anymore since Idris has changed a bit). Kanrens are small logic programming languages, most focusing on purity and determinism. The original authors prefer the term relational programming to emphasize that unification isn’t biased in a particular direction. For instance, “the head of a list” is a relation that could produce the single element at the front of a list or an infinite stream of lists where a given element is at the front (or even simply the set of all non-empty lists along with the first element of each). They’re fascinating languages. Anyone interested in learning more should work through The Reasoned Schemer and read the first few chapters of William E. Byrd’s PhD dissertation where the Core miniKanren language introduced and implemented in Scheme.

I’m not familiar with it. I’ll definitely check it out. Could inspire some fun demo applications and test the limits of the current API.

I recently heard about this, but haven’t had a chance to try it out yet. Looking at the README it’s not clear whether there’s been any focus on parallelism and distributed computing.

Part of why I’m excited about Backtrex is the massive scaling potential provided almost out of the box by the BEAM, and the opportunity to learn how to do that well.

Post #5

jmitchell

Yup, no sweat compared to all the potential bottlenecks in the backtracking algorithm and callback implementations. I’m working on generating flexible profiler reports now so I can identify bottlenecks and compare multiple implementations.

Post #10