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

 (dfns.dyalog.com)
1 ポイント 投稿者 GN⁺ 2024-10-07 | 1件のコメント | WhatsAppで共有
  • Dyalog APL の sudoku は、空欄を 0 としたパズル行列から 可能なすべての解答行列 を返し、同じ問題を APL/K スタイルで複数の方法で実装している
  • 基本対象は 9×9 の Sudoku で、各 3×3 ボックス、行、列には 1 から 9 までの数字が重複なく入らなければならない
  • 入力 prob は埋まっているマスに 1-9、空欄に 0 を入れ、任意の左引数 shape によって 2×3、3×4 のような 非正方形ボックス も指定できる
  • Veli-Matti Jantunen の解法アルゴリズムは、行列をベクトル化して行・列・ボックスのインデックスを作成し、候補を絞り込みながら 最も制約の強いグループ から展開していく
  • 例の s33 と s22 はそれぞれ 3 個の解答を持ち、3 4 sudoku s34 は 2 個の解答を持つ。Arthur Whitney の K 5 ワンライナーと複数の APL 再実装もあわせて紹介されている

Sudoku の入力と sudoku 関数の結果

  • Sudoku パズルは、3×3 ボックスが 3×3 に配置されたグリッドで、各マスは空であるか 1 から 9 までの数字を持つ
  • 解答は 3 つの重複禁止条件をすべて満たさなければならない
    • 各 3×3 ボックス に 1 から 9 までの数字が重複なく入る
    • 各 9 マスの行 に 1 から 9 までの数字が重複なく入る
    • 各 9 マスの列 に 1 から 9 までの数字が重複なく入る
  • prob 行列は、埋まっているマスに 1-9、空欄に 0 を使う
  • 任意の左引数 shape は、標準の正方形ではないパズルの ボックス形状 を指定する
    • 6×6 行列で部分領域が 2×3 なら、2 3 sudoku mat の形で呼び出す
  • 結果は、すべての解答行列を含むベクトル
    • 解答がなければ ⍬ を返す
    • エラー状況は '' で示されることがあり、文書では「発生すべきではないが、結果が非常に多いとき」とされている

Veli-Matti Jantunen の解法の流れ

  • アルゴリズムは Sudoku 行列を ベクトル として扱い、行・列・Sudoku 領域をそれぞれ インデックスベクトル で表す
  • 基本検査を通過した後、候補リストから代替案を 1 つずつ調べる
  • 各段階では、すべてのマスの可能な要素を絞り込む
    • 可能な値がないマスが 1 つでもあれば、その解答候補は除外される
    • 1 マスに候補数字が 2 つ以上ある場合は、最も制約の強いグループからマスを選び、そのマスの候補の組み合わせをリストに追加する
    • すべてのマスに数字が 1 つずつしか残らなければ、解答として処理して次の候補へ進む
  • 同じセクションには、既存の Sudoku 表を別の表にシャッフルする Shuffle 関数も含まれている

Arthur Whitney のワンライナーと代替実装群

  • David Crossley の代替 sudoku 実装は N×N 設定を入力として受け取り、ボックスサイズ N*÷2 が整数になる場合を対象としている
    • 入力は、一部のマスに 1 から N までの数字が入り、残りが 0 の有効な配置でなければならない
    • 各行、列、ボックスは、結果において 1 から N までのすべての数字を含まなければならない
    • 実装内部には valid, search, rules, sole, singles, uniques, matches, NinN, setup などの補助関数がある
  • Arthur Whitney の K 5 による解法は 1 行のコード として示されている
x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~* x
  • Phil Last は、Whitney のコードを D-function に移した sudoku 実装を提供している
  • Morten Kromberg の書き直しは、K の一部の構成要素を明示的に定義して、原文により近い形を取っている
    • K 版と同様に、行列ではなく 81 要素のベクトル を入力・出力する
  • Roger Hui の Sudoku 実装はより一般化された形で、非正方形パズルも扱う
    • svec は解答ベクトルを作り、pvex と pvec は可能な配置を展開する
    • avl は可能な数字の一覧を作り、emt は空欄の行・列インデックスを見つける
    • rcb, box, cmap, CMAP は行・列・ボックスの衝突関係を構成する

サンプルパズルと解答数

  • s33 は 9×9 のサンプル問題で、sudoku s33 の結果は 3 個の解答 を持つ
  • sbox 関数は内部ボックスを分割して Sudoku グリッドを読みやすく表示する
    • 0 は中点 (·) として表示される
    • ボックス境界が描かれた文字行列の形で出力される
  • s22 は 4×4 のサンプル問題で、sbox¨ sudoku s22 の結果は 3 個の解答 を持つ
  • s34 は 3×4 ボックスを使うサンプル問題
    • 3 4 sbox s34 で問題をボックス区切りの形で表示する
    • 3 4 sudoku s34 の結果は 2 個の解答 を持つ

参考リンクと関連項目

  • sudoku_bfs は、このアルゴリズムを示す例にリンクされている
  • TryAPL の「Learn」には段階的なデモがある: http://www.TryAPL.org
  • 実行の動作を示す動画がある: http://www.youtube.com/watch?v=DmT80OseAGs
  • 関連項目として queens, sudoku_bfs, X, sudokuX が挙げられている

関連記事

1件のコメント

 
GN⁺ 2024-10-07
Hacker Newsのコメント

  • この行は K で書かれている。K は Arthur Whitney が APL と Scheme をもとに作った言語だ。
    x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~*x

  • ときどき、コードの複雑さをコード行数と次の出力結果を比べて見積もることがある。
    tar -cf - . | gzip | base64 | wc -l
    つまり「どれだけうまく圧縮できるか？」を見ているわけだ。APL を見ると、誤って gzip の出力をターミナルに流してしまったときのことを思い出す。
    p←{(↑⍵)∘{(⍺∨.=⍵)/⍳n×n∘}¨,⍵},(n*÷2){⍵,⍺⊥⌊⍵÷⍺}'⍳n n←⍴⍵
    こんなコードを追いながら「バグを見つけられるか？」までやる人がいるのには感心する。まるで、みんなが同じ辞書を持っている圧縮済みバイナリデータのように感じる。

    • APL プログラマーが 保守性 と可読性をどう考えているのか本気で気になる。コードにものすごく丁寧にコメントを書くか、別途しっかり文書化するのだろうかと思う。
    • 「バグを見つけられるか？」という話なら、すぐにいくつか見つかる。閉じられていないシングルクォートや、右オペランドのない ∘ といった構文エラーがあるし、n n←⍴⍵ は n を二度設定して ⍵ が 2 次元だと期待している合図のように見えるが、意図次第では _ n←⍴⍵ や n←⊃⌽⍴⍵ のほうが自然だ。
      また ⊥ は ⍴⍵ が単一の整数か空ベクトルでなければエラーになるので、結局 n←⍴⍵ と変わらず、なおさら紛らわしい。重複した , や ↑⍵ もいくつか削れるし、式全体は実際のところ p←(n+1)⍴⊂⍳n×n←⍴⍵ とほぼ同じになり、1..n² ベクトルを n+1 個出す構造だ。
      見た目は奇妙でも、記号と基本演算を覚えれば APL は意外と素直だ。ただし熟達するには時間がかかり、その域に達すると超能力のように感じられる。
    • 英語以外の文字を読み書きする人が何十億人もいることを考えると、APL を読める人がいることがそれ以上に特別だったり驚くべきことだったりするのかはよく分からない。

  • 言語の支持者が速度、配列処理のしやすさ、表現力の高い文法を強調するというのはその通りだ。
    https://en.m.wikipedia.org/wiki/K_(programming_language)

    • ただし 保守性 まで長所かどうかは分からない。

  • コード行数は、言語ごとに行の使い方が違うので良い指標ではない。
    もっと良い尺度は、「定数」や「関数呼び出し」のような意味のある非終端記号を基準に 構文木ノード数 を数えることかもしれない。さらに、その木の深さや分岐係数まで考慮できればもっとよい。

    • 単に意味だけが重要だという考えには賛成しにくい。言語のユーザー体験、明確さ、思考様式、表現力も重要で、コードの視覚的な大きさがそこに影響する。
      ワンライナー解法は画面スペースをほとんど取らないので、複雑な問題を扱うときに大きな利点になる。視線を画面内で動かすほうが、ファイルをまたいでスクロールするよりずっと負担が小さく、認知負荷は重要だ。
      K を知らなくても、定数が並んで見えれば問題の直接的なデータ表現を使っているように見える。K の文化がこうしたコードを奨励し、直接性と単純さの方向へ思考を傾けるのなら、チームにそういう秘伝のタレを持ち込みたくなる。
    • 組み込み関数やシステムライブラリ API はこうした尺度を壊してしまう。たとえば HQ9+ は “Hello, world!” の出力に関してはかなり優秀だ。
      https://cliffle.com/esoterica/hq9plus/
    • 情報量を測るうえで好ましい尺度は、アルゴリズム情報理論と同じく単純に ビット数 だ。
      https://en.wikipedia.org/wiki/Algorithmic_information_theory
    • このワンライナーは明らかに冗談半分で作られたもので、これを合理的に読みやすいコードだと主張する人はいない。ここで定義論を持ち出すのは本質を外している。要点は「K では極度に高密度なコードを書ける」ということだ。

  • APL/K のような言語を使うと、プログラマーは実際に問題をより効率的に考えられるのか、前からよく気になっていた。

    • kdb+/Q プログラマーとして言えば、問題の種類による。データ配列を扱う場合、2 つの配列を足してから平均を取る処理を avg a+b として考え、書けるのは確かに楽だ。
      配列中心でない言語だと、境界チェックや大きな for ループ、合計や件数を入れる一時変数などが必要になる可能性が高い。C のような言語ならだいたい 6 行くらいになる処理が、Q では 6 文字で済むような違いだ。
      ただし、どの言語にも特定の問題をよりうまく推論できるようにする機能がある。代数的データ型とパターンマッチングを持つ関数型言語、たとえば OCaml や F# は大きな switch や if-else-if より優れているし、async/await のようなシンタックスシュガーを持つ言語は並行処理に向いている。
    • 簡単にベクトル化できる問題群では、配列指向言語が思考と解法をより効率的にしてくれる。データ構造や反復の細部を抽象化できるからだ。
      クオンツとして働いていたころ、kdb+/q を 5 年以上にわたって中頻度戦略で多用していたが、板情報の計算のように簡単にも効率的にもベクトル化できない高頻度取引の領域へ移ると、配列指向言語を使い続けることはかえって問題の推論を複雑にした。
    • Dyalog という現代的な APL 系言語の発表で、この表記法は特定のイディオムをより見つけやすくするという主張を聞いた。
      https://youtu.be/PlM9BXfu7UY?si=ORtwI1qmfmzhJGZX&t=3598
      その箇所はコンパイラ文脈の話だったが、発表全体では Dyalog と APL を数学的記法体系として扱っている。主な流れとしては、一般的なコードより数学的な式を最適化するほうが簡単な場合がある、ということだ。
    • Hillel Wayne もニュースレターでこの話題をときどき扱っている。彼が実際にいくつかの問題を 配列言語 でよりうまく考えられるという点には納得したが、その体験がどんな感覚なのかはいまだにうまく想像できない。
    • 配列言語スタイルの良い点は、アルゴリズムの変形を議論するとき、関連するコード断片が数文字で済むので本文の中にそのまま入れられることだ。同じことを言うのに何行も、あるいは何十行も必要な従来の縦長の言語では、コードブロックと説明文を絶えず行き来しなければならない。

  • ここで最も重要な点のひとつは、上部の問題生成器が非常に明快だということ。これが、JやKを含むIverson式の記号言語と他の言語との違いだ
    一行解法の優雅さや力強さはないが、厳密なコメントがなくてもとてもすっきりしていて理解しやすい。ただし、lampは良いコメント記号ではないと思う
    一行解法は驚異的で、暗黙的プログラミングは頭がねじ曲がるほどすごい。グリフベース言語の独特な圧縮性を関数型プログラミングの説明と実行に使い、それをさらに配列全体に適用した発想は天才的だ
    https://www.jsoftware.com/papers/fork.htm

    • すべてを空白なしの一行で書けるからといって、必ずそうすべきというわけではない
      もちろん、そうした能力を取り除けばより冗長なコードを書くよう強制はできるが、そうすると対話的ツールとしての強みが大きく損なわれる。Iverson式言語は非常に短いコードを書けるので、対話的作業に向いている。そのときのコードは保存すらされないので、本当に write-only コードだ
      ファイルに入れるコードを書くときは好きなスタイルを選べばよく、その場合はあまり圧縮しすぎない書き方を勧める。それでもIverson式言語は、冗長なスタイルで書いても大半の言語よりはるかに短いコードを提供する

  • ほとんどの人は記号を理由に敬遠するが、私の問題はそこではなかった
    APLや配列言語は好きで、そこで学んだことは他の言語を書くうえでも大いに役立った。だが日常的な道具にはならなかった。記号のせいではなく、3〜4年ほど断続的に触れているうちに越えられない壁にぶつかったからだ
    他の言語にはたいてい、問題をとりあえずでも解いていく一般的なアプローチがあり、後でその問題の「秘訣」を見つければ、もっと優雅で効率的に直せる。APLにはそうした一時的な回避策がなく、秘訣を知っているか知らないかのどちらかしかないように感じられた
    実際にそうなのか、秘訣を十分に学べば問題解決の直感が身につくのか、最後まで秘訣頼みなのか、それとも自分が中核となる戦略文書を読んでいないだけなのかは、よく分からない

    • その感覚は間違っていない。配列言語を学んでいると、そういう印象を受けるのはごく自然だ。長く使っている人は問題を見て「なんでそんなに複雑に解いたの、⍸⍣¯1を使えばいいのに？」と言いがちだが、そもそも誰かが⍸に逆演算があって、それをどう使うか教えてくれたとは限らない
      今でも何年もこうした言語を使っているが、一部の配列プログラマが作るコードの壁には少し気後れする。なぜそう書くのかは理解できるが、個人的にはコードに多少空白がある方が好みだ
      APLベースの配列言語を作っているのだが、初期目標のひとつは、if文のようなものを書く初心者を罰せず、命令型スタイルを第一級市民にすることだった。このスタイルは、純粋なAPL風と一般的な命令型言語の中間あたりだと考えている
      https://codeberg.org/loke/array/src/branch/master/array/standard-lib/output3.kap
    • その壁という話は、現在のAPL入門経路における実際の問題だ。昨年まさにこのテーマで発表もしたし、決して個人のせいではない
      とはいえ、それは言語自体の限界でもない。私の経験では、その壁を突破する過程こそがパラダイムが腑に落ちる過程だった。1年間YAMLパーサのプロトタイプを作りながら500時間ほどハックして、ようやく点と点がつながり始めた
      核心は、データ駆動設計の原則、良い記法のIverson的特性をソフトウェアアーキテクチャで具体的に活用する方法、そしてイディオムとそれがドメイン概念をどう表現するかに慣れること、その組み合わせのように感じる
      https://dyalog.tv/Dyalog23/?v=J4cg6SV92C4
      https://www.jsoftware.com/papers/tot.htm

  • この話題に関する動画がある
    https://www.youtube.com/watch?v=DmT80OseAGs
    解法は https://tryapl.org/ で自分で試せる

  • この一行をさまざまなプログラミング言語のコードゴルフ解法と比べてみると面白いかもしれない
    https://codegolf.stackexchange.com/questions/tagged/sudoku?tab=Votes

    • 面白いことに、ある特定の問題、つまり総当たりの数独ソルバでは、1位の解法がまさにKの断片だ。2位はそのK解法をまねて作られたJ解法になっている
      https://codegolf.stackexchange.com/a/5030