horizon 2021 09

horizon_202109.py

import numpy as np
import time
import sys
import itertools        


connections = [[0,1,0,1,1,1,0,1,0],
               [1,0,1,1,1,1,1,0,1],
               [0,1,0,1,1,1,0,1,0],
               [1,1,1,0,1,0,1,1,1],
               [1,1,1,1,0,1,1,1,1],
               [1,1,1,0,1,0,1,1,1],
               [0,1,0,1,1,1,0,1,0],
               [1,0,1,1,1,1,1,0,1],
               [0,1,0,1,1,1,0,1,0]]

assert np.array_equal(np.array(connections).T, np.array(connections))
    
barriers = {
    0: {
        4:[(1,3),(1,6),(2,3)],
        5:[(1,3),(1,4),(2,3),(2,4),(1,8),(2,7),(1,6)],
        7:[(1,3),(1,6),(3,4),(4,6),(2,3),(3,8),(5,6)],
    },
    1: {
        3:[(0,4),(0,5),(0,7)],
        4:[(0,5),(2,3)],
        5:[(2,3),(2,4),(2,7)],
        6:[(0,4),(0,7),(3,4),(3,7),(0,5),(2,3),(3,8)],
        8:[(2,4),(2,7),(4,5),(5,7),(5,6),(0,5),(2,3)],
    },
    2: {
        3:[(0,4),(0,5),(1,4),(1,5),(0,7),(1,8),(1,6)],
        4:[(0,5),(1,5),(1,8)],
        7:[(1,5),(1,8),(4,5),(4,8),(5,6),(3,8),(0,5)]
    },
    3: {
        4:[(0,7),(1,6)],
        7:[(1,6),(4,6),(5,6)],
        8:[(4,6),(4,7),(5,6),(5,7),(1,6),(0,7),(2,7)]
    },
    4: {
        5:[(1,8),(2,7)],
        6:[(0,7),(3,7),(3,8)],
        7:[(3,8),(5,6)],
        8:[(2,7),(5,7),(5,6)]
    },
    5: {
        6:[(3,7),(3,8),(4,7),(4,8),(2,7),(1,8),(0,7)],
        7:[(1,8),(3,8),(4,8)]
    }    
}

pos2num_org = {i:k for i,k in zip(range(9), [3,5,7,1,9,2,4,6,8])}
pos2num = pos2num_org.copy()

def check(hist):
    global pos2num
    p=0
    for h in hist:
        if pos2num[h]==p+1:
            p+=1
    return p==9


def possibles(hist, cur_connections):
    from_x = hist[-1]
    global barriers
    to_candidates = np.where(cur_connections[from_x]==1)[0]
    
    if len(to_candidates)==0:
        # out
        return 

    for to_x in to_candidates:
        if check(hist+[to_x]):
            print()
            seq=[pos2num[pos] for pos in hist+[to_x]]
                
            g=pos2num
            print(g[0],g[1],g[2])
            print(g[3],g[4],g[5])
            print(g[6],g[7],g[8],seq)
            sys.exit(0)

        to_connections = cur_connections.copy()
        to_connections[from_x, to_x] = 0
        to_connections[to_x, from_x] = 0
        s1, s2 = min(from_x, to_x), max(from_x, to_x)
        bars = barriers.get(s1, {}).get(s2, [])
        for bar in bars:
            f,t = bar
            to_connections[f][t] = 0
            to_connections[t][f] = 0
            
        possibles(hist + [to_x], to_connections)

#
# main
#
# run many processes as many as possible ; 
# in bash,
# 
#        for i in {0..36}; do python a.py $i & done
#
#
connections = np.array(connections)
cpu = int(sys.argv[1])
_i=0
for ai, bi in itertools.combinations(range(9), 2): # we need 36 processes.(9*8/2)
    if cpu == _i:
        pos2num = pos2num_org.copy()

        # swap
        t = pos2num[ai]
        pos2num[ai] = pos2num[bi]
        pos2num[bi] = t
        for i in range(9):
            possibles([i], connections)
    
    _i+=1
    

answer:

3 1 7
5 9 2
4 6 8 [3, 1, 2, 9, 3, 6, 4, 5, 6, 9, 1, 7, 2, 8, 9]

3 8 7
1 9 2
4 6 5 [3, 1, 9, 2, 8, 3, 9, 4, 2, 5, 6, 2, 7, 8, 9]

3 6 7
1 9 2
4 5 8 [3, 1, 9, 2, 3, 9, 4, 5, 2, 6, 7, 2, 8, 5, 9]

6 5 7
1 9 2
4 3 8 [6, 1, 9, 2, 3, 4, 9, 5, 6, 9, 7, 2, 8, 3, 9]

2 5 7
1 9 3
4 6 8 [1, 2, 5, 3, 9, 4, 5, 1, 4, 6, 9, 5, 7, 3, 8, 9]

3 5 2
1 9 7
4 6 8 [1, 5, 2, 7, 5, 3, 1, 4, 5, 9, 4, 6, 9, 7, 8, 9]

3 2 7
1 9 5
4 6 8 [1, 2, 3, 1, 4, 2, 9, 5, 6, 9, 7, 5, 8, 6, 4, 9]

3 5 6
1 9 2
4 7 8 [1, 5, 9, 2, 5, 3, 1, 4, 5, 6, 2, 7, 8, 2, 4, 9]

4 5 7
1 9 2
3 6 8 [1, 5, 2, 9, 3, 1, 4, 5, 9, 6, 3, 5, 7, 2, 8, 9]

3 4 7
1 9 2
5 6 8 [1, 4, 2, 9, 5, 1, 3, 4, 5, 6, 9, 4, 7, 2, 8, 9]

8 5 7
1 9 2
4 6 3 [1, 5, 2, 3, 6, 4, 5, 9, 6, 2, 7, 5, 8, 1, 4, 9]

3 5 7
1 2 9
4 6 8 [1, 2, 3, 1, 4, 2, 5, 7, 2, 6, 7, 9, 6, 8, 9]

3 5 7
4 9 2
1 6 8 [4, 1, 9, 2, 5, 3, 4, 5, 9, 6, 1, 5, 7, 2, 8, 9]

3 5 7
1 9 4
2 6 8 [1, 2, 6, 3, 9, 4, 5, 3, 1, 6, 9, 5, 7, 4, 8, 9]

3 5 7
1 9 6
4 2 8 [1, 2, 3, 1, 4, 2, 9, 3, 5, 9, 6, 5, 7, 6, 8, 9]

3 5 8
1 9 2
4 6 7 [1, 6, 2, 9, 3, 1, 4, 6, 3, 5, 9, 6, 7, 2, 8, 9]

3 5 7
1 6 2
4 9 8 [1, 9, 2, 6, 3, 1, 4, 9, 3, 5, 6, 7, 2, 8, 9]