##################################################################### # most current version: # #http://sites.math.rutgers.edu/~zeilberg/tokhniot/Kurchan.txt # ## Kurchan.txt Save this file as Kurchan.txt to use it, # # stay in the # ## same directory, get into Maple (by typing: maple ) # ## and then type: read `Kurchan.txt` # ## Then follow the instructions given there # ## # ## Written by Pablo Blanco and # #Doron Zeilberger, Rutgers University , # ###################################################################### print(`First Written: Dec. 8, 2025: tested for Maple 2020 `): print(`Version of Feb. 24, 2026`): with(combinat): with(plots): print(): print(`This is Kurchan.txt, A Maple package`): print(`to create and solve Spell Weaving Puzzles of the style designed by Rodolfo Kurchan `): print(` that appear in the New York Times Sunday magazine (starting Nov. 23, 2025).`): print(`It is one of the Maple packages accompanying the paper by Pablo Blanco and Doron Zeilberger`): print(``): print(`Counting (and Randomly Generating) Hamiltonian Cycles in Rectangular Grids`): print(): print(`The most current version is available from:`): print(` http://sites.math.rutgers.edu/~zeilberg/tokhniot/Kurchan.txt .`): print(`Please report all bugs to: DoronZeil at gmail dot com .`): print(): print(`-----------------------------`): print(`For general help, and a list of the MAIN functions,`): print(` type "ezra();". For specific help type "ezra(procedure_name);" `): print(): print(`-----------------------------`): print(`For a list of the supporting procedures type ezra1()`): print(`For specific help type "ezra(procedure_name);" `): print(`For a list of the supporting functions type: ezra1();`): print(): print(`-----------------------------`): print(`-----------------------------`): ezra1:=proc() if args=NULL then print(`The SUPPORTING procedures are: EXPAND,ExpandPuz, Extr1, GG, GtoN, IsBadPuz, IV1, Kur1, MakePuz1, Paths1, Paths1G, PickSE, PlotPuz1, PlotSol1, `): print(` `): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: HP, Kur, MakePuz, MakePuzDB, PlotC, PlotHP, PlotP, PlotPuz, PlotSol `): print(` `): elif nargs=1 and args[1]=EXPAND then print(`EXPAND(WOR,SetA) Given a word WOR and a set of assignments SetA outputs the set of possibilities. Try:`): print(`EXPAND([P,E,P,P,E,R],{[E,{[2,1],[3,3]}],[P,{[2,5],[6,5],[6,6]}], [R,{[4,5]}]});`): elif nargs=1 and args[1]=ExpandPuz then print(`ExpandPuz(PUZ) Given a puzzle of the format [m,n,WORD, SetOfPlacesOfLetters] outputs the set of puzzles`): print(`that Kur1 can handle. Try:`): print(`ExpandPuz([6,6,[P,E,P,P,E,R],{[E,{[2,1],[3,3]}],[P,{[2,5],[6,5],[6,6]}], [R,{[4,5]}]}]);`): elif nargs=1 and args[1]=Extr1 then print(`Extr1(L,S): Given a list L and a set,S, of members of L outputs the sublist of L consisting of S. Try:`): print(`Extr1([1,4,3,5,2,6],{2,4});`): elif nargs=1 and args[1]=GG then print(`GG(m,n): The grid-graph P_m x P_n . Try: `): print(`GG(4,6);`): elif nargs=1 and args[1]=GtoN then print(`GtoN(G): inputs a graph G=[V,E] and outputs [G,TableOfNeigbors]. Try:`): print(`GtoN([{1,2,3},{{1,2},{1,3}}]);`): elif nargs=1 and args[1]=HP then print(`HP(G,a,b): all the Hamiltonian paths from a to b in the graph G. Try:`): print(`HP(GG(5,5),[2,4],[3,3]);`): elif nargs=1 and args[1]=IsBadPuz then print(`IsBadPuz(PUZ): Given a Spell Weaving puzzle PUZ, decides whether there are repeated letters in the word and if there are whether reversing them also gives a solution. Try:`): print(`PUZ:=MakePuz(5,5,[P,E,A,C,E],10): IsBadPuz(PUZ);`): elif nargs=1 and args[1]=IV1 then print(`IV1(a,b,k): The set of all the vectors of length k that start with a and end witb b. Try:`): print(`IV1(2,5,3);`): elif nargs=1 and args[1]=Kur then print(`Kur(PUZ): inputs a puzzle PUZ=[[m,n],W, SetOfLetterPlacements) outputs all solutions.`): print(`For the example in the NYT try:`): print(`Kur([4,4, [P,A,T,H], { [A,{[2,2]}],[T,{[2,4]}],[P,{[3,2]}], [H, {[4,2]}]} ]);`): print(`For the Nov. 23, 2025 puzzle, type:`): print(`Kur([5,5,[S,T,A,R,T],{[S,{[2,4]}],[T,{[3,2],[3,3]}],[A,{[5,2]}],[R,{[2,2]}]}]);`): print(`For the Nov. 30, 2025 puzzle, type:`): print(`Kur([5,5,[P,A,P,E,R],{[P,{[3,3],[4,3]}],[A,{[4,5]}],[E,{[2,4]}],[R,{[5,3]}]}]);`): print(`For the Dec. 7, 2025 puzzle, type:`): print(`Kur([5,5,[G,L,A,S,S],{[G,{[4,2]}],[L,{[3,4]}],[A,{[5,5]}],[S,{[2,3],[5,3]}]}]);`): print(`For the Dec. 14, 2025 puzzle, type:`): print(`Kur([5,5,[P,E,A,C,E],{[P,{[2,4]}],[E,{[4,5],[3,5]}],[A,{[1,2]}],[C,{[4,3]}]}]);`): print(`For the Dec. 21, 2025 Try: `): print(` Kur([6,6,[P,E,P,P,E,R],{[E,{[2,1],[3,3]}],[P,{[2,5],[6,5],[6,6]}] , [R,{[4,5]}] }]);`): print(`For the Dec. 28, 2025 Try: `): print(` Kur([6,6,[T,H,E,A,T,E,R],{[A,{[3,1]}],[H,{[2,2]}], [T,{[4,2],[6,3]}], [R, {[5,3]}], [E,{[3,3],[2,5]}] }]);`): print(`For the Jan. 11, 2026 Try: `): print(` Kur([6,6,[M,E,S,S,A,G,E],{[M,{[6,3]}],[E,{[4,3],[5,3]}], [S,{[2,2],[5,5]}], [A, {[2,4]}], [G,{[1,4]}] }]);`): print(`For the Jan. 18, 2026 Try: `): print(` PUZ:=[6,6,[S,C,I,E,N,C,E],{[S,{[5,5]}],[C,{[1,4],[2,4]}], [I,{[1,1]}], [E, {[2,2],[6,1]}], [N,{[4,3]}] }]; Kur(PUZ);`): print(`For the Jan. 25, 2026 Try: `): print(` PUZ:=[7,7,[E,L,E,P,H,A,N,T],{[E,{[3,6],[7,5]}],[L,{[4,2]}], [P,{[4,7]}], [H, {[2,4]}], [A,{[4,3]}], [N,{[6,2]}], [T,{[6,6]}] }]; Kur(PUZ);`): print(`For the Feb. 1, 2026 Try: `): print(` PUZ:=[7,7,[S,U,N,S,H,I,N,E],{[S,{[6,2],[4,7]}],[U,{[3,6]}], [N,{[3,1],[4,3]}], [H, {[6,3]}], [I,{[5,5]}], [E,{[3,5]}]}]; Kur(PUZ);`): print(`For the Feb. 22, 2026 Try: `): print(`PUZ:=[8,8,[C,O,M,P,L,I,C,A,T,E,D],{[C,{[5,3],[3,6]}],[O,{[3,5]}], [M,{[7,2]}], [P, {[4,7]}], [L,{[7,7]}], [I,{[2,8]}], [A, {[3,2]}], [T,{[4,2]}], [E,{[5,4]}], [D,{[3,4]}] } ]; Kur(PUZ);`): elif nargs=1 and args[1]=Kur1 then print(`Kur1(P): inputs a puzzle P=[[m,n],[ [[a1,b1], Letter_1], ..., [[ak,bk],Letter_k]]]) `): print(`set of Hamiltonain paths in the grid graph [m]x[n] that d pass the points of S in that order`): print(`For the example in the NYT try:`): print(`Kur1([4,4, [ [[3,2],P],[[2,2],A],[[2,4],T],[[4,2],H] ] ]);`): print(`For the Nov. 23, 2025 puzzle, type:`): print(`Kur1([5, 5, [[[2, 4], S], [[3, 2], T], [[5, 2], A], [[2, 2], R], [[3, 3], T]]]);`): print(`For the Nov. 30, 2025 puzzle, type:`): print(`Kur1([5,5,[ [[3,3],P], [[4,5],A], [[4,3],P],[[2,4],E],[[5,3],R] ]]);`): print(`For the Dec. 7, 2025 puzzle, type:`): print(`Kur1([5,5,[ [[4,2],G], [[3,4],L], [[5,5],A],[[2,3],S],[[5,3],S] ]]);`): print(`For the Dec. 14, 2025 puzzle, type:`): print(`Kur1([5,5,[ [[2,4],P], [[4,5],E], [[1,2],A],[[4,3],C],[[3,5],E] ]]);`): elif nargs=1 and args[1]=MakePuz1 then print(`MakePuz1(m,n,W): Given positive integers m and n and a word W makes a random Spell Weaving puzzle with the word A. Try:`): print(`MakePuz1(5,5,[T,R,U,M,P]);`): elif nargs=1 and args[1]=MakePuz then print(`MakePuz(m,n,W,K): Given positive integers m and n and a word W makes a random Spell Weaving puzzle with the word A, by trying K times, using MakePuz1(m,n,W). Returns FAILs it it fails. Try:`): print(`MakePuz(5,5,[T,R,U,M,P],10);`): elif nargs=1 and args[1]=Paths1 then print(`Paths1(G,a,b,k,F): all the paths of length k from a to be in the graph G=[V,E], not using the vertices in F. Try:`): print(`Paths1(GG(3,3),[1,1],[1,2],8,{});`): elif nargs=1 and args[1]=Paths1G then print(`Paths1G(G,a,b,k,F,ST): all the paths of length k from a to b, in the graph G=[V,E], not using the vertices in F. Try:`): print(`Paths1G(GG(3,3),[1,1],[1,2],8,{}, [[1,2],[3,1]]);`): elif nargs=1 and args[1]=MakePuzDB then print(`MakePuzDB(m,n,W,K1,K2): Makes a set of K2 pairs [puzzle, solution] by trying MakePuz(m,n,K1) until you get K2 good pairs. Try:`): print(`MakePuzDB(5,5,[H,A,P,P,Y],20,2);`): elif nargs=1 and args[1]=PickSE then print(`PickSE(m,n,K): picks two vertices (S,E) in GG(m,n) such the set of Hamiltonian paths from S to E is non-empty. It tries K times. If it fails it returns FAIL. Try:`): print(`PickSE(5,5,20);`): elif nargs=1 and args[1]=PlotC then print(`PlotC(a,b,PA): plots the cycle PA `): print(`gu:=HP(GG(4,4),[1,1],[1,2]):PlotC(gu[1]); `): elif nargs=1 and args[1]=PlotHP then print(`PlotHP(a,b,PA): plots the Hamiltonian Path PA in the m by n grid. Try:`): print(`gu:=HP(GG(4,4),[1,1],[1,2]):PlotHP(4,4,gu[1]); `): elif nargs=1 and args[1]=PlotP then print(`PlotP(a,b,PA): plots the Path PA `): print(`gu:=HP(GG(4,4),[1,1],[1,2]):PlotP(gu[1]); `): elif nargs=1 and args[1]=PlotPuz then print(`PlotPuz(PUZ): inputs a puzzle `): print(`Plots it`): print(`For the example puzzle`): print(` PlotPuz([6,6,[T,H,E,A,T,E,R],{[A,{[3,1]}],[H,{[2,2]}], [T,{[4,2],[6,3]}], [R, {[5,3]}], [E,{[3,3],[2,5]}] }]);`): print(`For the Nov. 23, 2025 puzzle, type:`): print(`PUZ:=[5,5,[S,T,A,R,T],{[S,{[2,4]}],[T,{[3,2],[3,3]}],[A,{[5,2]}],[R,{[2,2]}]}]: PlotPuz(PUZ);`): print(`For the Nov. 30, 2025 puzzle, type:`): print(`PUZ:=[5,5,[P,A,P,E,R],{[P,{[3,3],[4,3]}],[A,{[4,5]}],[E,{[2,4]}],[R,{[5,3]}]}]: PlotPuz(PUZ);`): print(`For the Dec. 7, 2025 puzzle, type:`): print(`PUZ:=[5,5,[G,L,A,S,S],{[G,{[4,2]}],[L,{[3,4]}],[A,{[5,5]}],[S,{[2,3],[5,3]}]}]: PlotPuz(PUZ);`): print(`For the Dec. 14, 2025 puzzle, type:`): print(` PUZ:=[5,5,[P,E,A,C,E],{[P,{[2,4]}],[E,{[4,5],[3,5]}],[A,{[1,2]}],[C,{[4,3]}]}]: PlotPuz(PUZ); `): print(`For the Dec. 21, 2025 Try: `): print(` PUZ:=[6,6,[P,E,P,P,E,R],{[E,{[2,1],[3,3]}],[P,{[2,5],[6,5],[6,6]}] , [R,{[4,5]}] }]: PlotPuz(PUZ); `): print(`For the Dec. 28, 2025 Try: `): print(` PUZ:=[6,6,[T,H,E,A,T,E,R],{[A,{[3,1]}],[H,{[2,2]}], [T,{[4,2],[6,3]}], [R, {[5,3]}], [E,{[3,3],[2,5]}] }]: PlotPuz(PUZ); `): print(`For the Feb. 1., 2026 Try: `): print(` PUZ:=[7,7,[S,U,N,S,H,I,N,E],{[S,{[6,2],[4,7]}],[U,{[3,6]}], [N,{[3,1],[4,3]}], [H, {[6,3]}], [I,{[5,5]}], [E,{[3,5]}]}]; PlotPuz(PUZ);`): elif nargs=1 and args[1]=PlotPuz1 then print(`PlotPuz1(P): inputs a puzzle P=[[m,n],[ [[a1,b1], Letter_1], ..., [[ak,bk],Letter_k]]]) `): print(`Plots it`): print(`For the example puzzle`): print(`PlotPuz1([4,4, [ [[3,2],P],[[2,2],A],[[2,4],T],[[4,2],H] ] ]);`): print(`For the Nov. 23, 2025 puzzle, type:`): print(`PlotPuz1([5, 5, [[[2, 4], S], [[3, 2], T], [[5, 2], A], [[2, 2], R], [[3, 3], T]]]);`): print(`For the Nov. 30, 2025 puzzle, type:`): print(`PlotPuz1([5,5,[ [[3,3],P], [[4,5],A], [[4,3],P],[[2,4],E],[[5,3],R] ]]);`): print(`For the Dec. 7, 2025 puzzle, type:`): print(`PlotPuz1([5,5,[ [[4,2],G], [[3,4],L], [[5,5],A],[[2,3],S],[[5,3],S] ]]);`): elif nargs=1 and args[1]=PlotSol then print(`PlotPuz(PUZ,SOL): inputs a puzzle PUZ `): print(`and its solution`): print(`Plots it`): print(`For the example puzzle`): print(`PUZ:=[4,4, [P,A,T,H], { [A,{[2,2]}],[T,{[2,4]}],[P,{[3,2]}], [H, {[4,2]}]} ]: SOL:=Kur(PUZ)[1]: PlotSol(PUZ,SOL);`): print(`For the Nov. 23, 2025 puzzle, type:`): print(`PUZ:=[5,5,[S,T,A,R,T],{[S,{[2,4]}],[T,{[3,2],[3,3]}],[A,{[5,2]}],[R,{[2,2]}]}]: SOL:=Kur(PUZ)[1]: PlotSol(PUZ,SOL);`): print(`For the Nov. 30, 2025 puzzle, type:`): print(`PUZ:=[5,5,[P,A,P,E,R],{[P,{[3,3],[4,3]}],[A,{[4,5]}],[E,{[2,4]}],[R,{[5,3]}]}]: SOL:=Kur(PUZ)[1]: PlotSol(PUZ,SOL);`): print(`For the Dec. 7, 2025 puzzle, type:`): print(`PUZ:=[5,5,[G,L,A,S,S],{[G,{[4,2]}],[L,{[3,4]}],[A,{[5,5]}],[S,{[2,3],[5,3]}]}]: SOL:=Kur(PUZ)[1]: PlotSol(PUZ,SOL);`): print(`For the Dec. 14, 2025 puzzle, type:`): print(` PUZ:=[5,5,[P,E,A,C,E],{[P,{[2,4]}],[E,{[4,5],[3,5]}],[A,{[1,2]}],[C,{[4,3]}]}]: SOL:=Kur(PUZ)[1]: PlotSol(PUZ,SOL);`): print(`For the Dec. 21, 2025 Try: `): print(` PUZ:=[6,6,[P,E,P,P,E,R],{[E,{[2,1],[3,3]}],[P,{[2,5],[6,5],[6,6]}] , [R,{[4,5]}] }]: SOL:=Kur(PUZ)[1]: PlotSol(PUZ,SOL);`): print(`For the Dec. 28, 2025 Try: `): print(` PUZ:=[6,6,[T,H,E,A,T,E,R],{[A,{[3,1]}],[H,{[2,2]}], [T,{[4,2],[6,3]}], [R, {[5,3]}], [E,{[3,3],[2,5]}] }]: SOL:=Kur(PUZ)[1]: PlotSol(PUZ,SOL);`): print(`For the Jan. 11, 2026 Try: `): print(` PUZ:=[6,6,[M,E,S,S,A,G,E],{[M,{[6,3]}],[E,{[4,3],[5,3]}], [S,{[2,2],[5,5]}], [A, {[2,4]}], [G,{[1,4]}] }]:SOL:=Kur(PUZ)[1]: PlotSol(PUZ,SOL);`): print(`For the Jan. 18, 2026 Try: `): print(` PUZ:=[6,6,[S,C,I,E,N,C,E],{[S,{[5,5]}],[C,{[1,4],[2,4]}], [I,{[1,1]}], [E, {[2,2],[6,1]}], [N,{[4,3]}] }]; SOL:=Kur(PUZ)[1]: PlotSol(PUZ,SOL);`): print(`For the Jan. 25, 2026 Try: `): print(` PUZ:=[7,7,[E,L,E,P,H,A,N,T],{[E,{[3,6],[7,5]}],[L,{[4,2]}], [P,{[4,7]}], [H, {[2,4]}], [A,{[4,3]}], [N,{[6,2]}], [T,{[6,6]}] }]; SOL:=Kur(PUZ); PlotSol(PUZ,SOL); `): print(`For the Feb. 1, 2026 Try: `): print(` PUZ:=[7,7,[S,U,N,S,H,I,N,E],{[S,{[6,2],[4,7]}],[U,{[3,6]}], [N,{[3,1],[4,3]}], [H, {[6,3]}], [I,{[5,5]}], [E,{[3,5]}]}]; SOL:=Kur(PUZ): PlotSol(PUZ,SOL);`): elif nargs=1 and args[1]=PlotSol1 then print(`PlotPuz1(P,SOL): inputs a puzzle P=[[m,n],[ [[a1,b1], Letter_1], ..., [[ak,bk],Letter_k]]]) `): print(`and its solution`): print(`Plots it`): print(`For the example puzzle`): print(`PUZ:=[4,4, [ [[3,2],P],[[2,2],A],[[2,4],T],[[4,2],H] ] ]: SOL:=Kur1(PUZ)[1]: PlotSol1(PUZ,SOL); `): print(`For the Nov. 23, 2025 puzzle, type:`): print(`PUZ:=[5, 5, [[[2, 4], S], [[3, 2], T], [[5, 2], A], [[2, 2], R], [[3, 3], T]]]: SOL:=Kur1(PUZ)[1]: PlotSol1(PUZ,SOL); `): print(`For the Nov. 30, 2025 puzzle, type:`): print(`PUZ:=[5,5,[ [[3,3],P], [[4,5],A], [[4,3],P],[[2,4],E],[[5,3],R] ]]: SOL:=Kur1(PUZ)[1]: PlotSol1(PUZ,SOL);`): print(`For the Dec. 7, 2025 puzzle, type:`): print(`PUZ:=[5,5,[ [[4,2],G], [[3,4],L], [[5,5],A],[[2,3],S],[[5,3],S] ]]: SOL:=Kur1(PUZ)[1]: PlotSol1(PUZ,SOL); `): else print(`There is no such thing as`, args): fi: end: with(plots): with(plots): #GG(m,n): The grid-raph of an m by n square in matrix notation. Outputs [V,E]. #Try: #GG(3,4); GG:=proc(m,n) local i,j,V,E: V:={seq(seq([i,j],j=1..n),i=1..m)}: E:={seq(seq({[i,j],[i,j+1]},j=1..n-1),i=1..m),seq(seq({[i,j],[i+1,j]},j=1..n),i=1..m-1)}: [V,E]: end: #GtoN(G): inputs a graph G=[V,E] and outputs [G,TableOfNeigbors]. Try: #GtoN([{1,2,3},{{1,2},{1,3}}]); GtoN:=proc(G) local V,E,T,e,v: option remember: V:=G[1]: E:=G[2]: for v in V do T[v]:={}: od: for e in E do T[e[1]]:=T[e[1]] union {e[2]}: T[e[2]]:=T[e[2]] union {e[1]}: od: [V,op(T)]: end: #Paths1(G,a,b,k,F): all the paths of length k from a to be in the graph G=[V,E], not using the vertices in F. Try: #Paths(GG(3,3),[1,1],[1,2],8,{}); Paths1:=proc(G,a,b,k,F) local V,gu,G1,N,a1,gu1,gu11: option remember: V:=G[1]: G1:=GtoN(G): if not (member(a,V) and member(b,V)) then RETURN(FAIL): fi: if F minus V<>{} then RETURN(FAIL): fi: if k=0 then if a=b and not member(a,F) then RETURN({[a]}): else RETURN({}): fi: fi: gu:={}: N:=G1[2][a] minus F minus {a}: for a1 in N do gu1:=Paths1(G,a1,b,k-1,F union {a}): gu:=gu union {seq([a,op(gu11)],gu11 in gu1)}: od: gu: end: #HP(G,a,b): all the Hamiltonian paths from a to b in the graph G. Try: #HP(GG(5,5),[2,4],[3,3]); HP:=proc(G,a,b) Paths1(G,a,b,nops(G[1])-1,{}); end: #Extr1(L,S): Given a list L and a set,S, of members of L outputs the sublist of L consisting of S. Try: #Extr1([1,4,3,5,2,6],{2,4}); Extr1:=proc(L,S) local L1,i: L1:=[]: for i from 1 to nops(L) do if member(L[i],S) then L1:=[op(L1),L[i]]: fi: od: L1: end: #Kur1Old(m,n,a,b,S): inputs pos. integers m,n, two distinct members of [m]x[n] and a list S of points [m]x[n] with letters, outputs the #set of Hamiltonain paths in the grid graph [m]x[n] that d pass the points of S in that order #For the example in the NYT try: #Kur1Old([4,4,[[[3,2],P],[[2,2],A],[[2,4],T]],[[4,2],H]]]); #For the Nov. 23, 2025 puzzle, type: #Kur1Old([5,5, [[[2,4],S],[[3,2],T]],[[5,2],A]],[[2,2],R],[[3,3],T]]]); #For the Nov. 30, 2025 puzzle, type: #Kur1Old([5,5,[ [[3,3],P], [[4,5],A], [[4,3],P],[[2,4],E],[[5,3],R] ]]); Kur1Old:=proc(P) local m,n,a,b,S,i,gu,mu,mu1: m:=P[1]: n:=P[2]: S:=P[3]: a:=S[1][1]: b:=S[nops(S)][1]: S:=[seq(S[i][1],i=2..nops(S)-1)]: mu:=HP(GG(m,n),a,b): gu:={}: for mu1 in mu do if Extr1(mu1,{op(S),a,b})=[a,op(S),b] then gu:=gu union {mu1}: fi: od: gu: end: #PlotPu1(PUZ): plots the puzzle. Try: #PlotPuz1(a,b,S); Try: #PlotPuz1([5,5,{[[2,4],E],[[3,3],P],[[4,3],P],[[4,5],A],[[5,3],R]}); PlotPuz1:=proc(PUZ) local W,a,b,S,S1,s,T,i,j,C,p: W:=cat(op([seq(PUZ[3][i][2],i=1..nops(P[3]))])): a:=PUZ[2]: b:=PUZ[1]: S:=PUZ[3]: S1:={seq(S[i][1],i=1..nops(S))}: for s in S do T[s[1]]:=s[2]: od: p:=plot([[0,0],[a,0],[a,b],[0,b],[0,0]],thickness=3,axes=none,scaling=constrained): p:=p,textplot([trunc(a/2),b+1/2,W]): for i from 1 to b-1 do p:=p,plot([[0,i],[a,i]]): od: for j from 1 to a-1 do p:=p,plot([[j,0],[j,b]]): od: for i from 1 to b do for j from 1 to a do if member([i,j],S1) then C:=[j-1/2, b-i+1/2]: p:=p,textplot([op(C),T[[i,j]]]): fi: od: od: display(p): end: #PlotSol1(P,SOL): plots the puzzle. Try: #PlotSol1([5,5,{[[2,4],E],[[3,3],P],[[4,3],P],[[4,5],A],[[5,3],R]}); PlotSol1:=proc(P,SOL) local a,b,S,S1,s,T,i,j,C,p,C1,C2,W: a:=P[2]: b:=P[1]: S:=P[3]: S1:={seq(S[i][1],i=1..nops(S))}: for s in S do T[s[1]]:=s[2]: od: p:=plot([[0,0],[a,0],[a,b],[0,b],[0,0]],thickness=3,axes=none,scaling=constrained): W:=cat(op([seq(P[3][i][2],i=1..nops(P[3]))])): p:=p,textplot([trunc(a/2),b+1/2,W]): for i from 1 to b-1 do p:=p,plot([[0,i],[a,i]]): od: for j from 1 to a-1 do p:=p,plot([[j,0],[j,b]]): od: for i from 1 to b do for j from 1 to a do if member([i,j],S1) then C:=[j-1/2+0.1, b-i+1/2+0.1]: p:=p,textplot([op(C),T[[i,j]]]): fi: od: od: for i from 1 to nops(SOL)-1 do C1:=SOL[i]: C2:=SOL[i+1]: C1:=[C1[2]-1/2, b-C1[1]+1/2]: C2:=[C2[2]-1/2, b-C2[1]+1/2]: p:=p,plot([C1,C2],color=blue): od: display(p): end: #IV1(a,b,k): The set of all the vectors of length k that start with a and end with b. Try: #IV1(2,5,3); IV1:=proc(a,b,k) local gu,b1,mu,mu1: if k<2 then RETURN({}): fi: if k=2 then RETURN({[a,b]}): fi: gu:={}: for b1 from a+1 to b-1 do mu:=IV1(a,b1,k-1): gu:=gu union {seq([op(mu1),b],mu1 in mu)}: od: gu: end: #PickSE(m,n,K): picks two vertices (S,E) in GG(m,n) such the set of Hamiltonian paths from S to E is non-empty. It tries K times. If it fails it returns FAIL. Try: #PickSE(5,5,20); PickSE:=proc(m,n,K) local i,G,V,v1,v2: G:=GG(m,n): V:=G[1]: for i from 1 to K do v1:=V[rand(1..nops(V))()]: v2:=V[rand(1..nops(V))()]: if v1<>v2 and HP(G,v1,v2)<>{} then RETURN([v1,v2]): fi: od: FAIL: end: #MakePuz1(m,n,W): Given positive integers m and n and a word W makes a random Spell Weaving puzzle with the word A. Try: #MakePuz1(5,5,[T,R,U,M,P]); MakePuz1:=proc(m,n,W,pt1,pt2) local k, G,i1,gu,PUZ,mu,mu1: k:=nops(W): G:=GG(m,n): gu:=HP(G,pt1,pt2): gu:=gu[rand(1..nops(gu))()]: mu:=IV1(1,nops(gu),k): for mu1 in mu do PUZ:=[m,n, [seq([gu[mu1[i1]],W[i1]],i1=1..nops(mu1))]]: if nops(Kur1(PUZ))=1 and not IsBadPuz(PUZ) then RETURN(PUZ): fi: od: FAIL: end: #MakePuz(m,n,W,K): Given positive integers m and n and a word W makes a random Spell Weaving puzzle with the word A. Trying K times.Try: #MakePuz(5,5,[T,R,U,M,P],10); MakePuz:=proc(m,n,W,K) local ka,i,gu: ka:=PickSE(m,n,2*K): if ka=FAIL then RETURN(FAIL): fi: for i from 1 to K do gu:=MakePuz1(m,n,W,ka[1],ka[2]): if gu<>FAIL then RETURN(gu): fi: od: FAIL: end: #PlotHP(b,a,PA): plots the Hamiltonian Path PA in the m by n grid. Try: #gu:=HP(GG(4,4)):PlotHP(4,4,gu[1]): PlotHP:=proc(b,a,PA) local i,j,C1,C2,p: p:=plot([[0,0],[a,0],[a,b],[0,b],[0,0]],thickness=3,axes=none,scaling=constrained): for i from 1 to b-1 do p:=p,plot([[0,i],[a,i]]): od: for j from 1 to a-1 do p:=p,plot([[j,0],[j,b]]): od: for i from 1 to nops(PA)-1 do C1:=PA[i]: C2:=PA[i+1]: C1:=[C1[2]-1/2, b-C1[1]+1/2]: C2:=[C2[2]-1/2, b-C2[1]+1/2]: p:=p,plot([C1,C2],color=blue): od: display(p): end: #PlotP(PA): plots the Hamiltonian Path PA in the m by n grid. Try: #gu:=HP(GG(4,4)):PlotP(gu[1]): PlotP:=proc(PA) local i,C1,C2,p: C1:=PA[1]: C2:=PA[2]: p:=plot([C1,C2],axes=none,scaling=constrained): for i from 2 to nops(PA)-1 do C1:=PA[i]: C2:=PA[i+1]: p:=p,plot([C1,C2]): od: display(p): end: #PlotC(PA): plots the Hamiltonian cycle PA in the m by n grid. Try: #gu:=HP(GG(4,4),[1,1],[1,2]):PlotC(gu[1]): PlotC:=proc(PA) local i,C1,C2,p: C1:=PA[1]: C2:=PA[2]: p:=plot([C1,C2],axes=none,scaling=constrained): for i from 2 to nops(PA)-1 do C1:=PA[i]: C2:=PA[i+1]: p:=p,plot([C1,C2]): od: p:=p,plot([PA[-1],PA[1]]): display(p): end: #IsBadPuz(PUZ): Given a Spell Weaving puzzle PUZ, decides whether there are repeated letters in the word and if there are whether reversing them also gives a solution. Try: #PUZ:=MakePuz(5,5,W,10): IsBadPuz(PUZ); IsBadPuz:=proc(PUZ) local i,W,PUZ1,j: W:=[seq(PUZ[3][i][2],i=1..nops(PUZ[3]))]: if nops(convert(W,set))=nops(W) then RETURN(false): fi: for i from 1 to nops(W) do for j from i+1 to nops(W) do if W[i]=W[j] then PUZ1:=[PUZ[1],PUZ[2],[op(1..i-1,PUZ[3]),[PUZ[3][j][1],W[j]],op(i+1..j-1,PUZ[3]),[PUZ[3][i][1],W[i]],op(j+1..nops(PUZ[3]),PUZ[3])]]: if Kur1(PUZ1)<>{} then RETURN(true): fi: fi: od: od: false: end: #MakePuzDB(m,n,W,K1,K2): Makes a set of K2 pairs [puzzle, solution] by trying MakePuz(m,n,K1) until you get K2 good pairs. Try: #MakePuzDB(5,5,[H,A,P,P,Y],20,2); MakePuzDB:=proc(m,n,W,K1,K2) local gu,PUZ: gu:={}: while nops(gu)FAIL then gu:=gu union {[PUZ,Kur1(PUZ)[1]]}: fi: od: gu: end: #EXPAND(WOR,SetA) Given a word WOR and a set of assignments SetA outputs the set of possibilities. Try: #EXPAND([P,E,P,P,E,R],{[E,{[2,1],[3,3]}],[P,{[2,5],[6,5],[6,6]}]}],[R,{[4,5]}] }); EXPAND:=proc(WOR,SetA) local OT1,WOR1,SetA1,gu1,gu11,MySet,kv,kv1,S,gu: if WOR=[] then RETURN({[]}): fi: OT1:=WOR[1]: WOR1:=[op(2..nops(WOR),WOR)]: for S in SetA do if S[1]=OT1 then MySet:=S: kv:=S[2]: break: fi: od: gu:={}: for kv1 in kv do SetA1:=(SetA minus {MySet}) union {[OT1,kv minus {kv1}] }: gu1:=EXPAND(WOR1,SetA1): gu:=gu union {seq([[kv1,OT1],op(gu11)],gu11 in gu1)}: od: gu: end: #KurOld([6,6,[P,E,P,P,E,R],{[E,{[2,1],[3,3]}],[P,{[2,5],[6,5],[6,6]}]}]); KurOld:=proc(PUZ) local m,n,gu,gu1: m:=PUZ[1]: n:=PUZ[2]: gu:=EXPAND(PUZ[3],PUZ[4]): gu:={seq([m,n,gu1],gu1 in gu)}: {seq(op(Kur1Old(gu1)),gu1 in gu)}: end: #PlotPuz(PUZ): plots the puzzle. Try: #PlotPuz([6,6,[P,E,P,P,E,R],{[E,{[2,1],[3,3]}],[P,{[2,5],[6,5],[6,6]}]}]); PlotPuz:=proc(PUZ) local WOR,a,b,S,S1,T,i,j,C,p: a:=PUZ[2]: b:=PUZ[1]: WOR:=PUZ[3]: WOR:=cat(op(WOR)): S:=PUZ[4]: S1:={seq(op(S[i][2]),i=1..nops(S))}: for i from 1 to nops(S) do for j in S[i][2] do T[j]:=S[i][1]: od: od: p:=plot([[0,0],[a,0],[a,b],[0,b],[0,0]],thickness=3,axes=none,scaling=constrained): p:=p,textplot([trunc(a/2),b+1/2,WOR]): for i from 1 to b-1 do p:=p,plot([[0,i],[a,i]]): od: for j from 1 to a-1 do p:=p,plot([[j,0],[j,b]]): od: for i from 1 to b do for j from 1 to a do if member([i,j],S1) then C:=[j-1/2, b-i+1/2]: p:=p,textplot([op(C),T[[i,j]]]): fi: od: od: display(p): end: #PlotSol(PUZ,SOL): plots the solution. Try: PlotSol:=proc(PUZ,SOL) local a,b,S,S1,T,i,j,C,p,C1,C2,WOR: a:=PUZ[2]: b:=PUZ[1]: WOR:=cat(op(PUZ[3])): S:=PUZ[4]: S1:={seq(op(S[i][2]),i=1..nops(S))}: for i from 1 to nops(S) do for j in S[i][2] do T[j]:=S[i][1]: od: od: p:=plot([[0,0],[a,0],[a,b],[0,b],[0,0]],thickness=3,axes=none,scaling=constrained): p:=p,textplot([trunc(a/2),b+1/2,WOR]): for i from 1 to b-1 do p:=p,plot([[0,i],[a,i]]): od: for j from 1 to a-1 do p:=p,plot([[j,0],[j,b]]): od: for i from 1 to b do for j from 1 to a do if member([i,j],S1) then C:=[j-1/2, b-i+1/2]: p:=p,textplot([op(C),T[[i,j]]]): fi: od: od: for i from 1 to nops(SOL)-1 do C1:=SOL[i]: C2:=SOL[i+1]: C1:=[C1[2]-1/2, b-C1[1]+1/2]: C2:=[C2[2]-1/2, b-C2[1]+1/2]: p:=p,plot([C1,C2],color=blue): od: display(p): end: #Paths1G(G,a,b,k,F,ST): all the paths of length k from a to b, in the graph G=[V,E], not using the vertices in F. Try: #Paths1G(GG(3,3),[1,1],[1,2],8,{}, [[1,2],[3,1]]); Paths1G:=proc(G,a,b,k,F,ST) local V,gu,G1,N,a1,gu1,gu11: option remember: V:=G[1]: G1:=GtoN(G): if not (member(a,V) and member(b,V)) then RETURN(FAIL): fi: if F minus V<>{} then RETURN(FAIL): fi: if k=0 then if a=b and not member(a,F) and ST=[] then RETURN({[a]}): else RETURN({}): fi: fi: gu:={}: if ST=[] then N:=G1[2][a] minus F minus {a}: else N:=G1[2][a] minus F minus {a} minus convert([op(2..nops(ST),ST)],set): fi: for a1 in N do if ST<>[] and not ST[1]=a1 then gu1:=Paths1G(G,a1,b,k-1,F union {a},ST): gu:=gu union {seq([a,op(gu11)],gu11 in gu1)}: elif ST<>[] and ST[1]=a1 then gu1:=Paths1G(G,a1,b,k-1,F union {a},[op(2..nops(ST),ST)]): else gu1:=Paths1G(G,a1,b,k-1,F union {a},ST): fi: gu:=gu union {seq([a,op(gu11)],gu11 in gu1)}: od: gu: end: #Kur1(m,n,a,b,S): inputs pos. integers m,n, two distinct members of [m]x[n] and a list S of points [m]x[n] with letters, outputs the #set of Hamiltonain paths in the grid graph [m]x[n] that d pass the points of S in that order #For the example in the NYT try: #Kur1([4,4,[[[3,2],P],[[2,2],A],[[2,4],T]],[[4,2],H]]]); #For the Nov. 23, 2025 puzzle, type: #Kur1([5,5, [[[2,4],S],[[3,2],T]],[[5,2],A]],[[2,2],R],[[3,3],T]]]); #For the Nov. 30, 2025 puzzle, type: #Kur1([5,5,[ [[3,3],P], [[4,5],A], [[4,3],P],[[2,4],E],[[5,3],R] ]]); Kur1:=proc(P) local m,n,a,b,S,i: m:=P[1]: n:=P[2]: S:=P[3]: a:=S[1][1]: b:=S[nops(S)][1]: S:=[seq(S[i][1],i=2..nops(S)-1)]: Paths1G(GG(m,n),a,b,m*n-1,{},S): end: #KurOld([6,6,[P,E,P,P,E,R],{[E,{[2,1],[3,3]}],[P,{[2,5],[6,5],[6,6]}]}]); KurOld:=proc(PUZ) local m,n,gu,gu1: m:=PUZ[1]: n:=PUZ[2]: gu:=EXPAND(PUZ[3],PUZ[4]): gu:={seq([m,n,gu1],gu1 in gu)}: {seq(op(Kur1(gu1)),gu1 in gu)}: end: # Written by Pablo Blanco. # Supplementary code for Kurchan.txt. # Version written: Feb. 23, 2025. Kur:=proc(PUZ) local m,n,Ex,w,x,S,path: m:=PUZ[1]: n:=PUZ[2]: Ex:=EXPAND(PUZ[3],PUZ[4]): S:={}: for w in Ex do: S:=S union PrescribedPaths(m,n,[seq(x[1] ,x in w)]): od: S: end: # Input is a vertex v=[x,y] in the grid graph GG(a,b). Return the set of vertices S that are distance k from v. kDistVtcs:=proc(v,a::posint,b::posint,k::nonnegint) local i,j,x,y,bd1,bd2: if nops(v)<>2 then: error "v should be a list of length 2 (a vertex in the grid graph GG(a,b)).": fi: x:=v[1]: y:=v[2]: if x < 1 or y < 1 then: error "coordinates of v should be positive.": fi: if x > a or y > b then: error "coordinate of v should fit within the grid graph of dimensions a,b.": fi: if k + x + y > a+b and x+y-k < 2 then: return({}): fi: # I wanted to do this better, but this is what we have ({seq([x+i,y+k-abs(i)],i=-k..k)} union {seq([x+k-abs(j),y+j],j=-k..k)}) intersect {seq(seq([x+i,y+j], i=1-x..a-x),j=1-y..b-y)}: end: # computes distance between vertices in the grid graph GridDist:=proc(u,v): abs(u[1]-v[1]) + abs(u[2]-v[2]): end: # given vertices u and v, which are distance k in the grid graph (dimensions m,n), output a list of length k-1 # P, where P[i] are the neighbors which are distance i from u. SquareBalls:=proc(m,n,u,v) local k,P,i: k:=GridDist(u,v): P:=[0$k-1]: for i from 1 to k-1 do: P[i]:=kDistVtcs(u,m,n,i): od: P: end: # An object that will generate the "next" path , on k vertices, from vertex v in the (m by n) grid graph # L is a list of prescribed vertices that the path should pass L[1] = v and the target vertex is L[-1]. kGPaths:=proc(m,n,k,L): #description "An object that will generate the next path , of length k, from vertex v in the (m by n) grid graph. Try P:=kGPaths(3,3,[1,1]). Then, try P:-nextpath(), P:-path(), P:-index([1,2]).": # path will output the current path, as a list. # nextpath will consider the nextpath, then output it as a DEQueue. module() local Visited, Path,step,stepCounter,y,v,s,j,prescOrder,Lcop: export index, path, nextpath,pathlen: v:=L[1]: Lcop:=L: Path:=DEQueue([v]): Visited:=table(sparse=-1,[v=0]): path:=()->convert(Path,list): stepCounter:=table(sparse=0,[]): pathlen:=0: # current path length. j:=0: prescOrder:=table(sparse=-1,[]): for s in Lcop do: prescOrder[s]:=j: j++: od: index:=y->Visited[y]: nextpath:=proc() local i,x,u: # consider a new path now if pathlen = k then: x:=Path:-pop_back(): unassign('stepCounter[x]'): unassign('Visited[x]'): pathlen--: fi: # conditions which indicate we can still try to find a next path while pathlen < k and not(Path:-empty()) do: x:=Path:-back(): # the last vertex in the path #print(x): while stepCounter[x]<4 and step(x,stepCounter[x]) = FAIL do: stepCounter[x]++: od: # none of the neighbors for x were available to extend the path. if stepCounter[x]>=4 then: # backtrack by deleting x from the path, since it's no good Path:-pop_back(): unassign('stepCounter[x]'): unassign('Visited[x]'): pathlen--: next: # Maple's "continue" fi: u:=step(x,stepCounter[x]): if u = FAIL then: stepCounter[x]++: next: fi: # otherwise, u=step(x,stepCounter[x]) is a valid vertex to continue the path # add u to the path stepCounter[x]++: # next time we come back to x, don't consider u again Path:-push_back(u): pathlen++: Visited[u]:=Visited[x]+1: od: # we found all paths if Path:-empty() then: return(FAIL): fi: # there is a path we hadn't found yet. return it. return(Path): end: # try to take a step from vertex x to a new, unvisited, vertex. If this fails, output FAIL. Otherwise, output the new vertex. # if i= 0,1,2,3, corresponds to north, east, south, west steps. step:=proc(x,i) local prosp,NOTinBounds,indx,endDist: if i=0 then: prosp:=[x[1],x[2]+1]: elif i=1 then: prosp:=[x[1]+1,x[2]]: elif i=2 then: prosp:=[x[1],x[2]-1]: elif i=3 then: prosp:=[x[1]-1,x[2]]: else: return(FAIL): fi: #print(`prospect:`): #print(prosp): NOTinBounds:= evalb(prosp[1] > m or prosp[1] < 1 or prosp[2] > n or prosp[2] < 1): if Visited[prosp]<>-1 or NOTinBounds then: return(FAIL): fi: # # we can still add this many vertices to the path, if we add vertex prosp # note: if pathlen=k-2, then endDist=0 and prosp should be L[-1] to have a valid path # endDist:=(k-1)-pathlen-1: # this is basically the number of vertices we could still add after adding prosp #if prosp = L[-1] then: print(path(),pathlen): fi: # if GridDist(prosp,Lcop[-1]) > endDist then: # print(path(),prosp,nops(path())+1): # return(FAIL): # fi: # see if the current prospective vertex respects prescribed visitation order # note: the first vertex in the path v, has prescOrder[v]=0. if prescOrder[prosp] <> -1 then: indx:=prescOrder[prosp]+1: # index of prosp in L # if the previous vertex in L was unvisited, then FAIL if Visited[Lcop[indx-1]]=-1 then return(FAIL): fi: fi: return(prosp): end: end: end: # Given a list S of vertices in the m,n grid path, finds all hamiltonian paths that visit those vertices in that order. # Returns the set of all such paths. # Note: S[1] and S[-1] should also be the end points of the path. PrescribedPaths:=proc(m,n,S) local P,Q,currPath: description "Given a list S of vertices in the m,n grid path, finds all hamiltonian paths that visit the vertices of S in that order.\n Returns the set of all such paths. \n Note: S[1] and S[-1] should also be the end points of the path.\n Try: PrescribedPaths(5,5,[[1,1],[5,5]]);\n PrescribedPaths(5,5,[[1,1],[5,5],[3,3]]);": P:=kGPaths(m,n,m*n-1, S): Q:=DEQueue(): currPath:= P:-nextpath(): while currPath <> FAIL do: if P:-index(S[-1]) = n*m-1 then: Q:-push_back(P:-path()): fi: currPath:= P:-nextpath(): od: # while currPath <> FAIL do: # if VerifyPathOrder(P,S) then: # Q:-push_back(P:-path()): # fi: # currPath:= P:-nextpath(): # od: convert(Q,set): end: