Contrast this with the TDD approach: http://ravimohan.blogspot.com/2007/04/learning-from-sudoku-s...
Solving Every Sudoku Puzzle (2006)
11–20 of 101 posts
Re: Solving Every Sudoku Puzzle (2006)
#12I love it how with the Z3Py solver you just write down a few constraints (rows, columns, 3x3 boxes and the given values) and you immediately get an answer. [0] https://ericpony.github.io/z3py-tutorial/guide-examples.htm [1] https://yurichev.com/writings/SAT_SMT_by_example.pdf
Raymond Hettinger has a great video introduction to SAT solvers in python [47m]
Re: Solving Every Sudoku Puzzle (2006)
#13Sudoku solvers are near and dear to my heart. They’re my go to problem when learning a new programming language because they’re just complex enough to exercise a whole bunch of different language features. I built this when I wanted to learn Swift and dip my toe into machine learning: https://twitter.com/braddwyer/status/910030265006923776?s=21
That’s a really great way to learn a new language. Maybe take a Swift 101 course and then drag through a sudoku solver. Very cool!
Re: Solving Every Sudoku Puzzle (2006)
#14On a related note, Knuth has a cool algorithm to solve exact coverage problems like sudoku (similar logic as Norvig's DFS but implemented very differently). It's more work to code it than Norvig's but worth it for the education:) (and it solves faster)
Here's the paper describing the algorithm: https://arxiv.org/pdf/cs/0011047.pdf
Re: Solving Every Sudoku Puzzle (2006)
#15> I can copy values with values.copy() which is simple and efficient. If I implemented a possibility as a Python set or list I would need to use copy.deepcopy(values), which is less efficient.
The array deepcopy isn't too bad, at least when writing code, it compressed into a neat slice [:]
I wrote a hinter[2] which was more fun than the actual solver too, because it shows the "minimum remaining values" as a colour coded chart.
Re: Solving Every Sudoku Puzzle (2006)
#16Sudoku solvers are near and dear to my heart. They’re my go to problem when learning a new programming language because they’re just complex enough to exercise a whole bunch of different language features. I built this when I wanted to learn Swift and dip my toe into machine learning: https://twitter.com/braddwyer/status/910030265006923776?s=21
I do the same thing! The first program I ever wrote was a very simple sudoku solver on a TI-84 calculator (it performed the constraint propagation logic that Norvig describes), and for every programming language I have learned since I have re-written that code.
Re: Solving Every Sudoku Puzzle (2006)
#17Wrote a solver using basically the same idea back in college. Was kind of fun. Probably some stupid things in there that I would do differently now with more experience. https://github.com/war1025/sudoku-solver/blob/master/Sudoku/...
Same. Didn't save the code; wish I had just so I could see if I got a better execution time than his 1439 second example. Amusingly, my rationale was much like the author's; I freakin' hate Sudoku. So the fact it's such an obvious candidate to have an automated solver for meant I wrote one (it was also an excuse to do something more meaningful than the intro to CS exercises that class had me doing).
I left my solver running for 28 minutes and it never found a solution to that puzzle. Guess whatever corner case it's hitting in his program is the same as my program runs into.
Re: Solving Every Sudoku Puzzle (2006)
#18On a related note, Knuth has a cool algorithm to solve exact coverage problems like sudoku (similar logic as Norvig's DFS but implemented very differently). It's more work to code it than Norvig's but worth it for the education:) (and it solves faster) Here's the paper describing the algorithm: https://arxiv.org/pdf/cs/0011047.pdf
While dancing links is cool, when benchmarking it turns out using bits to represent values, and just copying, ends up being faster. This is because on modern CPUs about the worst thing you can do is lots of pointer following.
Re: Solving Every Sudoku Puzzle (2006)
#19On a related note, Knuth has a cool algorithm to solve exact coverage problems like sudoku (similar logic as Norvig's DFS but implemented very differently). It's more work to code it than Norvig's but worth it for the education:) (and it solves faster) Here's the paper describing the algorithm: https://arxiv.org/pdf/cs/0011047.pdf
While dancing links is cool, when benchmarking it turns out using bits to represent values, and just copying, ends up being faster. This is because on modern CPUs about the worst thing you can do is lots of pointer following.
I wrote a (straightforward) dancing links implementation that solves 17.000 puzzles/sec/core. It also validates uniqueness of the found solution.
How much faster does it get? I'm genuinely curious
Re: Solving Every Sudoku Puzzle (2006)
#20> 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.
That's hilarious! But what puzzles, or even activities wouldn't be classified by Ben as a DOS on humans?