[tylerneylon]

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

[abhgh]

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

[cb321]

It's not called "XCC" (or perhaps just "XC") as he mentioned in his talk, but there is this: https://en.wikipedia.org/wiki/Exact_cover which has a link to a Knuth algo (EDIT: and a section on what they call "generalized exact cover").

[svat]

The 'exact cover' problem has been studied for decades, possibly centuries. The generalization to "primary" and "secondary" items is Knuth's terminology, but the idea itself is a natural one and has been considered before. It is specifically "exact covering with colors" (XCC, not "XC") that is Knuth's innovation/discovery, what a large part of the recent volume discusses, and about which he said there isn't a Wikipedia article yet (because it hasn't caught on yet, and discussed in non-Knuth sources).

[cb321]

Sorry - I meant my "perhaps" to refer to the distinction you reiterated, but I can see why that may not have been clear.

If you feel the (also already mentioned) section on "generalized" exact cover is lacking, hey, it's Wikipedia - anyone can edit it. So, add a little material with alternate / supplementary Knuth terminology / pointers. My intent was merely to point to somewhere to make this material easier to find via search engines (eventually).

[svat]

Ah I see, you were suggesting an existing article on Wikipedia where this information could be added. (It doesn't yet make sense, per Wikipedia policy, to create an article for XCC, for the reasons I mentioned.)

Thanks, I'll look into adding some content to the exact cover article… will have to re-watch Knuth's talk and re-read some of his book/prefascicle sections first!