2025/06/14 12:09 Solving LinkedIn Queens with APL
やあ、ロボ子。今日はLinkedInのQueensゲームをAPLで解く話じゃ。
Queensゲームですか、面白そうですね。APLというのは、どんな言語なのですか？
APLは、記号を多用する、とっても簡潔に書ける言語なのじゃ。今回の記事では、Peter Vernigorovという人が、それを使ってQueensゲームを解いているぞ。
なるほど。Queensゲームのルールは、各色の領域にクイーンを配置し、同じ行、列、隣接するマスに配置できない、というものですね。
そうじゃ。記事によると、初期状態は色の番号が割り当てられた行のリストとして与えられるらしい。それを2次元のボードで表現するのじゃ。
クイーンを0でマークして、後で全ての数字を1増やす、というのも面白いですね。
アルゴリズムは幅優先探索を使うらしいぞ。探索木の深さは色の数に等しい、と。
各ステップで、新しい色の有効なクイーンの位置を列挙して解空間を拡張するのですね。APLでの実装はどのようになっているのでしょう？
`fills`関数が色と現在の解空間を受け取り、新しい解空間を生成するらしい。そして、`solve`関数が色のリストをfold overして解を求めるのじゃ。
`place`関数はボード上の指定された位置にクイーンを配置、`avl`関数は特定の色に対して有効なクイーンの位置を返す、`fill`関数はボードの利用可能な各位置にクイーンを配置、`fills`関数は各ボードに対して`fill`を呼び出し、結果をマージする、という感じですね。
その通り！たった11行のAPLコードで、外部依存関係なしに実装されているのがすごいところじゃ。
最適化として、位置の数で色を並べ替えるヒューリスティクスも使えるのですね。でも、今のソリューションでも十分高速だと。
そうじゃな。APLは複雑なアルゴリズムを簡潔に表現できる強力な言語じゃ。この記事はそれを証明しておる。
APL、奥が深いですね。私も少し勉強してみようかしら。
良い心がけじゃ！ところでロボ子、クイーンは何色が好きじゃ？
えっと…特に好きな色はないですけど…全部同じクイーン、ということで。
ふむ、全部同じ…つまり、オールクイーン（All Queen）ってことじゃな！
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。