Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Solving Every Sudoku Puzzle (2006)

norvig.com

Post reply on HN
Print view View original

21–29 of 29 posts

Re: Solving Every Sudoku Puzzle (2006)

#21

Post by fragmede »

DannyB2 wrote: post #19
johnfn wrote: post #3

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 t…

It was a denial of service attack, not in the sense of soaking up my brain cells solving puzzles, but in causing me to devise and program my own solver. (In Java, text console only.) Once I wrote a solver, I felt as if I had solved all puzzles. Then I got interested in devising puzzles with multiple solutions. Not too difficult. But making a few puzzles with two solutions was fun. Experiment_203( " 1 . . | 2 . 8 | .…

In that case, I have important news to tell you about! OpenAI has come out with am AI web browser! What is an AI web browser good for? I don't really know, but what you _can_ do, is log into hacker news with it, point it at your hacker news comment history, tell it to look at /newcomments page for stuff you'd want to comment on, and it'll shitpost for you!

What a wonderful time saver! Now you can get back to the important work of doing the dishes and folding laundry, and don't feel the need to personally participate in the denial of service attack on human intellect going on here.

Re: Solving Every Sudoku Puzzle (2006)

#22

Post by mzl »

senfiaj wrote: post #18
mzl wrote: post #11

Earlier quoted context omitted.

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 f…

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 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 sta…

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...

I should probably do some benchmarks on that with the standard MiniZinc solvers.

Re: Solving Every Sudoku Puzzle (2006)

#23

Post by mzl »

senfiaj wrote: post #18
mzl wrote: post #11

Earlier quoted context omitted.

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 f…

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 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 sta…

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.

Re: Solving Every Sudoku Puzzle (2006)

#24

Post by estimator7292 »

DannyB2 wrote: post #19
johnfn wrote: post #3

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 t…

It was a denial of service attack, not in the sense of soaking up my brain cells solving puzzles, but in causing me to devise and program my own solver. (In Java, text console only.) Once I wrote a solver, I felt as if I had solved all puzzles. Then I got interested in devising puzzles with multiple solutions. Not too difficult. But making a few puzzles with two solutions was fun. Experiment_203( " 1 . . | 2 . 8 | .…

Writing a sudoku solver/generator immediately and completely cured me of my crippling Sudoku addiction. I've been playing sudoku since I was probably 13, but after writing a solver I just can't muster up any interest to finish solving a puzzle. Not in a "my program could do this for me" sense, but more along the lines of "I've solved this and every other problem, now it's boring"

Re: Solving Every Sudoku Puzzle (2006)

#25

Post by senfiaj »

mzl wrote: post #23
senfiaj wrote: post #18

Earlier quoted context omitted.

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 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 sta…

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.

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 =).

Re: Solving Every Sudoku Puzzle (2006)

#26

Post by mzl »

senfiaj wrote: post #25
mzl wrote: post #23

Earlier quoted context omitted.

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.

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 jus…

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.

Re: Solving Every Sudoku Puzzle (2006)

#27

Post by senfiaj »

mzl wrote: post #26
senfiaj wrote: post #25

Earlier quoted context omitted.

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 jus…

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.

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.h... .

Re: Solving Every Sudoku Puzzle (2006)

#28

Post by mzl »

senfiaj wrote: post #27
mzl wrote: post #26

Earlier quoted context omitted.

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.

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.h... .

According to MDN it is expected to be an actual comparator: 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#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.

Re: Solving Every Sudoku Puzzle (2006)

#29

Post by senfiaj »

mzl wrote: post #28
senfiaj wrote: post #27

Earlier quoted context omitted.

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.h... .

According to MDN it is expected to be an actual comparator: 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#s... Further along, it is specified that only if the sort order is correct, are you guaranteed to get a permutation o…

Thanks. I changed to a proper shuffling. Although there was nothing catastrophic in JS (like corruption, duplication / loss of elements), just more biased randomness and slower execution time (not critical for generation). But yeah, it was worth it for fair randomness.
Post reply on HN