Hacker News new | past | comments | ask | show | jobs | submit login

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 (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.




+1 Dancing Link. Donald Knuth rules !




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: