4 ms·

That is an interesting post. However, a much more interesting challenge is solving larger Sudoku puzzles, as 9x9 is (as evidenced in the pos) a trivial problem

by mzl 11mo ago

That is an interesting post. However, a much more interesting challenge is solving larger Sudoku puzzles, as 9x9 is (as evidenced in the pos) a trivial problem to solve. 16x16 starts to get somewhat interesting, but at 25x25 it gets really interesting. Most solvers are trivially extensible to larger sizes, making it quite easy to benchmark. 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.

senfiaj 11mo ago
Some time ago I wrote a 9x9 Killer Sudoku solver (you can solve ordinary as well, the cages are optional) in JavaScript https://github.com/surenenfiajyan/killer-sudoku-solver https://github.com/surenenfiajyan/killer-sudoku-solver 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.
- mzl 11mo ago
  You will most likely need both smarter heuristics and better deductions for larger instances. As mentioned, I've seen well-engineered custom tight C++-solvers with decent heuristics and the normal deductions take >1 hour on some instances. Most cases I've tried can be solved reasonably quickly when using OR-Tools CP-SAT which uses constraint programming style lazy clause generation to a SAT solver and custom MIP relaxations in a portfolio. For a list of interesting instances to test, see this file: https://github.com/Gecode/gecode/blob/release/6.3.0/examples/sudoku-instances.hh https://github.com/Gecode/gecode/blob/release/6.3.0/examples... I should probably do some benchmarks on that with the standard MiniZinc solvers.
- mzl 11mo ago
  Btw, note that the line 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.
  - senfiaj 11mo ago
    This is just for generation of sudoku image. The actual solver doesn't do this this expensive operation (the sudoku generator just reuses the solver function to fill with random numbers). From my experience for just generation it works good enough and fast enough. Yes I know how to efficiently shuffle by swaps in O(n) time with the correct distribution of probabilities (I didn't know that algorithm name BTW), I'm just too lazy =).
    - mzl 11mo ago
      While Fisher-Yates or similar algorithms are more efficient, the real reason I wanted to mention it is that in many systems the sorting algorithm might crash or corrupt memory when used with a randomized comparison operator. It is inherently unsafe.
      - senfiaj 11mo ago
        In JavaScript it's OK. At that time I knew that it is not the most efficient solution (for generation O(n log n) shuffle is not critical), just wanted to do this with simple one liner. With C++ I would definitely use this https://en.cppreference.com/w/cpp/algorithm/random_shuffle.html https://en.cppreference.com/w/cpp/algorithm/random_shuffle.h... .
        mzl 11mo ago
        According to MDN it is expected to be an actual comparator: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#description:~:text=More%20formally%2C%20the%20comparator%20is%20expected%20to%20have%20the%20following%20properties https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... 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#sort-order 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.

by mzl 11mo ago

senfiaj 11mo ago

Some time ago I wrote a 9x9 Killer Sudoku solver (you can solve ordinary as well, the cages are optional) in JavaScript https://github.com/surenenfiajyan/killer-sudoku-solver https://github.com/surenenfiajyan/killer-sudoku-solver 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.

mzl 11mo ago
You will most likely need both smarter heuristics and better deductions for larger instances. As mentioned, I've seen well-engineered custom tight C++-solvers with decent heuristics and the normal deductions take >1 hour on some instances. Most cases I've tried can be solved reasonably quickly when using OR-Tools CP-SAT which uses constraint programming style lazy clause generation to a SAT solver and custom MIP relaxations in a portfolio. For a list of interesting instances to test, see this file: https://github.com/Gecode/gecode/blob/release/6.3.0/examples/sudoku-instances.hh https://github.com/Gecode/gecode/blob/release/6.3.0/examples... I should probably do some benchmarks on that with the standard MiniZinc solvers.
mzl 11mo ago
Btw, note that the line 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.
- senfiaj 11mo ago
  This is just for generation of sudoku image. The actual solver doesn't do this this expensive operation (the sudoku generator just reuses the solver function to fill with random numbers). From my experience for just generation it works good enough and fast enough. Yes I know how to efficiently shuffle by swaps in O(n) time with the correct distribution of probabilities (I didn't know that algorithm name BTW), I'm just too lazy =).
  - mzl 11mo ago
    While Fisher-Yates or similar algorithms are more efficient, the real reason I wanted to mention it is that in many systems the sorting algorithm might crash or corrupt memory when used with a randomized comparison operator. It is inherently unsafe.
    - senfiaj 11mo ago
      In JavaScript it's OK. At that time I knew that it is not the most efficient solution (for generation O(n log n) shuffle is not critical), just wanted to do this with simple one liner. With C++ I would definitely use this https://en.cppreference.com/w/cpp/algorithm/random_shuffle.html https://en.cppreference.com/w/cpp/algorithm/random_shuffle.h... .
      - mzl 11mo ago
        According to MDN it is expected to be an actual comparator: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#description:~:text=More%20formally%2C%20the%20comparator%20is%20expected%20to%20have%20the%20following%20properties https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... 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#sort-order 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.