Help:=proc(): print(` KtG(k,n),KiG(k,n),  ContP(G,P), GP(G,k) , CGP(G) `): 
print(`SAW1(G,a,b,k,S), SAW(G),  SAW1nu(G,a,b,k,S), SAWnu(G) `):
end:

#KtG(k,n): The Knight graph on a k by n board
KtG:=proc(k,n) local V,E,i,j,T1,v,Neighs,Moves,m,pt:

#The set the list of  vertices in the k by n board (using matrix indexing)
V:=[seq(seq(seq([i,j],j=1..n),i=1..k))]:

#T1 is a labelling of the vertices in V

for i from 1 to nops(V) do
T1[V[i]]:=i:
od:

#E is a list such that its i-th entry is the set of neighbors of V[i] using the above-indexing

E:=[]:

for i from 1 to nops(V) do
 pt:=V[i]:

Moves:={[1,2],[-1,2],[1,-2],[-1,-2],[2,1],[2,-1],[-2,1],[-2,-1]}:
#There are up to 8 neighbors of any vertex 
Neighs:={seq(pt+m,m in Moves)}:

#But many of them fall off the board, 
Neighs:=Neighs intersect convert(V,set):

#We append to the "list of neighbors" the set of neighbors of the current vertex BUT in terms of their "ids" (given by T1)
#getting a description of the graph in "cannical form"
E:=[op(E),{seq(T1[v],v in Neighs)}]:
od:

#We return the graph in "canonical form" where the vertices (members of V), are labelled by positive inetegers from 1 to nops(V)
#together with the "dictionary"
E,V:
end:




#KiG(k,n): The King graph on a k by n board
KiG:=proc(k,n) local V,E,i,j,T1,v,Neighs,Moves,m,pt:

#The set the list of  vertices in the k by n board (using matrix indexing)
V:=[seq(seq(seq([i,j],j=1..n),i=1..k))]:

#T1 is a labelling of the vertices in V

for i from 1 to nops(V) do
T1[V[i]]:=i:
od:

#E is a list such that its i-th entry is the set of neighbors of V[i] using the above-indexing

E:=[]:

for i from 1 to nops(V) do
 pt:=V[i]:

Moves:={[1,0],[-1,0],[0,1],[0,-1],[1,1],[-1,-1],[1,-1],[-1,1]}:
#There are up to 8 neighbors of any vertex 
Neighs:={seq(pt+m,m in Moves)}:

#But many of them fall off the board, 
Neighs:=Neighs intersect convert(V,set):

#We append to the "list of neighbors" the set of neighbors of the current vertex BUT in terms of their "ids" (given by T1)
#getting a description of the graph in "cannical form"
E:=[op(E),{seq(T1[v],v in Neighs)}]:
od:

#We return the graph in "canonical form" where the vertices (members of V), are labelled by positive inetegers from 1 to nops(V)
#together with the "dictionary"
E,V:
end:




#ContP(G,P): Inputs a graph (in Canonical form) and a good path (one that has no repeats) finds the set of
#good continations.
#Try: ContP(KG(3,10)[1],[1]):
ContP:=proc(G,P) local S,s,v:

#v is the last vertex in the path P
v:=P[nops(P)]:


#S  is the set of legal followers
S:=G[v] minus convert(P,set):

#The output is the set of legal continuations obtained by appending to P all the legal continuations
{seq([op(P),s], s in S)}:
end:

#GP(G,k): The set of all good paths of length k, in the graph G, starting with 1. Try:
#GP(KG(3,10)[1],30);
GP:=proc(G,k) local SetP,P:
option remember:

#This is the initial condition
if k=1 then
 RETURN({[1]}):
fi:

#We can the procedure recursively
SetP:=GP(G,k-1):

#We call ContP(G,P) for each of the members of that are good so far, and take their union
{seq(op(ContP(G,P)), P in SetP)}:

end:

#CGP(G): Given a graph G finds the set of Hamiltonian cycles starting with 1 
CGP:=proc(G) local S,AllP,NeiOne,P:

#AllP is the set of ALL Hamiltionain Paths 
AllP:=GP(G,nops(G)):
NeiOne:=G[1]:

#We now only include those that end with a neighbor of 1
S:={}:

for P in AllP do
 if member(P[nops(P)],NeiOne) then
  S:=S union {P}:
 fi:
od:

S:

end:


#SAW1(G,a,b,k,S): Inputs a graph G of {1, ..., n} and two vertices a and b and a pos. integer k and a set of vertices S, outputs the
#set of walks of length k from a to b that avoid S. Try
#SAW1(KtG(3,5)[1],1,2,5,{}):
SAW1:=proc(G,a,b,k,S) local gu,n,a1,lu,lu1,mu:
option remember:
n:=nops(G):
if not (1<=a and a<=n and 1<=b and b<=n) then
 RETURN(FAIL):
fi:

if k=1 then
 if member(b,G[a]) and  not member(a,S) and not member(b,S) then
  RETURN({[a,b]}):
 else
  RETURN({}):
 fi:
fi:


if (member(a,S) or member(b,S)) then
 RETURN({}):
fi:

mu:=G[a] minus (S union {a}):

gu:={}:

for a1  in mu do
 lu:=SAW1(G,a1,b,k-1,S union {a}):
 gu:=gu union {seq([a,op(lu1)],lu1 in lu)}:
od:

gu:

end:

#SAW(G): The set of Closed Hamiltonian paths in the graph G (in canonical form) starting at 1 and G[1][1]
#Try: SAW(KtG(3,10)[1]):
SAW:=proc(G):
SAW1(G,1,G[1][1],nops(G)-1,{}):
end:









#SAW1nu(G,a,b,k,S): Inputs a graph G of {1, ..., n} and two vertices a and b and a pos. integer k and a set of vertices S, outputs the
#NUMBER of walks of length k from a to b that avoid S. Try
#SAW1nu(KtG(3,5)[1],1,2,5,{}):
SAW1nu:=proc(G,a,b,k,S) local mu,n,a1:
option remember:
n:=nops(G):
if not (1<=a and a<=n and 1<=b and b<=n) then
 RETURN(FAIL):
fi:

if k=1 then
 if member(b,G[a]) and  not member(a,S) and not member(b,S) then
  RETURN(1):
 else
  RETURN(0):
 fi:
fi:


if (member(a,S) or member(b,S)) then
 RETURN(0):
fi:

mu:=G[a] minus (S union {a}):

add(SAW1nu(G,a1,b,k-1,S union {a}), a1 in mu):

end:


#SAWnu(G): The NUMBER of Closed Hamiltonian paths in the graph G (in canonical form) starting at 1 and G[1][1]
#Try: SAWnu(KtG(3,10)[1]):
SAWnu:=proc(G):
SAW1nu(G,1,G[1][1],nops(G)-1,{}):
end: