Backtracker
Inspired by an idea from Judy-anne Osborn, I've been working with Richard Brent, Paul Leopardi, and Nathan Van Maastricht (as well as Judy-anne) to create a web application for human-guided computer search in combinatorial search problems. The idea is to present a visual representation of the backtracking search tree, together with some information about candidate choices, and then allow the human to guide the computer search through their own heuristics (intuition).
A prototype version can be played here. (The app will open in a new window.) N.B., in future the app will very likely move to a different url.
This prototype works for the decomposition of a putative Gram matrix with the goal of finding maximal determinant matrices (the original inspiration), and two toy problems: open knight's tours on arbitrary boards, and the N queens problem.
What's the largest board for which you can find an open knight's tour? (Hints: Warnsdorff's rule is an effective heuristic, and mind the corners of the board.)
There is much still to do! The remaining stages will involve elements of game design, javascript programming, server side scripting, and research into the specific applications. We want the app to be both more attractive and “playable”, as well as useful for research through clever design of the computer search algorithm and use of parallel threads carrying out searches in the background.
The computer search runs client side, leveraging the great leaps in efficiency of javascript interpreters in recent years.
Note that it is only suitable for playing on a computer for the moment, i.e. it is not at all mobile friendly. This is because different kinds of mouse clicks are required to interact with the backtracking tree.
Brief instructions
Your goal is to search for a solution to the combinatorial search problem, e.g. a valid matrix decomposition, or a knight's tour, or a complete N queens configuration. These solutions are represented in the backtracking tree by dark green nodes.
First you must access the left-most menu to choose which application to use (Gram matrix decomposition, knight's tour, N queens), then choose the problem case for the application (e.g. board dimension for knight's tour).
Now, press the “Start” button to start the app.
The remaining menu specifies the “search depth”. A good default option is three, but one needs to be careful that this depth is not too great. If the branching ratio of the backtracking tree is too large then the search will not terminate in a reasonable time frame, and likely the memory allocated to the browser will be exhausted causing your web browser to crash. This is not a problem for the knight's tour and N queens applications where the branching ratio is bounded, but is a significant issue for the Gram matrix decomposition, especially the larger cases.
Solutions are dark green, while dead ends are red. These are, by necessity, leaves of the backtracking tree. Internal nodes may have one of three possible states, uncertain (amber), leads to solution (light green), and leads to only dead ends (pink).
To interact with the search tree you have three basic operations.
| Inspect: | Show the combinatorial object corresponding to a particular node in the tree. | Left click on the node. |
|---|---|---|
| Search: | Search the backtracking tree starting from a particular node. | Alt-click, Command-click / Windows key-click. |
| Shift: | Change the focus of the part of the tree that is shown. If you click on the root it will move the tree down one level, otherwise clicking on any other node will bring it to the root. | Shift-click. |
Finally, a limited amount of feedback is provided above the tree, keeping track of the number of search operations (moves), nodes searched, and solutions found.
Have fun! Any feedback would be gratefully received.