Literary Alfabet Soupe (Revisited)

Published Difficulty: Medium

Algorithm X Complexity: Is Algorithm X Really Needed?

Strategy

In the original discussion for this puzzle, I wrote:

Let’s assume you are at a point where you have some number of “candidate” languages for each excerpt. Some excerpts might have just one candidate language while others might have 2, 3, 4 or more candidate languages.

Can you do any problem-space reduction before running Algorithm X? Of course you can! Assume you have identified the following candidate languages for the first 3 excerpts:

Excerpt	Candidate Languages
1	Finnish, French, German, Irish
2	German
3	French, German, Spanish

Do you see the opportunity for problem-space reduction? The only option for excerpt 2 is German. Since each language can only be used one time, German can be removed from the candidate lists for excerpts 1 and 3.

Once you have a list of candidate languages for each excerpt, your problem-space reduction can be similar to what was covered a few pages back using Sudoku. This puzzle is not meant to be a complex exact cover problem, so keep your reduction algorithm simple. If you create a loop to reduce the candidate lists wherever possible, you might find that full solutions appear for each test case before you even begin setting up Algorithm X.