this is the example that made me finally understand how to embed NO complete problems into other NP complete problems.
and this mofo wrote zero code yet tricked a programming language into doing work anyway
In my testing, 25x25 Sudokus are algorithmically challenging. Solving times for a naive but well-tuned algorithm with reasonable heuristics can easily be on the order of an hour for a single puzzle. A smart system with advanced reasoning can be many orders of magnitude faster.
It does backtracking with recursion. It uses bitwise operations for fast conflict detection in rows, columns and 3x3 blocks. But one very important heuristics is that it firstly sorts the cells in such a way that the backtracking brute force starts from the most densely filled side. This eliminates a lot of wrong branches early, and actually helps a lot. I'm thinking maybe I can extend this to 16x16 or 25x25 as well. Not sure if this will scale up adequately. But this one usually cracks puzzles in a fraction of second. It only become slow for extremely hard killer sudoku puzzles.
For a list of interesting instances to test, see this file: https://github.com/Gecode/gecode/blob/release/6.3.0/examples...
I should probably do some benchmarks on that with the standard MiniZinc solvers.
const randomNumbers = random ? [1, 2, 3, 4, 5, 6, 7, 8, 9].sort(() => Math.random() - 0.5).sort(() => Math.random() - 0.5) : null
does not really do what you seem to intend. Sort requires a comparison function that is stable, and there are a lot of things that could go wrong if this is not supplied.For shuffling, use a shuffle algorithm. Fisher-Yates is the common suggestion on what to use.
The specification says that if the comparator is not a consistent comparator, the sort order is implementation defined: https://tc39.es/ecma262/multipage/indexed-collections.html#s... Further along, it is specified that only if the sort order is correct, are you guaranteed to get a permutation of the input as the result. I would not write code expecting this to work.