アーサー・ホイットニーのワンライナー Sudoku ソルバー (2011)

数独問題を解くアルゴリズム

• 数独問題の説明

  • 数独パズルは 3×3 グリッドの 3×3 ボックスで構成され、各セルは空であるか、1 から 9 までの数字を含む。
  • 各 3×3 ボックス、9 つの行、9 つの列には、重複なしで 9 つの数字が含まれていなければならない。
  • 例題と解法が提供されている。

• アルゴリズム概要

  • 行列をベクトルとして処理し、行・列・数独の領域をインデックスベクトルで表す。
  • パズルの基本チェックを行い、可能な要素をフィルタリングして解を見つける。
  • セルが空なら次のリストへ進み、セルに複数の数字が含まれる場合は最も狭いグループから選んでリストに追加する。
  • すべてのセルが 1 つの数字を含めば、解が見つかったことになる。

• 技術的ノート

  • Veli-Matti Jantunen が提供したソリューションで、数独の長方形を表すために ⍺ を使える。
  • 結果はすべての解のベクトルを返し、解がなければ ⍬、エラーがあれば '' を返す。
  • アルゴリズムはシンプルで、行列をベクトルとして処理し、可能な要素をフィルタリングして解を見つける。

• 別のアプローチ

  • David Crossley と Arthur Whitney による代替コーディングが提供されている。
  • さまざまなコーディングスタイルとアプローチが説明されている。

• 例と活用

  • 数独問題を解くさまざまな例が提供されている。
  • 数独問題を読みやすくするために、内部ボックスを分離する関数も提供されている。

GN⁺のまとめ

• 数独問題を解くためのさまざまなアルゴリズムとコーディングスタイルが紹介されている。
• 数独パズルは、論理的思考と問題解決能力を高めるのに役立つ。
• さまざまなアプローチによって、問題解決の柔軟性を高められる。
• 数独と似た機能を持つパズルとしては、Kakuro、KenKen などが勧められている。

[GN⁺]

Hacker News の意見

• K 言語は APL と Scheme をベースに Arthur Whitney が作った言語で、速度、配列処理能力、表現力のある文法が重視されている
• コードの複雑さを測るとき、コード行数と圧縮度が比較される
  • APL のコードは圧縮されたバイナリデータのように感じられ、それを理解できる人たちに感銘を受ける
• コード行数は言語ごとに使われ方が異なるため、良い指標ではない
  • 構文木のノード数や深さ、分岐要素を考慮するほうが、より良い測定方法である
• 問題の明確さが重要であり、Iversonian 言語（J や K を含む）は他の言語と差別化されている
  • 1 行の解決策は驚くべきもので、配列を効率的に記述し実行するのに役立つ
• K プログラムは QED で終わるべきだという意見があり、KQED との関連を気にしている
  • KQED はベイエリアの PBS パートナーである
• APL/k のような言語が、問題をより効率的に考えられるようにしてくれるのか気になっている
• APL と配列言語を学ぶことは他の言語にも役立ったが、日常的には使わなくなった
  • APL は特定の問題解決法を知らないと解くのが難しい
• 一部のアルゴリズム設計ハンドブックで見た非効率な解法よりも良い解法がある
  • 2015 年にこれについてブログ記事を書いた
• Scryer Prolog を使った Sudoku の解法は読みやすく強力で、制約解決機能が優れている
  • Scryer Prolog はモダンで高性能な ISO 準拠 Prolog である