Donald Knuth’s 2023 Christmas Lecture: Making the Cells Dance

This is a very nice observation that I've found in the dancing links paper :

My trusty old SPARCstation 2 computer, vintage 1992, is able to perform approxi- mately 0.39 mega-updates per second when working on large problems and maintaining the S fields. The 120 MHz Pentium I computer that Stanford computer science faculty were given in 1996 did 1.21 mega-updates per second, and my new 500 MHz Pentium III does 5.94. Thus the running time decreases as technology advances; but it remains essentially proportional to the number of updates, which is the number of times the links do their dance. Therefore I prefer to measure the performance of algorithm DLX by counting the number of updates, not by counting the number of elapsed seconds.

The Briggs & Torczon paper focuses on set representation rather than key-value style access, but of course one can get associative access with just a 2nd dense array of satellite data or, equivalently, wider-than integers in the one dense array (depending upon memory layout desires). Then you basically have a direct access index (like only 256 possible things, so use an 8-bit byte-sized index array of 256 entries) paired with a dense table.

This always struck me as very similar to early ideas in database indexing a la Ted Codd & crew (as perhaps more recently popularized in recent Python3.6 hash table impls). So, while Aho & Briggs & Torczon all deserve ongoing credit for popularization, I wonder if anyone out in HN-land knows of a reference to a database paper from the 60s or 70s introducing this? (For more complete attribution.)

This lecture covers Knuth's latest (and simplest-so-far) algorithm to solve the XCC problem; I'll describe XCC below.

The XCC problem is designed to solve problems that are NP-hard. So algorithms that solve XCC are not known to be polynomial-time. But they're interesting because they can solve a whole swath of problems that are difficult (not known to have a poly-time algorithm) and interesting. This is in the same world as SAT-solvers, in case you already know about those.

This particular Knuth lecture shows how you can simplify his original "dancing links" algorithm to a "dancing cells" version that no longer uses as complex a linked list structure internally, but rather uses flat arrays, although it does retain some link-like structure. The dancing cells alg isn't always better than dancing links, but for most of Knuth's test cases, this new version is faster.

Ok, what is XCC? It's the "exact covering with colors" problem. (Knuth mentioned that XCC doesn't yet have a wikipedia page, and maybe it should!) It's an extension of the "exact cover" problem -- you're given a set of items that should be covered, and a set of options (sets of items) that may cover some items. Each item must be covered exactly once (no more, no less). Now I'll add the "with colors" part: You can divide items into primary (these need to be covered exactly once) and secondary: these items may be either uncovered, or have possibly-many covering options, but the "color" of the coverings must be the same.

Here's a problem to help gain some intuition for XCC: Imagine trying to build an mxn word grid with valid English words. Each option can be either a word in a row or a word in a column. In this case your primary items could be something like "each row needs a word and each column needs a word." Then your secondary items would be the individual cells and each letter is a "color;" thus the use of consistent colors is a way to ensure that you can't assign different letters to the same cell.

Another description of XCC: https://docs.rs/xcc/latest/xcc/

Word squares: https://en.wikipedia.org/wiki/Word_square

This is a genuine question based on my desire to get a better understanding of our current progressive culture. I am not passing judgement and I hope you can answer honestly. Did you ask this question with the term 'cultural appropriation' in mind? Does this sweater make you uncomfortable and if so why?

I am yet to read up on xcc so this is helpful, thanks. One thing that I found useful as an application from Knuth's lecture (I'm not sure if it's edited out because it was an audience discussion, I attended the 2023 talk in person, reg. which I commented on another thread [1]), is that it can produce multiple SAT solutions, as opposed to just one,which seems to be the case now (definitely true for z3 which I have used a bit). This is important in practice because often there are downstream constraints which you might become aware of later (e.g., there're other hidden "soft" costs you didn't factor in), and because of which you now need to go back and need to run the solver again to find an alternative solution. This is time consuming but the worse part is there is no good way to avoid the first solution except by adding another constraint, e.g. original constraints + not(first solution).

Edit: as an extension of the above, the second solution mightn't work well too, in which case you'd need to repeat the above till you find a solution that you like. Very painful in practice.

[1] https://news.ycombinator.com/item?id=38775882