C / C ++のナンバーリンクゲーム？

ゲーム-n×n個の正方形の配列を想定します。これらのうち、いくつかの正方形は空であり、いくつかは中実であり、いくつかの非中実の正方形は整数1、2、3、…によって設定されます。各整数はボード上で正確に2つの異なる正方形を維持または占有します。プレーヤーのタスクは、水平方向と垂直方向の動きだけを実装する単純なパスを使用して、ボード上の各整数の2つのオカレンスを接続することです。 2つの異なるパスが互いに交差することは許可されていません。パスに塗りつぶされた正方形を含めることはできません（塗りつぶされた正方形をパスに表示することは許可されていません）。最後に、すべての非塗りつぶしの正方形はパスで埋める必要があります。

アルゴリズム-与えられたボードサイズn×nで有効なランダムパズルを構築するために、最初にボード上にランダムで単純な相互に交差しないパスを生成します。生成されたすべてのパスの外側にいくつかの孤立した正方形が残っている場合は、これらの孤立した正方形を塗りつぶし（禁止）としてマークします。次に、パスの端点と塗りつぶされた正方形のリストをパズルとして提供します。

したがって、最初にソリューションを作成し、次にソリューションからパズルを解きます。パスと塗りつぶされた正方形は、n×nボードを分割または分割します。このパーティションを生成するために、union-findデータ構造を実装します。データ構造は、ボード上のn^2個の正方形のセットのサブセットで処理されます。

擬似コード

• 正方形（a、b）と（c、d）をボード上でランダムに次のように配置します-

  • （a、b）と（c、d）は互いに隣接しており、

  • （a、b）も（c、d）も、これまでに作成されたパスに属していません。ボード全体にそのような正方形のペアが見つからない場合は、FAILURE / *を返します。ここで、（a、b）と（c、d）は、構築される新しいパスの最初の2つの正方形です。 * /

• （a、b）と（c、d）を含む2つのunion-findツリーの結合を作成します。

• 現在のパスを拡張できる限り繰り返します-

  • 名前を（a、b）=（c、d）に変更します。

• -

  となるように（a、b）のランダムな隣接する正方形（c、d）を見つけます

  • （c、d）は、これまでに作成されたパス（現在のパスを含む）に属していません

  • 部分的に構築された現在のパス上にある唯一のネイバー（c、d）は（a、b）です。

• そのようなネイバー（c、d）が見つからない場合、パスをそれ以上拡張できないため、ループを解除します

• それ以外の場合は、（a、b）と（c、d）が属する2つの和集合ツリーを和集合にします。

• 新しいパスの開始時と終了時にある2つの正方形のエンドポイントフラグを設定します。

• 成功を返す