The perverse hangman problem

Posted by Shalmanese on Stack Overflow See other posts from Stack Overflow or by Shalmanese
Published on 2009-12-07T10:49:10Z Indexed on 2012/09/18 3:38 UTC
Read the original article Hit count: 133

Filed under:

Perverse Hangman is a game played much like regular Hangman with one important difference: The winning word is determined dynamically by the house depending on what letters have been guessed.

For example, say you have the board _ A I L and 12 remaining guesses. Because there are 13 different words ending in AIL (bail, fail, hail, jail, kail, mail, nail, pail, rail, sail, tail, vail, wail) the house is guaranteed to win because no matter what 12 letters you guess, the house will claim the chosen word was the one you didn't guess. However, if the board was _ I L M, you have cornered the house as FILM is the only word that ends in ILM.

The challenge is: Given a dictionary, a word length & the number of allowed guesses, come up with an algorithm that either:

a) proves that the player always wins by outputting a decision tree for the player that corners the house no matter what

b) proves the house always wins by outputting a decision tree for the house that allows the house to escape no matter what.

As a toy example, consider the dictionary:

bat
bar
car

If you are allowed 3 wrong guesses, the player wins with the following tree:

Guess B
NO -> Guess C, Guess A, Guess R, WIN
YES-> Guess T
      NO -> Guess A, Guess R, WIN
      YES-> Guess A, WIN

© Stack Overflow or respective owner

Related posts about algorithm