クロスワードを生成する例の列挙について

「 クロスワードを生成するアルゴリズム 」という記事で、クロスワードを自動生成するプログラムに実装されたいくつかのヒューリスティックが提案されました。 提案されたヒューリスティックは十分に開発されているにもかかわらず、与えられたグリッドの中で最も複雑なクロスワードパズルを生成するのに妥当な時間を許可していませんでした。


これ以降の図はすべて元の記事から引用したものです。

この記事では、この問題を解決できるはるかに単純なソリューションについて説明します。

提案されたソリューションは、2つの主なアイデアに基づいています。

1. 正しい並べ替え順序
2. 同じアクションを繰り返さないでください

すべてのコードはScalaで書かれています。

データ構造

セル（セル）の2次元リストの形式のクロスワードフィールドを想像してください。

val field: List[List[Cell]] = readField("cross.in") 

さらに、各セルはタンパク質であり、文字（文字）または黒を含む必要があり、空のままにする必要があります（空）：

 sealed abstract class Cell case object Empty extends Cell //     case class Letter() extends Cell //     -  

単語は文字のシーケンスです：

 class Word(val letters: Seq[Letter]) 

辞書-長さでグループ化された多くの単語：

 val dictionary: Map[Int, Set[String]] = readWords("cross.txt", "WINDOWS-1251").groupBy(_.size) 

単語を強調する

フィールドの説明にマークされている単語がないことに注意してください。 単語は、空のセルまたはボードの端で区切られた（将来の）文字の垂直または水平のセットと見なされます。
単語を1行で強調表示する方法を学習します。

 def extractWords(row: List[Cell]): Seq[Word] = { val rest = row.dropWhile(_ == Empty) //    if (rest.isEmpty) Seq() //    else { //      ,      val word = new Word(rest.takeWhile(_ != Empty).map(_.asInstanceOf[Letter])) //         word +: extractWords(rest.dropWhile(_ != Empty)) } } 

すべての単語を選択するには、行から単語を選択し、フィールドを転置して、列から単語を選択します。 同時に、1文字の単語を削除します。

 val words = (field.flatMap(extractWords) ++ field.transpose.flatMap(extractWords)).filter(_.letters.size != 1) 

交差する単語をすばやく検索するために、情報を（将来の）文字に保存します。この単語は、それらの単語とこの単語の文字番号を通過します。

 case class Letter() extends Cell { var words = Array.empty[(Word, Int)] } for (word <- words; (letter, index) <- word.letters.zipWithIndex) { letter.words :+= (word, index) } 

ブルートフォース

2つのマッピング（マップ）を検索プロシージャに渡します：バリアントと割り当て。 まだ考慮されていない各単語の単語には、この場所にあることができる単語のリストが含まれ（最初はすべての単語が必要な長さです）、割り当てには既に考慮されている単語の固定値が含まれます（最初は空です）：

 //  def search(variants: Map[Word, List[String]], assignment: Map[Word, String]) //  search(words.map(w => (w, random.shuffle(dictionary(w.letters.size).toList))).toMap, Map.empty) 

呼び出すときに、リスト内の単語が混合されるため、異なる起動で異なるクロスワードが取得されることに注意してください。

これで、検索の最初のバージョンを書くことができます。

 def search(variants: Map[Word, List[String]], assignment: Map[Word, String]) { if (variants.isEmpty) { //    -   dump(assignment) } else { //        val (word, vars) = variants.head //    for (variant <- vars) { //      var newVariants = variants - word //   ,   ,     for ((letter, char) <- word.letters.zip(variant); (other, index) <- letter.words; if newVariants.contains(other)) { //    ,      (index)    newVariants = newVariants.updated(other, variants(other).filter(var => var(index) == char)) } //   search(newVariants, assignment.updated(word, variant)) } } } 

残念ながら、妥当な時間内に、このバストはオリジナルで言及された最も単純なグリッド（9x9）でも解決策を見つけることができません。
記事：

正しい並べ替え順序

幸いなことに、この問題は簡単に修正できます。 これを行うには、正しい考慮順序を選択するだけです。 検索で最初の単語が表示されます。

より効果的な戦略はありますか？ そこにあり、そのうちの1つは、1965年にSWゴロム、LD Baumertバックトラックプログラミング// Journal of the ACM Volume 12 Issue 4、1965の記事で提案されました。 残念ながら、私はこの記事をパブリックドメインで見つけることができませんでしたが、アイデア自体は非常に単純です。選択肢が少ないものをソートする必要があります。

私たちの場合、これは、任意の単語を使用するのではなく、残っている適切なオプションの数が最も少ない単語を使用することを意味します。

 val (word, vars) = variants.minBy(_._2.size) 

同時に2つの素敵なボーナスが無料で得られることに注意してください。 まず、単語にオプションのみが残っている場合、その単語がすぐに選択され、このブランチはそれ以上列挙せずに切断されます。 第二に、単語にオプションが1つしか残っていない場合、そのオプションはすぐに配置されるため、将来の検索が削減されます。

この最適化により、9x9グリッドのソリューションを即座に見つけることができ、50％以上のケースで「単純な」15x15グリッドのソリューションを見つけることができます。



ただし、11x11グリッドと「複雑な」15x15グリッドでは、時間がかかりすぎます。

同じアクションを繰り返さないでください

ほとんどのプログラムと同様に、検索ではほとんどの場合、「不適切な」単語を削除する最も内側のサイクルに占有されます。

 newVariants = newVariants.updated(other, variants(other).filter(_(index) == char)) 

一見、この行にはループはありませんが、実際にはフィルターメソッドの実装に潜んでいます。 ここでどのように時間を節約できますか？ そして、このサイクルの結果をキャッシュしましょう！

ここでは単語のリストが計算されることに注意してください。一部の文字は固定され、一部の文字は不明です。 このような「部分的な」単語を、「 ??? 」という形式のマスクの形式で表します。つまり、未知の文字ではなく疑問符を示します。

列挙では、「適切な」単語のリストではなく、マスク+リストの計算結果をキャッシュして操作します。

 def search(masks: Map[Word, String], assignment: Map[Word, String]) { if (masks.isEmpty) { //    -   dump(assignment) } else { //       val (word, mask) = masks.minBy(w => cache(w._2).size) //   for (variant <- cache(mask)) { var newVariants = masks - word //  ""  for ((letter, char) <- word.letters.zip(variant); (other, index) <- letter.words; if newVariants.contains(other)) { val oldMask = masks(other) val newMask = oldMask.updated(index, char) //  ,     cache.getOrElseUpdate(newMask, cache(oldMask).filter(_(index) == char)) newVariants = newVariants.updated(other, newMask) } search(newVariants, assignment.updated(word, variant)) } } } 

新しい検索機能を使用する前に、辞書の単語でキャッシュを満たし、すべての単語のソースマスクを生成する必要があります。

 for ((length, variants) <- dictionary) { cache.getOrElseUpdate("?" * length, random.shuffle(variants.toList).toArray) } search(words.map(w => (w, "?" * w.letters.length)).toMap, Map.empty) 

キャッシュを追加すると、最も複雑なグリッドでも検索でソリューションを見つけることができます。



30秒で生成されたクロスワードパズル（実際、この場合はランダムオームで幸運でした。クロスワードパズルは20のケースのいずれかですぐに生成されます）。

 acast ahum ahum 
アロララララガー 
あなみロックハーム 
無線送信機 
 mlanzy火口     
   アーネの師部 
マールケッチ俳優 
抗うつ薬 
あたすあーぱー 
カルトリ全体    
    インサイ雲 
加算 
ラフ・アラ・アナンド 
ロイック・キンディ 
ケーキアナエディ  

結論

いくつかの簡単な最適化を使用することで、対象分野の深い知識に基づいたヒューリスティックなソリューションよりも優れたソリューションを簡単に実装できました。 正しい並べ替え順序を選択し、同じカウントを繰り返さないでください！

• ソースコード
• 入力例
• 辞書 （ページの最後、 元の投稿のコメントからのリンク）