Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

5-Letter Mastermind

"Bookworm Adventures Volume 2" includes a mini-game called "Word Master" where you need to guess a five-letter word in five tries. The first letter is given to you. After each guess, you are told which letters are correct (with gold-colored tiles), and which letters are in the word but not in the correct position (with silver-colored tiles). If a letter appears multiple times, your guess is only annotated up to the number of letters present in the secret word. So if the secret word is STEEL and you guess EELLE, the first two E's would be colored silver, and the first L.

Your guess does not have to include previously-correct letters. However, you may only guess words which are in the dictionary.

Is it possible to always win this game? Or is there a first letter for which no winning strategy exists?

Another way to look at this problem is one of partitioning the words. You want a tree of "test" words such that, when the population is divided among the leaves of the test word (according to the gold and silver match indications), no word is at depth more than 4. (You need a 5th guess to actually answer the word.) For example, if you know the word starts with 'A' and your first guess is 'ALIEN', you partition the population into 49 subsets ranging in size from 1 to 142. Each of those sub-populations could be given a different test word to partition it further. Here's what 'ALIEN' looks like:

I used 'm' for exact match and 'p' for present elsewhere, rather than gold and silver.
[('mppp-', 2, ['AISLE', 'AIZLE']),
 ('m--mp', 11, ['ACNED', 'ACNES', 'ANGER', 'ANKER', 'ANNEX', ...]),
 ('mpmpp', 1, ['ANILE']),
 ('mmm--', 5, ['ALIAS', 'ALIBI', 'ALIFS', 'ALIST', 'ALIYA']),
 ('mp-p-', 14, ['ABELE', 'ADDLE', 'AKELA', 'AMBLE', 'AMOLE', ...]),
 ('mmmmm', 1, ['ALIEN']),
 ('m--mm', 5, ['ADMEN', 'ARPEN', 'ASHEN', 'ASPEN', 'AXMEN']),
 ('mmmpp', 1, ['ALINE']),
 ('mmm-m', 1, ['ALIGN']),
 ('mpp--', 9, ['AALII', 'ABOIL', 'AIOLI', 'ARGIL', 'ARMIL', ...]),
 ('m-p-p', 7, ['AINGA', 'AIRNS', 'AMNIA', 'AMNIC', 'AMNIO', ...]),
 ('m-pp-', 8, ['AECIA', 'AEGIS', 'AERIE', 'AESIR', 'AGGIE', ...]),
 ('mp--p', 4, ['ANGLO', 'ANLAS', 'ANNAL', 'ANNUL']),
 ('mm-pp', 2, ['ALANE', 'ALONE']),
 ('mm--p', 5, ['ALAND', 'ALANG', 'ALANS', 'ALANT', 'ALONG']),
 ('m-m-m', 5, ['ANION', 'APIAN', 'AVIAN', 'AVION', 'AXION']),
 ('m--p-', 73, ['ABASE', 'ABATE', 'ABEAM', 'ABEAR', 'ABETS', ...]),
 ('m-m--', 31, ['ACIDS', 'ACIDY', 'ADIOS', 'ADITS', 'AGIOS', ...]),
 ('mpm--', 6, ['AGILA', 'APIOL', 'ARILS', 'ATILT', 'AXIAL']),
 ('m-p-m', 7, ['ABRIN', 'ACTIN', 'ADMIN', 'AGAIN', 'AGRIN']),
 ('mpp-p', 1, ['ANVIL']),
 ('m----', 142, ['AARGH', 'ABACA', 'ABACK', 'ABACS', 'ABAFT', ...]),
 ('m---p', 35, ['ABAND', 'ABUNA', 'ADUNC', 'AGONS', 'AGONY', ...]),
 ('mp-m-', 14, ['ABLED', 'ABLER', 'ABLES', 'ABLET', 'AGLEE', ...]),
 ('m--m-', 61, ['AAHED', 'ABBED', 'ABBES', 'ABBEY', 'ABCEE', ...]),
 ('mp-pp', 5, ['ANCLE', 'ANELE', 'ANGLE', 'ANKLE', 'ANOLE']),
 ('mpmp-', 2, ['AGILE', 'AXILE']),
 ('mm-p-', 12, ['ALATE', 'ALECK', 'ALECS', 'ALEFS', 'ALEFT', ...]),
 ('m---m', 22, ['ABOON', 'ACORN', 'ACTON', 'ADHAN', 'ADMAN', ...]),
 ('mpmm-', 1, ['ARIEL']),
 ('mppm-', 1, ['AILED']),
 ('m-pmp', 1, ['AINEE']),
 ('mp--m', 1, ['AZLON']),
 ('mmp--', 3, ['ALCID', 'ALGID', 'ALLIS']),
 ('mmpp-', 1, ['ALKIE']),
 ('mmp-m', 2, ['ALGIN', 'ALOIN']),
 ('m-m-p', 16, ['ACING', 'ACINI', 'AGING', 'AHIND', 'AHING', ...]),
 ('mp-mp', 1, ['ANGEL']),
 ('m--pp', 22, ['ABUNE', 'AEONS', 'AGENE', 'AGENT', 'AGONE', ...]),
 ('m-pm-', 9, ['AIDED', 'AIDER', 'AIDES', 'AIMED', 'AIMER', ...]),
 ('m-mpp', 5, ['AMINE', 'ANIME', 'ANISE', 'AVINE', 'AZINE']),
 ('mmmp-', 2, ['ALIKE', 'ALIVE']),
 ('m-mp-', 10, ['ABIDE', 'AFIRE', 'AMICE', 'AMIDE', 'ARISE', ...]),
 ('mpm-p', 1, ['ANILS']),
 ('mm-m-', 11, ['ALBEE', 'ALDEA', 'ALDER', 'ALLEE', 'ALLEL', ...]),
 ('mp---', 33, ['ABLOW', 'ACOLD', 'ACYLS', 'ADULT', 'AFALD', ...]),
 ('m-mm-', 3, ['ABIES', 'ADIEU', 'AMIES']),
 ('mm---', 42, ['ALAAP', 'ALACK', 'ALAMO', 'ALAPA', 'ALAPS', ...]),
 ('m-p--', 58, ['AARTI', 'ABACI', 'ABRIM', 'ABRIS', 'ABSIT', ...])]


One possible way to answer is to brute-force the search space. However, with 12478 5-letter words (in SOWPODS, my typical word-reference source) this is rather expensive. Moreover, I would expect the answer to be that the game *is* always solveable, so we don't need to do exhaustive search to get the answer. So, I decided to implement a heuristic search.

At each node in the tree, we pick guesses at random from the word list and see how they partition the remaining words. After we've accumulated N such measurements, pick the one with the smallest maximum subset (the one that has the "least work remaining") and recursively search using that node.

With N=1000 this produces remarkably little backtracking. (N=100 didn't seem to work so well, but that was before I pseduo-randomized the order... probably it would work better if I actually randomized each level of the tree instead of just using a python set to provide a non-alphabetic order which is the same each time.) Here is the decision tree for words starting with 'A':


I didn't format this nicely, this is basically just my debug output reversed... 'RILES' is the first word, then at the specified # of guesses remaining find the line with the matching output.
success 4 [] RILES
success 3 ['RILES', '--p-m'] KOALA
success 2 ['RILES', '--p-m', 'KOALA', '--pm-'] YINCE
success 2 ['RILES', '--p-m', 'KOALA', '--ppp'] EMBOG
success 2 ['RILES', '--p-m', 'KOALA', '--mpp'] YINCE
success 2 ['RILES', '--p-m', 'KOALA', '-ppp-'] THOFT
success 3 ['RILES', '-----'] SNOUT
success 2 ['RILES', '-----', 'SNOUT', '-mp--'] WINCH
success 2 ['RILES', '-----', 'SNOUT', '-----'] SMOKY
success 1 ['RILES', '-----', 'SNOUT', '-----', 'SMOKY', '----m'] AGIST
success 1 ['RILES', '-----', 'SNOUT', '-----', 'SMOKY', '-p---'] AGIST
success 1 ['RILES', '-----', 'SNOUT', '-----', 'SMOKY', '----p'] RAUPO
success 1 ['RILES', '-----', 'SNOUT', '-----', 'SMOKY', '-----'] SHAYS
success 2 ['RILES', '-----', 'SNOUT', '-pm--'] WOODY
success 2 ['RILES', '-----', 'SNOUT', '---p-'] KAKAS
success 2 ['RILES', '-----', 'SNOUT', '--m-p'] SHLEP
success 2 ['RILES', '-----', 'SNOUT', '-p-p-'] DELAY
success 2 ['RILES', '-----', 'SNOUT', '--p--'] YINCE
success 2 ['RILES', '-----', 'SNOUT', '--m-m'] FYKED
success 2 ['RILES', '-----', 'SNOUT', '-p---'] ADMIX
success 2 ['RILES', '-----', 'SNOUT', '--m--'] DUOMO
success 2 ['RILES', '-----', 'SNOUT', '----m'] RAUPO
success 2 ['RILES', '-----', 'SNOUT', '----p'] SHAYS
success 3 ['RILES', '-pm--'] RAUPO
success 3 ['RILES', 'pp--m'] BRITH
success 2 ['RILES', 'pp--m', 'BRITH', '-mp--'] SHAYS
success 3 ['RILES', '-m-m-'] MANSE
success 3 ['RILES', '---p-'] TOADY
success 2 ['RILES', '---p-', 'TOADY', 'ppp--'] PANTO
success 2 ['RILES', '---p-', 'TOADY', '-pp--'] BONKS
success 1 ['RILES', '---p-', 'TOADY', '-pp--', 'BONKS', '-p---'] AGIST
success 1 ['RILES', '---p-', 'TOADY', '-pp--', 'BONKS', '-pp--'] AGIST
success 2 ['RILES', '---p-', 'TOADY', '--p--'] BONKS
success 1 ['RILES', '---p-', 'TOADY', '--p--', 'BONKS', '--p--'] AGIST
success 1 ['RILES', '---p-', 'TOADY', '--p--', 'BONKS', '-----'] RAUPO
success 1 ['RILES', '---p-', 'TOADY', '--p--', 'BONKS', 'p----'] DELAY
success 2 ['RILES', '---p-', 'TOADY', '-ppm-'] PANTO
success 2 ['RILES', '---p-', 'TOADY', '--m--'] GUMPS
success 1 ['RILES', '---p-', 'TOADY', '--m--', 'GUMPS', '-----'] FYKES
success 1 ['RILES', '---p-', 'TOADY', '--m--', 'GUMPS', 'p----'] ZOOID
success 2 ['RILES', '---p-', 'TOADY', '--p-p'] AGISM
success 2 ['RILES', '---p-', 'TOADY', '--pp-'] SHAYS
success 2 ['RILES', '---p-', 'TOADY', '-ppp-'] BORDS
success 2 ['RILES', '---p-', 'TOADY', 'p-m--'] AGISM
success 2 ['RILES', '---p-', 'TOADY', 'p-p--'] ENZYM
success 1 ['RILES', '---p-', 'TOADY', 'p-p--', 'ENZYM', 'pm---'] AGIST
success 1 ['RILES', '---p-', 'TOADY', 'p-p--', 'ENZYM', 'pp---'] AGIST
success 1 ['RILES', '---p-', 'TOADY', 'p-p--', 'ENZYM', 'p----'] RAUPO
success 3 ['RILES', '-m--m'] AGIST
success 3 ['RILES', '--p--'] KOALA
success 2 ['RILES', '--p--', 'KOALA', '-ppm-'] THOFT
success 2 ['RILES', '--p--', 'KOALA', '--pm-'] APART
success 2 ['RILES', '--p--', 'KOALA', '--ppp'] MINGY
success 2 ['RILES', '--p--', 'KOALA', '--mpp'] GRIND
success 2 ['RILES', '--p--', 'KOALA', 'p-pp-'] DELAY
success 2 ['RILES', '--p--', 'KOALA', '--pp-'] AGISM
success 1 ['RILES', '--p--', 'KOALA', '--pp-', 'AGISM', 'm----'] THOFT
success 1 ['RILES', '--p--', 'KOALA', '--pp-', 'AGISM', 'm---p'] RAUPO
success 2 ['RILES', '--p--', 'KOALA', '-ppp-'] FOUNT
success 3 ['RILES', '-m---'] AGIST
success 3 ['RILES', 'pp-p-'] DECAY
success 3 ['RILES', 'pp--p'] AGIST
success 3 ['RILES', '-p--p'] TOMIA
success 2 ['RILES', '-p--p', 'TOMIA', '--ppp'] AGIST
success 2 ['RILES', '-p--p', 'TOMIA', '---pp'] AGIST
success 2 ['RILES', '-p--p', 'TOMIA', '-p-pp'] AGIST
success 2 ['RILES', '-p--p', 'TOMIA', '---mp'] RAUPO
success 3 ['RILES', '--pp-'] PLANS
success 2 ['RILES', '--pp-', 'PLANS', 'ppp--'] SPEIR
success 2 ['RILES', '--pp-', 'PLANS', '-pp--'] MODGE
success 2 ['RILES', '--pp-', 'PLANS', '-mp--'] GESTE
success 2 ['RILES', '--pp-', 'PLANS', '-ppp-'] COGUE
success 1 ['RILES', '--pp-', 'PLANS', '-ppp-', 'COGUE', '----m'] ESTER
success 3 ['RILES', '--ppm'] FLISK
success 2 ['RILES', '--ppm', 'FLISK', '-m-p-'] YINCE
success 2 ['RILES', '--ppm', 'FLISK', '-p-p-'] EXULS
success 3 ['RILES', '-pp--'] BANAL
success 2 ['RILES', '-pp--', 'BANAL', '-p--m'] AGIST
success 2 ['RILES', '-pp--', 'BANAL', '-p-pp'] AGIST
success 2 ['RILES', '-pp--', 'BANAL', '-p--p'] AGIST
success 2 ['RILES', '-pp--', 'BANAL', '-pp-p'] AGIST
success 3 ['RILES', 'p--mp'] TSKED
success 3 ['RILES', '-p--m'] TOMIA
success 2 ['RILES', '-p--m', 'TOMIA', '--ppp'] DINAR
success 2 ['RILES', '-p--m', 'TOMIA', '---pp'] SHAYS
success 2 ['RILES', '-p--m', 'TOMIA', '-p-pp'] AGIST
success 2 ['RILES', '-p--m', 'TOMIA', '---mp'] APSOS
success 3 ['RILES', '---mm'] DUCKY
success 2 ['RILES', '---mm', 'DUCKY', '--p--'] NINTH
success 2 ['RILES', '---mm', 'DUCKY', '-----'] PASTS
success 2 ['RILES', '---mm', 'DUCKY', 'p----'] DELAY
success 3 ['RILES', 'p--pm'] COPRA
success 2 ['RILES', 'p--pm', 'COPRA', '---pp'] AGIST
success 2 ['RILES', 'p--pm', 'COPRA', '---mp'] AGIST
success 3 ['RILES', '-p-p-'] ADMIN
success 2 ['RILES', '-p-p-', 'ADMIN', 'm-ppp'] GRIND
success 2 ['RILES', '-p-p-', 'ADMIN', 'm--m-'] AGIST
success 2 ['RILES', '-p-p-', 'ADMIN', 'm--p-'] AGIST
success 2 ['RILES', '-p-p-', 'ADMIN', 'mp-p-'] BORDS
success 2 ['RILES', '-p-p-', 'ADMIN', 'm--pp'] ZOOID
success 3 ['RILES', '-p---'] DOING
success 2 ['RILES', '-p---', 'DOING', '--m--'] BETTA
success 2 ['RILES', '-p---', 'DOING', 'ppm--'] AGISM
success 2 ['RILES', '-p---', 'DOING', '--pp-'] YINCE
success 1 ['RILES', '-p---', 'DOING', '--pp-', 'YINCE', '-pp--'] RAUPO
success 1 ['RILES', '-p---', 'DOING', '--pp-', 'YINCE', '-ppp-'] UPRUN
success 2 ['RILES', '-p---', 'DOING', '--p-p'] AGIST
success 2 ['RILES', '-p---', 'DOING', '--mm-'] AGIST
success 2 ['RILES', '-p---', 'DOING', '--m-p'] TOMIA
success 2 ['RILES', '-p---', 'DOING', 'ppp--'] CHOUX
success 2 ['RILES', '-p---', 'DOING', '--p--'] EXULT
success 1 ['RILES', '-p---', 'DOING', '--p--', 'EXULT', '-----'] SHAYS
success 1 ['RILES', '-p---', 'DOING', '--p--', 'EXULT', '----m'] SHAYS
success 2 ['RILES', '-p---', 'DOING', '--mp-'] PASTA
success 2 ['RILES', '-p---', 'DOING', '--mmm'] CHOWK
success 1 ['RILES', '-p---', 'DOING', '--mmm', 'CHOWK', '-----'] PIXIE
success 2 ['RILES', '-p---', 'DOING', '-pmp-'] VARIX
success 2 ['RILES', '-p---', 'DOING', 'p-p--'] THYMI
success 3 ['RILES', '---mp'] ENSKY
success 2 ['RILES', '---mp', 'ENSKY', 'ppp--'] RAUPO
success 2 ['RILES', '---mp', 'ENSKY', 'p-m--'] AGIST
success 2 ['RILES', '---mp', 'ENSKY', 'p-pp-'] DELAY
success 2 ['RILES', '---mp', 'ENSKY', 'p-p--'] AGIST
success 3 ['RILES', 'p---m'] RUANA
success 2 ['RILES', 'p---m', 'RUANA', 'ppp--'] AGISM
success 2 ['RILES', 'p---m', 'RUANA', 'p-m-p'] PROUL
success 1 ['RILES', 'p---m', 'RUANA', 'p-m-p', 'PROUL', '-p---'] AGIST
success 1 ['RILES', 'p---m', 'RUANA', 'p-m-p', 'PROUL', '-m---'] GLARE
success 2 ['RILES', 'p---m', 'RUANA', 'p-p-p'] BORDS
success 2 ['RILES', 'p---m', 'RUANA', 'p-p--'] PROUL
success 3 ['RILES', 'p-pp-'] PROUL
success 3 ['RILES', 'p--mm'] CRAPY
success 3 ['RILES', '-ppp-'] KNELT
success 2 ['RILES', '-ppp-', 'KNELT', 'p-pp-'] AGIST
success 2 ['RILES', '-ppp-', 'KNELT', '--pm-'] AGIST
success 3 ['RILES', 'p----'] MHORR
success 2 ['RILES', 'p----', 'MHORR', '--pm-'] PANTO
success 2 ['RILES', 'p----', 'MHORR', '--mm-'] TENIA
success 1 ['RILES', 'p----', 'MHORR', '--mm-', 'TENIA', 'p---p'] RAUPO
success 1 ['RILES', 'p----', 'MHORR', '--mm-', 'TENIA', '----p'] DELAY
success 1 ['RILES', 'p----', 'MHORR', '--mm-', 'TENIA', '--p-p'] DELAY
success 2 ['RILES', 'p----', 'MHORR', '---p-'] GRIND
success 2 ['RILES', 'p----', 'MHORR', '--pp-'] AGIST
success 2 ['RILES', 'p----', 'MHORR', '-p-p-'] AGIST
success 2 ['RILES', 'p----', 'MHORR', '--ppm'] DELAY
success 2 ['RILES', 'p----', 'MHORR', '---m-'] PANTY
success 1 ['RILES', 'p----', 'MHORR', '---m-', 'PANTY', '-pp--'] RAUPO
success 1 ['RILES', 'p----', 'MHORR', '---m-', 'PANTY', '-p--m'] AGIST
success 1 ['RILES', 'p----', 'MHORR', '---m-', 'PANTY', '-p---'] DELAY
success 2 ['RILES', 'p----', 'MHORR', '----m'] PANTO
success 2 ['RILES', 'p----', 'MHORR', 'p--p-'] RAUPO
success 2 ['RILES', 'p----', 'MHORR', 'p--m-'] TOMIA
success 3 ['RILES', 'p-pm-'] ESTER
success 3 ['RILES', 'ppp--'] AGIST
success 3 ['RILES', '--m--'] ALWAY
success 2 ['RILES', '--m--', 'ALWAY', 'mpp--'] AGIST
success 2 ['RILES', '--m--', 'ALWAY', 'mp---'] AGIST
success 2 ['RILES', '--m--', 'ALWAY', 'mm---'] AGIST
success 3 ['RILES', '--mm-'] GYBED
success 2 ['RILES', '--mm-', 'GYBED', '---m-'] PROUL
success 2 ['RILES', '--mm-', 'GYBED', 'p--m-'] AGIST
success 3 ['RILES', '--mmm'] EXULS
success 3 ['RILES', '--m-m'] SNOUT
success 3 ['RILES', '-p-mm'] AGISM
success 3 ['RILES', 'pp---'] TOMIA
success 2 ['RILES', 'pp---', 'TOMIA', 'p--mp'] PROUL
success 2 ['RILES', 'pp---', 'TOMIA', '---pp'] GLARE
success 2 ['RILES', 'pp---', 'TOMIA', '---mp'] GRIND
success 3 ['RILES', '-pp-m'] ELFIN
success 3 ['RILES', '---pm'] TOMIA
success 3 ['RILES', 'p-p--'] CLOUT
success 2 ['RILES', 'p-p--', 'CLOUT', '-p---'] AGIST
success 2 ['RILES', 'p-p--', 'CLOUT', '-m---'] SHAYS
success 3 ['RILES', 'pp-pp'] AGIST
success 3 ['RILES', '---pp'] KALAM
success 3 ['RILES', '---m-'] ADHAN
success 2 ['RILES', '---m-', 'ADHAN', 'm----'] FYKES
success 2 ['RILES', '---m-', 'ADHAN', 'mm---'] MADID
success 2 ['RILES', '---m-', 'ADHAN', 'mp---'] UPBYE
success 2 ['RILES', '---m-', 'ADHAN', 'mp--p'] YINCE
success 3 ['RILES', 'p---p'] RAUPO
success 3 ['RILES', 'pm-m-'] VIRED
success 3 ['RILES', 'pm--m'] AGIST
success 3 ['RILES', '----m'] BANAK
success 2 ['RILES', '----m', 'BANAK', '-pp--'] ZIGAN
success 2 ['RILES', '----m', 'BANAK', '-p--p'] THOFT
success 2 ['RILES', '----m', 'BANAK', '-p-m-'] AUGHT
success 2 ['RILES', '----m', 'BANAK', '-ppm-'] AGIST
success 2 ['RILES', '----m', 'BANAK', '-p-p-'] SYLPH
success 1 ['RILES', '----m', 'BANAK', '-p-p-', 'SYLPH', 'pp---'] DELAY
success 1 ['RILES', '----m', 'BANAK', '-p-p-', 'SYLPH', 'p----'] AGIST
success 2 ['RILES', '----m', 'BANAK', '-p---'] THOFT
success 1 ['RILES', '----m', 'BANAK', '-p---', 'THOFT', 'p-m--'] YINCE
success 1 ['RILES', '----m', 'BANAK', '-p---', 'THOFT', '--p--'] RAUPO
success 1 ['RILES', '----m', 'BANAK', '-p---', 'THOFT', '--m--'] RAUPO
success 1 ['RILES', '----m', 'BANAK', '-p---', 'THOFT', '-----'] RAUPO
success 2 ['RILES', '----m', 'BANAK', 'pp---'] AGIST
success 2 ['RILES', '----m', 'BANAK', '-pp-p'] RAUPO
success 3 ['RILES', 'p--p-'] DRUPE
success 2 ['RILES', 'p--p-', 'DRUPE', 'pm--p'] DELAY
success 2 ['RILES', 'p--p-', 'DRUPE', '-p--m'] LOFTY
success 2 ['RILES', 'p--p-', 'DRUPE', '-m--m'] TIARA
success 2 ['RILES', 'p--p-', 'DRUPE', '-p-pp'] AGIST
success 2 ['RILES', 'p--p-', 'DRUPE', '-p--p'] BANAL
success 2 ['RILES', 'p--p-', 'DRUPE', '-m--p'] CARTA
success 3 ['RILES', '-p-pp'] GRIND
success 3 ['RILES', '--pm-'] PEDAL
success 2 ['RILES', '--pm-', 'PEDAL', '-p-pp'] SHAYS
success 2 ['RILES', '--pm-', 'PEDAL', '-p-pm'] AGIST
success 3 ['RILES', '----p'] DITSY
success 2 ['RILES', '----p', 'DITSY', '--pm-'] AGIST
success 2 ['RILES', '----p', 'DITSY', '---m-'] WINCH
success 2 ['RILES', '----p', 'DITSY', '---p-'] SHAYS
success 2 ['RILES', '----p', 'DITSY', '---pm'] SHAYS
success 2 ['RILES', '----p', 'DITSY', '--pp-'] SHAYS
success 3 ['RILES', 'p-mm-'] DELAY
success 3 ['RILES', '--pmm'] RAUPO
success 3 ['RILES', 'p--m-'] GRIND
success 2 ['RILES', 'p--m-', 'GRIND', '-m---'] TOMIA
success 2 ['RILES', 'p--m-', 'GRIND', '-p--m'] YINCE
success 2 ['RILES', 'p--m-', 'GRIND', 'pp---'] UPRUN
success 2 ['RILES', 'p--m-', 'GRIND', '-m--m'] CACKY
success 2 ['RILES', 'p--m-', 'GRIND', '-p-p-'] YINCE
success 2 ['RILES', 'p--m-', 'GRIND', '-p---'] ESTER
success 1 ['RILES', 'p--m-', 'GRIND', '-p---', 'ESTER', '---mm'] YINCE
success 1 ['RILES', 'p--m-', 'GRIND', '-p---', 'ESTER', '--mmm'] RAUPO


It's time for bed, so I'll report back tomorrow. So far solutions have been found for A-B, D-K, M-O. C and L look like they went down a bad path--- the worst case is still to search all 12K possible words. S is the largest case with 1521 words.

The case my search got stuck on for C is:
AROSE -p--p 
  ==> LENDS -p--m' 
    ==> 'COKES', 'COMES', 'COPES', 'COSES', 'COTES', 'COVES', 'COXES', 'COZES'

which doesn't look solvable, so it is going to have to backtrack on LENDS... unless there's a pair of five-letter words which together use 7 letters from KMPSTVXZ? Doesn't seem likely.

Probably it would be better to retry at multiple levels of the tree instead of purely heuristic-driven DFS.
Tags: programming, puzzles
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments