倉庫版ソルバー

アルゴリズム Python

を基にC++のコードをPythonに置き換えてみた。そのままPythonに置き換えただけなので改善の余地はある。

■■■■
■　　　■■■■
■　　　□人×■
■■■■■■■■

■：壁、□：箱、×：ゴール、人：人間
# -*- coding: utf-8 -*-

Nothing, Pillar, Cargo, Goal, Man = 0, 1, 2, 3, 4

class Point:
    '盤面上の位置'
    def __init__(self, x, y):
        self.x, self.y = x, y
    def __repr__(self):
        return 'Point(%d, %d)' % (self.x, self.y)
    def __cmp__(self, oth):
        if self.x == oth.x and self.y == oth.y: return 0
        else: return -1

class State:
    '荷物の位置と人の位置'
    def __init__(self, cargo, man):
        self.cargo = cargo
        self.man = man
    def __repr__(self):
        return 'Cargo(%d,%d), Man(%d,%d)' % \
            (self.cargo.x, self.cargo.y, self.man.x, self.man.y)
    def __cmp__(self, oth):
        if self.cargo == oth.cargo and self.man == oth.man: return 0
        else: return -1
    def __hash__(self):
        return self.cargo.x + self.cargo.y + self.man.x + self.man.y

class IState:
    '手数とState'
    def __init__(self, step, state):
        self.step = step
        self.state = state
    def __repr__(self):
        return 'IState(%d, (%s))' % (self.step, str(self.state))

class Problem:
    def __init__(self, width=0, height=0):
        self.width, self.height = width, height  # 盤面の幅と高さ
        self.mat = None   # 壁の配置
        self.goal = None  # ゴールの位置
        self.stat = None  # 初期状態
		
def solve(p):
    next = []
    done = set()
    # 初期手数と初期位置
    next.append(IState(0, p.stat))
    # 出現済み集合に初期位置を追加
    done.add(p.stat)
	
    while len(next) > 0:
        nextPair = next.pop(0)
        step = nextPair.step
        stat = nextPair.state
        cargo = stat.cargo
        man = stat.man
        for vct in ([1,0], [0,-1], [-1,0], [0,1]):
            to = Point(man.x + vct[0], man.y + vct[1])
            if to == cargo:
               nCargo = Point(to.x + vct[0], to.y + vct[1])
               if p.mat[nCargo.y][nCargo.x] == Nothing:
                   # 手数 step+1 の解を見つけた
                   if nCargo == p.goal:
                       return step + 1
                   # 新たな局面の作成
                   nStat = State(nCargo, man)
                   if nStat not in done:
                       done.add(nStat)
                       next.append(IState(step+1, nStat))
                       next.sort()
            elif p.mat[to.y][to.x] == Nothing:
                nStat = State(cargo, to)
                if nStat not in done:
                    done.add(nStat)
                    next.append(IState(step, nStat))
                    next.sort()
    return -1

if __name__ == '__main__':
    p = Problem(8, 4)
    p.goal = Point(6, 2)
    cargo = Point(4, 2)
    man = Point(5, 2)
    p.stat = State(cargo, man)
    p.mat = [
        [1, 1, 1, 1, 0, 0, 0, 0],
        [1, 0, 0, 0, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1] ]
    print solve(p)  # => 6

倉庫版の解法は、PSPACE完全問題らしく、工夫をしないと効率良い解き方はないらしい。研究すると面白そうであるが、どうせならGUIで解答を視覚化してみたい。