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