Remove one of the dancing links implementations

[Nils Bruin]

I noticed that sage presently has two implementations of DLX:

 - a toy one implemented in python:

https://github.com/sagemath/sage/blob/9cd86e9596a6d996611cd7cc9281ac5a95fda89c/src/sage/combinat/dlx.py

- a wrapper of a C++ implementation:

https://github.com/sagemath/sage/blob/9cd86e9596a6d996611cd7cc9281ac5a95fda89c/src/sage/combinat/matrices/dancing_links.pyx

The toy one actually shows up more prominently in the documentation:

https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/dlx.html

whereas the wrapper is only documented as "internal":

https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/matrices/dancing_links.html

As far as I can see, the two are almost drop-in replacements. The C++ implementation does seem to be the one in wider use in the rest of the library. Perhaps convert the documentation for "dlx" to use the (almost certainly) much more efficient C++ wrapper, and perhaps remove the toy implementation?

I happened to need a dlx solver and after searching found the python implementation in sage. Unaware of the C++ alternative I nearly went with using the python one, which would probably have performed badly.

Changing this over could be a nice introductory project for someone interested in familiarizing themselves with sage development.

[Nils Bruin]

For historical reference, both implementations were incorporated in sage in feb/march 2008:

https://groups.google.com/g/sage-devel/c/COEXL3dyBS8

It looks like implementing DLX is a finnish thing :-). From the thread, I don't get the impression there is any reason to prefer the python implementation. Neither author seems to be still involved, so we've inherited the code anyway. It's simple code, though, and useful.

[Sébastien Labbé]

I have been using the c++ implementation of dancing links a lot during the last decade for fun [1,2] and for research. There were some issues in the original C++ code that are now fixed (providing a empty set of rows was crashing sage, also, we can now reset the search from the start, reduction to sat and reduction to milp, etc). I forgot about the existence of the Python implementation, since I always use the C++ one.

[1] http://www.slabbe.org/blogue/2015/09/there-are-13.366.431.646-solutions-to-the-quantumino-game/

[2] https://ask.sagemath.org/question/81610/test-if-a-graph-has-a-claw-decomposition/

That being said, Franco Saliola from Montreal told me a few years ago that the code written by Knuth in recent years is faster (for some problems that Franco was working on) than the implementation currently in Sage. There are heuristics on the choice of the next column to deal with in the search that can be better suited for some problems. This is something on my TODO list since many years to check this out and maybe provide this in Sage if copyrights allows it.

Sincerely,

Sébastien