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
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.
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"?
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.
Then I got to looking at difficult puzzles on the web. Apparently AI escargot is the world's most difficult. (And the site http://www.aisudoku.com/index_en.html says I can't publish the board). So I'll only publish the stats of applying my solver to it.
Solution #1. Found in 0 days 00:00:00.029.
3,906 boards examined so far.
1 total solutions found.
7,832 total boards examined.
Total time 0 days 00:00:00.085.
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"
12 comments
[ 117 ms ] story [ 327 ms ] threadIn 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.
> 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"?
Sounds like social media feeds these days
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(
// Solution #1. Found in 0 days 00:00:00.004.// 245 boards examined so far.
// Solution #2. Found in 0 days 00:00:00.001.// 287 boards examined so far.
Then I got to looking at difficult puzzles on the web. Apparently AI escargot is the world's most difficult. (And the site http://www.aisudoku.com/index_en.html says I can't publish the board). So I'll only publish the stats of applying my solver to it.