Background on the Wheel of Fortune, for those unfamiliar with it: in a Wheel of Fortune game, players initially see a set of blanks, representing words with letters hidden. (So players know the length of each word, but not what letters the words contain.) As the game progresses, players guess letters; if the phrase contains that letter, all the locations of that letter in the phrase are revealed. For example, a game (with the hidden phrase "stack overflow") would initially be represented as ????? ????????, and after the letter "o" is guessed, the game would display ????? o?????ow.
For simplicity, let's suppose our games contain only a single hidden word. What data structure would I use to hold all the possible candidates for that word? (I'm playing around with an AI that picks what letter to guess next, so in order to make the choice, I want to be able to calculate statistics like the most common letter out of the remaining candidates.) To be clear, initially I know that my word contains N letters, and then I learn the positions of various letters in the word, as well as what letters the word does not contain.
There's a similar question at Good algorithm and data structure for looking up words with missing letters?, but I think this question is slightly different in that I have more than two blanks, and I'm also iteratively pruning my candidate list (whereas that question seems to only use a single search). My current idea is to just maintain a candidate list of words, initialized to all English words (there should be at most 300k-500k words), and then (taking a similar approach to that question) to use a Regex to iteratively prune this candidate list as I guess more letters, but I'm curious if there's a better data structure or algorithm.
