パズルWaterSortの解は必ず存在するの？

パズルWaterSortにちょっとハマってます。上記の疑問が湧きました。

瓶がN+2本、一つの瓶の水の量がMの場合、
N色の水がそれぞれMの量あり、それらがN本の瓶に配分されているとして、
どのような配分（初期状態）であっても、１つの瓶に１色をまとめる手順（解法）は存在するのでしょうか？
あるいは、解けない問題（手順の存在しない初期状態）は存在するのでしょうか？

移せるのは最上位の色の水だけで、移動先の瓶は、最上位の色が同色あるいは空の瓶だけで、移動が可能な場合だけです。

例えば、上から、
A:1123　と水が入っている瓶からは
B:--45
C:-167
D:--18
のＤへは色１の水を２単位移動できますが、
　Ｂは最上位の色が違う、
　Ｃは１単位しか空きがない
ため、移動できません。

写真のような盤面になってしまうと移動できる瓶はありませんので、解法は失敗となります。

No.5 ベストアンサー 回答者： eatern27 回答日時： 2022/10/14 20:16

数学的にN,Mの制約をつけなければいけない理由は何もないので、どんな制約をつけるかは何を考えたいかで決める話。

どんな(N,M)なら解法のない場合があるのか、最小のNは？Mは？とかなら解けるのかは知らないけど問題としては成立するかな。

あとは
>手元のパズルWaterSortでは、N≦１２，M≦６
に限定するとか。　一応これに抵触しない範囲でも解けない場合はありそうですね。

179axx
189axx
279axx
289axx
379axx
389axx
470bxx
480bxx
570bxx
580bxx
670bxx
680bxx
水の番号は0〜9とa,bです。xには残りの水が入ります。

この回答へのお礼

何回も回答ありがとうございます
N≦１２，M≦６に限定しても反例（解法のない初期状態）があるんですね。

ということは、
No2>問題作る際には、完成した状態からシャッフルするような作り方する
のようですね。

＞数学的にN,Mの制約をつけなければいけない理由は何もないので、どんな制約をつけるかは何を考えたいかで決める話。
そうです。
当初予想は、「余裕の空瓶は2本でM,Nの制約なしで任意の初期状態でも解法が存在する」でしたが、N=１２、M=6で反例をいただきましたので、予想は否定されました。

余裕の空瓶が十分にあれば、必ず解法が存在するので、余裕の空瓶の数の制約か、初期状態に対してある関数を定義して、関数の値で制約をつけるのでしょうかね。
このあたりは私のお楽しみで、また思いついたら、質問させていただきます。

お礼日時：2022/10/17 06:59

No.4 回答者： eatern27 回答日時： 2022/10/14 08:57

あら、本当ですね。

失礼しました。

上から順に
147891111
157891122
167892211
247893333
257893344
267894444
347895555
357895566
367896666
空瓶×2

でどうですかね。9瓶9色なので設定には違反してないはず(9の下は適当に入れてます)
9がどうやっても動かせないはずです。

この回答へのお礼

回答ありがとう
確かに、解法なしの初期状態ですね。
これでの、本質問は解決です！

余談
私の仮説（予想）の条件が緩すぎたようですね。
手元のパズルWaterSortでは、N≦１２，M≦６ですので、もう少し、N,Mに制約をつけないと、数学の問題（？）になりませんね。

もし、N,Mについての制約のアイデア等ありましたら、教示いただければと思いますので、質問を閉じるのは少し待っています。

お礼日時：2022/10/14 18:49

No.3 回答者： eatern27 回答日時： 2022/10/13 19:43

少なくともNとMの組み合わせに制限がないなら、

M=2N+1、N+1とN+2番の瓶が空とします。Nは2以上なら良いはず。


1からN番の瓶初期配置は次のようにします。
①i番の瓶の一番上はi番の水
②i番の瓶の上から2番目はN+i番の水
③全ての瓶の上から3番目は2N+1番の水
④残りは適当

最初の2手は空瓶を使うしかありません。
3手目に同じ色の水が一番上にないので詰みます。

この回答へのお礼

応答ありがとう

＞②i番の瓶の上から2番目はN+i番の水
N色の水しかないのですが・・・

お礼日時：2022/10/14 06:09

No.2 回答者： neKo_deux 回答日時： 2022/10/13 15:02

別のゲームやってて宣伝はよく出てきてたので知ってるけど、プレイしたことは無いです。

> どのような配分（初期状態）であっても、１つの瓶に１色をまとめる手順（解法）は存在するのでしょうか？

質問者さんが解けない例に上げたのが初期配置なら、解く手順は無いのでは。

> あるいは、解けない問題（手順の存在しない初期状態）は存在するのでしょうか？

MとかNが少ないとか一定の条件の場合に必ず解けるかどうか？みたいな話？


フツーに考えるなら、問題作る際には、完成した状態からシャッフルするような作り方するので、解けるようになってるのでは。
混ぜたら色が変わるとか、量が２になったら１ずつ動かせないとか、不可逆な要素が無いなら、ですが。
問題はランダムに作られるんでしたっけ？

この回答へのお礼

応答ありがとうございます。

＞質問者さんが解けない例に上げたのが初期配置なら、解く手順は無いのでは。
例に上げたのは途中経過であり、今回の質問での初期配置では
　２本は空の瓶
ですよ！　条件、よくご理解ください。

＞問題はランダムに作られるんでしたっけ？
そこが知りたいとこですね。
ダウンロードしたアプリでは、ゲームなので当然でしょうが、
　全て解ける問題ばかり
でした。また、
　「これがどうしても解けません。」
https://detail.chiebukuro.yahoo.co.jp/qa/questio …
というのが投稿されてましたので興味津々で解いてみると、この問題もあっさり解けてしまいました。ということで、

どのような配分（初期状態）であっても、１つの瓶に１色をまとめる手順（解法）は存在するのでしょうか？
あるいは、解けない問題（手順の存在しない初期状態）は存在するのでしょうか？

という疑問が湧いて質問しています。

お礼日時：2022/10/13 15:34

No.1 回答者： HONTE 回答日時： 2022/10/13 06:53

絶対に解けるッ！

と信じましょう。

この回答へのお礼

応答ありがとう

＞信じましょう。
せっかくのご回答感謝しますが、ここ、数学のカテゴリーですよ。

論理的な回答、お待ちしています。

お礼日時：2022/10/13 07:08