##########################################################################

                    ################################                    
                    #            knight            #                    
                    ################################                    
                                                                      
#                  knight tours on a 8x8 chessboard                     
#     coords are (1,1) in lower LF corner, (8,8) in upper RH corner    
                                                                      
#copyleft David Joyner, 5-21-1996                                      
##########################################################################

##
##initialization
##
knighttour:=proc()
 global Been, AT,KnightTree,MaxBranches,v1;

Been:=[]:  ## list of squares visited, initially empty
AT:=[1,1]: ##unused  - initially at (1,1)
networks[new](KnightTree);  ##Tree of knight moves
MaxBranches:=5;
#networks[addvertex](v.1,KnightTree); ##initial position in knight tree
networks[addvertex](v.1.1,KnightTree): ##initial position in knight tree
end:

##
##returns list of allowable next moves
##
cango:=proc(at::list)
 global Been;
 local temp,x,y,MM,NN;
## MM,NN are introduced to alow modification for an MMxNN board
##here we take MM=NN=8 (MM=#cols, NN=#rows)
MM:=8;
NN:=8;

temp:=[];
x:=at[1]; y:=at[2];
if (x+1<MM+1 and y+2<NN+1 and not(member([x+1,y+2],Been)))
  then temp:=[[x+1,y+2]]; fi;
if (x+2<MM+1 and y+1<NN+1 and not(member([x+2,y+1],Been)))
  then temp:=[op(temp),[x+2,y+1]]; fi;
if (x+2<MM+1 and y-1>0 and not(member([x+2,y-1],Been)))
  then temp:=[op(temp),[x+2,y-1]]; fi;
if (x+1<MM+1 and y-2>0 and not(member([x+1,y-2],Been)))
  then temp:=[op(temp),[x+1,y-2]]; fi;
if (x-1>0 and y-2>0 and not(member([x-1,y-2],Been)))
  then temp:=[op(temp),[x-1,y-2]]; fi;
if (x-2>0 and y-1>0 and not(member([x-2,y-1],Been)))
  then temp:=[op(temp),[x-2,y-1]]; fi;
if (x-2>0 and y+1<NN+1 and not(member([x-2,y+1],Been)))
  then temp:=[op(temp),[x-2,y+1]]; fi;
if (x-1>0 and y+2<NN+1 and not(member([x-1,y+2],Been)))
  then temp:=[op(temp),[x-1,y+2]]; fi;
#print(`from `,at,` can move to `,temp);
RETURN(temp);
end:

##
##finds last move where there were 2 possibilities
##
findlastfork:=proc(L::list)
local i,n;
n:=nops(L);
for i from n to 1 by -1 do
 if op(i,L)>=2 then
  RETURN(i);
 fi;
od;
RETURN(0);
end:

##
##moves knight n moves randomly from at
##(the random seed changes after each call)
##If n moves cannot be found, it stops
##
knightmoves:=proc(n::integer,at::list)
 local i,temp,temp1,temp2;
 global Been,LastBeen;

temp:=at;
for i from 1 to n do
 temp1:=nops(Been);
# print(i,temp1);
 temp:=nextmove(temp);
 temp2:=nops(Been);
# print(`2  `,temp2);
 if temp1=temp2 then 
    Been:=[op(Been),temp];
    RETURN(Been); 
 fi;
od;
print(`Knight has no untoured squares after `,nops(Been),` moves`);
RETURN(Been);
end:

##
##Tries using a simple backtrack, to find
##an n move "random" knight tour from at
##(the random seed changes after each call)
##
searchknightmoves:=proc(n::integer,at::list)
 local i,temp,temp1,temp2,beenlist,atlist,cg,numtries,
    numlist,bt,maxtry,listnumlist,temp3,maxtour,MaxBeen;
 global Been,LastBeen;

maxtry:=readstat(`How many tries? (use semicolon)`);
temp:=at;
numtries:=0;
atlist:=[at];
Been:=[];
MaxBeen:=Been;
beenlist:=[];
numlist:=[];
maxtour:=nops(Been);
listnumlist:=[numlist];
for i from 1 to n do
 cg:=cango(temp);
 numlist:=[op(numlist),nops(cg)]; ##list of possible moves at each step
 bt:=findlastfork(numlist); ##last fork for this list
 if nops(cg)=0 then 
   print(`Knight has no untoured squares after `,nops(Been)+1,` moves`);
 fi;
 if (nops(cg)=0 and nops(beenlist)>bt) then 
   Been:=beenlist[bt];
   temp:=op(bt,Been);
   numlist:=listnumlist[bt];
   i:=bt;
   numtries:=numtries+1;
 fi; 
 temp1:=nops(Been);
 temp:=nextmove(temp);
 temp2:=nops(Been);
 if (temp2>n-1) then 
    print(n,` move knight tour found`);
    RETURN(Been); 
 fi;
 if nops(cg)>0 then 
  atlist:=[op(atlist),temp];
  beenlist:=[op(beenlist),Been];
  listnumlist:=[op(listnumlist),numlist];
 fi;
 temp3:=maxtour;
 maxtour:=max(maxtour,nops(Been)+1);
 if maxtour<>temp3 then MaxBeen:=[op(Been),temp]; fi;
  if numtries>maxtry then 
      print(`Number of backtracks performed: `,numtries);
      Been:=MaxBeen;
      RETURN(Been);
  fi;
  if (numtries>=maxtry) then 
    Been:=MaxBeen;
    print(`Number of backtracks performed: `,numtries);
    RETURN(Been); 
  fi;
od;
Been:=MaxBeen;
RETURN(Been);
end:

##
##random next move, updates Been. If the next move choosen has
##no more moves then it randomly chooses a move again unless
##that is the only next move
##
nextmove:=proc(at::list)
 global LastBeen,Been;
 local x,y,temp,cg,n,rrr,Seed;

cg:=cango(at);
#print(cg);
if nops(cg)=0 then 
#  print(`Knight has no untoured squares after `,nops(Been),` moves`);
  LastBeen:=Been;
#Been:=[op(Been),at];
#  print(Been);
  RETURN(at);
fi;
Been:=[op(Been),at];
n:=nops(cg);
Seed:=readlib(randomize)();  ### randomize seed
randomize(Seed);
rrr:=rand(1..n);
temp:=op(rrr(),cg);
if n>1 and nops(cango(temp))=0 then 
 Seed:=readlib(randomize)();  ### randomize seed
 randomize(Seed);
 rrr:=rand(1..n);
 temp:=op(rrr(),cg);
fi;
RETURN(temp);
end:

##
##creates knight tour tree, indexing vertices by the 
##coords of the squares visited
##
##maple code for indexing vertices numerically is commented out
##
addnodes:=proc(at::list)
local cg,numvertices,n,x,y,v,vx,vy;

numvertices:=nops(networks[vertices](KnightTree));
cg:=cango(at);
x:=at[1];y:=at[2];
n:=nops(cg);
print(n);
#networks[addvertex](v.numvertices,KnightTree);
networks[addvertex](v.x.y,KnightTree);
if (cg=[] or nops(Been)>10) then 
 print(`tree complete`);
 networks[draw](KnightTree);
fi;
#for i from 1 to n do
# networks[addvertex](v.(numvertices+i),KnightTree);
# networks[addedge]([v.numvertices,v.(numvertices+i)],KnightTree); 
#od;
for v in cg do
 vx:=v[1];vy:=v[2];
 networks[addvertex](v.vx.vy,KnightTree);
 networks[addedge]([v.x.y,v.vx.vy],KnightTree); 
od;
end:

##
##prints array of knight tour
##
drawtour:=proc()
 local tourmatrix,i,j,x,y,n;

tourmatrix:=array(1..8,1..8);
for i from 1 to 8 do
 for j from 1 to 8 do
  tourmatrix[i,j]:=0;
 od;
od;
n:=nops(Been);
for i from 1 to n do
 x:=Been[i][1];
 y:=Been[i][2];
 tourmatrix[9-y,x]:=i;
od;
print(tourmatrix);
end:

##
##tries to find a knight tour N moves long
##
findtour:=proc(N::integer,at::list)
local numtries,maxtour,tempbeen,been1,tempnum,temp1,
 temp2,maxbeen,mintour,M,total,ave;
global Been,MaxBeen,MinBeen;

been1:=Been;
numtries:=0;
total:=0;
maxtour:=nops(Been);
tempbeen:=knightmoves(N,at);
if nops(tempbeen)>=N then 
  print(nops(tempbeen),` move tour found`);
  RETURN(tempbeen);
fi;
M:=readstat(`Enter number of searches: `);
while nops(tempbeen)<N and numtries<M do
#readlib(randomize)(numtries*500+2);  ### randomize seed
Been:=been1;
tempbeen:=knightmoves(N,at);
if numtries=0 then MinBeen:=Been; fi;
tempnum:=numtries;
if nops(tempbeen)>=N then 
  print(nops(tempbeen),` move tour found`);
  RETURN(tempbeen);
fi;
temp1:=maxtour;
maxtour:=max(maxtour,nops(Been));
total:=total+nops(Been);
if maxtour<>temp1 then MaxBeen:=Been; 
  else if nops(Been)<nops(MinBeen) then MinBeen:=Been; fi; 
fi;
numtries:=tempnum+1;
od;
print(`largest tour found: `,maxtour, ` numtries = `,numtries);
print(`shortest tour found: `,nops(MinBeen));
print(`Length of average tour: `,total/numtries);
Been:=MaxBeen;
#RETURN(MaxBeen);
end:

##
##tries to make all moves from at indicated
##by the list mv in \Prod_{i=1}^64 #(possible ith moves) 
##
listmove:=proc(mv::list,at::list)
local length,cg,i,temp,nummoves,nextmove;
global Been;

Been:=[at];
length:=nops(mv);
temp:=at;
for i from 1 to length do
 cg:=cango(temp);
 if nops(cg)=0 then 
  print(`Made `,i,` moves`);
  RETURN(Been);
 fi;
 nummoves:=nops(cg);
 nextmove:=`mod`(mv[i],nummoves);
 if nextmove=0 then nextmove:=nummoves; fi;
 temp:=cg[nextmove];
 Been:=[op(Been),temp];
od;
print(`Made all `,length,` moves`);
RETURN(Been);
end:

##
##tries to make all moves from at indicated
##by the list mv in \Prod_{i=1}^64 #(possible ith moves) 
##does some backtracking
##
listmove_with_bt:=proc(mv::list,at::list,maxtries::integer)
local length,cg,i,temp,nummoves,nextmove,beenlist,numtries,
mvlist,nbeen,stuckat;
global Been;

Been:=[at];
mvlist:=mv;
beenlist:=[Been];
numtries:=0;
length:=nops(mv);
temp:=at;
for i from 1 to length do
 cg:=cango(temp);
 if (nops(cg)=0 and i<length) then 
  stuckat:=i;
  print(`Made `,i,` moves - backtracking ...`);
  mvlist[stuckat-2]:=mvlist[stuckat-2]+1;
  Been:=beenlist[stuckat-2];
  i:=stuckat-2;
  numtries:=numtries+1;
  nbeen:=nops(Been);
  temp:=Been[nbeen];
  cg:=cango(temp);
  if numtries>maxtries then 
    print(`Made `,numtries,` backtracks`);
    print(`Made `,i,` moves.`);
    RETURN(Been);
  fi;
 fi;
 nummoves:=nops(cg);
 if nummoves>0 then nextmove:=`mod`(mvlist[i],nummoves); fi;
 if (nummoves>0 and nextmove=0) then nextmove:=nummoves; fi;
 temp:=cg[nextmove];
 Been:=[op(Been),temp];
 beenlist:=[op(beenlist),Been];
od;
print(`Made all `,length,` moves.  Total backtracks: `,numtries);
RETURN(Been);
end:

##
##implementation of warnsdorff's rule
##
warnsdorff:=proc(at::list)
local i,minmove,cg,nummoves,tempat,tempBeen;
global Been;
 
Been:=[at];
tempat:=at;
while nops(Been)<64 do
 minmove:=8;
 cg:=mincango(tempat);
 if nops(cg)=0 then
  print(`Knight tour `,nops(Been),` moves long.`);
  RETURN(Been);
 fi;
 tempat:=cg[1];
 Been:=[op(Been),tempat];
 if nops(Been)>63 then 
   print(`Complete knight tour found.`);
   RETURN(Been); 
 fi;
od;
RETURN(Been);
end:

##
##returns list of allowable next moves all of which
##have the min number of next moves (to be used with 
##warnsdorff's rule)
#
##
mincango:=proc(at::list)
 global Been;
 local temp,x,y,tempmin,minmoves,i,MM,NN;
## MM,NN are introduced to alow modification for an MMxNN board
##here we take MM=NN=8 (MM=#cols, NN=#rows)
MM:=8;
NN:=8;
temp:=[];
x:=at[1]; y:=at[2];
if (x+1<MM+1 and y+2<NN+1 and not(member([x+1,y+2],Been)))
  then temp:=[[x+1,y+2]]; fi;
if (x+2<MM+1 and y+1<NN+1 and not(member([x+2,y+1],Been)))
  then temp:=[op(temp),[x+2,y+1]]; fi;
if (x+2<MM+1 and y-1>0 and not(member([x+2,y-1],Been)))
  then temp:=[op(temp),[x+2,y-1]]; fi;
if (x+1<MM+1 and y-2>0 and not(member([x+1,y-2],Been)))
  then temp:=[op(temp),[x+1,y-2]]; fi;
if (x-1>0 and y-2>0 and not(member([x-1,y-2],Been)))
  then temp:=[op(temp),[x-1,y-2]]; fi;
if (x-2>0 and y-1>0 and not(member([x-2,y-1],Been)))
  then temp:=[op(temp),[x-2,y-1]]; fi;
if (x-2>0 and y+1<NN+1 and not(member([x-2,y+1],Been)))
  then temp:=[op(temp),[x-2,y+1]]; fi;
if (x-1>0 and y+2<NN+1 and not(member([x-1,y+2],Been)))
  then temp:=[op(temp),[x-1,y+2]]; fi;
#print(`from `,at,` can move to `,temp);
minmoves:=min(seq(nops(cango(temp[i])),i=1..nops(temp)));
tempmin:=[];
for i from 1 to nops(temp) do
 if nops(cango(temp[i]))=minmoves then
  tempmin:=[op(tempmin),temp[i]];
 fi;
od;
RETURN(tempmin);
end:

##
##implementation of a random version of warnsdorff's rule
##
random_warnsdorff:=proc(at::list)
local i,minmove,cg,nummoves,tempat,tempBeen,Seed,n,rrr,temp;
global Been;
 
Been:=[at];
tempat:=at;
while nops(Been)<64 do
 cg:=mincango(tempat);
 if nops(cg)=0 then
  print(`Knight tour `,nops(Been),` moves long.`);
  RETURN(Been);
 fi;
n:=nops(cg);
Seed:=readlib(randomize)();  ### randomize seed
randomize(Seed);
rrr:=rand(1..n);
tempat:=op(rrr(),cg);
#tempat:=cg[rrr]; 
Been:=[op(Been),tempat];
if nops(Been)>63 then 
   print(`Complete knight tour found.`);
   RETURN(Been); fi;
od;
RETURN(Been);
end:

save `knight.m`;