blog.dnpp.org

ナンプレ (いわゆる数独) の問題生成アルゴリズムの話。

概要

iOS と macOS ネイティブなアプリを作った ので、技術的な話を書きます。

詳細

拠所無い事情からコンピュータサイエンスというか基本的なアルゴリズムの実装の勉強を leetcode でやっていた時期が 2023 年の 9 月頃にありまして、「折角勉強したんだし何か作るか」という気持ちでアプリを作りまして…。

リリースまでなんとか持っていった訳なんですが、実装だけならいいものの、ゲームデザインとか、 Web サイト作成とか、アイコン含むいわゆるデザイン的なものとか、そういうのも本当に 1 人で全部やってたからなんやかんや 3 ヶ月かかってしまって、まぁ大変だったんですがそこそこ満足な出来栄えになったので是非ダウンロードして触ってみてください。

数独はニコリの登録商標となっているためアプリの名称はナンプレとしていますが、この記事はアルゴリズムの技術的な解説やゲームデザインの話といった内容なので以降は数独という名称を使用しています。問題があれば書き換えます。

本題

数独のルールは単純で、 9*9 の 81 マスの中に 1~9 の数字を各々 9 個ずつ、縦 ・ 横 ・ 3*3のエリア内で重複がないように配置する、というもの。

具体例を出した方がイメージしやすいと思うので手元で生成してみます。こんな感じ。

+-------+-------+-------+
| 9 1 5 | 3 7 8 | 6 4 2 |
| 6 7 4 | 1 9 2 | 5 3 8 |
| 3 2 8 | 5 4 6 | 1 9 7 |
+-------+-------+-------+
| 1 9 6 | 8 5 3 | 2 7 4 |
| 4 5 2 | 9 1 7 | 8 6 3 |
| 7 8 3 | 2 6 4 | 9 5 1 |
+-------+-------+-------+
| 5 6 7 | 4 2 1 | 3 8 9 |
| 2 3 9 | 7 8 5 | 4 1 6 |
| 8 4 1 | 6 3 9 | 7 2 5 |
+-------+-------+-------+

最終的にこの解答に辿り着くように、適当な箇所に穴を空けていきます。具体的にはこんな感じ。

+-------+-------+-------+
| 9 . . | . . . | . . . |
| . . . | . . 2 | . 3 . |
| . . . | . . 6 | 1 . 7 |
+-------+-------+-------+
| . . . | . 5 3 | . 7 4 |
| . 5 . | . 1 . | . . . |
| 7 8 . | . . . | 9 . 1 |
+-------+-------+-------+
| . . . | 4 2 . | . 8 9 |
| . 3 . | . 8 . | . . . |
| . . 1 | . . 9 | . . . |
+-------+-------+-------+

大まかな問題生成の方針としては

  1. 数独の制約を満たす解答の盤面を生成する。
  2. 盤面から適当なマスを選んで穴を空ける。
  3. 数独の問題として解く。(つまりソルバーが必要)
  4. 複数の解答が発生しない (つまり全探索の必要がある) ことと、生成した解答と一致することを確認する。
  5. 2 の手順に戻って穴を追加で空ける。
  6. 以上を再帰的に実行し、解けなくなる限界まで空けるか、前もって指定した穴の数に達するまで続ける。

という流れになります。

数独ナンプレ愛好家界隈では穴の空き方が対称的であることに美しさを見出すような文化もあるらしいので、ここは要調整かもしれません。

ともあれ、まずは解答の盤面を生成する必要があります。その話からしましょう。

数独の解答を生成する。

組み合わせ爆発が起こるので、戦略的に実装をしないと盤面の生成ですら現実的な時間で終わらないことになります。

数独の解答として成立する盤面の種類は既に先人によって数え上げられており、 6670903752021072936960 ≒ 6.7 * 10^21 とのこと。

更にそこから相似形を除くと 54億7273万0538 とのこと。

パっと見ると多いような気がするのですが、凄い単純に考えて 81 マスに 81 個の数字を配置するパターンは 81! になる訳で、これはざっくり 5.7 * 10^120 オーダー。実際には数字は 1~9 までで重複してるので、何回か 9! で割れるはずというか、まぁ流石にそんな実装はせんやろって感じだけど、仮に 1~9 の数字を 9 個ずつ入れた要素が 81 個ある配列をシャッフルしたとき、偶然数独のルールを満たした盤面になる可能性は限りなく 0 な訳です。

という訳で深さ優先で探索していく。

まず最初に埋める場所を決めます。適当な 1 列か、1 行か、 1 ボックス、なんでもいいんですが、今回は一番上の横一列を選びます。

選んだ場所に 1~9 を適当にシャッフルして配置するまでは確定で行えるので、探索はそこから開始します。用途的に複数の解答を生成する必要がないため、深さ優先で探索し、1 つ見付かったら終了する方針で良いでしょう。

以降は DFS の教科書的な実装になります。Stack を用意して、順番にマスを走査しながら、そのマスに入る候補の数字を集合から計算してランダムに入れていきます。この時マスに入る候補がない場合は枝刈りができるのでさっさとループを抜けて Stack から pop すると効率が良いかと思います。

実装上の工夫ですが、配列が最初からソート済のものを定数で用意しておくと添字による定数時間アクセスで値を弄ることができ、大量のループ内で走るような処理ではそれなりに高速化されます。

例えば、そのマスに入れることができる候補を計算する際のコードです。

// current の型は [[Int]] で、初期値は 0 で埋めた Int の二重配列。盤面の表現。左上原点で、横の座標が x で縦の座標が y
// relatedPositions は、指定された座標を含む縦・横・ボックスから、自分自身の座標を引いたもの。頻繁に同じ計算することになるため、全座標に対して結果をキャッシュしている。
var candidates = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for relatedPosition in Position.relatedPositions(x: x, y: y) {
    // array が [1,2,3,4,5,6,7,8,9] とソート済であることを利用して、 value - 1 の index を使って -1 で埋めて、最後に removeAll することで 1 ループで済むようにしてる。
    let value = current[relatedPosition.y][relatedPosition.x]
    if value > 0 {
        candidates[value - 1] = -1
    }
}

candidates.removeAll { $0 == -1 }

if candidates.count == 0 {
    impossible = true // 以下枝刈り
}

// 以下実装が続く ...

細かい最適化を考えるのは楽しいんですが、コメントがないと自分で実装したものなのに意図が分からなくなるという副作用もあり、本質的な難しさがありますね…。

数独のソルバーを作る。

問題を作るには、正しく解けるかを確認するためにソルバーが必要です。順番的にはこちらの方が先ですね。

数独のソルバーを実装する問題は leetcode (37. Sudoku Solver) でも出題されており、ここのコミュニティを参照したり、ChatGPT さんに解法を聞いたりすると「Backtracking で実装しましょう！」と教えてくれます。

競プロ的にはそれはそれでいいんですが、実際のゲーム内で使用するには微妙です。というのも、この辺の実装には「解答が 1 つしかない数独の問題が与えられている」という前提があるため、そのまま使うと「複数解答がある場合は、その内の 1 つに辿り着く」ことになってしまうからです。

解答が真に 1 つしかないことを保証するためには全探索をする必要があります。しかし無理に全ての解答を探索する必要はありません。解答が 2 つ以上見付かったら、その時点で問題としては不成立ということで枝刈りできます。

そしてこれはゲーム性の都合ですが、人間が実際に数独を解くときに試すであろう解法を落とし込んで実装をします。生成される問題の難易度の調整のために、人間が試す単純な解法のみで解ける問題に限定するという用途に使用します。

またゲーム性の都合でヒント機能も実装したいので、そこでも人間的な解法を使用することになります。

難易度の評価関数を実装し、予め設定した評価値の範囲内に収まるまで問題を生成し続けるという手法もあるとは思いますが、iPhone アプリとしてリリースするには問題の生成が一瞬で終わる方が望ましいという事情があり、問題を生成するだけで数秒かかるユーザー体験は許容できないという判断ですね。

人間的な不完全ソルバーを実装する。

以下のような方針で実装していきます。

第一フェーズ

  1. 空きマスに関連するマス (縦・横・ボックス) に入っている数字の集合を計算する。
  2. (1,2,3,4,5,6,7,8,9) の集合と引き算して、マスに入る候補を得る。
  3. 候補の集合の要素が 1 個のみの場合、答えとして確定させる。
  4. 確定させたマスに関連するマス (縦・横・ボックス) に確定させた数字の候補があれば消す。その結果候補が 1 個になった場合は答えとして確定させて、同じ操作を繰り返す。
  5. 全ての空きマスに対して同じ操作を繰り返し、候補の集合の要素が 1 個のみのマスがなくなるまで続ける。ここで解ければ終了。解けず候補が無くなったら第二フェーズへ移行。

第二フェーズ

  1. 縦・横・ボックスいずれかの 9 個のマスに属する空きマスの候補に対して、1 箇所にしか存在しない候補がないか調べる。
  2. 存在していれば答えとして確定させ、確定させたマスに関連するマス (縦・横・ボックス) に確定させた数字の候補があれば消す。その結果候補が 1 個になった場合は答えとして確定させて、同じ操作を繰り返す。
  3. 第二フェーズを中断し、第一フェーズの操作に戻る。

この辺の匙加減は難しいところでして、先の話になりますが、生成された問題を実際に手で解いてみて難易度の調整で悩んだ結果、

「複数の候補が入っているものの、縦・横で見ればその行・列にしか入っていないことが分かるため、他の場所の候補を消すことができる」

という手法を第三フェーズとして実装をすると、出てくる問題の難易度が跳ね上がる（ような気がする、個人の感覚です）ので、一旦ここで止めてあります。

不完全なソルバーでは全ての問題を解けないので、続きの探索コードを普通に書く。

折角人間的なソルバーを実装したので途中まではそれで解いて、これ以上進まなくなった場合に全探索に移行する、というような実装をしています。

これが良い感じの枝刈りとして機能したようで、単純な Backtracking アルゴリズムのソルバーよりも性能が良い (ちゃんとベンチ取った訳ではなく、感覚ですが…) ものが得られました。

実際に人間が解く場合も、上級テクニックを知らない、あるいは気付けなかった場合、候補が 2 個くらいまで絞られたところから仮置きして矛盾が出るか調べるということをすると思いますが、それに近い形になったようです。

また前述の通り、全探索とはいっても今回の用途では「解答が真に 1 つであること」を確かめるだけで良いので、2 つ以上見付かった時点で打ち切るような実装もします。

やっと数独の問題を生成できる。

という訳で、数独の解答の盤面を生成し、ランダムに穴を空け、ソルバーに食わせて解答が 1 つしかないことを確かめる、という手法で問題を生成できます。

難易度の調整どうしよう…。

パズルゲームとして成立させるには、難易度調整が必須ですね。

個人的な所感ですが、問題の生成段階で人間的な不完全ソルバーを使えば、難易度の調整は空きマスの数の指定のみで十分であろうという感じです。

というのも、 問題の難易度は必ずしも空きマスの数だけでは評価できない とした先行研究がありまして、確かに感覚的にもその通りかなという感じなのですが、逆に言えば単純な解法で解けるものに限定すれば空きマスの数だけで難易度の判定としては十分ということです。もちろん厳密な議論ではありませんが、まぁここはアカデミックな場ではないので…。

という訳で色々と調整した結果、不完全ソルバーで解ける問題に限定した上で、

  • 初心者レベル
    • 空きマス 28 (初期配置 53)
  • 初級レベル
    • 空きマス 34 (初期配置 47)
  • 中級レベル
    • 空きマス 44 (初期配置 37)

という調整に落ち着きました。

逆に難しい問題を生成するにはどうする？

ここで他のアプリのレビュー欄や SNS の声などを調査していくと、「マジで難しいテクニックが要求される問題」と「難しく見えるけど根気強くやれば上級テクニックを知らなくても解ける問題」あたりの難易度の設定が良いんじゃないかという結論に至りました (個人の感覚です)

「難しく見えるけど根気強くやれば上級テクニックを知らなくても解ける問題」の生成について

方針としては、不完全ソルバーで解ける範囲で限界まで穴を空ける、という形になります。

  1. まず空きマス 40 の不完全ソルバーのみで解決可能な問題を生成する。 (40 前後であれば適当に穴を空けても大抵の場合は不完全ソルバーで解決が可能という経験則による)
  2. 不完全ソルバーのみで解決可能な状態を維持しながら、深さ優先で限界まで穴を空ける。
  3. もし空きマスが 56 に満たなければ問題生成からやり直す。 (56 にしたのは、この手法で生成し得る問題は概ねその辺りまで行くことが多いが、たまに外れ値が出てくるのでそれを除外するため。これも経験則による)

という手法に落ち着きました。

経験則が続く感じで申し訳ないのですが、手元で数万程度の問題を生成して試したところ、空けられる穴の最大の数は解答の初期配置に強く依存しているような挙動を示したんですよね。ということで空きマスの数が 56 に達するポテンシャルがある解答の盤面を生成し直す方が良い結果が得られた感じです。

「マジで難しいテクニックが要求される問題」の生成について

上記の手法から使うソルバーだけを変えてやって「人間的な不完全ソルバーでは絶対に解けないけど、全探索すれば出てくる」という条件を付けて問題を生成しています。

しかしこれはまだちょっと問題の難易度ガチャがあることは否めず、割と簡単に解ける問題が出てくる場合もあれば、仮置きしないと解けないという界隈的には邪道な問題が出てくる場合もあるようです。これは今後の課題ですね。

穴を空けられる数の限界ってどの辺なんだろう。

数独の問題として成立する最小の初期配置は 17 個 (空きマスにすると 64 個) であることが 先人によって確かめられています。

が、 64 個も穴を空けられる盤面なんて全然出てこないというのが実態です。やるなら戦略的に生成する必要があるでしょう。

手元にある ProblemGenerator を一晩回したときの調査メモがコメントに残っていたのですが、

// requiredBlankCount: nil で 9000 個生成して blank の分布を見る
// blank: 50 => ... 0 ( 0.000 %)
// blank: 51 => 1     ( 0.011 %)
// blank: 52 => 7     ( 0.077 %)
// blank: 53 => 87    ( 0.966 %)
// blank: 54 => 520   ( 5.777 %)
// blank: 55 => 1731  (19.233 %)
// blank: 56 => 3053  (33.922 %)
// blank: 57 => 2525  (28.055 %)
// blank: 58 => 912   (10.133 %)
// blank: 59 => 160   ( 1.777 %)
// blank: 60 => 4     ( 0.044 %)
// blank: 61 => 0 ... ( 0.000 %)

こういう感じの分布になるようです。問題を 9000 個生成して、 60 マス穴を空けられたのがたったの 4 つということで、かなり厳しいですね。

もしお手元の iPhone や Mac で 64 個の穴が空いた問題が生成されたらマジでラッキーです。是非お気に入りに登録しておいてください。

締め

正直アルゴリズム部分とか、難易度調整部分の実装や調整って 1~2 週間くらいで良い感じになったんですよね。それで完成した気になってしまったんですけど、そこからの方が圧倒的に長かった…。アプリ開発は辛いですね。