#####################################################################################################
##This is ComboProject1.txt, a Maple package to generate and investigate integer sequences counting #
##the number of HAMILTONIAN CYCLES for interesting graphs that come from Chess. Generalizing #
##the famous Knight's tour in a 3 by board #
####It is the Maple package created by Team 1 in Dr. Z.'s Combinatorics Clss at #
#Rutgers University, Fall 2020. #
# Save this file as `ComboProject1.txt`, to use it #
#Type, in a Maple session #
#read `ComboProject1.txt`): #
#and then to get a list of the functions type #
#Help(): #
#For Help with any of the functions, type #
#Help(FunctionName) #
#Team Leader: #
#Team members: #
####################################################################################################
print(``):
print(`This is ComboProject1.txt, a Maple package that is part of Project 1 in Dr. Z.'s Combinatorics Class at Rutgers University, Fall 2020`):
print(`Its purpose is to generate and investigate integer sequences counting `):
print(`the number of HAMILTONIAN CYCLES for interesting graphs that come from Chess. Generalizing and Extending Euler's Knight's tour`):
print(``):
print(`VERSION OF Dec. 14, 2020`):
print(`-----------------------------------------`):
print(`-----------------`):
print(``):
print(`Team Leader: Eshaan Gandhi `):
print(``):
print(`Other Team members: Soham Palande, Treasa Bency Biju, Ravali Bommanaboina `):
print(``):
print(`-----------------`):
print(``):
print(`------------------------------------`):
print(`Added Oct. 27, 2020: William Wang detected a bug in SAW and SAWnu, that is now fixed. He won 5 dollars.`):
print(`------------------------------------`):
print(`For a list of all the functions type: Help(); `):
print(`For Help with any of the functions, type Help(FunctionName):`):
Help1:=proc():
if nargs=0 then
print(`The secondary procedures are, CF, KiRtL, KiRtG, Lang, PtoW `):
else
Help(args):
fi:
end:
Help:=proc()
if nargs=0 then
print(`The available procedures are`):
print(` CGP, ContP, GP, KiG, KtG, CGP(G), KingTours3, QiG`):
print(`KingToursGF, KiTours(k,n), KtTours(k,n), KnightTours3, QiTours(k,n), `):
print(`SAW1(G,a,b,k,S), SAW(G), SAW1nu(G,a,b,k,S), SAWnu(G), WtEWalks `):
elif nargs=1 and args[1]=CGP then
print(`CGP(G): Given a graph G finds the set of Hamiltonian cycles (i.e. CLOSED paths) starting with 1 `):
print(`Using a bottom up approach`):
print(`Try: `):
print(`CGP(KtG(3,10)[1]; `):
elif nargs=1 and args[1]=CF then
print(`CF(G): Given a directred graph G=[V,E] where V is the set of vertices and E is the set of edges`):
print(`outputs it in canonical form, followed by the translation Try:`):
print(`CF([{1,2,3},{[1,2],[1,3]}]);`):
elif nargs=1 and args[1]=ContP then
print(`ContP(G,P): Inputs a graph (in Canonical form) and a good path (one that has no repeats) finds the set of`):
print(`good continuations.`):
print(`Try: ContP(KG(3,10)[1],[1]):`):
elif nargs=1 and args[1]=GP then
print(`GP(G,k): The set of all good paths of length k, in the graph G, starting with 1. Try:`):
print(`GP(KG(3,10)[1],30);`):
elif nargs=1 and args[1]=KiG then
print(`KiG(k,n): The KING graph on a k by n chess-board. It returns G,V where `):
print(`G is the graph in CANONICAL FORM, where the vertices are named {1, ... ,n} (where n is the length of the list G)`):
print(`and G[i] is the set of neighbors of vertex i, and V is the "dictionary" telling you the real name of vertex i.`):
print(`For example, to get the graph of King's Tour on the 3 by 10 chessboard, type`):
print(`KiG(3,10); `):
elif nargs=1 and args[1]=KiRtG then
print(`KiRtG(k,Max): The grammar of King's Tours in a chess-board of width k done empirically up to length Max`):
print(`as soon as the langues for two consecutive length agree it stops. It this does not happen before Max it returns FAIL. Try:`):
print(`KiRtG(2,7);`):
elif nargs=1 and args[1]=KiRtL then
print(`KiRtL(m,n): The language of the King's Tours in an m by n Chess board`):
print(` Try: `):
print(`KiRtL(3,4); `):
elif nargs=1 and args[1]=KingTours3 then
print(`KingTours3(t): The precomputed generating function for the number of King's tours on a 3 by n board,`):
print(`in other words, the rational functions whose coefficient of t^n (in its Taylor expansion around 0) is`):
print(`that number. Try:`):
print(`KingTours3(t);`):
elif nargs=1 and args[1]=KingToursGF then
print(`KingToursGF(k,Max,t): The generating function whose coefficients (in its Taylor series) of t^n is the`):
print(`number of King's tours on a k by n Chess board. It uses an empirical-linguist approach`):
print(`by trying to find a grammar up to boards of length Max. If it fails, it returns FAIL.`):
print(`(you can try and make Max bigger, and get a bigger computer). try:`):
print(`KingToursGF(2,7,t);`):
elif nargs=1 and args[1]=KiTours then
print(`KiTours(k,n): set of CLOSED KING-TOURS in a k by n chessboard. `):
print(`For example, type`):
print(`KTours(3,4); `):
elif nargs=1 and args[1]=KnightTours3 then
print(`KnightTours3(z): The generating function, in z, due to Knuth (and possibly Elkins also) for the number of Knight's tours`):
print(`on a 3 by n board. Try:`):
print(`KnightTours3(z);`):
elif nargs=1 and args[1]=KtG then
print(`KtG(k,n): The Knight graph on a k by n chess-board. It returns G,V where `):
print(`G is the graph in CANONICAL FORM, where the vertices are named {1, ... ,n} (where n is the length of the list G)`):
print(`and G[i] is the set of neighbors of vertex i, and V is the "dictionary" telling you the real name of vertex i.`):
print(`For example, to get the graph of Knight's Tour on the 3 by 10 chessboard, type`):
print(`KtG(3,10); `):
elif nargs=1 and args[1]=KtTours then
print(`KtTours(k,n): set of CLOSED KNIGHT-TOURS in a k by n chessboard. `):
print(`For example, to prove Euler wrong (who believed that it is impossible), type`):
print(`KtTours(3,10); `):
elif nargs=1 and args[1]=Lang then
print(`Lang(Corp): Given a set of words finds the linguistic graph in canonical form followed by the`):
print(`list L such that L[i] is the actual letter whose id is i. Try: `):
print(`Lang(KiRtL(3,3);`):
elif nargs=1 and args[1]=PtoW then
print(`PtoW(P): Given a path of lattice points outputs a word in certain alphabet of triples of pairs. Try: `):
print(` P:=KiTours(3,4)[1]; PtoW(P,3,4); `):
elif nargs=1 and args[1]=SAW then
print(` SAW(G): The set of Closed Hamiltonian paths in the graph G (in canonical form) starting at 1 and G[1][1] `):
print(`Using a TOP down approach`):
print(`same thing at CGP(G) except for orientation `):
print(`Try: SAW(KtG(3,10)[1]);` ):
elif nargs=1 and args[1]=SAWnu then
print(` SAWnu(G): The NUMBER of Closed Hamiltonian paths in the graph G (in canonical form) starting at 1 and G[1][1] `):
print(`Using a TOP down approach`):
print(`same thing at CGP(G) except for orientation. Try: `):
print(`SAW(KtG(3,10)[1]);`):
elif nargs=1 and args[1]=WtEWalks then
print(`WtEwalks(G,a,b,t): The weight enumerator, according to the weight t^LengthOfWalk, of the set of paths in a directed graph G`):
print(`(given in canonical form) from vertex a to vertex b. Try:`):
print(`WtEwalks([{2,3},{1,3},{1,2}],1,2,t);`):
else
print(`There is no Help for`):
print(args):
fi:
end:
with(plots);
#################### Base Functions #####################################################
#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) local i:
{seq(op(SAW1(G,1,G[1][i],nops(G)-1,{})),i=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) local i:
add(SAW1nu(G,1,G[1][i],nops(G)-1,{}),i=1..nops(G[1])):
end:
#KtTours(k,n): The set of closed Knight-Tours in a k by n chess-board. Try:
#KtTours(3,10);
KtTours:=proc(k,n) local G,V,TOURS,t,i:
G:=KtG(k,n):
V:=G[2]:
G:=G[1]:
TOURS:=SAW(G):
{seq([seq(V[t[i]],i=1..nops(t)),V[t[1]]],t in TOURS)}:
end:
#PtoW(P,m,n): Given a path of lattice points in {1,2,..,m}x {1,...,n} outputs a word in certain alphabet of m-tuples of pairs
#Try:
#PtoW(KiTours(3,4)[1],3,4);
PtoW:=proc(P,m,n) local T,i,j:
if nops(P)<>m*n+1 then
print(`Bad input`):
RETURN(FAIL):
fi:
if nops(convert(P,set))<>m*n then
print(`Bad input`):
RETURN(FAIL):
fi:
if P[1]<>[1,1] or P[-1]<>[1,1] then
print(`P must start and end with`, [1,1]):
RETURN(FAIL):
fi:
T[[1,1]]:=[P[-2]-P[-1] , P[2]-P[1]]:
for i from 2 to nops(P)-1 do
T[P[i]]:=[P[i-1]-P[i],P[i+1]-P[i]]:
od:
[seq([seq(T[[i,j]],i=1..m)],j=1..n)]:
end:
#Lang(Corp): Given a set of words finds the linguistic graph in canonical form followed by the
#list L such that L[i] is the actual letter whose id is i. Try:
#Lang(KiRtL(3,3));
Lang:=proc(COR) local VERTICES,EDGES,w,i1:
#VERTICES IS THE SET OF ALL LETTERS THAT SHOWED UP
VERTICES:={seq(op(w), w in COR)}:
EDGES:={seq(seq([w[i1],w[i1+1]],i1=1..nops(w)-1), w in COR)}:
[VERTICES, EDGES]:
end:
#CF(G): Given a directred graph G=[V,E] where V is the set of vertices and E is the set of edges
#outputs it in canonical form, followed by the translation Try:
#CF([{1,2,3},{[1,2],[1,3]}]);
CF:=proc(G) local T,V,e,i,G1:
V:=convert(G[1],list):
for i from 1 to nops(V) do
T[V[i]]:=i:
od:
for i from 1 to nops(V) do
G1[i]:={}:
od:
for e in G[2] do
G1[T[e[1]] ]:=G1[T[e[1]] ] union {T[e[2]]}:
od:
[seq(G1[i],i=1..nops(V))],V:
end:
#WtEwalks(G,a,b,t): The weight enumerator, according to the weight t^LengthOfWalk, of the set of paths in a directed graph G
#(given in canonical form) from vertex a to vertex b. Try:
#WtEwalks([{2,3},{1,3},{1,2}],1,2,t);
WtEwalks:=proc(G,a,b,t) local eq,var,X,eq1,i,j:
if not (1<=a and a<=nops(G) and 1<=b and b<=nops(G)) then
print(a,b, `must be integers between 1 and `, nops(G)):
RETURN(FAIL):
fi:
var:={seq(X[i],i=1..nops(G))}:
#X[i] is the weight-enumerator of walks from i to b
eq:={}:
for i from 1 to nops(G) do
#Every walk from i to b unless it is of length 0 (that its weight is 1) starts with a walk from a neighbor of i
eq1:=X[i]-t*add(X[j], j in G[i]):
#if i=b we must also include the empty walk
if i=b then
eq1:=eq1-1:
fi:
eq:=eq union {eq1}:
od:
normal(subs(solve(eq,var),X[a])):
end:
#################### King #####################################################
#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:
#KiTours(k,n): The set of closed King-Tours in a k by n chess-board. Try:
#KiTours(3,4);
KiTours:=proc(k,n) local G,V,TOURS,t,i:
G:=KiG(k,n):
V:=G[2]:
G:=G[1]:
TOURS:=SAW(G):
{seq([seq(V[t[i]],i=1..nops(t)),V[t[1]]],t in TOURS)}:
end:
#KiRtL(m,n): The language of the King's Tours in an m by n Chess board
#Try:
#KiRtL(3,4);
KiRtL:=proc(m,n) local S,P:
S:=KiTours(m,n):
{seq( [0,op(PtoW(P,m,n)),1], P in S)}:
end:
#KiRtG(k,Max): The grammar of King's Tours in a chess-board of width k done empirically up to length Max
#as soon as the langues for two consecutive length agree it stops. It this does not happen before Max it returns FAIL. Try:
#KiRtG(2,7);
KiRtG:=proc(k,Max) local i:
for i from 1 to Max do
if Lang(KiRtL(k,i))=Lang(KiRtL(k,i+1)) then
RETURN( CF(Lang(KiRtL(k,i)))):
fi:
od:
FAIL:
end:
#KingToursGF(k,Max,t): The generating function whose coefficients (in its Taylor series) of t^n is the
#number of King's tours on a k by n Chess board. It uses an empirical-linguist approach
#by trying to find a grammar up to boards of length Max. If it fails, it returns FAIL.
#(you can try and make Max bigger, and get a bigger computer). try:
#KingToursGF(2,7,t);
KingToursGF:=proc(k,Max,t) local G,f:
G:=KiRtGnew(k,Max) :
if G=FAIL then
RETURN(FAIL):
fi:
if not (G[2][1]=0 and G[2][2]=1) then
RETURN(FAIL):
fi:
#we divide by t since in our model where we have a starting letter 0 and an ending letter 1,
#each path has one extra length
f:=normal(WtEwalks(G[1],1,2,t)/t):
#We manually add the coefficient of t^2
f:=normal(f+nops(KiTours(k,2))*t^2 ):
#Following the convention (from Kinght's Tours) that we don't count different orienations, we divide by 2
f:=f/2:
normal(f):
end:
#KingTours3(t): The precomputed generating function for the number of King's tours on a 3 by n board,
#in other words, the rational functions whose coefficient of t^n (in its Taylor expansion around 0) is
#that number. Try:
#KingTours3(t);
KingTours3:=proc(t):
2*t^2*(3*t^4+4*t^3+2*t^2-2)/(6*t^4+8*t^3+15*t^2+4*t-1):
end:
#################### Knights #####################################################
#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:
#KtRtL(m,n): The language of the Knight's Tours in an m by n Chess board
#Try:
#KtRtL(3,4);
KtRtL:=proc(m,n) local S,P:
S:=KtTours(m,n):
{seq( [0,op(PtoW(P,m,n)),1], P in S)}:
end:
#KtRtGnew(k,Max): The grammar of Knight's Tours in a chess-board of width k done empirically up to length Max
#as soon as the langues for two consecutive length agree it stops. It this does not happen before Max it returns FAIL. Try:
#KtRtG(2,7);
KtRtGnew:=proc(k,Max) local i,L1,L2,L:
#i must start from the first config where a knight's tour exists for a kxn board
L:=[[{},{}]]:
for i from 10 to Max do
L1:=L[i]:
L2:=Lang(KtRtL(k,i+1)):
L:=[op(L),L2]:
if L1=L2 then
RETURN(CF(Lang(L1))):
fi:
od:
FAIL:
end:
#KtRtG(k,Max): The grammar of Knight's Tours in a chess-board of width k done empirically up to length Max
#as soon as the langues for two consecutive length agree it stops. It this does not happen before Max it returns FAIL. Try:
#KtRtG(2,7);
KtRtG:=proc(k,Max) local i:
#i must start from the first config where a knight's tour exists for a kxn board
for i from 10 to Max do
if Lang(KtRtL(k,i))=Lang(KtRtL(k,i+1)) then
RETURN(CF(Lang(KtRtL(k,i)))):
fi:
od:
FAIL:
end:
#KnightToursGF(k,Max,t): The generating function whose coefficients (in its Taylor series) of t^n is the
#number of Knight's tours on a k by n Chess board. It uses an empirical-linguist approach
#by trying to find a grammar up to boards of length Max. If it fails, it returns FAIL.
#(you can try and make Max bigger, and get a bigger computer). try:
#KnightToursGF(2,7,t);
KnightToursGF:=proc(k,Max,t) local G,f:
G:=KtRtG(k,Max) :
if G=FAIL then
RETURN(FAIL):
fi:
if not (G[2][1]=0 and G[2][2]=1) then
RETURN(FAIL):
fi:
#we divide by t since in our model where we have a starting letter 0 and an ending letter 1,
#each path has one extra length
f:=normal(WtEwalks(G[1],1,2,t)/t):
#We manually add the coefficient of t^2
f:=normal(f+nops(KtTours(k,2))*t^2 ):
#Following the convention (from Knight's Tours) that we don't count different orienations, we divide by 2
f:=f/2:
normal(f):
end:
#KiRtGnew(k,Max): The grammar of King's Tours in a chess-board of width k done empirically up to length Max
#as soon as the langues for two consecutive length agree it stops. It this does not happen before Max it returns FAIL. Try:
#KiRtG(2,7);
KiRtGnew:=proc(k,Max) local i,L,L1,L2:
L:=[]:
L:=[op(L),Lang(KiRtL(k,1))]:
for i from 1 to Max do
L1:=L[i]:
L2:=Lang(KiRtL(k,i+1)):
L:=[op(L),L2]:
if L1=L2 then
RETURN(CF(L1)):
fi:
od:
FAIL:
end:
#KnightTours3(z): The generating function, in z, due to Knuth (and possibly Elkins also) for the number of Knight's tours
#on a 3 by n board. Try:
#KnightTours3(z);
KnightTours3:=proc(z)
16 * (z^5 + 5*z^6 - 34*z^7 - 116*z^8 + 505*z^9 + 616*z^10 - 3179*z^11 - 4*z^12 + 9536*z^13 - 8176*z^14 - 13392*z^15 + 15360*z^16 + 13888*z^17 + 2784*z^18 - 3328*z^19 - 22016*z^20 + 5120*z^21 + 2048*z^22) / (1 - 6*z - 64*z^2 + 200*z^3 + 1000*z^4 - 3016*z^5 - 3488*z^6 + 24256*z^7 - 23776*z^8 - 104168*z^9 + 203408*z^10 + 184704*z^11 - 443392*z^12 - 14336*z^13 + 151296*z^14 - 145920*z^15 + 263424*z^16 - 317440*z^17 - 36864*z^18 + 966656*z^19 - 573440*z^20 - 131072*z^21):
end:
#################### King With Double Steps #####################################################
#KiDoubleG(k,n): The King graph on a k by n board
KiDoubleG:=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],[2,0],[-1,0],[-2,0],[0,1],[0,2],[0,-1],[0,-2],[1,1],[2,2],[-1,-1],[-2,-2],[1,-1],[2,-2],[-1,1],[-2,2]}:
#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:
#KiDoubleTours(k,n): The set of closed King-Tours in a k by n chess-board. Try:
#KiTours(3,4);
KiDoubleTours:=proc(k,n) local G,V,TOURS,t,i:
G:=KiDoubleG(k,n):
V:=G[2]:
G:=G[1]:
TOURS:=SAW(G):
{seq([seq(V[t[i]],i=1..nops(t)),V[t[1]]],t in TOURS)}:
end:
#KiDoubleRtL(m,n): The language of the King Doubles Tours in an m by n Chess board
#Try:
#KiDoubleRtL(3,4);
KiDoubleRtL:=proc(m,n) local S,P:
S:=KiDoubleTours(m,n):
{seq( [0,op(PtoW(P,m,n)),1], P in S)}:
end:
#KiDoubleRtG(k,Max): The grammar of King's Tours in a chess-board of width k done empirically up to length Max
#as soon as the langues for two consecutive length agree it stops. It this does not happen before Max it returns FAIL. Try:
#KiDoubleRtG(2,7);
KiRtG:=proc(k,Max) local i:
for i from 1 to Max do
if Lang(KiRtL(k,i))=Lang(KiRtL(k,i+1)) then
RETURN( CF(Lang(KiRtL(k,i)))):
fi:
od:
FAIL:
end:
#################### Rook #####################################################
#RiG(k,n): The Rook graph on a k by n board
RiG:=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]:
#Since it is a k * n chessboard it can basically go all the k's and all the ns
Moves:= {seq([0, l], l = 1..k),seq([u, 0], u = 1..n), seq([0, -l], l = k..1, -1),seq([-u, 0], u = n..1, -1)}:
#Moves:=Moves minus {pt}:
#print(Moves):
#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:
#RiTours(k,n): The set of closed Rook-Tours in a k by n chess-board. Try:
#RiTours(3,4);
RiTours:=proc(k,n) local G,V,TOURS,t,i:
G:=RiG(k,n):
V:=G[2]:
G:=G[1]:
TOURS:=SAW(G):
{seq([seq(V[t[i]],i=1..nops(t)),V[t[1]]],t in TOURS)}:
end:
#################### Bishop #####################################################
#BiG(k,n): The Bishop graph on a k by n board
BiG:=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]:
#Since it is a k * n chessboard it can basically go all the k's and all the ns
Moves:= {seq([l, l], l = 1..k),seq([-u, -u], u = 1..n), seq([l, -l], l = k..1, -1),seq([-u, u], u = n..1, -1), seq([l, l], l = 1..n),seq([-u, -u], u = 1..k), seq([l, -l], l = n..1, -1),seq([-u, u], u = k..1, -1)}:
#Moves:=Moves minus {pt}:
#print(Moves):
#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:
#BiTours(k,n): The set of closed Bishop-Tours in a k by n chess-board. Try:
#BiTours(3,4);
BiTours:=proc(k,n) local G,V,TOURS,t,i:
G:=BiG(k,n):
V:=G[2]:
G:=G[1]:
TOURS:=SAW(G):
{seq([seq(V[t[i]],i=1..nops(t)),V[t[1]]],t in TOURS)}:
end:
#################### Queen #####################################################
#QiG(k,n): The Queen graph on a k by n board
QiG:=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]:
#Since it is a k * n chessboard it can basically go all the k's and all the ns
Moves:= {seq([0, l], l = 1..k),seq([u, 0], u = 1..n), seq([0, -l], l = k..1, -1),seq([-u, 0], u = n..1, -1), seq([l, l], l = 1..k),seq([-u, -u], u = 1..n), seq([l, -l], l = k..1, -1),seq([-u, u], u = n..1, -1), seq([l, l], l = 1..n),seq([-u, -u], u = 1..k), seq([l, -l], l = n..1, -1),seq([-u, u], u = k..1, -1)}:
#Moves:=Moves minus {pt}:
#print(Moves):
#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:
#QiTours(k,n): The set of closed Queen-Tours in a k by n chess-board. Try:
#QiTours(3,4);
QiTours:=proc(k,n) local G,V,TOURS,t,i:
G:=QiG(k,n):
V:=G[2]:
G:=G[1]:
TOURS:=SAW(G):
{seq([seq(V[t[i]],i=1..nops(t)),V[t[1]]],t in TOURS)}:
end:
Help()