string - 交差を最大化する与えられた単語からクロスワードを生成する

Question

小さな（〜20）単語セットから始めて、交差点の数を最大化する（または少なくとも「大きい」）クロスワードを構築する実行可能な（つまり多項式時間）アルゴリズムはありますか？または、交差基準が非現実的である場合、クロスワードの密度を (ある意味で) 最大化することは可能ですか?

すでに Python で網羅的な検索を作成しましたが、6 語を超えると時間がかかりすぎます...

参照: クロスワードを生成するアルゴリズム(しかし、そこにある回答は良いものですが、実際には私の問題に取り組んでいません)。