はじめに
アルゴリズムの勉強として川渡りクイズを解きました。今回の課題（宣教師と先住民）
「宣教師と先住民」（「宣教師と人食い人種」とも言われる）を解きます。ルールは以下の通りです。
３人の宣教師と３人の人先住民がいる。 舟には２人まで乗ることができる。 宣教師の数がそこにいる先住民の数より少なくなると殺されしまう。
まずは非常にシンプルに
Pythonスクリプト
import queue import numpy as np class state: def __init__(self, prestate, premove, persons, boat): self.prestate= prestate self.premove = premove self.persons = persons self.boat= boat move_list = [ np.array([1, 0]), np.array([2, 0]), np.array([0, 1]), np.array([0, 2]), np.array([1, 1]) ] move_message_list = [ '宣教師一人', '宣教師二人', '先住民一人', '先住民二人', '宣教師と先住民', ] def isOK(np_array): if not np.all(np_array >= np.array([0, 0])): return False if not np.all(np_array <= np.array([3, 3])): return False left_senkyoshi, left_senjumin = [int(x) for x in np_array] right_senkyoshi, right_senjumin = [3- int(x) for x in np_array] if (left_senkyoshi > 0) and (left_senkyoshi < left_senjumin): return False if(right_senkyoshi >0) and (right_senkyoshi < right_senjumin): return False return True state_queue = queue.Queue() isChecked = [] start_state = state(None, None, np.array([3, 3]), -1) isChecked.append(tuple(start_state.persons * start_state.boat)) state_queue.put(start_state) while not state_queue.empty(): now = state_queue.get() if(np.all(now.persons == np.array([0, 0]))): break for move_number, move in enumerate(move_list): next_persons = now.persons + move * now.boat if isOK(next_persons): next_hash = tuple(next_persons * now.boat * (-1)) if next_hash not in isChecked: isChecked.append(next_hash) next_state = state(now, move_number, next_persons, now.boat * (-1)) state_queue.put(next_state) move_stack = queue.LifoQueue() while not now.premove == None: move_stack.put(now.premove) now = now.prestate print('解答：%d回'%move_stack.qsize()) while not move_stack.empty(): now_move = move_stack.get() print(move_message_list[now_move])
出力（解答）
解答：11回 先住民二人 先住民一人 先住民二人 先住民一人 宣教師二人 宣教師と先住民 宣教師二人 先住民一人 先住民二人 宣教師一人 宣教師と先住民
問題点
上記Pythonスクリプトでクイズは解けますが問題があります。解答の１つを見つけた時点でプログラムが終了してしまうことです。実は今回の問題は別解があります。ネットで公開されているものや書籍に載っていいるものは大体ここでプログラム完成としています。
今回、別解もすべて解答できるようにプログラムを修正してみました。
すべての解答を見つける
Pythonスクリプト
import queue import numpy as np import copy class state: def __init__(self, prestate, premove, move_count, persons, boat): self.prestate= prestate self.premove = premove self.move_count = move_count self.persons = persons self.boat= boat move_list = [ np.array([1, 0]), np.array([2, 0]), np.array([0, 1]), np.array([0, 2]), np.array([1, 1]) ] move_message_list = [ '宣教師一人', '宣教師二人', '先住民一人', '先住民二人', '宣教師と先住民', ] def isOK(np_array): if not np.all(np_array >= np.array([0, 0])): return False if not np.all(np_array <= np.array([3, 3])): return False left_senkyoshi, left_senjumin = [int(x) for x in np_array] right_senkyoshi, right_senjumin = [3- int(x) for x in np_array] if (left_senkyoshi > 0) and (left_senkyoshi < left_senjumin): return False if(right_senkyoshi >0) and (right_senkyoshi < right_senjumin): return False return True def hash_check(_list, _number, _hash): temp_list = [] for i in range(_number + 1): temp_list.extend(_list[i]) return _hash not in temp_list state_queue = queue.Queue() isChecked = [] answer_list = [] start_state = state(None, None, 0, np.array([3, 3]), -1) isChecked.append([]) isChecked[0].append(tuple(start_state.persons * start_state.boat)) state_queue.put(start_state) while not state_queue.empty(): now = state_queue.get() if(np.all(now.persons == np.array([0, 0]))): answer_list.append(copy.deepcopy(now)) continue for move_number, move in enumerate(move_list): next_persons = now.persons + move * now.boat if isOK(next_persons): if len(isChecked) <= now.move_count + 1: isChecked.append([]) next_hash = tuple(next_persons * now.boat * (-1)) if hash_check(isChecked, now.move_count, next_hash): isChecked[now.move_count+1].append(next_hash) next_state = state(now, move_number, now.move_count + 1, next_persons, now.boat * (-1)) state_queue.put(next_state) for each_answer in answer_list: move_stack = queue.LifoQueue() now = each_answer while not now.premove == None: move_stack.put(now.premove) now = now.prestate print('解答：%d回'%move_stack.qsize()) while not move_stack.empty(): now_move = move_stack.get() print(move_message_list[now_move]) print('\n')
出力（解答）
解答：11回 先住民二人 先住民一人 先住民二人 先住民一人 宣教師二人 宣教師と先住民 宣教師二人 先住民一人 先住民二人 宣教師一人 宣教師と先住民 解答：11回 先住民二人 先住民一人 先住民二人 先住民一人 宣教師二人 宣教師と先住民 宣教師二人 先住民一人 先住民二人 先住民一人 先住民二人 解答：11回 宣教師と先住民 宣教師一人 先住民二人 先住民一人 宣教師二人 宣教師と先住民 宣教師二人 先住民一人 先住民二人 宣教師一人 宣教師と先住民 解答：11回 宣教師と先住民 宣教師一人 先住民二人 先住民一人 宣教師二人 宣教師と先住民 宣教師二人 先住民一人 先住民二人 先住民一人 先住民二人
「キャベツとヤギとオオカミを運ぶ商人」も解いてみる
ほとんど一緒の方法で解けます。キモはisOKを定義する部分です。numpyを使っているのですっきり書けます。
def isOK(np_array): notOK_list = [(0, 1 ,1, 0), (0, 1, 1, 1), (0, 1, 0, 1)] if not np.all(np_array >= np.array([0, 0, 0, 0])): return False if not np.all(np_array <= np.array([1, 1, 1, 1])): return False if tuple(np_array) in notOK_list: return False if tuple(1 - np_array) in notOK_list: return False return True
最終的なPythonスクリプト
import queue import numpy as np import copy class state: def __init__(self, prestate, premove, move_count, persons, boat): self.prestate= prestate self.premove = premove self.move_count = move_count self.persons = persons self.boat= boat move_list = [ np.array([1, 0, 0, 0]), np.array([1, 1, 0, 0]), np.array([1, 0, 1, 0]), np.array([1, 0, 0, 1]) ] move_message_list = [ '農夫のみ', 'ヤギを運ぶ', 'オオカミを運ぶ', 'キャベツを運ぶ' ] def isOK(np_array): notOK_list = [(0, 1 ,1, 0), (0, 1, 1, 1), (0, 1, 0, 1)] if not np.all(np_array >= np.array([0, 0, 0, 0])): return False if not np.all(np_array <= np.array([1, 1, 1, 1])): return False if tuple(np_array) in notOK_list: return False if tuple(1 - np_array) in notOK_list: return False return True def hash_check(_list, _number, _hash): temp_list = [] for i in range(_number + 1): temp_list.extend(_list[i]) return _hash not in temp_list state_queue = queue.Queue() isChecked = [] answer_list = [] start_state = state(None, None, 0, np.array([1, 1, 1, 1]), -1) isChecked.append([]) isChecked[0].append(tuple(start_state.persons * start_state.boat)) state_queue.put(start_state) while not state_queue.empty(): now = state_queue.get() if(np.all(now.persons == np.array([0, 0, 0, 0]))): answer_list.append(copy.deepcopy(now)) continue for move_number, move in enumerate(move_list): next_persons = now.persons + move * now.boat if isOK(next_persons): if len(isChecked) <= now.move_count + 1: isChecked.append([]) next_hash = tuple(next_persons * now.boat * (-1)) if hash_check(isChecked, now.move_count, next_hash): isChecked[now.move_count+1].append(next_hash) next_state = state(now, move_number, now.move_count + 1, next_persons, now.boat * (-1)) state_queue.put(next_state) for each_answer in answer_list: move_stack = queue.LifoQueue() now = each_answer while not now.premove == None: move_stack.put(now.premove) now = now.prestate print('解答：%d回'%move_stack.qsize()) while not move_stack.empty(): now_move = move_stack.get() print(move_message_list[now_move]) print('\n')
出力（解答）
解答：7回 ヤギを運ぶ 農夫のみ オオカミを運ぶ ヤギを運ぶ キャベツを運ぶ 農夫のみ ヤギを運ぶ 解答：7回 ヤギを運ぶ 農夫のみ キャベツを運ぶ ヤギを運ぶ オオカミを運ぶ 農夫のみ ヤギを運ぶ
ちゃんと二通りの解答を返してくれました。
