Solving Sudoku (for general sized grids) is np-complete, but usually fairly easy. Many people write quite good sudoku solvers that can solve any 9x9 in a few milliseconds.
Now, a valid sudoku is a grid which has one unique answer. What’s the smallest number of clues a valid sudoku can have?
That problem is still in a 9x9 grid, and has been solved but it up at the limit of what we can do. It took a whole bunch of clever maths, and about a million CPU hours.
> 7.1 million core-hours of processing time on a machine with 640 Intel Xeon hex-core processors. They started in January 2011 and finished in December.
Though the paper at https://arxiv.org/abs/1201.0749 says Sudoku solving is "only" NP-complete, so it's not really an example of "harder than NP-Complete".
Thanks for the reference, and I’d misremembered the amount of CPU required.
However, I will say that while solving sudoku is np-complete, this “finding minimal” problem is harder than np-complete — it is common to have situations where solving a problem is np-complete, but then asking what is the biggest/hardest/smallest/etc problem is harder than np-complete.
I'm not criticizing. I think less than an order of magnitude from an off-the-head memory is just fine. And after 10 years, computers have gotten more powerful. ;)
I misread the paper. I think is saying that finding the minimal size is NP-complete. Here's the abstract:
"The hitting set problem is computationally hard; it is one of Karp’s 21 classic NP-complete problems. A standard backtracking algorithm for finding hitting sets would not be fast enough to search for a 16-clue sudoku puzzle exhaustively, even at today’s supercomputer speeds."
"It has been known since Karp’s seminal 1972 paper [42] that the problem of determining whether a given set family has a hitting set of size no greater than some k is NP-complete.
That is an interesting contrast. I don't know the smallest number of clues a kakuro puzzle can have, but I made easier ones with many clues, and harder ones, that also have many clues, generously fitting the heart shape, but I'd only be willing to spend tens of CPU hours on optimizing it.
Solving Sudoku (for general sized grids) is np-complete, but usually fairly easy. Many people write quite good sudoku solvers that can solve any 9x9 in a few milliseconds.
Now, a valid sudoku is a grid which has one unique answer. What’s the smallest number of clues a valid sudoku can have?
That problem is still in a 9x9 grid, and has been solved but it up at the limit of what we can do. It took a whole bunch of clever maths, and about a million CPU hours.