"Perhaps it was written by him in his spare time". OF COURSE it was written in his spare time. His a prime minister, he doesn't write code on the job. What comments do you want? The code is simple and obvious. What data structures to explain? If you are too stupid to understand them immediately, then you shouldn't be programming. What lack of error checking? What scenario do you suggest where error checking would help?
Easy. What does (x & -x) compute, off the top of your head?
There's so much bit-twiddling there that it's confusing and does boggle the mind. It's clever, yes, but guess what? Clever sucks. It's the code you get from prima donnas who don't expect to maintain it. Heck, someone posted a link to bit twiddling hacks on a Stanford server - it's a lot of elaborate code that's non-obvious (and even that hack isn't actually in the list, interestingly).
And yes, error checking. Sure it's a simple app that doesn't need error checking, but it's useful to have common error checks put in - I mean an 80 char buffer for a 9 char string is not an error prevention. Using scanf() with a field width specifier is dangerous - you might as well just use gets() and be done with it - you get the same result. And we know WHY you don't use gets().
You seem extraordinarily proud that he might code something up like this. Perhaps. All I say is that perhaps it isn't 100% original code, he didn't sit down one day and say "I can't solve this Sudoku, so I'll write my own solver" and crank that out. It almost seems like someone provided basically everything and his "contribution" is he typed it in.
There are enough fancy tricks in there coupled with a lot of interesting issues that I would call it as perhaps a bit more effort than what Obama did, but not by much.
And comments? Yeah, they're important, especially assuming it was done in his spare time. I mean, if he's doing it on and off, I expect him to forget. Anyone who maintains software knows after a month, the code you wrote might as well be written by someone else.