There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem

for valid Sudoku puzzles, because they admit precisely one solution, and the constraint solver deduces this unique solution by reasoning about the decision diagram. There's a severe drawback to this: The BDD may be exponential in the number of variables. That's a problem, because there are dozens of variables in many Sudoku puzzles. In practice, we are often lucky, and the worst-case space requirements do not arise. For comparison, the CLP(FD/ℤ) formulation is based on constraint propagation that ensures a certain kind of consistency for all individual constraints in isolation, but not necessarily for the combination of all constraints, i.e., the problem as a whole. In practice, at least for Sudoku puzzles, this also often leads to finding the unique solution without any search. This may also be the case if only the minimum number of clues for a valid Sudoku puzzle (i.e., 17, per https://arxiv.org/abs/1201.0749) is specified, as the parent mentions. In general, search is still required. In the concrete case of (standard) Sudoku, the required search, if there is any at all, is typically very small, because the many constraints usually narrow down the entire space considerably. Reducing the amount of required search is the key attraction and goal of the consistency techniques that are used by constraint systems. The available systems differ in how much and how fast they are able to prune inconsistent values, leading to notions such as global consistency, domain consistency, bounds consistency etc. that give some indication of propagation strength.

high-pass or a low-pass filter. Researchers want to publish in prestigious journals since it signals that their work is high quality, and it gives greater exposure to their work—prestigious journals have a broader reader base than unknown journals. This considered, the author got a point. In experimental domains of science such as Biology, Physics, Chemistry, Psychology (and sometimes even Math! [2]), reproducibility is of paramount importance and publishing negative results helps both researchers save time by not doing repeated work and avoid statistical bias in meta studies. In fact, what the author of this article implicitly looks for already exists![3] But they usually fail to gain traction, and this for a precise reason: writing and publishing a paper takes a great amount of time. Publishing a paper in favor of the null hypothesis usually does not bring much recognition, and the time could instead be used to research or write the next paper. What can be done then? A solution could be to create a platform where scientific results can be made available without the whole publishing overload. No literature review, no verbose explanations, only "what we did" and "what we got". And if possible, in a machine-readable format. Any fellow HNers? [1] https://en.wikipedia.org/wiki/ArXiv#Controversy [2] https://arxiv.org/abs/1201.0749 [3] http://www.jasnh.com/

Indeed, the paper [1] estimates that our original checker of late 2006 would take over 300,000 processor-years in order to search every sudoku grid." https://arxiv.org/pdf/1201.0749.pdf The estimate in the comment (9!*9!) seems to be implying a simple enumeration, not a complex strategy of symmetry-folding. But even if you do reduce the enumeration, the authors of that paper say their software requires 800 CPU years. I'm not making any claims about whether getting that down to a day might be possible, but I wish you good luck. By all means, show everyone how to do it with a proper implementation and a large cluster! ;)