今回のパズル「水差し問題」はいろいろな呼び方があって、参考文献『Ｃ言語による最新アルゴリズム事典』では「水をはかる問題」ですが、参考文献『Prolog の技芸』は「水差し問題」と呼んでいます。このほかに、「水を測り出す問題」と呼ぶ場合があります。それでは問題です。
大きな容器に水が入っています。目盛の付いていない 8 リットルと 5 リットルの容器を使って、大きな容器から 4 リットルの水を汲み出してください。4 リットルの水は、どちらの容器に入れてもかまいません。水をはかる最短手順を求めてください。なお、水の総量に制限はありません。
それではプログラムを作りましょう。今回は「幅優先探索」で解いてみます。使用するプログラミング言語は Python3 (ver 3.8.10) です。最初に大域変数を定義します。
リスト : 大域変数の定義 # 定数 MAX_A = 8 MAX_B = 5
8 リットルの容器を A、5 リットルの容器を B とします。2 つの容器の状態はタプル (A, B) で表すことにします。A の容量は MAX_A で、B の容量は MAX_B で表します。
水差し問題の場合、次に示す 3 通りの操作があります。
3 の操作は、容器が空になるまで水を移す場合と、もう一方の容器が満杯になるまで水を移す場合があります。容器は 2 つあるので、全部で 6 通りの操作があります。これらの操作を関数 move1() から move6() で行うことにします。プログラムは次のようになります。
リスト : 容器の操作
# A を空にする
def move1(a, b): return 0, b
# A を満杯にする
def move2(a, b): return MAX_A, b
# A -> B
def move3(a, b):
c = MAX_B - b
if a <= c: return 0, a + b
return a - c, b + c
# B を空にする
def move4(a, b): return a, 0
# B を満杯にする
def move5(a, b): return a, MAX_B
# B -> A
def move6(a, b):
c = MAX_A - a
if b <= c: return a + b, 0
return a + c, b - c
関数の引数 a が A に入っている水の量、引数 b が B に入っている水の量を表します。move1() から move3() が A の操作、move4() から move6() が B の操作です。容器からもう一方の容器に水を移す操作 move3() と move6() では、容器の空き容量を調べて、水が全部入るかチェックしています。
これらの操作を行うためには、容器に入っている水の量をチェックする必要がありますが、これらの関数では行っていません。意味の無い操作、たとえば空の容器を空にする、または満杯の容器に水を満たす操作を行っても、容器の状態は変化しません。関数 bfs() で容器の状態をチェックすることで、無効な操作を省くようにしました。
あとはオーソドックスな「幅優先探索」なので、難しいところはないと思います。詳細はプログラムリストをお読みくださいませ。
それでは実行結果を示します。手順は容器の状態 (A, B) で表しています。
>>> bfs(4) [(0, 0), (0, 5), (5, 0), (5, 5), (8, 2), (0, 2), (2, 0), (2, 5), (7, 0), (7, 5), (8, 4)]
最短手数は 10 手になります。今回は「幅優先探索」で解きましたが、「反復深化」でも簡単に解けると思います。興味のある方は挑戦してみてください。
ところで、このパズルは容器の大きさの最大公約数の倍数だけ水をはかることができます。その理由を簡単に説明しましょう。
この問題は 8 リットルの容器 A と 5 リットルの容器 B の 2 つしかないので、最初は A で水を汲むか B で水を汲むことになります。B で水を汲んだ場合、それを空にしては後戻りするので、B から A に水を移すことになります。次に、A から B に水を移すのは後戻りするので、B で水を汲むことになります。そして、B から A に水を移しますが、A が満杯になると水を移すことができないので A を空にします。
このように考えると、水の流れは B で水を汲む、B から A に移す、A を空にする、と一方向になります。けっきょく、B で水を m 回汲み A の水を n 回捨てたとき、容器に残っている水の容量だけをはかることができるわけです。これを式で表すと次のようになります。
z = b * m - a * n
z が水の容量、a は A の容量、b は B の容量を表します。ここで、a と b の最大公約数を k とすると、a = k * a1, b = k * b1 と書き直すことができるので、z は次の式で表すことができます。
z = k * (b1 * m - a1 * n)
z は k の倍数になりますね。したがって、水は a と b の最大公約数の倍数だけしかはかることができない、というわけです。8 と 5 の最大公約数は 1 になるので [*1]、1 リットル単位で水をはかることができます。容器が 10 リットルと 4 リットルになると最大公約数が 2 になるので、2 の倍数の水をはかることはできますが、5 リットルとか 7 リットルの水をはかることはできません。
それでは、5m - 8n = 4 を満たす m と n を求めてみましょう。参考文献『どこまで解ける日本の算法 和算で頭のトレーニング』の「油分け算」に面白い方法が紹介されています。最初に、5m - 8n = 1 になる m と n を求めます。a と b が互いに素であれば、a * 1, a * 2, ... a * (b - 1), a * b の値を b で割ると、余りは 0 から b - 1 までの値がひとつずつ現れます。したがって、5m - 8n = 1 を満たす m と n の値は必ず見つけることができます。
5 * 1 / 8 = 0 余り 5 5 * 2 / 8 = 1 余り 2 5 * 3 / 8 = 1 余り 7 5 * 4 / 8 = 2 余り 4 5 * 5 / 8 = 3 余り 1 5 * 6 / 8 = 3 余り 6 5 * 7 / 8 = 4 余り 3 5 * 8 / 8 = 5 余り 0
m = 5, n = 3 であることがわかります。次に、両辺を 4 倍します。
5 * 5 - 8 * 3 = 1 5 * 20 - 8 * 12 = 4
ここで、5 * 20 = 5 * (8 * 2 + 4), 8 * 20 = 8 * (5 * 2 + 2) と表すことができるので、式を展開すると次のようになります。
5 * (8 * 2 + 4) - 8 * (5 * 2 + 2) = 5 * 8 * 2 + 5 * 4 - 8 * 5 * 2 - 8 * 2 = 5 * 4 - 8 * 2
この式は、5 リットルの容器で水を 4 回汲み、8 リットルの容器で水を 2 回捨てると 4 リットルの水が残ることを表しています。最短手順と比べてみると、確かに 5 リットルの容器で水を 4 回汲み上げています。ただし、このパズルは 4 リットルの水をはかることが目的なので、8 リットルの容器で水を捨てる回数は 1 回少なくても、5 リットルの容器に 4 リットルの水をはかることができます。
最初に A から水を汲む場合も同じように解くことができます。今度は、A で水を汲み、A から B に移し、B を空にする、という流れになります。この場合は次のようになります。
8 * m - 5 * n = 1 8 * 2 - 5 * 3 = 1 8 * 8 - 5 * 12 = 4 8 * (5 + 3) - 5 * (8 + 4) = 8 * 3 - 5 * 4
この場合、8 リットルの容器で水を 3 回汲み、5 リットルの容器で水を 4 回捨てます。こちらの方が手数は長くなります。実際に試してみてください。このほかにも、グラフを使った解き方があります。興味のある方は、青木先生のホームページ「数学の部屋」の「油をはかろう」を読んでください。とても参考になります。
#
# water.py : 水差し問題
#
# Copyright (C) 2022 Makoto Hiroi
#
# 定数
MAX_A = 8
MAX_B = 5
#
# 操作関数
#
# A を空にする
def move1(a, b): return 0, b
# A を満杯にする
def move2(a, b): return MAX_A, b
# A -> B
def move3(a, b):
c = MAX_B - b
if a <= c: return 0, a + b
return a - c, b + c
# B を空にする
def move4(a, b): return a, 0
# B を満杯にする
def move5(a, b): return a, MAX_B
# B -> A
def move6(a, b):
c = MAX_A - a
if b <= c: return a + b, 0
return a + c, b - c
# 幅優先探索
def bfs(goal):
queue = [[(0, 0)]]
while len(queue) > 0:
moves = queue.pop(0)
a, b = moves[-1]
if a == goal or b == goal:
print(moves)
return
for move_func in [move1, move2, move3, move4, move5, move6]:
st = move_func(a, b)
if st in moves: continue
ms = moves[:]
ms.append(st)
queue.append(ms)
|
|
「油分け算」は大きな容器に入っている油を 2 つの容器で二等分する古典的な問題 [*1] です。
14 リットルの容器 A に油が満杯に入っています。これを 11 リットルの容器 B と 3 リットルの容器 C を使って二等分してください。容器 A と B には 7 リットルずつ油が入ります。油を二等分する最短手順を求めてください。
簡単に解けた方は、容器 B と C のサイズが 9 リットルと 5 リットルの場合も考えてみてください。
それではプログラムを作りましょう。水差し問題のプログラムを改造すると簡単です。最初に大域変数を定義します。
リスト : 大域変数の定義 MAX_A = 14 # 容器 A の容量 MAX_B = 11 # 容器 B の容量 MAX_C = 3 # 容器 C の容量
14 リットルの容器を A、11 リットルの容器を B、3 リットルの容器を C とします。3 つの容器の状態はタプル (A, B, C) で表すことにします。A の容量は MAX_A で、B の容量は MAX_B で、C の容量は MAX_C で表します。
油分け算の場合、容器が 3 つあるので次に示す 6 通りの操作があります。
これらの操作は関数 move1() - move6() で行います。
リスト : 油を移す操作
# A -> B
def move1(a, b, c):
d = MAX_B - b
if a <= d: d = a
return a - d, b + d, c
# A -> C
def move2(a, b, c):
d = MAX_C - c
if a <= d: d = a
return a - d, b, c + d
# B -> A
def move3(a, b, c):
d = MAX_A - a
if b <= d: d = b
return a + d, b - d, c
# B -> C
def move4(a, b, c):
d = MAX_C - c
if b <= d: d = b
return a, b - d, c + d
# C -> A
def move5(a, b, c):
d = MAX_A - a
if c <= d: d = c
return a + d, b, c - d
# C -> B
def move6(a, b, c):
d = MAX_B - b
if c <= d: d = c
return a, b + d, c - d
関数の引数 a が A に入っている油の量、引数 b が B に入っている油の量、引数 c が C に入っている油の量を表します。容器からもう一方の容器に水を移すとき、容器の空き容量を調べて、油が全部入るかチェックしています。
あとはオーソドックスな「幅優先探索」なので、難しいところはないと思います。詳細はプログラムリストをお読みくださいませ。
それでは実行結果を示します。
>>> bfs() [(14, 0, 0), (3, 11, 0), (3, 8, 3), (6, 8, 0), (6, 5, 3), (9, 5, 0), (9, 2, 3), (12, 2, 0), (12, 0, 2), (1, 11, 2), (1, 10, 3), (4, 10, 0), (4, 7, 3), (7, 7, 0)]
最短手数は 13 手になりました。今回は「幅優先探索」で解きましたが、「反復深化」でも簡単に解けると思います。興味のある方は挑戦してみてください。
ところで、高木茂男氏の著書「パズル遊びへの招待 オンライン版」の「油分け算」には、一般的な解法が示されています。同ページより引用します。
Ａ、Ｂ、Ｃ、３種類の容器があって、Ａ＞Ｂ＞Ｃだとすると、
油分け算の一般的な解法は次のとおりである。
(1)Ｂが空なら、Ａの油をＢに満たす。
(2)Ｂに油が入っていたら、次のどちらかを行う。
(ア)Ｃが一杯でなければ、Ｂの油でＣを満たす。
(イ)Ｃが一杯なら、それをＡにあけてから、(ア)を行う。
以上の操作を繰り返せばよい。
実際、今回の問題はこの方法で求めた手順が最短手数となります。ところが、油分け算はどんな大きさの容器を使っても解ける、というわけではありません。油分け算は 2 つの容器を使って油を分けるので、「水差し問題」と同じように容器の最大公約数の倍数だけ油をはかることができます。
たとえば、14 リットルの油を 9 リットルと 5 リットルの容器で 7 リットルに分ける場合、9 と 5 は互いに素なので 1 リットル単位で油を分けることができます。ところが、10 リットルと 4 リットルの容器を使う場合、10 と 4 の最大公約数は 2 なので、油は 2 リットル単位でしかはかることができません。この場合、7 リットルずつに分けることはできないのです。
このほかに、もうひとつ条件があります。水差し問題では水の総量に制限はありませんが、油分け算では油の総量が決まっています。容器 A, B で水をはかる場合、B で水を汲む、B から A に移す、A を空にする、という操作を行います。B で水を m 回汲み A の水を n 回捨てたとき、容器に残っている水の容量は次の式で表すことができます。
z = b * m - a * n
この式は B で水を汲むとき満杯にならないと成立しません。水差し問題がこの条件を満たしていることは明らかです。ところが、油分け算では油の総量と容器の大きさによって、この条件が成立しない場合があります。
たとえば、9 リットルと 5 リットルの容器の場合、油が 14 リットル以上あれば、9 リットルの容器が満杯でも必ず 5 リットルの容器に油を満たすことができますね。つまり、2 つの容器の合計が油の総量以下であれば、油分け算は水をはかる問題と同様に解くことができるのです。実際、9 リットルと 5 リットルの容器を使うと、14 リットルの油は次のように 1 リットル単位で分けることが可能です。
(13, 1), (12, 2), (11, 3), (10, 4), (9, 5), (8, 6), (7, 7)
2 つの容器の合計が油の総量よりも大きくなると、容器の大きさが互いに素でも、油を 1 リットル単位で分けることができない場合があります。たとえば、14 リットルの油を 11 リットルと 6 リットルの容器で分ける場合、11 と 6 は互いに素なので、油を 1 リットル単位で分けることができるように思われます。ところが、この場合は 10 リットルと 4 リットルに分けることはできません。実際に試してみましょう。
Ａ Ｂ Ｃ (A = 14, B = 11, C = 6) ----------------------------------- 14 ０ ０ 初期状態 ３ 11 ０ A から B へ移す ３ ５ ６ B から C へ移す ９ ５ ０ C から A へ戻す ９ ０ ５ B から C へ移す ０ ９ ５ A から B へ移す（満杯にできない） ０ 11 ５ もしも B を満杯にできると ０ 10 ６ B から C へ移して 10 リットルをはかることができる
このように、油の総量が少ないと分割できない場合があります。たとえば、10 リットルの油を分ける場合を考えてみましょう。容器の大きさを変えて試してみたところ、結果は次のようになりました。
| 分割 | 6,5 | 7,4 | 8,3 | 7,5 | 7,6 | 8,5 | 9,4 | 9,5 |
|---|---|---|---|---|---|---|---|---|
| 9 : 1 | ○ | ○ | ○ | ○ | ○ | × | ○ | ○ |
| 8 : 2 | ○ | ○ | ○ | ○ | ○ | ○ | ○ | × |
| 7 : 3 | ○ | ○ | ○ | ○ | ○ | ○ | × | × |
| 6 : 4 | ○ | ○ | ○ | ○ | ○ | × | ○ | ○ |
| 5 : 5 | ○ | ○ | ○ | ○ | × | ○ | ○ | ○ |
容器の大きさは 10 > B > C, B + C > 10 を満たしています。容器の合計が 11 リットルまたは 12 リットルの場合は、1 リットル単位で分割することができました。容器の合計が大きくなると分割できない場合が出てきます。分割の可否を簡単に調べる方法がないかいろいろ考えてみたのですが、残念ながらよくわかりませんでした。何か良い方法がありましたら教えてくださいませ。
#
# oil.py : 油分け算
#
# Copyright (C) 2022 Makoto Hiroi
#
# 定数
MAX_A = 14
MAX_B = 11
MAX_C = 3
#
# 操作関数
#
# A -> B
def move1(a, b, c):
d = MAX_B - b
if a <= d: d = a
return a - d, b + d, c
# A -> C
def move2(a, b, c):
d = MAX_C - c
if a <= d: d = a
return a - d, b, c + d
# B -> A
def move3(a, b, c):
d = MAX_A - a
if b <= d: d = b
return a + d, b - d, c
# B -> C
def move4(a, b, c):
d = MAX_C - c
if b <= d: d = b
return a, b - d, c + d
# C -> A
def move5(a, b, c):
d = MAX_A - a
if c <= d: d = c
return a + d, b, c - d
# C -> B
def move6(a, b, c):
d = MAX_B - b
if c <= d: d = c
return a, b + d, c - d
# 幅優先探索
def bfs():
queue = [[(14, 0, 0)]]
while len(queue) > 0:
moves = queue.pop(0)
a, b, c = moves[-1]
if a == 7 and b == 7:
print(moves)
return
for move_func in [move1, move2, move3, move4, move5, move6]:
st = move_func(a, b, c)
if st in moves: continue
ms = moves[:]
ms.append(st)
queue.append(ms)
|
|
|
|