Puzzle: Eight chess knights ...
Omrežje skokov
# 0 1 2 3
# 4 x 5 6
# x 7 8 x
# x 9 10 x
# Vladimir Batagelj, 11. april 2012
def solutions(a,b,c,s=""):
global n, S
if a+b+c == 0:
n += 1; S[s] = n; net.write(str(n)+' "'+s+'"\n'); return
if a > 0: solutions(a-1,b,c,s+'.')
if b > 0: solutions(a,b-1,c,s+'B')
if c > 0: solutions(a,b,c-1,s+'C')
global n, S
net = open('horse.net','w')
net.write('*vertices \n')
n = 0; S = {}
solutions(3,4,4)
print('# of vertices = ',len(S))
skoki = [[5,7], [8,6], [4,7], [8], [2,8,9], [0,9],
[1,7,10], [0,2,6], [1,3,4], [4,5], [6] ]
net.write('*edges\n')
for sol in S.keys():
for i in range(11):
if sol[i]=='.':
for j in skoki[i]:
tol = sol[:i]+sol[j]+sol[(i+1):]
tol = tol[:j]+'.'+tol[(j+1):]
si = S[sol]; ti = S[tol]
if ti>si: net.write(str(si)+' '+str(ti)+'\n')
net.close()
print('graph is on the file horse.net')
Iščemo najkrajše poti med ..BB.BBCCCC in ..CC.CCBBBB . V Pajku dobimo ustrezno podomrežje. Najkrajše poti imajo dolžino 18. Rešitev je veliko.
Če natančneje preberemo nalogo, vidimo, da dopušča tudi zaporedja skokov istega konjička - poteze in sprašuje po rešitvi, ki zahteva najmanj potez.
Možne so le poteze dolžine 1, 2 ali 3.
Omrežje potez
Omrežju dodamo poteze dolžine 2 (2 skoka) čez dvojnike srednje točke.
i k j ---------------------------------- u | |c| |.| |.| | ---------------------------------- ---------------------------------- t | |.| |c| |.| | ---------------------------------- ---------------------------------- v | |.| |.| |c| | ----------------------------------
Uteži novih povezav so 1/2. Nato še poteze dolžine 3 z utežmi povezav 1/3
i k m j ------------------------------------------- u | |c| |.| |.| |.| | ------------------------------------------- ------------------------------------------- t | |.| |c| |.| |.| | ------------------------------------------- ------------------------------------------- z | |.| |.| |c| |.| | ------------------------------------------- ------------------------------------------- v | |.| |.| |.| |c| | -------------------------------------------
Iskane rešitve so najkrajše poti v omrežju potez.
Omrežje skokov dopolnimo s potezami:
from Graph import Graph
def Knights():
G = Graph.loadPajek('horse.net')
S = { G.getNode(k,'lab') : k for k in G.nodes() }
n = len(S); print("# of vertices = ",n); A = "abcdefghijk"
skoki = [[5,7], [8,6], [4,7], [8], [2,8,9], [0,9],
[1,7,10], [0,2,6], [1,3,4], [4,5], [6] ]
for T in S.keys():
t = S[T]; p = [i for i in range(11) if T[i] == '.']
for [i,j] in [ [p[0],p[1]], [p[0],p[2]], [p[1],p[2]] ]:
for k in set(skoki[i]) & set(skoki[j]):
U = T[:i]+T[k]+T[(i+1):]; U = U[:k]+'.'+U[(k+1):]
V = T[:j]+T[k]+T[(j+1):]; V = V[:k]+'.'+V[(k+1):]
u = S[U]; v = S[V]
if (u!=t) & (v!=t):
n += 1; G.addNode(n); G.setNode(n,'lab',T+A[k])
G.addEdge(u,n,0.5); G.addEdge(n,v,0.5)
for T in S.keys():
t = S[T]; p = [i for i in range(11) if T[i] == '.']
for i in p:
for k in set(skoki[i])-set(p):
ch = T[k];
U = T[:i]+ch+T[(i+1):]; U = U[:k]+'.'+U[(k+1):]; u = S[U]
for m in (set(skoki[k])&set(p))-{i}:
Z = T[:m]+ch+T[(m+1):]; Z = Z[:k]+'.'+Z[(k+1):]; z = S[Z]
for j in (set(skoki[m])&set(p))-{i,k}:
V = T[:j]+ch+T[(j+1):]; V = V[:k]+'.'+V[(k+1):]; v = S[V]
n += 1; G.addNode(n); G.setNode(n,'lab',T+A[k])
G.addEdge(u,n,1/3)
n += 1; G.addNode(n); G.setNode(n,'lab',Z+A[k])
G.addEdge(n-1,n,1/3); G.addEdge(n,v,1/3)
G.savePajek('8knights.net',False)
print("done, # of vertices = ",n)
if __name__ == '__main__':
Knights()
V Pajku dobimo za poteze dolžine 2 dve najkrajši poti dolžine 12
Ko dodamo še poteze dolžine 3, je rešitev dolžine 12 več
Opravki: Skoke in poteze pobarvati z barvo konjička, ki skače - črni ali beli (večrelacijsko omrežje). Morda vrednosti uteži zamenjati s 6, 3 in 2. Tako se pri iskanju najkrajših poti izognemo morebitnim zaokrožitvenim napakam - računamo s celimi števili.