I would agree with Sam. If you are looking for a natural solution, I am not aware of any. (I have had various breeds over the period of 50 years). There is a solution that I do not recommend - artificial turf. The kind used by some professional sports teams.
- You have some issues that you may not be able to control. Intelligence is a factor of the breed. A similar issue to your current one would be training your dogs to stay of certain furniture but allowed on others. Move the furniture and see if the dogs follow. Most dogs are trained all or nothing.
- Another issue is that certain breeds are natural diggers. And other breeds are natural followers. From your question, it appears that you have at least one natural digger.
- Most dogs if kept out side often outside but unsupervised,treat in the house as yours and the yard is ours.If they have not been specifically trained what to do outside, in their mind you are the invader and they are the boss (except when they are trained for specific things).
- dividing your yard will partially solve your situation, but only on your side.
- your dogs can be trained the way you want with a capable trainer and time.
The question you need to ask, is it worth paying a capable trainer (who might be expensive) and the time necessary to change their behavior.