DouKaku?

import copy
import time
def mahobunkatsu(N):
    m = set()
    for i in xrange(1,N**2+1):
        m.add(i)
    ave = N*(N**2+1) / 2
    
    def createPair(restNumber,numberSum, pair, count, pairList):
        for i in restNumber:
            if count and (count+1)%N == 0:
                if numberSum + i == ave:
                    if count+1 == N**2:
                        pair.append(i)
                        pairList.append(copy.copy(pair))
                        pair.pop()
                        continue
                else:
                    continue
            if numberSum + i > ave:
                continue
            restNumber.remove(i)
            pair.append(i)
            createPair(restNumber, (numberSum + i) % ave, pair, count + 1, pairList)
            restNumber.add(i)
            pair.pop()
        return

    pairList = []
    createPair(m, 0, [], 0, pairList)

    def listToSortedPairs(pairList):
        temp = []
        for l in pairList:
            temp.append([])
            for i in range(N):
                temp[-1].append(l[i*N:(i+1)*N])
                temp[-1][-1].sort()
                temp[-1].sort()
        return temp

    sortedList = listToSortedPairs(pairList)

    uniqueList = set()
    for x in sortedList:
        uniqueList.add(str(x))

    print uniqueList
    return uniqueList


t = time.time()
for x in range(2,6):
    n = len(mahobunkatsu(x))
    print "Size=",x,"Mahozin_num=",n,"time=",time.time()-t
    t = time.time()