4 ms·

Solving Every Sudoku Puzzle (2006)

73 points by djoldman 1y ago

boat-of-theseus 11mo ago
[dead]
- wat10000 11mo ago
  Then check out perhaps the worst sudoku solver, which works by translating the puzzle to a series of Python package requirements and then asking the package manager to resolve them: https://github.com/konstin/sudoku-in-python-packaging https://github.com/konstin/sudoku-in-python-packaging
  - fnands 11mo ago
    That's incredible and completely unhinged. I love it.
  - boat-of-theseus 11mo ago
    I will propose marriage to whoever wrote this: “you NP-complete me”
  - boat-of-theseus 11mo ago
    you know what the actual most interesting thint about this is for me? 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
- 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 =).
- anthk 11mo ago
  This guy under Common Lisp would shine.
johnfn 11mo ago
I've seen this article every now and then, and it's always fun to read. Something jumped out at me this time, though: > As computer security expert Ben Laurie has stated, Sudoku is "a denial of service attack on human intellect". Several people I know (including my wife) were infected by the virus, and I thought maybe this would demonstrate that they didn't need to spend any more time on Sudoku. Ah, yes... remember the halcyon days of 2006, when something as benign as Sudoku was considered to be a "denial of service attack on human intellect"?
- jader201 11mo ago
  > As computer security expert Ben Laurie has stated, Sudoku is "a denial of service attack on human intellect". […] I thought maybe this would demonstrate that [my wife doesn’t] need to spend any more time on Sudoku. The same could be said about every logic puzzle, or other types of puzzles. People don't do them so actually solve any sort of new problem, or achieve some sort of productivity. The same reason people don’t jog to get from point A to point B, or to learn how to get around more quickly. Logic puzzles are exercising parts of our brain that don’t get exercised regularly.
  - a2800276 11mo ago
    Feels like the "demonstrated it's no longer necessary to solve sudokus" statement may have been a joke :)
  - charlysisto 11mo ago
    Probably a joke... nevertheless I had the same reaction ! It exercises your deduction, binary thinking, also stochastic vs systematic methodology (first look around randomly find the most obvious before going number by number). Getting to discover all the tricks and reasoning in various "dimensions" is very satisfactory as well. But above all sudokuing puts you in a sort of meditative state : focusing your mind on this micro deductive world gets rid of all the noise and can be very relaxing between 2 pomodoros :)
  - anthk 11mo ago
    Most logic puzzles such as the software pack made from SGT (or under the paper puzzle booklets, same concept but with pens and paper) are trivially solvable with computers and often STEM people will get bored with them fast. Solve it once, solve it for all. If any, the challenge and fun would come by solving them with an algorithm under its favourite programming language. Also, lateral thinking based riddles/puzzles are often more fun to solve, such as the crime related ones.
lightbendover 11mo ago
[dead]
nlitsme 11mo ago
I was a bit disappointed that he did not in fact solve all billions/trillons of possible sudoku puzzles.
- madcaptenor 11mo ago
  You'd appreciate "Every 5x5 Nonogram": https://news.ycombinator.com/item?id=44140918 https://news.ycombinator.com/item?id=44140918

73 points by djoldman 1y ago

boat-of-theseus 11mo ago

[dead]

wat10000 11mo ago
Then check out perhaps the worst sudoku solver, which works by translating the puzzle to a series of Python package requirements and then asking the package manager to resolve them: https://github.com/konstin/sudoku-in-python-packaging https://github.com/konstin/sudoku-in-python-packaging
- fnands 11mo ago
  That's incredible and completely unhinged. I love it.
- boat-of-theseus 11mo ago
  I will propose marriage to whoever wrote this: “you NP-complete me”
- boat-of-theseus 11mo ago
  you know what the actual most interesting thint about this is for me? 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
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 =).
anthk 11mo ago
This guy under Common Lisp would shine.

johnfn 11mo ago

I've seen this article every now and then, and it's always fun to read. Something jumped out at me this time, though: > As computer security expert Ben Laurie has stated, Sudoku is "a denial of service attack on human intellect". Several people I know (including my wife) were infected by the virus, and I thought maybe this would demonstrate that they didn't need to spend any more time on Sudoku. Ah, yes... remember the halcyon days of 2006, when something as benign as Sudoku was considered to be a "denial of service attack on human intellect"?

jader201 11mo ago
> As computer security expert Ben Laurie has stated, Sudoku is "a denial of service attack on human intellect". […] I thought maybe this would demonstrate that [my wife doesn’t] need to spend any more time on Sudoku. The same could be said about every logic puzzle, or other types of puzzles. People don't do them so actually solve any sort of new problem, or achieve some sort of productivity. The same reason people don’t jog to get from point A to point B, or to learn how to get around more quickly. Logic puzzles are exercising parts of our brain that don’t get exercised regularly.
- a2800276 11mo ago
  Feels like the "demonstrated it's no longer necessary to solve sudokus" statement may have been a joke :)
- charlysisto 11mo ago
  Probably a joke... nevertheless I had the same reaction ! It exercises your deduction, binary thinking, also stochastic vs systematic methodology (first look around randomly find the most obvious before going number by number). Getting to discover all the tricks and reasoning in various "dimensions" is very satisfactory as well. But above all sudokuing puts you in a sort of meditative state : focusing your mind on this micro deductive world gets rid of all the noise and can be very relaxing between 2 pomodoros :)
- anthk 11mo ago
  Most logic puzzles such as the software pack made from SGT (or under the paper puzzle booklets, same concept but with pens and paper) are trivially solvable with computers and often STEM people will get bored with them fast. Solve it once, solve it for all. If any, the challenge and fun would come by solving them with an algorithm under its favourite programming language. Also, lateral thinking based riddles/puzzles are often more fun to solve, such as the crime related ones.

lightbendover 11mo ago

[dead]

nlitsme 11mo ago

I was a bit disappointed that he did not in fact solve all billions/trillons of possible sudoku puzzles.

madcaptenor 11mo ago
You'd appreciate "Every 5x5 Nonogram": https://news.ycombinator.com/item?id=44140918 https://news.ycombinator.com/item?id=44140918