The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes. The first trick is to implement each assumption of the search with reversible local operations on doubly linked lists. By this trick, every step of the search affects the data incrementally. The second trick is to add a ghost square that represents the identity of each polyomino. Thus puts the rule that each polyomino be used once on the same footing as the rule that each square be covered once. The coding simplifies to a more abstract form which is equivalent to 0-1 integer programming. More significantly for the total computation time, the search can naturally switch between placing a fixed polyomino or covering a fixed square at different stages, according to a combined heuristic. Finally the author reports excellent performance for his algorithm for some familiar puzzles. These include tiling a hexagon by 19 hexiamonds and the N queens problem for N up to 18.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
> I implemented branching and backtracking
The solvers they describe
are indeed based on depth-first search and backtracking; in Python, the backtracking part involves some copying:
for v in cands:
new_board = [row[:] for row in board]
new_board[i][j] = v
solved = solve(new_board)
For anyone interested in solving sudokus, I recommend reading Knuth's Dancing Links paper [1] and implement sudoku solver as an exact cover problem. The idea is to completely get rid of copying the state, switching the pointers of doubly linked lists instead, which speeds up the backtracking part a lot.
It's a little bit more code than plain DFS, but much more exciting when it actually works!
[1]: https://arxiv.org/pdf/cs/0011047
Indeed it is, and Donald Knuth spends a substantial part of the latest volume (4B) of The Art of Computer Programming on solving exact cover problems like this using Dancing Links! He presented an earlier version of the algorithm in this legendary article [1], but as good as that article is, the book is even better (and the algorithm improved!). It also has tons of exercises like this. Cannot recommend it highly enough.
[1]: https://arxiv.org/abs/cs/0011047
Donald Knuth's Dancing Links paper is a beautiful exploration of the power of linked lists. He uses a table with doubly linked lists (for rows and cols) to solve omino tiling. The linked lists allow for an elegant unpicking of rows (and re-attaching when backtracking)
The paper's a really enjoyable read, Knuth's tone throughout is "look at this, this is fun"
https://arxiv.org/abs/cs/0011047
Knuth's Dancing Links is originally from 2001, and was first published to book form in Fasicle 6 (2019).
Dancing Links seems to have outstanding performance for a generic cover problem, even on modern cache heavy processors.
It seems like the static layout of the links benefits greatly from cache locality. Seriously, study the algorithm before hating on it.
EDIT: Knuth's original writing style may be "too mathematical" for some. Here's a dumbed down version: https://medium.com/javarevisited/building-a-sudoku-solver-in...
The original Knuth: https://arxiv.org/abs/cs/0011047
The 2001 code is suboptimal in a few ways compared to the more recent updates. Knuth discusses the…
Read the full comment
updates in Fasicle 6, the cweb source code is: https://www-cs-faculty.stanford.edu/~knuth/programs/dlx1.w
-------------------
EDIT: But... I hate it when people tell me to read other papers without pointing out the issue. :-)
The specific issue is that in Dancing Links: 1 -> 2 -> 3 becomes 1->3, and then later becomes 1 -> 2 -> 3 again. This pattern of insert (and then un-insert at the same place) means that all linked-list operations will execute in L1 cache.
Furthermore, Knuth lays out the data such that 1, 2, and 3 are sequential in memory. So the entire process is incredibly cache-efficient and takes advantage of both temporal and spatial locality. (Because 1 usually inserts / removes 2, and because 1 and 2 are always next to each other in memory, you're never leaving L1 cache).
As such, all DXL-operations are outstandingly fast. Furthermore, the pattern of insert-uninsert is useful for Exact Cover (which Knuth then used to solve graph coloring, N-Queens, Sudoku, and other NP-complete problems at relatively high speed). No, its not a generic SAT solver, but it does pretty darn good, especially considering how simple the operations are.
> certain algorithms are more intuitive if implemented imperatively.
FWIW, "Dancing Links" is a wonderful technique that would be worse than pointless in an immutable language.
https://arxiv.org/pdf/cs/0011047.pdf
On a related note, Knuth has a cool algorithm to solve exact coverage problems like sudoku (similar logic as Norvig's DFS but implemented very differently). It's more work to code it than Norvig's but worth it for the education:) (and it solves faster)
Here's the paper describing the algorithm: https://arxiv.org/pdf/cs/0011047.pdf
I found Knuth’s “Dancing Links” paper [1] very well written and a somewhat easy read (I had to reread certain parts a couple times). I had to write a sudoku solver for one of my classes and I read that dancing links and algorithm x was one way to do it [2]. I then read some things around the internet to apply dancing links to sudoku solving [3] [4]. If you read the Wikipedia entry on exact cover problems there is a section on sudoku as an exact cover problem [5] this is one thing necessary to understand in order to implement a sudoku solver with algorithm x and dancing links.
Knuth even talks about dancing links in his new 2017 Christmas Tree Lecture [6] specifically here…
Read the full comment
at 4:28 [7]. Basically he uses dancing links to solve for certain n in the problem he sets up in that lecture.
[1] https://arxiv.org/abs/cs/0011047
[2] https://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Exac...
[3] http://garethrees.org/2007/06/10/zendoku-generation/
[4] https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudok...
[5] https://en.wikipedia.org/wiki/Exact_cover#Sudoku
[6] https://www.youtube.com/watch?v=BxQw4CdxLr8
[7] https://youtu.be/BxQw4CdxLr8?t=4m28s
Interestingly, when I run this through an old Dancing Links [1] based solver I wrote a while back for solving general puzzles, it solves the first one in 0.04 seconds, uses 65 columns, 242 rows, does 181510 de-queues, and finds a unique solution.
The same solver on the hard version runs in 0.01 seconds, 67 columns, 272 rows, 245626 de-queues, and finds no solutions.
So as others have noted, the hard puzzle solution must be some weird rotation, and/or not spaced on "integral" coordinates.
Since I don't have time to write such a solver, I will leave it for now :)
Note: if you have not looked at the Dancing Links paper by Knuth and learned how to use it to solve backtracking problems, you should. It's amazingly useful for solving such problems, for enumerating all solutions, and it is fast and completely general.
[1] http://arxiv.org/abs/cs/0011047
Dancing Links - Donald Knuth - http://arxiv.org/abs/cs/0011047
Lots of fun and is a weekender, but you can expand it to solve anything from sudoku to all kinds of tiling problems. David Goodger's webpage, http://puzzler.sourceforge.net/, solves all sorts of polyform puzzles using DLX algorithm.
Dancing Links (Knuth's paper: https://arxiv.org/pdf/cs/0011047.pdf )
> In computer science, dancing links is the technique suggested by Donald Knuth to efficiently implement his Algorithm X. Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem. Some of the better-known exact cover problems include tiling, the n queens problem, and Sudoku.
~ https://en.wikipedia.org/wiki/Dancing_Links
Also SEQUITUR http://www.sequitur.info/
> Sequitur (or Nevill-Manning algorithm) is a recursive algorithm developed by Craig Nevill-Manning and Ian H. Witten in 1997[1] that infers a hierarchical structure…
Read the full comment
(context-free grammar) from a sequence of discrete symbols. The algorithm operates in linear space and time. It can be used in data compression software applications.
~ https://en.wikipedia.org/wiki/Sequitur_algorithm
Part of the reason I like these both is that they each require sharp pointer manipulation to work efficiently.
I'm a functional programming fan, these beautiful and useful algorithms remind me that purity isn't everything, eh? Also, it's fun to think about how you might get FP code to emit correct pointer-munging code for them.
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
The recent discovery of the Spectre and Meltdown attacks represents a watershed moment not just for the field of Computer Security, but also of Programming Languages.
This paper presents a personal view of the evolution of six generations of Smalltalk in which the author played a part, starting with Smalltalk-72 and progressing through Smalltalk-80 to Squeak and Etoys.