My backyard has gone to the dogs too. If digging for the sake of digging makes them happy and tired, dig on lil doggies. My front yard is my pretty yard and no one sees the back anyway.

Glacier's suggestions are going to be the best and cheapest solutions. Kodie will learn that digging in the yard will only lead to poop and digging in a sand box will get him treats. Good luck.