この記事は RECRUIT MARKETING PARTNERS Advent Calendar 2015 の投稿記事です。

はじめまして

現在リクルートマーケティングパートナーズで内定者アルバイトをしている井原です。現在は英語サプリチームにiOSエンジニアとして参加しています。今回は業務のことではなく、個人的にやっている趣味のことについて書かせていただきます。

ナンバーリンク

みなさん、〈ナンバーリンク〉というものはご存知ですか？ナンバーリンクは株式会社ニコリが提供している盤面にある同じ数字同士を線でつなぐパズルです。ルール自体はとてもシンプルなものですが、理詰めよりひらめきが重要と言われていて、数独¹⁾株式会社ニコリの登録商標などの細かな条件を論理的に積み上げていくようなパズルとは趣が違います。

解き方の流れ

上に書いた通り、ナンバーリンクでは「ひらめき」が重要視されるので、コンピューターとの相性は決して良くありません。そのことから、ソルバーの設計も容易ではありません。今回は導入ということで、ナンバーリンクの解の導き方の基本的な考え方のみ紹介します。

盤面のグラフ化

問題を解き易くするために盤面をグラフ化します。また、数字が入っている点を端点と呼ぶことにします。

グラフ化

点: 白マス

辺: 白マスの境界線

解探索の流れ

端点間の経路探索には迷路法のような幅優先探索を用います。今回はA*アルゴリズムと呼ばれる終端までの推定コストを用いた探索方法を使いました。

A*アルゴリズムとは探索アルゴリズムの一種です。経路をノードで表現して、スタートノード（開始地点）からゴールノード（目標地点）までの経路を計算し、この経路が最短であることを保証するアルゴリズムです。そしてスタートからゴールまでの間に障害物があっても迂回する経路を出力します。

しかし、1マスに2本以上の線を引くのは禁止というルールが存在するため、A*アルゴリズムだけでは探索の順番によっては解を出力できない可能性があります。このルールをグラフ上で考えると、グラフにおいては異なる端点間の経路で同じ点を使ってはいけないというルールと考えることができます。

このルールを満たしつつ探索の順番による影響を極力下げるため、Rip-up and Rerouteと呼ばれる手法を用います。この手法は、最初に一時的に重なりを許容してすべての端点間の経路を探索します。その後、他の経路と重なっている端点間の経路をすべて引き剥がして、重なっていた点のコストを高くして経路探索に使いづらくします。その後、引き剥がした端点間の経路を再度探索をします。このフローを経路の重なりがなくなるまで繰り返し行うという手法です。

A*アルゴリズムとRip-up and Rerouteを組み合わせて例題を解いてみます。下の図では点Aで異なる端点間の経路が重なっているので、引き剥がして点のコストを高くして再度探索を行います。この繰り返しで端点間の経路の重なりがない探索結果が得られました。

ナンバーリンクのルールを満たしている解答が得られました。しかし、この手法では下のような例題だと探索が終了しません。

これは問題のオーダーが増えたため、探索中に組合せ爆発を起こし答えが返ってきません。このように、このままの手法だとナンバーリンクのような密度の高い問題には適切ではありません。

外周に着目した経路決定法

これまでの話は単純な経路探索の話でしたが、上記の通りこのままでは密度の高い問題に対応できません。ここでは、前処理としていくつかの端点間の経路を見つけて問題のオーダーを下げる手法について紹介します。

外周に配置されている端点に注目します。その順番を保ったまま、シーケンスを構築します。

外周端点のシーケンス(時計回り)
1 10 10 9 6 2 1 8 7 7 8 4

ここで10 10, 7 7のような同じ数字が連続して並んでいるペアに注目します。このような端点間を繋げてしまっても他の端点間の経路に影響を与えないので固定します。そして外周を更新して、さらに同じ処理を繰り返します。

3. 外周端点のシーケンス
1 6 2 1 13 5 11 4

ある程度繰り返したら同じ数字が連続して並んでいるペアがなくなることがあります。しかし、この例題では更に経路を決定することができます。その方法について説明します。

シーケンスに両端点が含まれている数字に着目します。ここでは1の端点がどちらもシーケンスに含まれています。両端点がどちらもシーケンスに含まれているような経路は全端点を2つのグループに分けるような経路になります。

異なる端点間の経路で同じ点を使ってはいけないというルールがあるため、同じ数字の端点は同グループ内に含まれていないといけません。

ここでは13の端点に着目します。先ほど書いた通り、13の端点はどちらも同グループに含まれていないといけません。13の端点に着目して、1の端点間経路によるグループ分けを考えます。

• [NG] 経路A: 13の端点は外周の下に接しているのでこのような経路は生成できない
• [NG] 経路B: 13の端点が別グループに属するため全体の解が生成できなくなる
• [OK] 経路C: 13の端点が同グループに属する。全体の解を生成できる可能性がある

このことから、右の外周に配置されている1の端点から上のような伸ばす経路が確定します。その後、外周を更新をして今の処理を繰り返し実行すると、1の経路が下の2の端点の下を通ることも同様に確定します。

この例題ではこのような前処理だけで解答を得ることができます。もし経過の詳細が興味ありましたら、ぜひお手元で試してみてください。

まとめ

このようにナンバーリンクはルール自体は比較的簡単ですが、それを解くアルゴリズムの設計は簡単ではありません。実際、上に書いたような方法だけでは問題が複雑になると解くことはできません。今回は導入という位置付けでナンバーリンクの解の導き方の基本的な考え方を紹介しました。もし興味を持たれたらぜひ解き方を自分で考えてみてください。

年に1回、国内でコンテストも開かれてます。様々な人が様々な方法でアルゴリズムを考えているので、そちらも興味があれば調べてみてください。