不宜咖啡

代码来自于这里，说真的我不觉得我有必要对他的实现做任何的解释！
#coding: utf-8

from itertools import chain

# 用来加速python程序的。在我的机器上，不用psyco是每秒780个结点，用psyco是913个结点，17%的性能提升。
import psyco
psyco.full()


class Item(object):
    u''' 棋盘上的对象，注，棋盘的左上角坐标为(1, 1)，右下角坐标为(4, 5) '''

    # 以下4个函数是对象向上下左右移动，如果移动后出界，返回False

    def left(self):
        self.x -= 1
        for x, y in self.pixels():
            if not x > 0:
                return False
        return True

    def right(self):
        self.x += 1
        for x, y in self.pixels():
            if not x < 5:
                return False
        return True

    def up(self):
        self.y -= 1
        for x, y in self.pixels():
            if not y > 0:
                return False
        return True

    def down(self):
        self.y += 1
        for x, y in self.pixels():
            if not y < 6:
                return False
        return True

    def clone(self):
        u''' 复制一份对象 '''
        return self.__class__(self.x, self.y)

    def __lt__(self, other):
        u''' 对象的坐标比较 '''
        return self.x < other.x or self.x == other.x and self.y < other.y

    def __str__(self):
        u''' 对象的输出 '''
        return '%s at (%d, %d)' % (self.__class__.__name__, self.x, self.y)
    __repr__ = __str__


class Dot(Item):
    u''' 用来表示一个小方格的对象，对应游戏里的'兵'和'卒' '''
    C = ord('D')

    def __init__(self, x, y):
        if not 1<= x <= 4 or not 1 <= y <= 5:
            self.valid = False

        self.x = x
        self.y = y

    def pixels(self):
        yield (self.x, self.y)


class VerticalBar(Item):
    u''' 用来表示一个竖条的对象，对应游戏里的'黄忠'和'马超'等 '''
    C = ord('V')

    def __init__(self, x, y):
        if not 1<= x <= 4 or not 1 <= y <= 4:
            self.valid = False

        self.x = x
        self.y = y

    def pixels(self):
        yield (self.x, self.y)
        yield (self.x, self.y+1)


class HorizontalBar(Item):
    u''' 用来表示一个横条的对象，对应游戏里的'关羽' '''
    C = ord('H')

    def __init__(self, x, y):
        if not 1<= x <= 3 or not 1 <= y <= 5:
            self.valid = False

        self.x = x
        self.y = y

    def pixels(self):
        yield (self.x, self.y)
        yield (self.x+1, self.y)


class Box(Item):
    u''' 用来表示一个正方形的对象，对应游戏里的'曹操' '''
    C = ord('B')

    def __init__(self, x, y):
        if not 1<= x <= 3 or not 1 <= y <= 4:
            self.valid = False

        self.x = x
        self.y = y

    def pixels(self):
        yield (self.x, self.y)
        yield (self.x+1, self.y)
        yield (self.x, self.y+1)
        yield (self.x+1, self.y+1)


class Board(Item):
    u''' 整个棋盘 '''

    def check_validity(self):
        pixels = set()
        for item in self.items():
            for x, y in item.pixels():
                if (x, y) in pixels:
                    return False
                pixels.add((x, y))

        return len(pixels) == 18

    def __init__(self, box, dots, vbs, hbs):
        self.box = box
        self.dots = dots
        self.vbs = vbs
        self.hbs = hbs

        self.dots.sort()
        self.vbs.sort()
        self.hbs.sort()


        if not self.check_validity():
            self.valid = False
            return

        # 用一个Long型的变量来唯一地表示一个棋盘的状态。
        self.statuscode = reduce(lambda code, item: (code<<5) + ((item.x-1)<<3)+item.y-1, self.items(), 0L)

    def __str__(self):
        result = [[ord(' ')]*4 for i in xrange(5)]
        for item in self.items():
            for x, y in item.pixels():
                result[y-1][x-1] = item.C
        return '\n'.join(''.join(chr(c) for c in line) for line in result)

    def items(self):
        u''' 按顺序返回棋盘里的所有对象 '''
        return chain([self.box], self.dots, self.vbs, self.hbs)


    OP = ['up', 'down', 'left', 'right']

    def permutate_items(self):
        u''' 枚举棋盘上可能的移动方案，返回新的棋盘 '''

        # 试着往4个方向移动box
        for op in Board.OP:
            newbox = self.box.clone()
            if not getattr(newbox, op)():
                continue

            newboard = Board(newbox, self.dots, self.vbs, self.hbs)
            if not hasattr(newboard, 'valid'):
                yield newboard

        # 试着往4个方向移动dot
        for i in xrange(len(self.dots)):
            origindot = self.dots[i]
            for op in Board.OP:
                newdot = origindot.clone()
                if not getattr(newdot, op)():
                    continue

                newdots = self.dots[:]
                newdots[i] = newdot
                newboard = Board(self.box, newdots, self.vbs, self.hbs)
                if not hasattr(newboard, 'valid'):
                    yield newboard
                    for op2 in Board.OP:
                        newdot2 = newdot.clone()
                        if not getattr(newdot2, op2)() or newdot2.x == origindot.x and newdot2.y == origindot.y:
                            continue

                        newdots = self.dots[:]
                        newdots[i] = newdot2
                        newboard = Board(self.box, newdots, self.vbs, self.hbs)
                        if not hasattr(newboard, 'valid'):
                            yield newboard


        # 试着往4个方向移动vertical bar
        for i in xrange(len(self.vbs)):
            for op in Board.OP:
                newvb = self.vbs[i].clone()
                if not getattr(newvb, op)():
                    continue

                newvbs = self.vbs[:]
                newvbs[i] = newvb
                newboard = Board(self.box, self.dots, newvbs, self.hbs)
                if not hasattr(newboard, 'valid'):
                    yield newboard
                    newvb = newvb.clone()
                    if not getattr(newvb, op)():
                        continue

                    newvbs = self.vbs[:]
                    newvbs[i] = newvb
                    newboard = Board(self.box, self.dots, newvbs, self.hbs)
                    if not hasattr(newboard, 'valid'):
                        yield newboard



        # 试着往4个方向移动horizontal bar
        for i in xrange(len(self.hbs)):
            for op in Board.OP:
                newhb = self.hbs[i].clone()
                if not getattr(newhb, op)():
                    continue

                newhbs = self.hbs[:]
                newhbs[i] = newhb
                newboard = Board(self.box, self.dots, self.vbs, newhbs)
                if not hasattr(newboard, 'valid'):
                    yield newboard
                    newhb = newhb.clone()
                    if not getattr(newhb, op)():
                        continue

                    newhbs = self.hbs[:]
                    newhbs[i] = newhb
                    newboard = Board(self.box, self.dots, self.vbs, newhbs)
                    if not hasattr(newboard, 'valid'):
                        yield newboard

    def worked_out(self):
        u''' 返回当前棋盘是否是获胜的棋盘，即box是否走到了坐标(2, 4) '''
        return self.box.x == 2 and self.box.y == 4


def solve_the_board(board):
    u''' 求指定的棋盘的解 '''
    from datetime import datetime

    if hasattr(board, 'valid'):
        print 'original data error!'
        return

    print 'original status: %x' % (board.statuscode)

    searched = {}       # 一个dict，保留了statuscode到board的映射
    bfs = []            # 记录我们广度优先搜索的节点
    board.previous_status = None
    bfs.append(board)
    searched[board.statuscode] = board
    board.step = 0

    # 开始做广度优先搜索（BFS）
    start = datetime.now()
    i = 0
    current_step = 0
    while i < len(bfs):
        board = bfs[i]      # 取第i个结点做推演

        if board.step != current_step:
            current_step = board.step
            print 'current step: %d, i = %d' % (current_step, i)

        i += 1
        if i % 1000 == 0:   # 每处理1k个结点，输出一些信息
            print i
            delta = datetime.now() - start
            dt = delta.days * 24 * 60 * 60.0 + delta.seconds
            if dt:
                print 'len(bfs) = %d, len(searched) = %d, %.2f nodes / sec' % (len(bfs), len(searched), i / dt)

        # 找这个结点棋盘所有可能的下一步
        for nb in board.permutate_items():
            # 如果这一步曾经到过，就不再处理了。
            if nb.statuscode in searched:
                continue

            nb.step = board.step + 1

            # 如果已经找到解了，输出然后退出
            if nb.worked_out():
                result = [nb]

                # 由每一个结点棋盘的previous_status属性，计算出走的过程
                previous_status = board.statuscode
                while previous_status:
                    pre = searched[previous_status]
                    result.append(pre)
                    previous_status = pre.previous_status

                for board in reversed(result):
                    print board
                    print '-' * 20

                print 'total steps:', nb.step
                return

            # 计录下新的节点是由当前节点而来的，方便后面的输出。
            nb.previous_status = board.statuscode

            # 把新计算出来的结点，放到bfs的后面
            searched[nb.statuscode] = nb
            bfs.append(nb)

    # 如果所有的结点都找完了，说明无解。
    print 'not solution!'


def main():
    # 第1关 横刀立马
    #board = Board(Box(2, 1),        # 曹操的位置
    #          [Dot(1, 5), Dot(2, 4), Dot(3, 4), Dot(4, 5)],     # 所有点点的位置
    #          [VerticalBar(1, 1), VerticalBar(1, 3), VerticalBar(4, 1), VerticalBar(4, 3)], # 竖条的位置
    #          [HorizontalBar(2, 3)],     # 横条的位置
    #          )

    # 第53关 四将连关
    board = Board(Box(1, 1),        # 曹操的位置
              [Dot(1, 5), Dot(3, 4), Dot(4, 4), Dot(4, 5)],     # 所有点点的位置
              [VerticalBar(1, 3), VerticalBar(2, 3)],           # 竖条的位置
              [HorizontalBar(3, 1), HorizontalBar(3, 2), HorizontalBar(3, 3)],     # 横条的位置
              )

    solve_the_board(board)

main()


# 下面两个函数是用来做性能分析的


def runhotshot():
    import hotshot
    prof = hotshot.Profile('/home/leojay/my/test.log')
    prof.runcall(main)
    prof.close()
#runhotshot()


def printhotshot():
    import hotshot.stats
    stats = hotshot.stats.load('/home/leojay/my/test.log')
    stats.strip_dirs()
    stats.sort_stats('time', 'calls')
    stats.print_stats(20)
#printhotshot()