There is no way to define 'solvability' of a sentence with cloze blanks by the number of gaps. What makes a gap solvable is the ability of the speaker to determine what is missing from context. And there is no algorithmic way to define that with absolute precision (in fact, even humans are not all that good at it). Nouns happen to be pretty much the worst possible part of speech to pick at random because they are a very open largely context independent class. So even a simple sentence with a single blank like:
Jane ate some ____ for dinner.
is unsolvable. There are just too many possible things for Jane to eat. Even with the verb as a blank:
Jane ____ some chicken for dinner.
you have at more options than it may appear: ate, had, cooked, made, bought, etc.
Perhaps the only parts of speech you could do this with with some success are prepositions but even here, you couldn't guarantee 100% accuracy. Consider the blank in '_ the sea'
a. Fish live in the sea.
b. The Johnsons live by the sea.
Basically, your best bet would be to look at quite stable collocations, if you're relying on an algorithm.
The prisoners lived on bread and _____.
The men and _____ of the jury reached a verdict.
You could generate your own list of collocations or use an existing one (e.g. http://www.collocates.info or Google n-grams).
You could then run a sentence through a prediction tree and every time you'd come with a high enough number of predictability, you could delete the word. I have no idea how accurate this would be but I suspect that you would have to set a high threshold to get much accuracy and this would result in most sentences not having blanks.
Things would be much easier if each blank had a multiple choice. Then you could look for semantically and collocationally distant words. Google n-grams and WordNet and FrameNet would come in handy, here. Like:
Fred ate some ____ for dinner.
If the blank was chicken, you could use WordNet to determine that chicken is a type of animal and food and pick distractors that would not collide. E.g. chair, sky, road. Of course, you could still get stuff like 'water' which would be more difficult. Or, you could use FrameNet to determine the frame of 'eat' and only offer things that don't fit the frame. The problem is that you could only do this with quite simple sentences depending on your ability to parse them. And you would still get collisions:
Fred had to eat his words/crow.
We recently tried to do something similar for a project but the best we could do was suggest alternatives to a human adjudicator. But we did not have much time and it wasn't central to our efforts.
Ultimately, you're looking at a problem unsolvable with current NLP techniques, if your aim is to generate meaningful exercises for language learners that would always provide a unique correct answer without human intervention.
Update 1 (Response to updated question)
You have much more leeway if you're presenting users with complete texts rather than sentences because they can build up more of a context to enable them to guess.
However, even then you're still essentially playing a lottery if you just randomly eliminate nouns (or any any other words). In the right context, you could remove all the nouns and most of the pronouns and still have a near 100% hit rate.
John asked Mary to marry him.
But ______ told him _ wouldn't marry _ if ___ was the last _____ on _____.
In the case, above you can even remove proper nouns because of the repetition. However, in other cases you could not remove even a single noun to have a unique completion.
They asked us what car our friends the Smiths should buy.
We said that ________ had recommended to us that we should buy __________.
In general, you are more likely to have luck with repetition but even that is not foolproof.
Should I get a horse or a canoe?
Get a _____.
In general, you're better off deleting nouns from the focus rather than topic part of a sentence but these may not be easy to identify automatically.
The only way to find the answer to your question is experiment with a large number of texts and see which algorithm gets you closer to where you need to get.
It also depends on how high stakes the cloze activity is. If it's for a puzzle or a game, that's fine. If it's for reinforcing language learning, you might get somewhere close. But ff it's for an exam, you will not get anywhere near with the current state of NLP.
Update 2 (Quick literature survey):
If you do a quick search on "automatic cloze generation", you will find a number of articles describing several promising approaches. However, they focus on the combination of the three following tasks:
- Focus on finding appropriate distractors (http://aclweb.org/anthology/R/R13/R13-1067.pdf)
- Identifying appropriate sentences with promising keywords (http://aclweb.org/anthology/R/R13/R13-1067.pdf)
- Present an educator with options to choose from when constructing exercises (http://nlp.cs.rpi.edu/paper/learning.pdf)
Both of these are consonant with what I suggested above.
