再帰関数から始める論理パズル #再帰関数

Hello, World! あーみーです．
この記事はLife is Tech! Tokai Mentors Advent Calendar 2018 2日目の記事です．

はじめに

今回は再帰関数を始めに触れて，論理パズルに挑戦していきたいと思います．

再帰関数

まずはじめに再帰関数の定義から始めます．

再帰関数

関数の中からその関数自身を呼び出す処理を行う関数のこと

です．
再帰的なもののイメージとしては鏡を向かい合わせに置いたときにどこまでも続くように見えますが，あれが再帰です．

ただ注意が必要で，どこまでも続くように見えるというのはプログラムでいうと，それは無限ループを意味します．なので実装するときには

はじめに終了条件を書いておく
終了条件に達するように自身の内部状態を変える

以上2つを気をつけなければなりません．

フィボナッチ数列

以下に再帰関数を用いる簡単な問題として「フィボナッチ数列」で例を挙げます．

フィボナッチ数列

2つ前の項と1つ前の項の和からなる数列のこと
$F_0=0$，$F_1=1$とした時
$F_{n+2}=F_n+F_{n+1}(n\geqq0)$となる

具体的には以下のような数列です．

F_n=0,1,1,2,3,4,8,13,21,34,55,89,\cdots

このフィボナッチ数列の第7項の数字を知りたいとします．普通にプログラムで書こうと思うと，

n = 7

f_0 = 0
f_1 = 1

f_n = 0
for _ in range(n-1):
    f_n = f_0 + f_1
    f_0 = f_1
    f_1 = f_n

print(f_n) # 13

こうなります．
これを再帰関数を用いて書くと，

def fibonacci(n):
    if(n <= 1):
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(7)) # 13

こうなります．とても完結で美しいですね．
しかも今回，再帰関数内のreturn文はフィボナッチ数列の定義と同じです．直感的でわかりやすい．

普通にプログラムで書いてもできるじゃん！なんで再帰関数使うの？他のサイト見たらデメリットが多くて心配！

と思う人もいるとは思いますが，今回はフィボナッチ数列だから簡単にプログラムを書くことができました．違う問題ならとても難しかったかもしれません．
先の見えない探索問題でもルールを設けて繰り返すことで答えが見つかるかもしれない．それが再帰関数のメリットだと僕は思います．ただ使う場面はケースバイケースです．

さて，次からはよく知られている論理パズルを解いていきます．

宣教師と人食い人種の問題

問題

川の一方の岸に3人の宣教師と３人の人食い人種がいて，舟を使って向こう岸に渡ろうとしています．
舟には2人まで乗ることができます．ただし，どんな状況でも，宣教師の数がそこにいる人食い人種の数より少なくなると，彼らに食べられてしまいます．
6人全員が向こう岸まで川を渡るにはどうすればよいでしょうか？

問題の定式化

いくつかの行動を選択した先に答えがあるはずで，その行動を探索できるように問題を紐解いていきます．

初期状態として宣教師3人，人食い人種3人が一方の岸にいる状態を考えます．
また，最終状態として宣教師3人，人食い人種3人が向こう岸にいる状態を考えます．

行える行動としては

舟がある岸の宣教師1人が川を渡る
舟がある岸の宣教師2人が川を渡る
舟がある岸の人食い人種1人が川を渡る
舟がある岸の人食い人種2人が川を渡る
舟がある岸の宣教師と人食い人種が1人ずつ川を渡る

が挙げられると思います．

問題を解くためにプログラムっぽく書いていきます．

初期状態

岸A = [宣教師，宣教師，宣教師，人食い人種，人食い人種，人食い人種]
岸B = []

最終状態

岸A = []
岸B = [宣教師，宣教師，宣教師，人食い人種，人食い人種，人食い人種]

可能な行動

舟がある岸の宣教師1人が川を渡る

舟がある岸の宣教師2人が川を渡る

舟がある岸の人食い人種1人が川を渡る

舟がある岸の人食い人種2人が川を渡る

舟がある岸の宣教師と人食い人種が1人ずつ川を渡る

舟

行動を取ると向こう岸に移動する

行動の制限

選択ができない行動

移動したら食べられる状態に遷移する行動

移動したら初期状態に遷移する行動

「行動を選択して現在の状態を把握」を繰り返していけばなんとか解けそうですよね．

注意としては，しっかりと行動を制限していくことが必要ということです．

では実際にプログラムを書いてみます．

プログラム

missionary = "宣教師"
cannibal = "人食い人種"

# 初期状態
initial_left_side = [missionary, missionary, missionary, cannibal, cannibal, cannibal]
initial_right_side = []

# 最終状態
final_left_side = []
final_right_side = [missionary, missionary, missionary, cannibal, cannibal, cannibal]

# 現在の状態
left_side = [missionary, missionary, missionary, cannibal, cannibal, cannibal]
right_side = []

# 初期状態と同じならTrue
def is_initial_state():
    left_side.sort(), right_side.sort()
    initial_left_side.sort(), initial_right_side.sort()    

    if left_side == initial_left_side and right_side == initial_right_side:
        return True
    return False

# 最終状態と同じならTrue
def is_finish_state():
    left_side.sort(), right_side.sort()
    final_left_side.sort(), final_right_side.sort()

    if left_side == final_left_side and right_side == final_right_side:
        return True
    return False

# 食べられているならTrue
def is_eaten():
    if 0 < left_side.count(missionary) < left_side.count(cannibal) or 0 < right_side.count(missionary) < right_side.count(cannibal):
        return True
    return False

# 移動できるならTrue
def can_moved(river_side, people):
    array = []
    lst = river_side.copy()
    for person in people:
        try:
            lst.remove(person)
        except ValueError:
            pass
        else:
            array.append(person)
    if array == list(people):
        return True
    return False

# 行動に伴う人数
move_people=[[missionary],[missionary,missionary],[cannibal],[cannibal,cannibal],[missionary,cannibal]]

boat_on_the_left_side = True # 舟が左の岸にあるか

# 移動する
def move(people):
    if boat_on_the_left_side:
        for person in people:
            index = left_side.index(person)
            right_side.append(left_side.pop(index))
        move_boat()
    else:
        for person in people:
            index = right_side.index(person)
            left_side.append(right_side.pop(index))
        move_boat()

# 舟を移動させる
def move_boat():
    global boat_on_the_left_side
    boat_on_the_left_side = not(boat_on_the_left_side)

# 舟がある岸の宣教師1人が川を渡る
def move_one_missionary():
    move(move_people[0])

# 舟がある岸の宣教師2人が川を渡る
def move_two_missionary():
    move(move_people[1])

# 舟がある岸の人食い人種1人が川を渡る
def move_one_cannibal():
    move(move_people[2])

# 舟がある岸の人食い人種2人が川を渡る
def move_two_cannibal():
    move(move_people[3])

# 舟がある岸の宣教師と人食い人種が1人ずつ川を渡る
def move_both():
    move(move_people[4])

# 行動の配列
action = list([move_one_missionary, move_two_missionary, move_one_cannibal, move_two_cannibal, move_both])

# 行動の履歴
history = []

def search(last_action):
    if is_finish_state():
        print(history)
        exit()

    for i, act in enumerate(action):
        if last_action == i:
            pass
        else:
            if boat_on_the_left_side:
                if can_moved(left_side, move_people[i]):
                    act()
                    history.append(act.__name__)
                    if is_eaten():
                        act()
                        history.pop()
                    elif is_initial_state():
                        act()
                        history.pop()
                    else:
                        search(i)
            else:
                if can_moved(right_side, move_people[i]):
                    act()
                    history.append(act.__name__)
                    if is_eaten():
                        act()
                        history.pop()
                    elif is_initial_state():
                        act()
                        history.pop()
                    else:
                        search(i)
    action[last_action]()
    history.pop()
    return

search(-1)

出力結果

['move_two_cannibal', 'move_one_cannibal', 'move_two_cannibal',
 'move_one_cannibal', 'move_two_missionary', 'move_both',
 'move_two_missionary', 'move_one_cannibal', 'move_two_cannibal',
 'move_one_missionary', 'move_both']

これで全員が無事に向こう岸まで川を渡ることができました．

また，他にも回答はありますが，一つ回答を見つけたら終了するようにしているので，今回はこれだけです．

終わりに

今回は再帰関数を使って論理パズルを解いてみました．他にもいろいろな論理パズル，探索問題があると思うので，是非プログラムを書いて解いてみてください．

ただ，あまりにも状態数が大きくなる探索問題にはメモリ的，計算時間的に適用できないので，その時はそれに合った探索アルゴリズムを適用すると良いと思います．

それでは，Happy Hacking!