Algorithmic programming, sure, but to get to that point you need to cover the basics and then, most of the time, I think you could have the same educational experience focusing on the problem and math to solve it.
Couldn't you just teach algorithms to children with some high level language that handles most of the advanced mathematics in abstract ways that they would understand? And actually, if you've ever taken a computer science course, most teachers will show you how to break abstract, every day tasks into simple routines and how this thinking applies to computers and programming in general. You actually learn about algorithms first and then step into how these routines are resolved mathematically. You could theoretically teach children bubble sort by setting up some kind of abstract system (i.e. blocks with numbers written on them) with set constraints that would force them to algorithmically sort the blocks with the same routines a computer would use.
This actually coincides with what you said about how games like checkers and DnD can teach kids problem solving skills because it IS a form of game. Of course forcing a kid to organize blocks "bit by bit" wouldn't go over so well; even as a programmer myself, organizing blocks doesn't sound like much fun. But there are plenty ways to spice up bland routines with satisfying visuals. Just think of how many people spend hours and hours grinding in MMOs just to fill up a percentage bar and call it "fun".
Programming is ubiquitous enough to where there is an undeniable advantage to at least knowing about it. There's no reason why we shouldn't at least give students the opportunity to appreciate the subject. Think of the look on a kid's face when they learn that the game they were playing is actually completely beatable with a five line script.
Kleeneness is next to Godelness.