数独を大人げなく解いた話
この記事はKumano dorm. 2nd Advent Calendar 2022 - Adventarの記事です。
OP向けは寮祭とは関係ないそうなのでこちらに
はじめに
寮祭、今年も土日に加え、平日も半分休みを取って月曜火曜の企画に参加させていただいた。大変お世話になりました。
さて、百花繚乱の寮祭企画の中で数年前から恒例となっている、数独を解く企画がある。今年は11/29の夜から11/30の明け方くらいに時間をとっての開催であった。主催者はこの企画に備え、常日頃から数独にとてつもない時間を費やし、数独力を高めているらしい。
筆者はというと、企画開始（23時くらい？）からは少し遅れて、0時ごろに参加。初級問題と名のついた16*16の数独の問題用紙と鉛筆を受け取った。
企画としては、初級問題、中級問題、みたいな感じで数問用意されており、それらを次々に解いていき、解けたタイムを競う方式。最初に渡された問題も、初級といいながらしょっぱなから16*16で、そこそこ処理量はありそうなのだ。参加者にOPは筆者一人。まあ初級問題くらいはスルッと解いて、サクッと修士卒のパワー見せちゃうかーというテンションで参加した。
ちなみに主催者は企画開始から早々に一時間くらいで初級問題を解き終わり、さらにもう一時間くらいで中級問題も終わらせていた。負けてらんねえなこりゃ
参加した方ならお分かりですね。
解けない…
解けない！！！！！
この数独、まったく一筋縄ではいかない代物だった。主催者以外に、誰も解けたという声をあげないのである。
初級編である、というのはさすがに看板に偽りありと思われた。解けたタイムを競う、とかそういう話では実際のところ全くなかった。
参加者は体感で延べ30人ほど、明け方までトライし続けたのも10人程度はいたと思うが、主催者を除いてクリアしたのは、二人がかりで議論を重ね6時間ほどかけて解いた一組。ソロプレイでクリアしたのは誰もいないという惨状であった。
ミスによる矛盾を発見するたびに叫び声が上がり、問題用紙を新しいものへと交換する様はそれなりに盛り上がっていたが、それでもだんだんと参加者は脱落していく、という感じ。
一時間で解いた主催者は何者だったのだろうか。後から考え直してみれば、まさに圧倒的であった。
まあ言い訳の要因は色々あるが（たぶん全員めっちゃ寝不足とかね）、それにしたって一応最高学府の学生や卒業生が雁首を揃えてこれはあんまりである。
筆者も最後まで頑張ったものの、問題用紙を三枚消費した挙句、ああ無念明け方7時ごろに撤退するに至った。
その帰途の神宮丸太町駅において、本企画をpythonで無理やり解いたろう、という暗い情熱が生まれた。受けた屈辱をネタにして返す、その闘いの記録を書き起こしたものが本記事である。
問題はこちら。以後の文章の内容は問題のネタバレになるため、先に解きたい方は気を付けてください。
状況整理
本記事を書くにあたっての前提と方針、注意事項などをここで整理しておく。
・筆者のプログラミングのスキルとしては、たまにc++でatcoderをだらだらやっているが、現在は緑の中ほどであり水色に上がれる見込みは今のところないといったところ。pythonは触り始めて半年ほどであり、ほかの言語についても独学なので、用語の使い方などが怪しい。
・・本記事の中には、こういう風に実装しました、みたいなノリでコードのスクショを貼っている部分もある。プログラミングに興味がない方は、適宜読み飛ばしてください。
・始めるにあたって、数独をプログラミングで解く方法をいくつか調べたが、総当たりをベースにしたアルゴリズムで、問題を入れたら次の瞬間には自動で答えをポンと出されてしまっては味気ないな、という風に感じた。そのため、ミスを生むのを防ぐ道具としてpythonを使用する雰囲気を目指した。
・・左上から右下まで一回探索することを、走査と呼ぶことにする。その走査の部分を拡張し、走査を繰り返せば問題が解けるというイメージ。
・この文章を作成することを念頭に置いて作業を開始した。作業の過程でスクショと感想を書いた文章を記録している。
・それに加えて、解くのにかかった時間を競うというもともとの企画の方針を尊重し、各工程でかかった時間もざっくり記録した。
・目標は①この問題を解いて鬱憤を晴らすこと、②多少なりともpythonを触る機会を作ること、③アドベントカレンダーのネタにすること、の3点。
・諦めたらそこで試合終了。安西先生が決めたルールなので当然。
・ポケモン（スカーレット）とスプラトゥーン3により多忙であったため、作業は主に通勤時間で行われている。そのため、時間の記録は大変おおまかなものである。しかしながら作業の順番については、実際に辿った経緯を崩さず記載している。
・熊野寮アドベントカレンダーに投稿する都合上、大学生との年齢差を誇張した表現を含んでいるが、筆者はまだ27歳なので若い。人生はこれからである。
それではやっていきましょう
戦闘開始
基盤部分の作成
まずは問題を二次元配列として入力。そして、16*16の配列を渡したら画像を表示させるプログラムを組んでいく。
見づらくて、問題の入力部分になんか意外と時間がかかってしまう。もっといい方法あったかも。
16*16の格子の画像を準備し（エクセル方眼紙をスクショするのが一番早かった）、その上に数字を描画して、表示させるという簡単な形式。
ハイこんな感じ。浅学ゆえ画像加工用のライブラリとかのレベルからググって進めているので、ここまで50分くらい。数字がマスの中央でないとかいろいろあるが、こっちはタイムを競っているので細かいところは気にしていられない。
せっかくなので、一回走査して、新しく数字が入った場所は赤い文字にしたいな、とかも思ったので、書式用の配列も準備し、色を付けよう
このあたりはpythonの基本的な知識がないことが露呈し苦しい。
色を付けるあたりでちょっと苦労するも、まあ開始から一時間半くらいで各種の処理を整えた。細かいIOを考えるのが面倒だったので、while(True)で一生走査が続くようにし、デバッガとbreakpointを駆使して問題を解いていくことにした。
while文の中では、書式をリセットし、問題を走査し、そして描画する。
二つ目の走査部分を拡張していけば、問題が解けるはずである。
10分もかからず、とりあえず書いた（たたんでるけど）
書いたのは、「数字が入っていないそれぞれのマスについて、そのマスに入りうる数字をリストアップし、それが一つしかなければその数字を入力する」、という仕組みである。
まあ最初なのでこんなもんでいいでしょう。
早速回してみよう
トライ1
おお
なんかそれっぽいね
はいはいはい。
走査を続けて赤い数字がでてこなくなったら、新しく数字が増えていないということですね
そうなる前にすべて埋まってほしいところ。
赤い数字が出てこなくなった。以上で詰みです。
ご高覧ありがとうございました。
トライ2
とはいかない。ここまで開始から2時間くらいかかっている。
しょうがないので走査4回目の画像をじっと眺めてみると、左上の太枠、12の下には3しか入らないことがすぐわかる。そこに3が入らなければ、左上の太枠の中に3が入る場所が他にないためだ。
なるほど…人間的には結構自明だが、これはさっきのメソッドだけでは入らないらしい。
というわけで、とりあえず次に、各太枠で、入っていない数字が入りうる場所が一つしかなければそこを確定させるコードも書く。これをメソッド②と呼ぶ。
できた（コードのスクショ取り忘れた）
いざいざ
おお
左上太枠の3もちゃんと入っている。
一回の走査で入るマスが格段に増えた。これは効率的にもいいですね。
ちょっとここで立ち止まって、表示部分をいじることにした。
メソッド①→そのマスに入りうる数字が一つしかないなら、数字を入力するメソッド
メソッド②→太枠の中で、ある数字が入りうる場所が一つ以外ないなら、数字を入力するメソッド
これらのそれぞれで、色を分けてみる ついでに文字も大きくした
（①→オレンジ、②→ピンク）
おお なんかすごくいい感じ
ぱっと見うまくいっていますね
メソッド②を作るのに1時間ほど。続けていってみましょう。
3回目ですでに嫌な予感がする 新規で入った数字が一個しかないので止まっちゃうかな？
3回目で止まっちゃうかなと思ったが、そうでもないらしい 新規の数字がガコっと増えた
ちなみに、この辺のコメントも、実際に作業しながら書いている。
7回目でも、まだまだ行けそうですね。すげえなこりゃ
入る数字がまたすごく増えた。人間が解いてても、「うおーここが決まったから連鎖でどんどん行ける～～～」みたいなフェーズがあるが、機械にやらしてもそれはそうらしい
左上から順に走査しているので、右下のは相対的に後になりやすいという仮説はある。つまり右下が増えてきたら終わりが近いような気もする。
でもまだ一回の走査で7個空いているので、まだいけそうか？
ここまで来ると、あれ？これで最後まで行けちゃうのでは？となる。なーんだ、チョロいか？？
あれ…マジでこのままいけるやん！
科学の力ってスゲー 空きマスも残り少ないし、ここまできたら全部埋まります。あとちょっとです
んんん？？？？？
早とちりはよくないのでもう一回走査してみる。
空きマスがあるのにもかかわらず、赤系の色の数字が消えてしまった。
しかし、こんなところで止まるはずはない。
これは、もしかして矛盾している……？？？？？？
確かによく見ると、空いてるマスはすべて矛盾している…
なんで？？いつから？こんなになる前に、なぜ止まらない？？
メソッド②を実装して、ぐにゃあまで30分。
単純なメソッドしかないのに、矛盾するはずはない。
つまり原因はわかりません。
ご高覧ありがとうございました。
トライ3
…わかった！！（＋30分）
右下の太枠に、変な13が入っている！！
自分の字を、問題の字と見間違えたんですね しかもどうやらそれが間違っている！！
はいリトライ
はいはいはいという感じ。スクショを18回も取ったりしたトライ2が全部無駄だったのか、という気持ちを必死に振り払う。まあさっきいいとこまで行ったし、これでワンチャン解けてもおかしくない
え…？止まった…？
右下の13のおかげで右上の11が早々に確定していたが、今回はそれもない模様。さっき解決間際まで行ったのは、普通に砂上の楼閣でした、という話
ちょっと舐めてたね…
が、まあ今は太枠についてしか②を実行していないので、これで解けないとみなすのは時期尚早感がある。
仕方がないので、とりあえずメソッド②「ある太枠で見たときに、足りない数字が入りうる場所が一つしかなければ確定」を拡張し、②-2と②-3を作成することに。
②-1「ある太枠で見たときに～
②-2「ある行で見たときに～
②-3「ある列で見たときに～
果たして。
トライ4
後で見直すと冗長だったので割愛するが、メソッド②-2と3を実装するここの段階で結構バグった。以下バグとの闘いの歴史だけ載せる
結局②-2,3を作るのに1時間ちょいかかっている。合間合間に文章も書いてるから多分90分くらい。
まあ結果的には完成したのでヨシ。トライしていこう。
この時点では②-3も実装されているが、オリーブ色の数字はない。まあ今後出てくるでしょう。実際、①→②-1→②-2→②-3の順で埋めているので、②-3で引っかかるはずのものは、その前に他の走査方法で引っかかってしまうという事情もあるのかもしれない
EEEEEEEEEEEEEEEEEE
これは…止まってる？
何かの間違いかと思い、人力で①→②-1→②-2→②-3を実行してみたが（30分）、やはりプログラムは正しい。つまりアルゴリズムが間違っているというか不十分。
ガチでか…
トライ5
こちら不退転の覚悟であるため前を向くと、ここからの方向性は主に二つ考えられた。
①マスに入りうる数字の候補を記録していき、それをベースに二国同盟法とか、x-wing法とかそこらの上級アルゴリズムを実装する
(参考：数独の解き方【上級編①】「２国同盟」法 | 数学の面白いこと・役に立つことをまとめたサイト (analytics-notty.tech))
②あるマスについて仮定して、背理法的に進む
①はバグをとったりする作業がやばそうなので、クールに②を選択。以下これを「オトナの方法」と呼ぶことにする。
ここまでの道のりで、簡単な走査にかかる手間は格段に減っている。頭のよさそうなアルゴリズムを使わずとも、ゴリゴリ仮定してどんどん試行錯誤していくという解き方が出来るようになってるんですね。
大人に逆らうとこうなるんだぞ！！！！！？？？！！！ということを見せつけていきたい。
実際には数独ではやらん方がいい汚い解き方だが、結果がすべてなんでね。
ここまでは、通勤電車などで細切れに作業してきたが、この方法をとっているのは金曜の夜であった。家で画面を開きながら、今日完成させてやろう、という気持ちが芽生える。
さて、単に背理法的に進むといってもよくわからないであろう蒙昧な読者のために、デモンストレーションとして、トライ2で明らかになったミスを使って説明していく。家でがっつり作業する気分になったので、準備運動といったところですね。
あの後、トライ3,4でメソッドが増えているので、その状態でもう一回回してみる。
矛盾することはわかっている。いざいざ
色とりどりでいいですね。埋まるスピードは速いが、それでも面倒なので途中を割愛。
ここでフィニッシュ。ということは矛盾している。ということは右下のあそこは13ではない、と分かる。これが背理法であり、これを繰り返していけば理論上解けますね（たぶん）。
これがオトナの方法ってやつです。
ここでいったん、エラーが起こった時にわかりやすいようにさらに表示部分を改造することに。読者を意識していてえらい。
①のメソッドは、各マスについて、入りうる数字をピックアップして、それが一つなら入力するという風に実装している。
②のメソッド3つは、すべて各太枠・行・列について、入ってない数字が入りうる座標をすべてピックアップして、それが一つなら入力する、という風に実装している。
つまり、①で入りうる数字が0個だった場合、そして②で入りうる座標の個数が0個だった場合は矛盾していると分かる。
見た目にわかりやすいように、それらの矛盾があった場合は画像の色を反転させることにした。
話を戻して、右下のポイントに入る可能性があるのは、3,9,10,11,13の5種類。意外と多いな…と思いつつ、しかしながら話の流れもあるので、あそこをスタートにする方針は変えないままでいく。
それぞれ入れてみて、走査を回してみて、
①色が反転してしまったら、その数字は間違いである
②色が反転せずに、黒青以外の数字が出てこなくなったら、そこからさらに仮定が必要
ということになる。早速やってみよう。
トライ5-仮定1（右下太枠）
3を入れてみる
新規の数字が少ないと普通にちょっと悲しくなる
あーあ。ここからさらに分岐するための仮定が必要。
もちろん3が正しい道のりであるパターンも考えられるが、逆に、候補となる数字全部が、一回の仮定では矛盾をあぶりだせず、こうなることも考えられる。
3のまま深堀りする前に、ちょっと一旦別の数字で試してみよう。
次は9。
おお！わりとすぐ矛盾。サクサク進んでほしいですね。
続いて10。
3回目でアウト。いい調子。
最後に11。
しょっぱなからアウト。ちょっとびっくりした。
まとめるとこんな感じ。13はかなり深い枝だったようだ。まあ成功したのが一つに絞れたのでまあよし。ここからさらに分岐していく。
トライ5-仮定2 左上太枠
5択とかはちょっと面倒なので、最初から2択くらいのところで仮定を置いていきたい。盤面を眺めるとすぐ見つかった。左上の太枠、空きは2と15しか入らない。
まずは左2右15から。
手ごたえがすごい。いつ解けてしまうか分からないとあって、緊張が高まる。
あれ、なんか埋まるマス少なめだな…
ここでまたも分岐ッ！！肩透かし感がすごい。この時点で、オトナの方法にシフトしてから1時間半が経過している。
一旦、右2左15を試行。
おお。二択くらいだとすぐ確定していいですね
再び2択になってる場所を目視で探す。
トライ5-仮定3 左下太枠
左下の太枠に着目すると、太枠の一番右の行にはすでに15が入っているので、15が入るのは二択となる（11の下：左、8の下：右）
ここでいきましょう。
15が左のパターン
今度こそ！
4回目でストップ。
15が右のパターン
3回目でエラーが出たため、15は左で確定。しかし、一回の仮定で進む距離が短すぎる。
再度二択になっている場所を探す。しかし疲れてきた。もっと一つ仮定を置いたらがりがり進むもんだと思っていたので、期待との差で消耗が激しい。
トライ5-仮定4 左、上から二つ目の太枠
左の上から二つ目の太枠で、一番左の行に入るのは10と16の二択になっている。
そうと分かればつべこべ言わず手を動かす。こちとら社会人なのでね
おお、じゃあ16上10下が正しいな。一応やっとくか
あれ…？
ちょっと眠くなってきていたところから、一気に頭を殴られたような衝撃を受ける。
二択ということは、どちらかが間違いならどちらかが正解ということです…（進次郎）
…いやこれね、凡ミスで、仮定3のときに15は左で確定したのに、右に入ったままになっているんよね。戻し忘れ。
すぐに発見し、修正。
10が上はアウト。これで10が下もアウトになったらどうしよう、と戦々恐々としながらトライ。
ここでストップ。なんだこれ、全然進まねえじゃん！！！！
まあやむを得ないので、粛々と進めていく。昼間に8時間労働しているので、その辺の大学生とは体力が違うのだ。
トライ5-仮定5 左から3行目
左から3行目の空きマスは二つ。選択肢は9と15。やっていきます。
3回目で分岐。15上のパターンもやってみる。
入る数が減ってくると、「ああ、アウトにならずに終了して分岐が必要になるんだな」と感じ取れるようになってきた。しかしここでアウトになってくれないと、仮定5はどちらも分岐してしまう。頼む、矛盾してくれ。
やはり矛盾せず終了。はあ
いつのまにか遠くまで来たね
新たな景色までは見えてないけど…
全然気持ちよくなれない なんなんだこれは 早く気持ちよくなりたい。
トライ5-仮定6 一番上の行
仮定5はいったんなかったことにして、仮定6を模索。
一番上の行で入っていないのは（9,11,13）の3つであり、右上の太枠の一番上の行には(11,13)のどちらかしか入らない。
なんか選択肢が仮定1に似てて、ロングランできるんじゃないか？と期待を抱く。オトナの方法とか言い出してから2時間強が経過していた。
サクッと否定されてくれていいですね。ということは仮定6の右上は13で確定と思われる。エラーが出たらあきらめようかな、という思いも心をよぎる。
右上13でトライ。
おや…？？
なんだかこれまでになく雰囲気がいい。埋まる数字が多い。止まる気配もない。これは結構進むのかもしれない。
あれ…？？クリアが…ついに来たか…？？
！！！！！！！！！！！！！！！！！！！！！来た！！！
すべて埋まって！！！る！！！！！！！！！！！！
いえええええええええいいいいいい
きもちいいいいいいい
まさに急転直下という感じ。
オトナの方法へシフトしてから二時間半で解くことができました やったね
まとめ
無事に8時間ほど（たぶん）で解くことができました。
所感としては以下。
・最初の方の作業が結構コマ切れだったのと、この文章を書くことを意識して記録をきちんとしていたことで、脳内で混乱してしまったり方針がぶれてしまうことがなかったのがよかった。
・仮定を置いて進める作業はやめておいた方がいい。今回はプログラミングの手助けがあったからできたものの、矛盾するまで埋めていく作業の部分を人力でやろうとすると人間には処理できない量が発生して詰む気がする。やめておいた方がいい。将棋棋士レベルの処理能力があったら行けるのだろうか…？
・たまにはアウトプットも悪くない。
以上です。ありがとうございました。