WikiMath

import networkx as nx import pylab as pb

ech = range(9)

sommets = [] for b1 in ech :

   for b2 in ech :
      for n1 in ech :
         for n2 in ech :
            if len(set([b1,b2,n1,n2])) == 4:
               sommets += [(b1,b2,n1,n2)]

sommets = [(b1,b2,n1,n2) for b1 in ech for b2 in ech for n1 in ech for n2 in ech if len(set([b1,b2,n1,n2])) == 4]

def sont_lies(o,e):

   def un_chgt_au_plus(o,e):
      r = True
      if sum([ 1 if o[x] != e[x] else 0  for x in range(len(o))]) > 1:
         r = False
      return r


   def depl_c(x):
      r={
         0:{5,7},
         1:{6,8},
         2:{3,7},
         3:{2,8},
         4:{},
         5:{0,6},
         6:{1,5},
         7:{0,2},
         8:{1,3}}
      return r[x]

   def un_chgt_au_moins(o,e):
      r = False
      for x in range(len(o)):
         for y in depl_c(o[x]):
            if e[x] == y :
               r= True 
      return r

   return un_chgt_au_moins(o,e) and un_chgt_au_plus(o,e)

sommets = list(sommets) print len(sommets) l = len(sommets) G=nx.Graph() G.add_nodes_from(sommets)

for j in range(l-1):

    for k in range(j+1,l):
        o,e = sommets[j], sommets[k]
        if sont_lies(o,e):
            G.add_edges_from([(o,e)])

1. Gp = G.subgraph(nx.node_connected_component(G, (0,2,6,8)))

print nx.shortest_path(G,(0,2,6,8),(8,6,2,0))