不宜咖啡

chessman.py
from move import Move

class ChessmanFactory(type):
    u''' 棋子的工厂 '''

    def __init__(cls, name, bases, dic):
        super(ChessmanFactory, cls).__init__(name, bases, dic)
        cls.instances = {}

    def __call__(cls, x, y):
        #cls.xs和cls.ys表示该种棋子合法的x和合法的y
        if x not in cls.xs or y not in cls.ys:
            return None
        _ = x, y
        if _ not in cls.instances:
            cls.instances[_] = super(ChessmanFactory, cls).__call__(x, y)
        return cls.instances[_]

class Chessman(object):
    u''' 棋盘上的棋子，注，棋盘的左上角坐标为(0, 0)，右下角坐标为(3, 4) '''

    __metaclass__ = ChessmanFactory

    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.position = self.x + 4 * self.y
        self.mask = 0
        for x, y in self.ps:
            x = self.x + x
            y = self.y + y
            self.mask |= 1 << (x + 4 * y)
        self.hash = self.position + (self.id << 5)
        self._moves = None

    @property
    def moves(self):
        if self._moves is None:
            self._moves = []
            for x, y in [(0,1), (0, -1), (1, 0), (-1, 0)]:
                dst = self.__class__(self.x + x, self.y + y)
                if dst:
                    self._moves.append(Move(self, dst))
        return self._moves

    @property
    def positions(self):
        for x, y in self.ps:
            x = self.x + x
            y = self.y + y
            yield x, y

    def __lt__(self, other):
        u''' 对象的坐标比较 '''
        return self.hash < other.hash

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

class Dot(Chessman):
    u''' 用来表示一个小方格的对象，对应游戏里的'兵'和'卒' '''
    C = 'D'
    id = 3
    count = 1
    xs = range(4)
    ys = range(5)
    ps = [(0,0)]

class VerticalBar(Chessman):
    u''' 用来表示一个竖条的对象，对应游戏里的'黄忠'和'马超'等 '''
    C = 'V'
    id = 2
    count = 2
    xs = range(4)
    ys = range(4)
    ps = [(0,0), (0,1)]

class HorizontalBar(Chessman):
    u''' 用来表示一个横条的对象，对应游戏里的'关羽' '''
    C = 'H'
    id = 1
    count = 2
    xs = range(3)
    ys = range(5)
    ps = [(0,0), (1,0)]

class Box(Chessman):
    u''' 用来表示一个正方形的对象，对应游戏里的'曹操' '''
    C = 'B'
    id = 0
    count = 4
    xs = range(3)
    ys = range(4)
    ps = [(0,0), (1,0), (0,1), (1,1)]
move.py
#coding=utf-8

class Move(object):
    u''' 棋子的走法对象 '''

    def __init__(self, src, dst, mask=0):
        self.src = src
        self.dst = dst
        self.mask = mask
        if mask == 0:
            self.mask = (dst.mask | src.mask) ^ src.mask
        self._nexts = None

    @property
    def nexts(self):
        u''' 对这个棋子连续移动的走法 '''
        if self._nexts is None:
            self._nexts = []
            masks = [1 << i for i in range(20)]
            if self.mask in masks:
                for move in self.dst.moves:
                    if move.mask in masks and move.dst is not self.src:
                        self._nexts.append(Move(self.src, move.dst, self.mask | move.mask))
        return self._nexts

    def __str__(self):
        return '%s to %s' % (self.src, self.dst)
    __repr__ = __str__
pyhrd.py
#coding: utf-8

from itertools import chain
from chessman import Dot, HorizontalBar, VerticalBar, Box

class BoardFactory(type):
    def __init__(cls, name, bases, dic):
        super(BoardFactory, cls).__init__(name, bases, dic)
        cls.instances = {}
    @staticmethod
    def mask(chessmen):
        mask = 0
        for cm in chessmen:
            mask |= ( 1 << cm.position) | mask
        return mask
    def __call__(cls, box, dots, vbs, hbs, mask=0, parent=None):
        if mask == 0:
            count = 0
            for cm in chain([box], dots, vbs, hbs):
                count += cm.count
                if mask & cm.mask:
                    return
                mask |= cm.mask
            if count != 18:
                return
        dmask = BoardFactory.mask(dots)
        vmask = BoardFactory.mask(vbs)
        hmask = BoardFactory.mask(hbs)
        hash = (box.position << 60) | (vmask << 40) | (hmask << 20) | dmask
        if hash not in cls.instances:
            cls.instances[hash] = super(BoardFactory, cls).__call__(box, dots, vbs, hbs, hash, mask)
            cls.instances[hash].parent = parent
        return cls.instances[hash]
class Board(object):
    __metaclass__ = BoardFactory
    def __init__(self, box, dots, vbs, hbs, hash, mask):
        self.box = box
        self.dots = dots
        self.vbs = vbs
        self.hbs = hbs

        self.hash = hash
        self.mask = mask
    def __hash__(self):
        return self.hash
    @property
    def nexts(self):
        box, dots, vbs, hbs = self.box, self.dots, self.vbs, self.hbs
        for move in self.box.moves:
            if (move.mask & self.mask) == 0:
                yield Board(move.dst, dots, vbs, hbs, self.mask ^ move.src.mask ^ move.dst.mask, self)
        box, dots, vbs, hbs = self.box, self.dots, self.vbs, self.hbs
        for cm in dots:
            for move  in cm.moves:
                if (move.mask & self.mask) == 0:
                    dots = [cm for cm in self.dots if cm is not move.src]
                    dots.append(move.dst)
                    yield Board(box, dots, vbs, hbs, self.mask ^ move.src.mask ^ move.dst.mask, self)
                    for move in move.nexts:
                        if (move.mask & self.mask) == 0:
                            dots = [cm for cm in self.dots if cm is not move.src]
                            dots.append(move.dst)
                            yield Board(box, dots, vbs, hbs, self.mask ^ move.src.mask ^ move.dst.mask, self)
        box, dots, vbs, hbs = self.box, self.dots, self.vbs, self.hbs
        for cm in vbs:
            for move  in cm.moves:
                if (move.mask & self.mask) == 0:
                    vbs = [cm for cm in self.vbs if cm is not move.src]
                    vbs.append(move.dst)
                    yield Board(box, dots, vbs, hbs, self.mask ^ move.src.mask ^ move.dst.mask, self)
                    for move in move.nexts:
                        if (move.mask & self.mask) == 0:
                            vbs = [cm for cm in self.vbs if cm is not move.src]
                            vbs.append(move.dst)
                            yield Board(box, dots, vbs, hbs, self.mask ^ move.src.mask ^ move.dst.mask, self)
        box, dots, vbs, hbs = self.box, self.dots, self.vbs, self.hbs
        for cm in self.hbs:
            for move  in cm.moves:
                if (move.mask & self.mask) == 0:
                    hbs = [cm for cm in self.hbs if cm is not move.src]
                    hbs.append(move.dst)
                    yield Board(box, dots, vbs, hbs, self.mask ^ move.src.mask ^ move.dst.mask, self)
                    for move in move.nexts:
                        if (move.mask & self.mask) == 0:
                            hbs = [cm for cm in self.hbs if cm is not move.src]
                            hbs.append(move.dst)
                            yield Board(box, dots, vbs, hbs, self.mask ^ move.src.mask ^ move.dst.mask, self)
    def __str__(self):
        seq = [[' ', ' ', ' ', ' '], [' ', ' ', ' ', ' '], [' ', ' ', ' ', ' '], [' ', ' ', ' ', ' '], [' ', ' ', ' ', ' ']]
        for cm in chain([self.box], self.dots, self.hbs, self.vbs):
            for x, y in cm.positions:
                seq[y][x] = cm.C
        return '\n'.join(''.join(i) for i in seq)
    @property
    def boards(self):
        if self.parent:
            for b in self.parent.boards:
                yield b
        yield self
def solve(board):
    import time
    start = time.time()
    node = 0
    def solved():
        for board in dmap[depth]:
            if board.box.position == 13:
                return board
        return False
    bmap = {board:0}
    dmap = {0:[board]}
    depth = 0
    while dmap[depth]:
        board = solved()
        if board:
            delta = time.time() - start
            print delta, node, depth
            return board
        boards = dmap[depth]
        depth += 1
        dmap[depth] = []
        for board in boards:
            for new in board.nexts:
                if new not in bmap:
                    node = node + 1
                    dmap[depth].append(new)
                    bmap[new] = depth

def main():
    board = Board(Box(1, 0),
        [Dot(0, 0), Dot(3, 0), Dot(0, 3), Dot(3, 3)],
        [VerticalBar(0, 1), VerticalBar(3, 1)],
        [HorizontalBar(1, 2), HorizontalBar(1, 3), HorizontalBar(1, 4)],
        )
    return solve(board)
main()
代码也相当简单。