In terms of “computational complexity” we mean the following:
Consider the following generalization of Sudoku.
There is a number, N, and a grid of squares with N2 squares per side. (So the grid in total has N4 squares.)
Each row and column of the grid has N2 squares. The grid therefore contains an N2 number of NxN subgrids (this corresponds to the 3x3 boxes in regular sudoku, called Houses).
The puzzle is to fill each row, column, and house with the numbers from 1 to N2 with no duplicates.
The complexity is then a measure of how much harder the puzzles get when N is increased. Sudoku is a classic example of a so-called “NP-Hard” problem. Most puzzles that people think of as difficult are NP-hard. The ELI5 is that given a claimed solution to a sudoku puzzle, you can check if it really is the solution quickly (where again “quickly” is in terms of N). This is not true for the hardest types of puzzles in the witness.
This is only a proxy for how difficult humans will find the smaller puzzles but it’s remarkably accurate. The hardest puzzles using every mechanic from the witness (realistically, only using two of them including the last one) are going to be much harder for a human than the hardest sudokus.
Doesn’t that depend on the sudoku though?
Or do you mean that there were puzzles that were harder to solve than even the hardest sudokus in the world?
In terms of “computational complexity” we mean the following:
The complexity is then a measure of how much harder the puzzles get when N is increased. Sudoku is a classic example of a so-called “NP-Hard” problem. Most puzzles that people think of as difficult are NP-hard. The ELI5 is that given a claimed solution to a sudoku puzzle, you can check if it really is the solution quickly (where again “quickly” is in terms of N). This is not true for the hardest types of puzzles in the witness.
This is only a proxy for how difficult humans will find the smaller puzzles but it’s remarkably accurate. The hardest puzzles using every mechanic from the witness (realistically, only using two of them including the last one) are going to be much harder for a human than the hardest sudokus.