装甲悪鬼村正の魔方陣を適当に遺伝アルゴリズムで解く

攻略サイトを見るのも無粋だと思うほど面白い作品なのでちょっと手を止めて適当に解いてみた。

data = []
data.append(
     [ 25, 16, 80,104, 90,
      115, 98,  4,  1, 97,
       42,111, 85,  2, 75,
       66, 72, 27,102, 48,
       67, 18,119,106,  5,
      ])
data.append(
     [ 91, 77, 71,  6, 70,
       52, 64,117, 69, 13,
       30,118, 21,123, 23,
       26, 39, 92, 44,114,
      116, 17, 14, 73, 95,
      ])
data.append(
     [ 47, 61, 45, 76, 86,
      107, 43, 38, 33, 94,
       89, 68, 63, 58, 37,
       32, 93, 88, 83, 19,
       40, 50, 81, 65, 79,
      ])
data.append(   
     [ 31, 53,112,109, 10,
       12, 82, 34, 87,100,
      103,  3,  0,  0,  0,
      113, 57,  0,  0,  0,
       56,120,  0,  0,  0, 
      ])
data.append(
     [121,108,  7, 20, 59,
       29, 28,122,125, 11,
       51, 15,  0,  0,  0,
       78, 54,  0,  0,  0,
       36,110,  0,  0,  0,
      ])

choices = [ 62,  9, 41,
            49,105, 96,
             8, 22,101,
            55, 35, 46,
            84, 60, 99,
            24, 74,124,
            ]

def get_patterns():
    p = []
    for x in xrange(5):
        for y in xrange(5):
            p.append([[x,y,z] for z in xrange(5)])
    for y in xrange(5):
        for z in xrange(5):
            p.append([[x,y,z] for x in xrange(5)])
    for z in xrange(5):
        for x in xrange(5):
            p.append([[x,y,z] for y in xrange(5)])

    for x in xrange(5):
        p.append([[x,yz,yz] for yz in xrange(5)])
        p.append([[x,4 - yz,yz] for yz in xrange(5)])
    for y in xrange(5):
        p.append([[xz,y,xz] for xz in xrange(5)])
        p.append([[4 - xz,y,xz] for xz in xrange(5)])
    for z in xrange(5):
        p.append([[xy,xy,z] for xy in xrange(5)])
        p.append([[4 - xy,xy,z] for xy in xrange(5)])
    
    def transform(p):
        temp = []
        for t in p:
            temp.append([[i[0], i[1] * 5 + i[2]] for i in t])
        return temp
       
    return transform(p)
patterns = get_patterns()

targets = []
for Level in xrange(3,5):
    for Index in (12, 13 ,14, 17, 18, 19, 22, 23 ,24):
        targets.append([Level,Index])

def get_score(data):
    scores = []
    for t in patterns:
        score = 0
        for i in t:
            Level,Index = i
            score += data[Level][Index]
        scores.append(score)
    avg = float(sum(scores)) / len(scores)
    return sum([(score - avg)**2 for score in scores])

def swap(old):
    from copy import deepcopy
    from random import randint
    a = randint(0,len(targets) - 1)
    while True:
        b = randint(0,len(targets) - 1)
        if a != b:
            break
    Level,Index = targets[a]
    a_choice = old[Level][Index]
    Level,Index = targets[b]
    b_choice = old[Level][Index]
    new = deepcopy(old)
    Level,Index = targets[a]
    new[Level][Index] = b_choice
    Level,Index = targets[b]
    new[Level][Index] = a_choice
    return new
    
def optimization():
    for i in xrange(len(targets)):
        Level,Index = targets[i]
        data[Level][Index] = choices[i]
    pop = []
    for i in xrange(20):
        pop.append(swap(data))
    
    last_score = 9999
    round = 0
    while round < 1000:
        scores=[[get_score(v),v] for v in pop]
        scores.sort()
        ranked=[v for (s,v) in scores]
        pop = ranked[0:10]
        for i in xrange(10):
            pop.append(swap(pop[i]))
        best = scores[0]
        print best
        last_score = best[0]
        if last_score == 0:
            for i in xrange(len(targets)):
                Level,Index = targets[i]
                if i != 0 and i % 3 == 0:
                    print ''
                print best[1][Level][Index],
            print ''
            break
        round += 1
        
optimization()
105 8 96 
9 62 74 
55 49 35 
41 124 84 
99 24 60 
46 22 101