Simpath

gistfile1.py

#!/usr/bin/env python
# -*- coding:utf-8 -*-

def grid(w, h):
    edge = []
    for i in range(h):
        for j in range(w):
            edge.append( ((i,j), (i,j+1)) )
            edge.append( ((i,j), (i+1,j)) )
        edge.append( ((i,w), (i+1,w)) )
    for j in range(w):
        edge.append( ((h,j), (h,j+1)) )
    edge.sort(key = lambda a: a[0][0] + a[0][1])
    return [(1+ai*(w+1)+aj, 1+bi*(w+1)+bj) for (ai, aj), (bi, bj) in edge]

count_count = 0
def main():
    def isgoal(mate):
        if mate[start] != goal:
            return False

        for i, j in enumerate(mate):
            if j == 0 or i == start or i == goal:
                continue
            if i != j:
                return False
        return True

    def frontier():
        for i, all in enumerate(edge_count):
            selected = edge_selected[i]
            unselected = edge_unselected[i]
            if selected == 0 and unselected == 0:
                continue
            if selected + unselected == all:
                continue
            yield i

    def count(i, mate):
        global count_count
        count_count += 1
        if count_count % 1000 == 0:
            print selected

        if i >= len(edge):
            if isgoal(mate):
                return 1
            else:
                return 0

        key = (i, tuple((f, mate[f]) for f in frontier()))
        if key in cache:
            return cache[key]

        a, b = edge[i]
        c, d = mate[a], mate[b]
        cnt = 0
        flag = True

        # スタートとゴールからは1本以上枝が出ていなければならない
        if (a == start or a == goal) and edge_unselected[a] == edge_count[a] - 1:
            flag = False
        if (b == start or b == goal) and edge_unselected[b] == edge_count[b] - 1:
            flag = False

        # スタートとゴール以外の点を通る場合、入る枝と出ていく枝が必要
        if (a != start and a != goal) and edge_selected[a] == 1 and edge_unselected[a] == edge_count[a] - 2:
            flag = False
        if (b != start and b != goal) and edge_selected[b] == 1 and edge_unselected[b] == edge_count[b] - 2:
            flag = False

        # edge[i]を通らない
        if flag:
            edge_unselected[a] += 1
            edge_unselected[b] += 1
            cnt += count(i+1, mate)
            edge_unselected[a] -= 1
            edge_unselected[b] -= 1

        flag = True

        # 枝の両端がパスの途中なら中断
        if c==0 or d==0:
            flag = False

        # 輪ができてしまう場合中断
        if a==d or b==c:
            flag = False

        # 三叉路ができてしまう場合中断
        if edge_selected[a]>=2 or edge_selected[b]>=2:
            flag = False

        # スタートとゴールは1つしか枝が出ない
        if (a == start or a == goal) and edge_selected[a]==1:
            flag = False
        if (b == start or b == goal) and edge_selected[b]==1:
            flag = False

        # スタートとゴール以外の点を通る場合、入る枝と出ていく枝が必要
        if (a != start and a != goal) and edge_selected[a] == 0 and edge_unselected[a] == edge_count[a] - 1:
            flag = False
        if (b != start and b != goal) and edge_selected[b] == 0 and edge_unselected[b] == edge_count[b] - 1:
            flag = False

        # edge[i]を通る
        if flag:
            edge_selected[a] += 1
            edge_selected[b] += 1
            new_mate = mate[:]
            new_mate[a] = 0
            new_mate[b] = 0
            new_mate[c] = d
            new_mate[d] = c
            selected.append(edge[i])

            cnt += count(i+1, new_mate)

            selected.pop()
            edge_selected[a] -= 1
            edge_selected[b] -= 1

        cache[key] = cnt
        return cnt

    # 枝の情報
    edge = [
        (1, 2),
        (1, 3),
        (2, 4),
        (2, 5),
        (3, 6),
        (4, 5),
        (4, 7),
        (5, 9),
        (6, 8),
        (7, 9),
        (7, 8),
        ]
    edge = grid(9, 9)

    # 枝接続の情報
    mate = range(0, max(
            max(i for i, j in edge),
            max(j for i, j in edge))+1)
    start = 1
    goal = len(mate)-1

    # 各頂点に出入りする枝の数
    edge_count = [0 for i in mate]
    for i, j in edge:
        edge_count[i] += 1
        edge_count[j] += 1

    # 選択された枝の数・選択されなかった枝の数
    edge_selected = [0 for i in mate]
    edge_unselected = [0 for i in mate]

    # 選択された枝
    selected = []
    cache = {}

    print count(0, mate)
    print count_count

    return

if __name__=='__main__':
    main()