====== 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