3 ms·
"I think a Sudoku puzzle that is harder for humans would not be that much harder for optopus to solve, but I have not tested it." Try it. You may be surprised.
by jerf 17y ago
"I think a Sudoku puzzle that is harder for humans would not be that much harder for optopus to solve, but I have not tested it."
Try it. You may be surprised. Here's a good one: zonkedyak.blogspot.com/2006/11/worlds-hardest-sudoku-puzzle-al.html
Also try a 5-based instance of the same problem (against the standard 3-base of sudoku, that is, a 5x5 matrix of 5x5 matrices containing the numbers 1-25), and compare performance of that problem to a normal solver.
I'm not going to tell you what will happen, because you won't believe me. Somebody seems to have cast a glamor on GP.
- merraksh 17y agoThat is a nice instance, an optimization solver took 13 seconds to solve instead of the 0.2 seconds for the problem posted by the OP. Some people in combinatorial optimization are addressing the problem of finding the hardest Sudoku problem. For an introduction of how the problem can be modeled, see: http://diuflx71.unifr.ch/lpl/lplmodels/puzzles/sudoku.pdf http://diuflx71.unifr.ch/lpl/lplmodels/puzzles/sudoku.pdf
- daivd 17y agoOK, I will try it. And if you had said that it would be almost impossible, because there are too many local minima, I would have believed you. A serious try with GA would require abandoning Python for a faster fitness function in C, that does not copy dozens of lists back and forth. I estimate that just about anyone could make it more than 100 times as fast. The slow implementation will have to suffice for now. The interesting part is of course not the absolute times, but if the complexity scales differently. If a real Sudoku solver takes about 50 times as long to solve that problem, I will consider it a victory if the GA does the same.
- bryanh 17y agoAs a quick fix, check out Psyco. I've had success running algorithms in Python up to 6-8x faster.