slitherlinkのためのブログ枠
JUGEMブログで開くこんばんは 関口です
とりあえず目次をつけました
はじめに？
slitherlinkを解くコードの解説記事を書くと宣言してしまっていたので書きにきました。正直書きたいかと言われると全くそんなことはないです。でも、約束を守らない人間は嫌いなので、自分を嫌いにならないために書きます。
結論から言えばこれです。
正直自作のコードはクソ長いし見るに耐えないのでそこらへんの詳細な解説はしません。制作に関する話をした方が面白いと思うのでそこら辺を書きます。slitherlinkを解くコードの制作の解説記事ですね。そもそもslitherlinkってなんやねんって人はここをみてください。
まず、このコードを作った原因はボブにあります。制作を始めた2024年2月当時、ボブはslihterlinkというパズルゲームにハマっていました。oaksに行った時や練習前後などこれでもかというくらいやっていたので、興味を持たずにはいられなかったわけですよ。実際やってみると結構面白いと。2023年度のAセメスターにC言語を学習していた自分は思うわけです。これプログラミングで解けるな。と これが大量の時間を溶かすとも知らずに。
2023年当時はまだ生成AI黎明期で、確か大学が声明を発表してはいたもののGPT-3程度のモデルしかなく、生成AIはまだとてもすごいおもちゃ程度の位置付けだったと思います。なので、プログラミングをするにしても初心者ですらAIよりも自分で書いた方が早いという時代です。多分。
そんな中でコードを書きました。削除した関数とかを含めればざっと1万行程度のコードを書いたと思います。相当な時間もかけました。そんな感じで完成したのがmy_solver-ver0.cです。でも、このコードは30×25程度の問題は解けても、それ以上大きくなると解けません。つまりザコです。 コードが書けてもアルゴリズムやデータ構造を学ばないとslitherlinkくらい複雑な問題は解けないわけです。
そんでもって、引退前にこのブログの枠を確保しておいたので、卒論が終わった頃に制作をしたのがBob's_idea_solver.cです。これは千行くらいのコードで、解がある問題は全て解けます。時間も多分6時間くらい？で、できたと思います。少しAIの力は借りましたが。この2年間で正しいコードを多分10分の1くらいの労力と時間で書けるようになったわけです。まあ要するに圧倒的成長を感じていたわけですよ。
ふと疑問に思って、生成AI(Gemini 3.1Pro) に「slitherlinkを解くコード」という要件だけでコードを書かせてみたわけです。翔も言う通り、AIは異常なまでに凄いので。そしたら40秒くらいの思考と生成で解説文つきで完全なPythonコードを生成しやがったわけです。
萎えました。とても萎えました。や、まあ、Pythonだし、そんな高速な動作しないしな。とか思ってましたが、C言語で自分のアイデア込みでコードを書かせたら自分のコードの10倍くらい高速なコードも書いてくれました。🤗
👉これめっちゃ**世界変わってる**
って感じです。コードを書くと言う分野においてはもう人間は勝てる余地なんてないんですね。結構割と真剣にITエンジニア的な職業を視野に入れていたので、これはしんどいと思いました。人間ができることは設計と、コードに責任を持つことくらいなわけで、コードを書けるということ自体に全く価値がない時代になってしまったわけです。自然言語が超高級言語としてプログラミング言語界に爆誕したと言うことなんでしょう。
クソみたいな時代ですね
誤解がないように訂正しておくと、コードを書けることには意味はなくなると思いますが、コードを読んで理解できることの価値は依然残ると思います。あと、電子メールが普及しても郵便局は潰れなかったし、スマホが普及しても携帯電話会社は潰れなかった(端末だけ売る会社はたくさん消えた)ことを考えると、ITエンジニアも生き残る層はあると思います。でも大きな変革があるのは間違いないですよね。めんどい
圧倒的成長を実感してそれがほぼ無に帰した話はここまでにして、以下では諸々説明をしていきます。プログラミングとかくだらんと思う人は読まないでいいです。マジで。ただ、slitherlinkはまあまあ面白いので、そこの解説はみてもいいかも。
slitherlinkって何？
slitherlinkの基本ルールは
1.点と点を結んで、ひとつの大きな「輪っか」を作ること。
2.数字の周りには、その数字と同じ数だけ線を引くこと（「3」なら周囲に3本）。
3.線は交差したり、枝分かれしたりしてはいけない。
と言う3つです。
以下に実際に遊べるようにしておきました。
こいつの実装をするにあたって、JUGEM(このブログのサイト)ではHTMLとCSSの大抵の操作はできるけど、Javascriptは厳しそうなことを学びました。中括弧が自動変換されちゃうんですよね。なので、Code Penと言うサイトを今回は使いました。今後ブログでJavascriptを使いたい人は是非どうぞ。
あと、この中身のコードは生成AIが100％作ってくれてます。やっぱすごい。
slitherlinkを解くには定石を知っている方がやりやすいです。wikipediaに少し載っていますが自分で見つけるのも楽しいので、調べすぎないことをお勧めします
簡単なやつを一つだけここに載せます。3が隣り合う場面では以下が確定します。
|
×
|
||||
| 3 | 3 | |||
|
×
|
||||
バツは線が引かれないことが確定しているところです。なんでなのかは考えてみてください。
実際に遊べるようにしておいた部分でもこの定石が使えます。
ここら辺を前提にして、コードの簡単な解説をしていきます
slitherlinkを解くコード解説
一応反省を込めて解説していきますが、コードの具体的内容にはほぼ立ち入りません。知りたければコードを生成AIに投げつけて聞いてください。
my_solver-ver0.c
これは私が割と初学者の頃に書いたコードです。
基本的な考え方として、まず、slitherlinkを「線を引いて輪っかを作る作業」から「各マス（数字の入る正方形）が輪っかのの内側か外側かを判定する作業」に読み変えたと言う点が大きなアイデアとしてあります。これは考えるべき変数が減るという点で優れていると考えたためです。実際、マスが2×2のとき、線の数は12本です。線を引く引かないと言う2状態を12箇所について探索するのと、マスが内側外側という2状態を4箇所について探索するのは直感的には後者の方が容易そうです。
ですが、実際には、答えとしてあり得る形（輪っかの形や、内側の配置）を探索します。答えとしてあり得る形はどちらに見方でも同じ数しかないので、両者に探索の範囲から考えてどちらが優れているというほどの差異はないとわかります。逆に、slitherlinkで利用できていた知見を、内側か外側かという問題に読み替えないといけないという点、状態数が少ないために表現力が低い（例えば、ある箇所に線を引くことが確定しているということを表現するのに工夫が必要）という点で、内側か外側かという見方は大変利用しづらいものだとわかります。
そんなことには気づかないで、コードを書き進めてしまったものがmy_solver-ver0.cです。このコードの特徴としては人間の操作を非常に安直に実装し、ある箇所に線を引くことが確定しているということを表現することは諦めています。コードの流れとしては、読み込み→定石で解く→定石だけで確定しなかったところを深さ1の仮定をおいて考える→それでも確定しなかった部分を総当たりという感じです。褒めたい部分は、深さ1の仮定を置く際に、内側、外側のどちらの仮定を置いたとしても同じ結論に至る部分を確定とするという推論を用いていることです。ダメな部分はたくさんあります。一つ取り上げるなら、同じ計算を繰り返しすぎているという点です。あと多分コードが正しくなくて解けない問題があります。
Bob's_idea_solver.c
これは私が最近書いたコードです。
基本的考えは一緒ですが、線を引くことが確定していることを表現する方法としてボブの考え方を利用しました。簡単に言えば、ある箇所が内側ならそれに連動して内側・外側となるマスをメモしているという感じです。これは、同じ計算を繰り返さなくて良くなる工夫として優秀です。メモをする際に、union-find木の考え方を利用しました。これはグループ分けを高速に処理するのに使えるアルゴリズムです。
問題は全て解けますが、輪が一つだけになるか、という判定のために盤面全体を参照しているためやや遅いです。また、ディープコピーを何度も行うのでメモリ効率も悪いです
ai-generated.c ai-generated_from0.py
これらはAIに書かせたコードです。
両方とも元の、線を引くかどうかという思考のままでコードが組まれています。ai-generated.cは自力で出せたであろうコードの中で一番正解のものです。このコードの特徴としては、定石を一切利用していないという点です。深さ1の仮定で、どの仮定でも共通する部分というのが定石になるため必要ないということです。逆に自作コードで定石の実装が必要だったのは盤面での表現力の低さが原因なので、線を引くかどうかという思考の方が実装が容易なことがここからもわかります。基本的構造は深さ優先探索なので、もう少し工夫をすればさらなる高速化も望めます。
ai-generated_from0.pyは、Z3 SMTソルバーという高度な定理証明器を使った実装です。このコードは100行程度で非常に簡潔なので、可読性が桁違いにいいです。Z3 SMTソルバーについて少し解説すると、CDCL（Conflict-Driven Clause Learning：競合駆動節学習）というアルゴリズムが使われていて、探索途中で矛盾にぶつかった際、「なぜ矛盾したのか」を数学的に分析します。そして、その矛盾を引き起こした根本原因を新しいルールとして記憶し、今後の探索空間から無駄なパターンを削り落すといった感じです。要するに、定石になる部分や、確定する線を特定しながら探索を行うということですね。実際にはCDCLを行うSATソルバーというものは真偽値の利用しかできないため、論理演算などを処理するための専用アルゴリズム群がZ3 SMTソルバーには搭載されているようです。当然、ai-generated.cと異なり、slitherlinkに特化した構造やアルゴリズムを持っているわけではないので、自作のBob's_idea_solver.cよりも10倍くらい遅くなります。
まとめ
自分で書いていてもよくわからんくなってきたのでここはAIに任せます。
ざっくり一言でまとめると、**「AIが生成した2つのコードが圧倒的に優秀で、独自ロジックを詰め込んだ残りの2つは設計に無理がある」**ということです。
用途に合わせて、以下のどちらかを選ぶのが正解です！
とにかくバグなく、賢く解かせたいなら：
Pythonの ai-generated_from0.py がベストです。数学的な証明ツール（Z3）に丸投げする賢いアプローチで、コードが短くメンテナンスも超簡単です。
計算速度を極めたい、アルゴリズムの勉強がしたいなら：
C言語の ai-generated.c がベストです。パズルを解くためのプロレベルの設計（状態の巻き戻しや高速なループ検知など）が綺麗にまとまっています。
選んではいけないもの：
Bob's_idea_solver.c と my_solver-ver0.c は、人間がパズルを解くときの「この数字の時はこう線を引く」というルールを気合と根性で全部コードに書き出そうとしています。その結果、コードがぐちゃぐちゃになり、少しでも難しい問題が来るとパンクしてしまう状態です。
自作コードは選んではいけないもの判定でした。えぐい
ちなみにBob's_idea_solver.c は難しい問題に対しても高速に動作するのでパンクはしません。利用しているgeminiにはPython以外のコードを実行する機能がついていないので、そこら辺の判定がまだまだ甘いですね。
本当は平井さんの「どうしようもなく今を生きてる」を超える大作を生み出そうと思っていたのですが、1万字というのはなかなかしんどいですね (このブログは5,000字超えくらい) 自分の卒論ですら約19,500文字だったので卒論を半分書き直すようなものです。ただ書くなら簡単ですが、この内容のまま読む価値ある文章にするのはおそらく不可能です。
見た目のリッチさはどんな過去作にも負けてないと思うのでそこで満足しておきます。
では最後に
今回のクソゲー
引退ブログにこのコード解説を書くわけにもいかないなと思って枠を用意しときましたが、クソゲー解説も最後にやる機会ができてよかったです。とはいっても今回は、slitherlinkを紹介します。以下のリンクは僕が使ったやつです。slitherlinkは商標が取られているみたいなので、囲いゲームとかいう謎名称になってますね。このゲームは僕の時間を奪っていったので紛うことなきクソゲーです。ハイ。プログラミングの練習させてくれてありがとう。でも大方水泡に帰したよ。
これは2026年3月2日に公開しました。引退ブログは3月7日までに書く予定なので、それまでに気づけた人はすごいです(多分Slackでの通知が行かないので)。引退ブログより前に気づいた人にはプロテインを差し上げます。