パズドラのような要素のプログラム？

[RyukyuOB]

こんにちは。

個人的な趣味としてプログラミングをしているものです。

少し行き詰まった事があったので質問させてもらいました。

言いにくいのですが、具体例としてNxNに分割された９枚のバラバラの写真を全探索などを用い、最短で導くというプログラムです。

９枚の画像を数字に置き換えたとして

187
942
356
という画像ファイルがあったら
123
456
789
の順番通りに最短で並べ替えるようにするのが目標です。

動かし方はパズドラのように交換していく形式です。

参考になりそうなサイトや、探索の方法（貪欲法等）があれば解答してくださると幸いです。

因に言語はC/C++/Javaが扱えます。

[RyukyuOB]

具体例としてNxNに分割された９枚のバラバラの写真

N^2の誤りです。

[てすとと]

パズドラのような交換方法というのが2つの要素を入れ替える動作をするというだけなのでしたら
{1,8,7,9,4,2,3,5,6}のデータを{1,2,3,4,5,6,7,8,9}に並び替える作業とおなじですよね.
ということはソートの最短手数を求めることになりますね.
解決にはならないですね、ごめんなさい。

[hide]

パズドラのような交換方法というのが2つの要素を入れ替える動作をするというだけなのでしたら
{1,8,7,9,4,2,3,5,6}のデータを{1,2,3,4,5,6,7,8,9}に並び替える作業とおなじですよね.
ということはソートの最短手数を求めることになりますね.
解決にはならないですね、ごめんなさい。

N*Nに分割と書いてあるのでただのソートにはならないのでは
ABC
DEF
GHI
のCとDを入れ替えることはできないというものだと思われます。

RyukyuOBさんはもう少し仕様をちゃんと説明したほうがいいですよ。
パズドラのように、では全員わかるわけではありませんし
パズドラは一度ドロップを掴んだらはなすことができなかったように記憶しています。
最短の条件も何を数えて最短なのかを示したほうがいいかもしれません。

[RyukyuOB]

パズドラのような交換方法というのが2つの要素を入れ替える動作をするというだけなのでしたら
{1,8,7,9,4,2,3,5,6}のデータを{1,2,3,4,5,6,7,8,9}に並び替える作業とおなじですよね.
ということはソートの最短手数を求めることになりますね.
解決にはならないですね、ごめんなさい。

N*Nに分割と書いてあるのでただのソートにはならないのでは
ABC
DEF
GHI
のCとDを入れ替えることはできないというものだと思われます。

RyukyuOBさんはもう少し仕様をちゃんと説明したほうがいいですよ。
パズドラのように、では全員わかるわけではありませんし
パズドラは一度ドロップを掴んだらはなすことができなかったように記憶しています。
最短の条件も何を数えて最短なのかを示したほうがいいかもしれません。

そうですね、仕様をもう少し細かに書くべきでした。

仕様としては、
123
456
789
この状態から9を７の地点まで最短で動かしたとすると
123
456
978
のように、数字を次々に交換していきます。
縦列も同様です。
今度は9を1まで最短で動かします。すると
923
156
478
となります。
このようにして動かしていくことにします。
更に言い忘れましたが、
一度離したら終了ではなく、指定された回数(不規則)まで選択できることにもしつつ、最短の経路を求めるようなプログラムを求めています。
アルゴリズムの知識ならばある程度はあります。(ダイクストラ法、動的計画法、貪欲法etc...)
15スライドパズルを応用してもできないかとも考えてみましたが、煮詰まってしまいました。どなたか良いご意見があれば解答よろしくお願いします

[みけCAT]

盤面の状態を頂点、動かし方を辺としたグラフに対してダイクストラ法を使えばできると思います。
【追記2】頂点を、選択できる残りの数で分割するべきだと思います。そうなると、計算量が厳しいかもしれません。
そもそも、下の追記で書いた部分の読解が不完全なので、全く違うかもしれません。

【追記】
よく見たら、

言いにくいのですが、具体例としてNxNに分割された９枚のバラバラの写真を全探索などを用い、最短で導くというプログラムです。

この部分の、N×N (N^2)への分割の仕方がわかりません。
9枚の写真があるのは読み取れますが、それをどう分割しているのでしょうか？

[RyukyuOB]

盤面の状態を頂点、動かし方を辺としたグラフに対してダイクストラ法を使えばできると思います。
【追記2】頂点を、選択できる残りの数で分割するべきだと思います。そうなると、計算量が厳しいかもしれません。
そもそも、下の追記で書いた部分の読解が不完全なので、全く違うかもしれません。

【追記】
よく見たら、

言いにくいのですが、具体例としてNxNに分割された９枚のバラバラの写真を全探索などを用い、最短で導くというプログラムです。

この部分の、N×N (N^2)への分割の仕方がわかりません。
9枚の写真があるのは読み取れますが、それをどう分割しているのでしょうか？

ー追記の返信についてー
すみません、訂正の仕方が悪かったです。
少し訂正を加えます.NxMに分割された適当な写真を並べ替えます。
縦と横が同じ大きさで分割されているとは限りません。

後、盤面の状態を頂点に置く、とはどういうことでしょうか？
ダイクストラ法をまだ少ししか勉強していないので知識が浅いです。

[みけCAT]

少し訂正を加えます.NxMに分割された適当な写真を並べ替えます。
縦と横が同じ大きさで分割されているとは限りません。

例えば、縦3×横4に分割するとしたら、

コード:

 1  2  3  4
 5  6  7  8
 9 10 11 12

となるということですか？

後、盤面の状態を頂点に置く、とはどういうことでしょうか？

例えば、
187
942
356
という状態(Aとする)を1個の頂点、
817
942
356
という状態(Bとする)を別の頂点にし、
Aから1手でBにできるならAからBへのコスト1の辺を張り、
Bから1手でAにできるならBからAへのコスト1の辺を張り…
ということです。
頂点をID(?)に変換する処理を考える必要があるかもしれませんし、
分割する数が多くなると、例えば5×5では1.55×10^25通りの盤面が考えられるため、この方法では不可能です。
ただ、3×3で、「手を離す」ことのコストや制限回数がない場合は、盤面は362880通りなのでなんとかできそうだと思います。

[dic]

じつにおもしろい

[RyukyuOB]

少し訂正を加えます.NxMに分割された適当な写真を並べ替えます。
縦と横が同じ大きさで分割されているとは限りません。

例えば、縦3×横4に分割するとしたら、

コード:

 1  2  3  4
 5  6  7  8
 9 10 11 12

となるということですか？

後、盤面の状態を頂点に置く、とはどういうことでしょうか？

例えば、
187
942
356
という状態(Aとする)を1個の頂点、
817
942
356
という状態(Bとする)を別の頂点にし、
Aから1手でBにできるならAからBへのコスト1の辺を張り、
Bから1手でAにできるならBからAへのコスト1の辺を張り…
ということです。
頂点をID(?)に変換する処理を考える必要があるかもしれませんし、
分割する数が多くなると、例えば5×5では1.55×10^25通りの盤面が考えられるため、この方法では不可能です。
ただ、3×3で、「手を離す」ことのコストや制限回数がない場合は、盤面は362880通りなのでなんとかできそうだと思います。

成る程。頂点等の意味は理解できました。
ID(?)というのは一応自分で調べておきます。
併し、最終的には8x8あたりまで分割された画像も並べ替えられるようにしてみたいので、
ダイクストラ法ではある程度のところで無理が出て来てしまうかと思います。
なのでまだ一応未解決にしておきます。みけCATさん、情報ありがとうございます。役立ちました。