It is indeed quite complicated. But if you handwavily estimate the results of all that complexity -- the probabilities of divisibility by various things -- then the estimate you get is the one cousin_it gave earlier, because the Prime Number Theorem is what you get when you estimate the density of prime numbers by treating divisibility-by-a-prime as a random event. (Which for many purposes works very well.)
There are 143 primes between 100 and 999. We can, therefore, make 2,924,207 3x3 different squares with 3 horizontal primes. 50,621 of them have all three vertical numbers prime. About 1.7%.
There are 1061 primes between 1000 and 9999. We can, therefore, make 1,267,247,769,841 4x4 different squares with 4 horizontal primes. 406,721,511 of them have all four vertical numbers prime. About 0.032%.
I strongly suspect that this goes to 0, quite rapidly.
How many Sudokus can you get with 9 digit primes horizontally and vertically?
Not a single one. Which is quite ob...
If it's worth saying, but not worth its own post, then it goes here.
Notes for future OT posters:
1. Please add the 'open_thread' tag.
2. Check if there is an active Open Thread before posting a new one. (Immediately before; refresh the list-of-threads page before posting.)
3. Open Threads should start on Monday, and end on Sunday.
4. Unflag the two options "Notify me of new top-level comments on this article" and "