Yes, his program would be very fast for a beginner's sudoku problem, where there is just one way to place each digit. But there are much more advanced problems, where advanced logical tactics have to be used. Just as an example, if a row or box contains two cells with two possible entries, say 3 7, then you know that that row or box must contain both 3 and 7, you just don't know in which order. That fact then excludes 3 and 7 from appearing in certain other cells. Solving a puzzle using trial and error (dancing links) can solve quickly for simple puzzles. But some puzzles will require lots of backtracking, which tends to increase the memory references and execution time exponentially. Dancing links for sudoku should be tested with a sudoku having a maximal amount of backtracking, to make sure it will complete in a reasonable time. Such a test can be done easily without finding a maximally-complex sudoku by modifying the dancing links program to deliberately use backtracking every time backtracking is possible.
As mentioned in the video, the problem of solving a sudoku is NP-Hard (and NP-Complete), so there will always be some sort of exponential complexity involved. The best we can do is use some heuristics to simplify it in most cases. Most solvers use a naive approach of simply iterating through every number and backtracking, and this approach still takes a reasonable amount of time (a few seconds) on most modern computers. The dancing links algorithm uses the heuristic of picking constraints with the fewest options to satisfy them (or the option which satisfies the most constraints), which narrows down the guessing tremendously. With the data structure proposed as well, it can backtrack in constant time rather than the (at least) linear time required otherwise. Applied towards a specific problem (such as specifically sudoku), and the data structure can even be stored in static memory. If we tried applying first-order logic, we would still have to guess which rules to apply to which pieces of knowledge, and knowledge would grow exponentially in that way as well.
@@bleachisback Thank you for these good comments. I think for sudoku, the practicality of a general dancing links algorithm has to be tested using actual puzzles. I would expect some puzzles to be solved in a fraction of a second, while others might require quite a long time. How long depends on the amount of backtracking, so a good in the worst case test would be a computer-generated sudoku having a provably maximum amount of backtracking required.
@@david203 I happen to be writing a Bachelor's thesis (and plan on continuing research afterwards) precisely on this algorithm. Knuth indeed tested this approach on actual puzzles - and found that it solves even the most difficult puzzles in less than 300 steps, and it solves most of them in less than 100 steps, which is pretty much instant on any reasonable hardware. I tried this algorithm on the queens problem - and it finds a solution for a 30x30 chess board (with 30 non-attacking queens) in a matter of seconds, while a regular depth-first search pretty much becomes useless at around 13x13 (however, there are algorithm that solve this specific problem much faster, some of them even using dancing links in a different way from this algorithm). You are absolutely right that this specific algorithm would be terrible for many puzzles - there are generalized versions of this algorithm that can solve many more puzzles, and even those don't work very well for many puzzles and problems that require backtracking, as I found with my own experiments. Of course, there are algorithms that work faster for specific puzzles than this very general algorithm - for example, I tried to solve the vertex cover problem using a generalized variant of this algorithm, and it ended up performing absolutely terribly compared to a purpose-made algorithm, but my theory is that we can use dancing links to make the purpose-made algorithm faster, but the data structure will perhaps looks quite different.
@RU-vid please automatically delete the uh, I'm, & stammering at least from the audio. For extra credit trim the video during the new silent places if the video doesn't change.
