This shows you the differences between two versions of the page.
— |
notes:net:puzz1 [2015/07/16 22:39] (current) vlado created |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== Puzzle: Eight chess knights ... ====== | ||
+ | * http://www.ageofpuzzles.com/Puzzles/ChessPuzzles.htm | ||
+ | |||
+ | {{:pics:notes:knightsProblem.png}} | ||
+ | |||
+ | * [[http://zvonka.fmf.uni-lj.si/netbook/lib/exe/fetch.php?id=paper%3A2-mode%3Asemi&cache=cache&media=pub:zip:april18.zip|Graph April 18, 2011]] | ||
+ | |||
+ | ===== Omrežje skokov ===== | ||
+ | |||
+ | <code> | ||
+ | # 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') | ||
+ | </code> | ||
+ | |||
+ | {{:notes:data:knights.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. | ||
+ | <code> | ||
+ | i k j | ||
+ | ---------------------------------- | ||
+ | u | |c| |.| |.| | | ||
+ | ---------------------------------- | ||
+ | |||
+ | ---------------------------------- | ||
+ | t | |.| |c| |.| | | ||
+ | ---------------------------------- | ||
+ | |||
+ | ---------------------------------- | ||
+ | v | |.| |.| |c| | | ||
+ | ---------------------------------- | ||
+ | </code> | ||
+ | |||
+ | Uteži novih povezav so 1/2. Nato še poteze dolžine 3 z utežmi povezav 1/3 | ||
+ | <code> | ||
+ | i k m j | ||
+ | ------------------------------------------- | ||
+ | u | |c| |.| |.| |.| | | ||
+ | ------------------------------------------- | ||
+ | |||
+ | ------------------------------------------- | ||
+ | t | |.| |c| |.| |.| | | ||
+ | ------------------------------------------- | ||
+ | |||
+ | ------------------------------------------- | ||
+ | z | |.| |.| |c| |.| | | ||
+ | ------------------------------------------- | ||
+ | |||
+ | ------------------------------------------- | ||
+ | v | |.| |.| |.| |c| | | ||
+ | ------------------------------------------- | ||
+ | </code> | ||
+ | Iskane rešitve so najkrajše poti v omrežju potez. | ||
+ | |||
+ | Omrežje skokov dopolnimo s potezami: | ||
+ | <code> | ||
+ | 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() | ||
+ | </code> | ||
+ | |||
+ | {{:notes:data:8knights.net}} | ||
+ | |||
+ | V Pajku dobimo za poteze dolžine 2 dve najkrajši poti dolžine 12 | ||
+ | |||
+ | {{:notes:pics:knights.png}} | ||
+ | |||
+ | Ko dodamo še poteze dolžine 3, je rešitev dolžine 12 več | ||
+ | |||
+ | {{:notes:data:8knightsSol.net}} | ||
+ | |||
+ | **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. | ||
+ | |||
+ | * http://vlado.fmf.uni-lj.si/seminar/dmfa08/ | ||
+ | * http://www.presek.si/3/3-4-Batagelj.pdf |