Differences

This shows you the differences between two versions of the page.

Link to this comparison view

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
notes/net/puzz1.txt · Last modified: 2015/07/16 22:39 by vlado
 
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki