Für mich klingt das nach einem Fall für eine Tiefensuche mit dynamischer Programmierung / Memoisation.
Wähle ein Wort, versuch es einzufügen, prüfe ob das in Ordnung ist. Wenn ja, wähle das nächste Wort und wiederhole. Wenn nein, wähle die nächste mögliche Position und versuche es erneut. Wenn...