[パズル]2次元配列に格納された数値、上下左右を探索し合計が10になる組み合わせを探したい

Question

現在以下のようなルールのパズルゲームを制作中です。(C#)

• 縦10マス × 横10マスのフィールドがある（2次元配列で管理）
• 数字がかかれたブロックを１つずつフィールドに設置していく
• 設置したブロックから上下左右につながったブロックの数値を再帰的に合計し、合計10になるブロックを消す

#やりたいこと
フィールド上の数値をチェックし、合計10になる組み合わせを探す。
この時に、2次元配列の縦横のインデックス(位置)のリストを、組み合わせ毎に取得したい。
組み合わせ毎に取得したい理由は、「この組み合わせで10ができた！」という表示を個別に分けてしたいため。

#例
フィールドが以下のような場合

||[0]|[1]|[2]|[3]|[4]|
|--|--|:--:|--:|
|[0]||||||
|[1]| |1| |4| |
|[2]| |2|3|3||
|[3]| | |5|1| |
|[4]| | | | | |
|[5]| | | | | |

得たい結果はインデックスを(x,y)と表現すると、

{(1,1) (1,2) (2,2) (3,2) (3,3)}
{(1,2) (2,2) (2,3)}
{(2,2) (3,2) (3,1)}

という、10ができる組み合わせ毎のインデックスリストを得たいです。

ぷよぷよのアルゴリズムような再帰関数での取得を考えましたが
インデックスの組み合わせを考えると上手く実装できません。
良いアルゴリズムはありますでしょうか。
実装例も合わせて提示していただけると助かります。

Answer 1

自己解決しました。

過去にぷよぷよの探索アルゴリズムは作成したことがあるので違いだけ。
・上下左右に探索していき、その地点にある数値を足していくのは一緒。
・探索を進める時に、座標を履歴で保存する。
・空欄・壁に当たった時に探索を終了するのではなく、履歴の座標の上下左右をさらに探索する。

Comments

[YAmaGNZ]

fanaさんの回答と何が違うのでしょうか？

[fana]

私の回答の文面が簡素すぎた(or etc)ために
結果的にそこからでは具体的なアルゴリズムに結びつかなかった
というだけの話かと思います．

（結果が同じ話だったとしても）別のルートから自力でたどり着いたならば，それはそれで良いのではないでしょうか．
本件の場合は，「書かれた回答の内容を用いて"自己解決"とする」というのとは違う雰囲気の様子に見えますので．

Answer 2

設置したブロックから上下左右につながったブロック

を見ていくだけで良いように思います．

塗りつぶしとか，
マップが升目なSLGの移動可能範囲探索
のような話を検索してみると良いかと．

Comments

[hinatahinata]

回答ありがとうございます。
SLGの移動可能範囲探索アルゴリズムを調べましたが、今回の要件を満たすような実装が浮かびません。
可能であれば、実装例を提示していただけると助かります。

[fana]

それを実装することに個人的に得るものがないと思えるので私はやりません．
単に隣接マスの値を次々に足し算していくつまらない処理です．
スタックか何かに探索状況を積みつつ気のすむまで探索すればよいでしょう．
処理効率とか枝刈りとかは度外視して，まずはやってみればよいのでは．
「合計１０になるパターンを，自分はどうやって探すだろうか？」というのを愚直にコード化すればよいでしょう．

SLGの例で言えば，
マスに書かれた数値が消費移動力だと見立てたときに，
キャラクターが，移動力を全部使切る移動経路を探すことと等価に思えるけど，どうなんでしょう．

[hinatahinata]

要件を満たす処理の流れをご提示いただきたかったのですが
自己解決しましたので閉じさせていただきます。

[fana]

・質問を「自己解決」とする方法が存在するので，適切にそれを行ってください．

・「低評価」をくれた人はその理由をコメントで述べてください．
　例えば，本回答は私としては，（質問者が言うところの）"処理の流れ"の話にたどり着くのに十分な内容を示した回答であるつもりでおりましたが，読み手の立場から見てそれが不足と思えるのであれば，それが低評価の理由に該当します．