You've already got a start on it. They're called dogs. They can and do breed true with wolves, so they aren't far off.
Differences & Similarities in Wild Canids vs. Dogs
First and foremost, let's address one of the coolest things about the genes of wolves and dogs which may help somewhat.
Gene plasticity aka phenotypic plasticity. Gene plasticity basically means is that their genes respond fairly quickly to the environment. And that means it can be easier (compared to other species) to breed for specific characteristics. And further, because of this gene plasticity, dogs developed something that separates them from wolves, something else called excitatory synaptic plasticity. This means that dogs are better, not necessarily at problem solving, but with better memory than wolves:
Here, we demonstrate that genes involved in glutamate metabolism,
which account partially for fear response, indeed show the greatest
population differentiation by whole-genome comparison of dogs and
wolves. However, the changing direction of their expression supports a
role in increasing excitatory synaptic plasticity in dogs rather than
reducing fear response. Because synaptic plasticity are widely
believed to be cellular correlates of learning and memory, this change
may alter the learning and memory abilities of ancient scavenging
wolves, weaken the fear reaction toward humans, and prompt the initial
interspecific contact.
Getting to dogs from wolves actually took way less time than we previously thought. The Russian Fox experiment selected for tameness and responsiveness to humans, and that only took 25 years. These foxes began getting spots on their coats, floppy ears and a much wider variation in color than the foxes they started with.
Wolves aren't necessarily less smart than dogs, they're just way less interested in getting human approval. Dogs' dependance on humans, actually make them less smart than, say a dingo, when given a problem to solve WITHOUT a social component. An intermix of dogs and wild canids such as wolves and dingos might serve you well at the start of the program, just to breed out a little of the dependence.
Types of tests
But the kinds of tests you are talking about, dogs tend to pass more than wolves at least (but not more than dingos!) They are more capable of learning than wolves are because according to brain mapping, dogs are better at recalling things and people in general. There's one lab at Duke University testing the way dogs think. To test them they take dogs through a series of tests that you might take children through to learn how smart they are.
Run a breeding group through those sorts of tests, then select for the smartest. Keep testing and selecting over several generations. The ones that don't pass, move them on.
Math for Dogs, Beginning level
Dogs CAN do simple math:
In the canine version of this test the dog was shown a single large treat and a low screen was put in front of it. Then the dog watched as the experimenter obviously placed another treat behind the screen. If the dog can do the math he knows that 1 + 1 = 2 and he should expect that when the screen was raised there should be two dog treats. However, just like in the case of the babies, sometimes the experimenters surreptitiously removed the second treat so that when the screen was raised the dog saw only one. As in the case of the babies, the dogs stared at this unexpected outcome for a longer time than they did when the arithmetic came out correctly, apparently "surprised" at what they saw. Similarly, if an extra treat was secretly added so that the dogs saw three instead of the expected two, the dogs appear to be equally surprised. This suggests that dogs can not only count, but can also do simple addition and subtraction. SOURCE
So you would look for surprise, as you see in infants as one of the "first step" tests, and gradually ramp things up as you go.
Short term Memory & Dogs and Test that's been used in the past
As to short term memory, dogs, like most animals are terrible at it but they are actually surprisingly better than chimps.
They are better at long term memory, and frankly if it doesn't have to do directly with survival or food, there's really not a reason to. They chose untrained animals for this who had not seen the test before.
Dogs forget an event within two minutes. Chimpanzees, at around 20 seconds, are worse than rats at remembering things, while the memory spans of three other primates—baboons, pig-tailed macaques, and squirrel monkeys—exceeded only bees (the sole study participant that wasn't either a mammal or a bird). [SOURCE see link above]
It turns out that chimps, our closest relatives are actually WORSE than dogs at this particular test. Here's the test they used:
In this test, an animal is typically shown a visual stimulus such as a red circle. The red circle disappears, then, after a delay, it's shown again with another sample stimulus—a blue square, say. The animal, usually with the incentive of a food reward, has to select the original sample it saw.
So start selecting/breeding for this trait. Dogs do have a head start vs. other animals.
Spatial Recognition
As to spatial recognition--there are lots of dog breeds that are already very, very good at this. Herding breeds especially so compared to others. You might be talking about something specific, like object permanence, but you can look at for something specific and search for that as far as children's cognitive tests (toddlers and babies to start). Generally there's a dog version out there.
Selecting for Language Understanding & Analytical abilities
Dogs do understand a lot of language, and if you want to select for that, chose dogs to breed who have a large vocabulary. Rico the dog not only understood 200 words, he also USED logic. If you told him to fetch something and you used a word he had not learned, he would fetch the new and unfamiliar thing in a massive pile of toys. That shows analytical thinking, or enough intelligence to be able to infer. Which is amazing! Other dogs, generally border collies have learned up to 1,000 different words.
How to search for your tests
You can use the examples above, but we have plenty of tests geared for people who can't talk (babies and toddlers) as well as animals in the annals of scientific intelligence test, which test the very things you are talking about. Research those and apply them for first steps. Then look at cognitive tests at a higher level, and so on and so on.
Bottom line, there are plenty of intelligence tests you can give that in no way involve talking. There's a whole world out there of animal intelligence tests and tests for babies and toddlers.
