Puzzler - part 1

I don't much like Sudoku. Only if I'm really bored on the train to work do I do the ones in the paper. When they first became popular, rather than actually doing the puzzles, I wrote a Sudoku solver. It's surprisingly easy to get the solution if you give up on brain power and just use brute force.

You try putting a 1 in the first empty square and see if you've broken the rules about where the numbers are allowed. If you have, try a 2, and so on. At some point you find a number that's allowed, but it still may not be correct. The brute force part is that you just assume that it's right, and carry on looking for a solution. If you find one, your guess was good, and if you don't, just try another number.

When I say "carry on looking for a solution", what does that mean? The thing to notice is that a Sudoku puzzle with one more number filled in is just another Sudoku puzzle. So when we've guessed a number, the approach is the same as before: guess a number in the first empty square. We can solve the puzzle recursively. Eventually we may get to a grid where no number will fit in the first square. Oops. Somewhere in our chain of guesses we went wrong. No problem: just back up and guess again.

At the time I did this, I worked with someone who was very keen on Sudoku. He would do the most difficult puzzle in the newspaper, working hard at it, applying logic and deduction, painstakingly filling in one number after several minutes thought. I showed him what I'd done, and it offended his sense of rightness. How could something so challenging be solved by such a brain-dead method? He had a go at writing a solver, not with recursive guessing, but using intelligent deduction. It never worked. To be fair, he probably wasn't as obsessive about such things as I am, and I think that people have done it his way.

So that was the end of that, except that I found a web page for the shortest Sudoku solver, and tried compressing my code. I didn't get it as as short as the Python version, but pretty small. I'd solved an apparently difficult puzzle by writing code, and I forgot about it for a few years...

...until part 2 of the story

---

Edit: couldn't find this earlier:

class S{boolean t(String g){int p=g.indexOf('0');if(-1==p){System.out.println(g
);return true;}for(char c='1';c<='9';c++){String n=m(g,c,p);if(null!=n&&t(n))
return true;}return false;}String m(String o,char c,int p){int r=p/9,k=p%9,b=r/
3*3+(k/3);for(int i=0;i<9;i++)if(o.charAt(i+r*9)==c||o.charAt(i*9+k)==c||o.
charAt(b*9+i+(i/3-b%3)*6)==c)return null;return o.replaceFirst("0",""+c);}
public static void main(String[]a){new S().t(a[0]);}}

Could probably be shorter (perhaps by inlining m), but I can't be bothered to think about it much. You need to give it an 81-digit string where zero represents an empty square.