2015年04月12日

C#で水の移し替えパズルを解く

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その84

■問題 (出題者:光成さん)
A, B, Cの容器があり,それぞれ水が4L, 2L, 10L入っている. ここで次の操作を繰り返す.

(*)「A, B, Cのどれか二つの容器から水を1Lずつくみ上げ,残りの容器に移す.」
たとえばA, Bから1Lずつくみ上げて移せばA=3L, B=1L, C=12Lとなる. くみ上げる前の容器には必ず水が入っているとする.
(*)を繰り返してどれか一つの容器にのみ水がはいっている状態にする最小手数を求めよ.
可能ならA=827392L,B=65536L,C=122880Lのときも求めよ.

まず、移動を表す Moveクラスと、現在の3つの容器の状態を表す State クラスを定義します。


class State {
    public State(int[] buckets, State prev) {
        Buckets = (int[])buckets.Clone();
        PrevState = prev;
        Times = (prev == null) ? 0 : prev.Times + 1;
    }
    public int Times { get; private set; }
    public State PrevState { get; private set; }
    public int[] Buckets { get; private set; }
}

class Move {
    public byte From1 { get; set; }
    public byte From2 { get; set; }
    public byte To { get; set; }
}

次に、これを使って、愚直に幅優先の探索で解を求める BfSolver クラスを定義してみました。

class BfSolver  {
    public State Search(State state) {

        // 最初に訪問するノードをキューに入れる
        Queue<State> queue = new Queue<State>();
        queue.Enqueue(state);
        while (queue.Count != 0) {
            //キューの先頭からノード currentNode を取り出す
            State current = queue.Dequeue();
            if (IsFinish(current.Buckets)) {
                return current;
            }

            foreach (var mv in GetMoves()) {
                if (!IsOK(mv, current.Buckets))
                    continue;
                int[] next = new int[3];
                next[mv.From1] = current.Buckets[mv.From1] - 1;
                next[mv.From2] = current.Buckets[mv.From2] - 1;
                next[mv.To] = current.Buckets[mv.To] + 2;
                State newstate = new State(next, current);
                if (IsLoop(current, newstate))
                    continue;
                if (ExistsInQueue(queue, newstate))
                    continue;
                queue.Enqueue(newstate);
            }
        }
        // 見つからなかった。
        return null;
    }

    private bool IsFinish(int[] buckets) {
        return buckets.Count(n => n == 0) == 2;
    }

    private IEnumerable<Move> GetMoves() {
        yield return new Move { From1 = 0, From2 = 1, To = 2 };
        yield return new Move { From1 = 0, From2 = 2, To = 1 };
        yield return new Move { From1 = 1, From2 = 2, To = 0 };
    }
    private bool IsOK(Move mv, int[] buckets) {
        if (buckets[mv.From1] <= 0)
            return false;
        if (buckets[mv.From2] <= 0)
            return false;
        return true;
    }

    private bool ExistsInQueue(Queue<State> queue, State state) {
        return queue.Any(x => x.Buckets.SequenceEqual(state.Buckets));
    }

    private bool IsLoop(State state1, State state2) {
        if (state1 == null)
            return false;
        if (state1.Buckets.OrderBy(n => n).SequenceEqual(state2.Buckets.OrderBy(n => n)))
            return true;
        return IsLoop(state1.PrevState, state2);
    }
}

Searchメソッドの戻り値は、 Stateオブジェクトとなり、この Times プロパティを見れば、移動回数が分かります。
Stateがnull の時には、解が見つからなかったことを示しています。

今回は、回数だけを求めればいいので、その状態推移を表示するコードは書いていませんが、 Stateには、PrevStateがあるので、これを辿れば、容器のリットル数がどう変化していったのかが分かるようになっています。

しかし、このプログラムは、A=3L, B=1L, C=12L 程度ならば、問題ないですが、 A=827392L,B=65536L,C=122880Lとなると、調べる手があまりにも多すぎて、永遠に終わりそうにありません。
試しに、A=171L, B=162L, C=180L と3桁の値でやってみたら、10分経っても終わらないので、 あきらめて途中で終了させてしまいました。

そこで、コンピュータに考えさせるのではなく、もうすこし自分で考えてみました。
そうしたら、意外と単純な問題であることに気が付きました。
そのコードを以下に示します。

class SmartSolver {
    public int Calc(State state) {
        var nums = state.Buckets.OrderBy(n => n).ToArray();
        if ((nums[1] - nums[0]) % 3 == 0)
            return nums[1];
        if ((nums[2] - nums[1]) % 3 == 0)
            return nums[2];
        if ((nums[2] - nums[0]) % 3 == 0)
            return nums[2];
        return -1;
    }
}

なんと、これだけでした。これならば、A=827392L,B=65536L,C=122880Lのときも 一瞬で求まります。
答えは 827392です。

ざっと説明すると、
例えば、最終的な状態が、

A=0L, B=0L, C=xL
のような状態になるのですから、そのひとつ前は、

A=1L, B=1L, C=(x-2)L

そのひとつ前は

A=2L, B=2L, C=(x-4)L

そのひとつ前は

A=3L, B=3L, C=(x-6)L or A=3L, B=0L, C=(x-3)L

つまり、最終的に 0になる AとBの、水の増減は (+1,+1) (+1,-2) (-2,+1) となるわけです。 ここから、A =B か、A と B の差が3の倍数かのどちらかであることが分かります。
そして、水は1Lずつしか減らないので、どんなに頑張っても、A とBの大きい数だけ、水の移動回数が 必要となります。
これらのことから、上のコードが導きだせるということになります。

これが正しいかを確認するために、最初に書いた BfSolver と SmartSolver の結果が同じになるか 確認してみました。
以下が、そのコードと実行結果です。

class Program {
    static void Main(string[] args) {
        Test(4, 2, 10);
        Test(5, 2, 10);
        Test(2, 8, 11);
        Test(1, 2, 3);
        Test(12, 8, 11);
        Test(7, 16, 51);
        Test(44, 22, 15);
        Test(53, 22, 1);
        Test(8, 8, 7);
        Test(20, 20, 23);
        Console.ReadLine();
    }

    private static void Test(int n1, int n2, int n3) {
        State state = new State(new int[] { n1, n2, n3 }, null);

        var sol = new SmartSolver();
        int n = sol.Calc(state);
        Console.Write("{0}\t",n);

        BfSolver s = new BfSolver();
        State last = s.Search(state);
        if (last == null)
            Console.WriteLine(-1);
        else
            Console.WriteLine(last.Times);       
    }
}

■実行結果
10      10
5       5
8       8
-1      -1
11      11
16      16
-1      -1
22      22
8       8
20      20

途中結果を表示する機能がありませんが、原理が分かっているので、 SmartSolver に途中結果を表示させる機能をつけるのも、それほど難しくはないですね。



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52412628