C/C++で実装するナンバーリンクパズル ― ランダム盤面生成アルゴリズムの徹底解説

ナンバーリンクとは？

ナンバーリンクは、n×n のマス目からなる盤面を使って遊ぶパズルです。盤面上のマスは「空きマス」と「塗りつぶし（障害物）マス」に分かれており、さらに一部の空きマスには「1、2、3…」という整数が割り当てられています。各整数は必ず盤上の異なる2つのマスに置かれており、プレイヤーの課題は、同じ数字同士を縦横移動のみで進む単純経路（一本道）で結ぶことです。

その際、次のルールを守る必要があります。

• 異なる経路同士は交差してはならない
• どの経路も塗りつぶしマスを通ってはならない
• 最終的に、すべての空きマスがいずれかの経路で埋め尽くされていること

ランダムな問題を生成するアルゴリズム

ここでは、指定したサイズ n×n の妥当なランダムパズルを作る手順を紹介します。基本となる発想は、「まず解答となる経路群を作り、そこから問題を逆算する」というものです。

1. 盤上に、互いに交差しないランダムな単純経路を複数本生成する。
2. 生成された経路の外側に取り残された孤立マスがあれば、それらを塗りつぶし（使用禁止）マスとして扱う。
3. 各経路の両端点と、塗りつぶしマスの一覧を組み合わせて、パズルとして出力する。

このとき、経路と塗りつぶしマスによって n×n の盤面はいくつかの領域へと分割されます。この分割状態を効率よく管理するために、union-find（素集合データ構造）を利用します。このデータ構造は、盤面上の n² 個のマスからなる集合の部分集合を扱うのに非常に適しています。

疑似コード

• 次の条件を満たす2つのマス (a, b) と (c, d) を盤上からランダムに選択する。
  • (a, b) と (c, d) は互いに隣接している
  • どちらのマスも、それまでに生成されたどの経路にも属していない

  そのようなマスペアが盤面全体に存在しない場合は FAILURE を返す。（この (a, b)、(c, d) が新しく作られる経路の最初の2マスになります。）

• (a, b) を含む木と (c, d) を含む木を union（統合）する。
• 現在の経路を延長できる限り、以下を繰り返す。
  • (a, b) ← (c, d) と名前を付け替える。
  • 次の条件を満たす (a, b) の隣接マス (c, d) をランダムに選ぶ。
    • (c, d) は、現在の経路を含め、これまでに生成されたすべての経路に属していない
    • (c, d) が構築途中の現在の経路上にもつ唯一の隣接マスが (a, b) である
  • 条件を満たす隣接マス (c, d) が見つからなければ、経路はそれ以上延長できないためループを抜ける。
  • 見つかった場合は、(a, b) と (c, d) それぞれが属する2つの木を union（統合）する。
• 新しい経路の始点と終点にあたる2つのマスに、端点フラグを設定する。
• SUCCESS を返す。