There's no shortage of people ragging on the code. "It's not C++ enough to be called C++," "there's not enough comments", "it uses C stdio.h", etc. Get over it.
This looks like the sort of program I might dash out over an afternoon (maybe two) to satisfy some intellectual curiosity. Programming as play. This isn't production code, it's fun code, written to satisfy oneself.
Is it perfect? WHO CARES! That's not important. That misses the point. If you doodle in your notepad and it brings you a smile, does anyone care it's not as good as the Mona Lisa? You sure as heck don't. And that's what this code is. A doodle. It just happens to be in simple, straightforward procedural C/C++ code.
I personally think playing with programming is important. Sure, you'll write a lot of dreck. But, you'll also learn a lot. You learn real lessons when you do write dodgy code, and the dodgy code actually bites you. You also can try new things fearlessly. After all, you're programming a toy for oneself, and you're under no deadline pressure. There's no spec you have to fulfill. You can experiment and enjoy it.
Programming as play still helps build your programming reflexes. If and when you do sit down to write professional grade software, all of that play will make the basic work of programming natural. Rather than focusing your energy on the basic details of programming, you can instead focus your energy designing maintainable code that meets the business requirements and documenting that design. Writing the code just flows naturally.
So, yeah, I'm impressed. This Sudoku solver brought a smile to my face. It's incredibly cool that the prime minister shared a code doodle with us.