1. HOME
  2. テックブログ
  3. ナンバーリンクソルバーを作りたい

ナンバーリンクソルバーを作りたい

私はペンシルパズルを趣味で解きます。ペンシルパズルとは、示された図の問題に対して徐々に答えを書き込見ながら最終的な解答を導いていく形式のパズルで、代表的なものには迷路や、虫食い算、クロスワードパズル、数独(ナンバープレース)*1などがあります。

*1:数独は二コリの商標です。

その中でもとくに「ナンバーリンク」という同じ数字同士を線が交わらない様に全て結ぶパズルが好きで、解くだけでは飽き足らず、自分で問題を作ったりもしています。

難しいものですが、自作の問題のリンクを貼っておきます。
https://bit.ly/2UfeC1W

「ナンバーリンク」はペンシルパズルとしては珍しく理詰めで決まらないことが多いパズルであり、基本的に直観で線を引いていく必要があります。ただ、数独やクロスワードパズルほど人気の高いパズルではないので、ナンバーリンクのみを掲載した本はほとんど見受けられません。

どうしたら多くの問題を解くことができるだろうかを考え、問題を自動生成すれば良いのではと気付きました。検索してみると、下記のサイトで、ナンバーリンクを無限に自動生成できることが分かりました!

https://semiexp.net/games/infinite_numberlink/index.html

これで万事解決!
ナンバーリンクを無限に生成して沢山解くことができて満足です!

…とはならず、この自動生成プログラムを自分で作って、自分の作成したのと見分けが付かないものを作らせたい!思うようになりました。

そこで、どのような仕組みにすれば問題を自動生成することができるかを考えた結果がこちらです。

まず盤面をランダムに生成します。

正解が1つになれば、問題は完成です。そうならなかった場合は、何度も生成を繰り返します。

つまり、自動生成をするためには、まず唯一解かどうかを判定するソルバーを作る必要があるのです。いきなり完全なソルバーを作成するのは難しいと考えたため、まずは「論理的に解けるナンバーリンク」を解くことができるソルバーを作ることにしました。

しかし普段私は企画とコーダーを担当しているため、得意な開発言語がありません。今回は、努力すれば何とか自分が書けそうなjavascriptを使用して書くことにしました。

入出力は必要ないので、盤面はjs内で定義し、consoleで解答を出力することにします。空きマスは0と表現することにしました。


ナンバーリンクを解いていく流れとしては以下の流れを想定しました。

まず、四方の空きマスの数を数えて、空きマスが1マスだったら伸ばすようにしました。


すると、以下のようになってしまいました。

何故、以下の様になってしまったのかを順を追って見ていったところ、「四方のうち1方向だけが空きマスである」のみを見て判定していたため、数字が繋がった後にも条件に合致している場合に数字が伸びてしまっているのが分かりました。

そこで、線が繋がったら(=今いるマスの四方に同じ数字が2つあったら)その数字に-1を掛けて、それ以上線が伸びないようにしました。


これで完成!と思いきや、大きい盤面でやってみると、上手くいきません。

小さい盤面では気付きませんでしたが、長さが5以上になると、線のつながり方によっては途中の数字において、四方に同じ数字が2つある状態になってしまい、そこで処理が止まってしまいました。

そのため、線を伸ばした数字に順次-1を掛けることで、解決させました。

これで、シンプルな手続きで解ける物は解けるようになりました。

しかし、ナンバーリンクの問題のほとんどはこの手続きだけでは解くことができません。

他の方のソルバーを見た感じ、ひたすら仮定をしているようですが、恐らく多重仮定が必要になってきたり、効率の良い仮定をしたりしないと、解くのに非常に時間が掛かってしまうことが予測されます。

今後はゲームツリーについて時間を見つけて調べてつつ、引き続き挑戦していければと考えています。


ファブリカコミュニケーションズで働いてみませんか?

あったらいいな、をカタチに。人々を幸せにする革新的なサービスを、私たちと一緒に創っていくメンバーを募集しています。

ファブリカコミュニケーションズの社員は「全員がクリエイター」。アイデアの発信に社歴や部署の垣根はありません。

“自分から発信できる人に、どんどんチャンスが与えられる“そんな環境で活躍してみませんか?ご興味のある方は、以下の採用ページをご覧ください。

◎ 新卒採用の方はこちら
◎ キャリア採用の方はこちら


この記事を書いた人

おしだ
インターネットサービス事業本部
おしだ

おすすめの記事