###################################################################### ## CircuitBoard.txt Save this file as CircitBoard.txt to use it, # # stay in the # ## same directory, get into Maple (by typing: maple ) # ## and then type: read `CircuitBoard.txt` # ## Then follow the instructions given there # ## # ## Written by Doron Zeilberger, Rutgers University , # ## DoronZeil at gmail dot com # ###################################################################### print(`Written: Nov. 2021: tested for Maple 2020 `): with(combinat): read `CircuitBoardPre.txt`: with(combinat): with(linalg): print(): print(`This is CircuitBoard.txt, A Maple package`): print(`to create and solve Circuit Board puzzles designed by Kousha Nejad `): print(` that appeared in the New York Times magazine during the Fall of 2021.`): print(): print(`The most current version is available from:`): print(` http://sites.math.rutgers.edu/~zeilberg/tokhniot/CircuitBoard.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(`-----------------------------`): print(`For generat help type ezra()`): print(`For specific help type "ezra(procedure_name);" `): print(): print(`-----------------------------`): print(`-----------------------------`): print(`For help that came from SPAN.txt ezraS();`): print(`For specific help type "ezra(procedure_name);" `): print(): print(`-----------------------------`): ezra1:=proc() if args=NULL then print(`The SUPPORTING procedures are`): print(` DrawG, Kids, Kids1, RG, Sq55a, Sq65, Sq66a, Sq66aE, Sq66b, Sq66c, Sq66bE, Sq66c, STd, STfNu, STmtt, STmttF, STnu `): else ezra(args): fi: end: ezraS:=proc() if args=NULL then print(` SPAN.txt: A Maple package automating to generate and count spanning trees with degree restrictions `): print(`The SPANprocedures are`): print(` GG, ST, STf `): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are`): print(` GGsp, MakePuz55a, MakePuz65, MakePuz66a, MakePuz66aE, MakePuz66b, MakePuz66bE, MakePuz66c, MakePuz66cE, MakePuz66d, Nejad66a, Nejad66b, Nejad66c, Nejad66d, Solve55a, Solve65, Solve66a, Solve66b, Solve66c `): elif nargs=1 and args[1]=DrawG then print(`DrawG((m,n,S,E)):Draws the m by n grid with the members of S blackded out and the edges in E added Try`): print(`DrawG(6,6,{[1,6],[6,6]},{{[6,2],[6,3]}})`): elif nargs=1 and args[1]=GG then print(`GG(m,n,S): inputs positive integers m and n a subset S of [1,m]x[1,n] and outputs the graph in our data structure`): print(`in the from [N,E,C] where N is the number of vertices (alias m*n-nops(S)) followed by the set of edges E ( a set of pairs in {1,...,N}, followed by the code C`): print(`where C[n] is the actual grid point. Try:`): print(`GG(6,6,{[6,1],[6,6]});`): elif nargs=1 and args[1]=GGsp then print(`GGsp(m,n,S,F): inputs positive integers m and n a subset S of [1,m]x[1,n], and a set of forbidden degrees F,and outputs `): print(` a list of length 3 consisisting of`): print(`(i) the set of vertices (as grid points [i,j]) using matrix notation [i,j] a subset of [1,m]x[1,n]`): print(`(ii) the set of all edges`): print(`(iii) the set of all spanning trees where the degrees are not allowed to be in F. Try:`): print(`GGsp(5,5,{[1,4],[1,5],[5,5]},{2,4});`): elif nargs=1 and args[1]=Kids then print(`Kids(n,G,T,E,L): given a pos. integer n, a graph G, a partial spanning tree with a set of vertices T and a set of edges E, and a subset of T, the current leaves`): print(`(it is implied by T and E, but it is convenient to have) outputs the set of all "children" such partial trees`): print(`where one of the leaves gets children. Try:`): print(`Kids(4,{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}},{1,2,4},{{1,2},{1,4}},{2,4});`): elif nargs=1 and args[1]=Kids1 then print(`Kids1(n,G,T,E,L,a): given a pos. integer n, a graph G, a partial spanning tree with a set of vertices T and a set of edges E, and a subset of T, the current leaves`): print(`(it is implied by T and E, but it is convenient to have) and a member a of L, outputs the set of all "children" such partial trees`): print(`where a is no longer a leaf but has children. Try:`): print(`Kids1(4,{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}},{1,2,4},{{1,2},{1,4}},{2,4},2);`): elif nargs=1 and args[1]=MakePuz55a then print(`MakePuz55a(): Makes a random Circuit Board puzzle, with a unique solution, on a 5 by 5 board, with cells [4,1], [5,1] and [5,5] removed. It outputs the puzzle and solution. try:`): print(`MakePuz55aa();`): elif nargs=1 and args[1]=MakePuz65 then print(`MakePuz65(): Makes a random Circuit Board puzzle, with a unique solution, on a 6 by 5 board. It outputs the puzzle and solution. try:`): print(`MakePuz65();`): elif nargs=1 and args[1]=MakePuz66a then print(`MakePuz66a(): Makes a random Circuit Board puzzle, with a unique solution, on a 6 by 6 board, with cells [1,6] and [6,6] removed. It outputs the puzzle and solution. try:`): print(`MakePuz66a();`): elif nargs=1 and args[1]=MakePuz66aE then print(`MakePuz66aE(K): Makes a random Circuit Board puzzle, with a unique solution, on a 6 by 6 board, with cells [1,6] and [6,6] removed, with about K edges. It outputs the puzzle and solution. try:`): print(`MakePuz6aE(15);`): elif nargs=1 and args[1]=MakePuz66b then print(`MakePuz66b(): Makes a random Circuit Board puzzle, with a unique solution, on a 6 by 6 board, with cells [1,6] and [2,6] removed. It outputs the puzzle and solution. Try: .`): print(`MakePuz66b();`): elif nargs=1 and args[1]=MakePuz66bE then print(`MakePuz66bE(K): Makes a random Circuit Board puzzle, with a unique solution, on a 6 by 6 board, with cells [1,6] and [2,6] removed, with about K edges. It outputs the puzzle and solution. try:`): print(`MakePuz66bE(15);`): elif nargs=1 and args[1]=MakePuz66c then print(`MakePuz66c(): Makes a random Circuit Board puzzle, with a unique solution, on a 6 by 6 board, with cells [1,1] and [6,5] removed. It outputs the puzzle and solution. try:`): print(`MakePuz66c();`): elif nargs=1 and args[1]=MakePuz66d then print(`MakePuz66d(): Makes a random Circuit Board puzzle, with a unique solution, on a 6 by 6 board, with cells [1,3] and [3,4] removed. It outputs the puzzle and solution. try:`): print(`MakePuz66d();`): elif nargs=1 and args[1]=Nejad66a then print(`Nejad66a(): the pre-computed output of GGsp(6,6,{[1,6],[6,6]},{2,4}); That's what is need to solve the Circuit Board puzzles publisshed in the New York Times magazine. Fall 2021 devised by Koushan Nejad.Try: `): print(`Nejad66a():`): elif nargs=1 and args[1]=Nejad66b then print(`Nejad66b(): the pre-computed output of GGsp(6,6,{[1,6],[2,6]},{2,4}); That's what is need to solve the other kind of Circuit Board puzzles publisshed in the New York Times magazine. Fall 2021 devised by Koushan Nejad.Try: `): print(`Nejad66b():`): elif nargs=1 and args[1]=Nejad66c then print(`Nejad66c(): the pre-computed output of GGsp(6,6,{[1,1],[6,5]},{2,4}); That's what is need to solve the other kind of Circuit Board puzzles publisshed in the New York Times magazine. Fall 2021 devised by Koushan Nejad.Try: `): print(`Nejad66b():`): elif nargs=1 and args[1]=Nejad66d then print(`Nejad66d(): the pre-computed output of GGsp(6,6,{[1,3],[3,4]},{2,4}); That's what is need to solve the other kind of Circuit Board puzzles publisshed in the New York Times magazine. Fall 2021 devised by Koushan Nejad.Try: `): print(`Nejad66d():`): elif nargs=1 and args[1]=RG then print(`RG(n,K): A random graph with n vertices and K edges. Try:`): print(`RG(5,12);`): elif nargs=1 and args[1]=Solve55a then print(`Solve55a(S): inputs a set of edges S, a subset of GG(5,5,{[1,4],[1,5],[5,5]}), and outputs all the spanning trees with vertex-degrees either 1 or 3`): print(`For example for the example problem in the New York Times, type`): print(`Solve55a({{[1,1],[2,1]}, {[1,2],[2,2]}, {[1,4],[1,5]}, {[3,3],[4,3]},{[4,2],[4,3]}, {[5,3],[5,4]}});`): elif nargs=1 and args[1]=Solve65 then print(`Solve65(S): inputs a set of edges S, a subset of GG(6,5,{}), and outputs all the spanning trees with vertex-degrees either 1 or 3`): print(`For example for the example problem in the New York Times, type`): elif nargs=1 and args[1]=Solve66a then print(`Solve66a(S): inputs a set of edges S, a subset of GG(6,6,{[1,6],[6,6]}), and outputs all the spanning trees with vertex-degrees either 1 or 3`): print(`that contains it. To get the New York Times puzzles, Nov. ?, 2021, type:`): print(`Solve66a({{[2,3],[2,4]},{[2,3],[3,3]},{[3,1],[3,2]},{[3,3],[3,4]},{[3,5],[3,6]},{[3,3],[4,3]},{[3,4],[4,4]},{[4,4],[4,5]},{[4,2],[5,2]},{[4,5],[5,5]},{[5,3],[5,4]},{[5,5],[5,6]},{[5,2],[6,2]},{[5,4],[6,4]},{[6,2],[6,3]}});`): print(`To get the New York Times puzzles, Nov. 28, 2021 (read upside-down), type:`): print(`Solve66a({{[1,2],[2,2]},{[2,5],[2,6]},{[2,3],[3,3]},{[3,2],[3,3]},{[3,4],[3,5]},{[3,3],[4,3]},{[4,2],[4,3]},{[4,4],[5,4]},{[4,6],[5,6]},{[5,2],[5,3]},{[5,4],[5,5]},{[5,2],[6,2]},{[5,3],[6,3]},{[5,4],[6,4]}});`): elif nargs=1 and args[1]=Solve66b then print(`Solve66b(S): inputs a set of edges S, a subset of GG(6,6,{[1,6],[2,6]}), and outputs all the spanning trees with vertex-degrees either 1 or 3`): print(`that contains it. To get one of the New York Times puzzles, Nov. ?, 2021, type:`): print(`Solve66b({{[1,3],[1,4]},{[1,4],[1,5]},{[1,1],[2,1]},{[2,2],[2,3]},{[2,2],[3,2]},{[3,4],[3,5]},{[3,3],[4,3]},{[3,4],[4,4]},{[3,5],[4,5]},{[4,2],[5,2]},{[4,3],[5,3]},{[4,5],[5,5]},{[5,5],[6,5]},{[6,1],[6,2]},{[6,4],[6,5]}});`): elif nargs=1 and args[1]=Solve66c then print(`Solve66c(S): inputs a set of edges S, a subset of GG(6,6,{[1,1],[6,5]}), and outputs all the spanning trees with vertex-degrees either 1 or 3`): elif nargs=1 and args[1]=Solve66d then print(`Solve66d(S): inputs a set of edges S, a subset of GG(6,6,{[1,3],[4,3]}), and outputs all the spanning trees with vertex-degrees either 1 or 3`): print(`To solve the New York Times puzzles of Dec.5, 2021, type:`): print(`Solve66d({{[1,4],[2,4]},{[2,4],[2,5]},{[2,1],[3,1]},{[2,6],[3,6]},{[4,2],[4,3]},{[4,3],[4,4]},{[4,4],[4,5]},{[4,2],[5,2]},{[4,6],[5,6]},{[5,3],[6,3]},{[5,6],[6,6]},{[6,3],[6,4]});`): elif nargs=1 and args[1]=Sq55a then print(`Sq55a(P): Given a puzzle P generated by MakePuz55a. finds a subset that still has a unique solution`): elif nargs=1 and args[1]=Sq65 then print(`Sq65(P): Given a puzzle P generated by MakePuz65. finds a subset that still has a unique solution`): elif nargs=1 and args[1]=Sq66a then print(`Sq66a(P): Given a puzzle P generated by MakePuz66a. finds a subset that still has a unique solution`): elif nargs=1 and args[1]=Sq66aE then print(`Sq66aE(P,K): Given a puzzle P generated by MakePuz66a. finds a subset that still has a unique solution, and with at most K edges`): elif nargs=1 and args[1]=Sq66b then print(`Sq66b(P): Given a puzzle P generated by MakePuz66b. finds a subset that still has a unique solution`): elif nargs=1 and args[1]=Sq66c then print(`Sq66c(P): Given a puzzle P generated by MakePuz66c. finds a subset that still has a unique solution`): elif nargs=1 and args[1]=Sq66d then print(`Sq66d(P): Given a puzzle P generated by MakePuz66d. finds a subset that still has a unique solution`): elif nargs=1 and args[1]=Sq66aE then print(`Sq66bE(P,K): Given a puzzle P generated by MakePuz66b. finds a subset that still has a unique solution, and with at most K edges`): elif nargs=1 and args[1]=STmtt then print(`STmtt(n,G): Given a simple graph G on n vertices outputs the set of spanning trees. It uses the Matrix Tree Theorem and computer algebra.`): print(`Try: `): print(`STmtt(5,RG(5,10));`): elif nargs=1 and args[1]=ST then print(`ST(n,G): Given a simple graph G on n vertices outputs the set of spanning trees. It uses dynamical programming.`): print(`Try: `): print(`ST(3,RG(3,3));`): elif nargs=1 and args[1]=STf then print(`STf(n,G,F): Given a simple graph G on n vertices and a set of forbidden degrees, F, outputs the set of spanning trees where no vertex can have a degree in F. It uses dynamical programming.`): print(`Try: `): print(`STf(3,RG(3,3),{2});`): elif nargs=1 and args[1]=STnu then print(`STnu(n,G): Given a simple graph G on n vertices outputs the NUMBER of spanning trees. It uses the Matrix Tree Theorem`): print(`Try: `): print(`STnu(5,RG(5,10));`): elif nargs=1 and args[1]=STd then print(`STd(n,G,d): Given a simple graph G on n vertices and a degree sequence of length n, outputs the set of spanning trees with the degree sequence. Try:`): print(`STd(3,{{1,2},{1,3},{2,3}},[1,1,2]);`): elif nargs=1 and args[1]=STmttF then print(`STmttF(n,G,F): Same as STf(n,G,F) but using the Matrix Tree Theorem and symbolic computations.`): print(` Try`): print(`STmttF(5,RG(5,10),{2});`): elif nargs=1 and args[1]=STfNu then print(`STfNu(n,G,F): Given a simple graph G on n vertices and a set of positive integers F, outputs the NUMBER of spanning trees of G`): print(`where none of the degrees of the vertices belongs to F. Try`): print(`STfNu(5,RG(5,10),{2,4});`): else print(`There is no such thing as`, args): fi: end: #RG(n,K): A random graph with n vertices and K edges RG:=proc(n,K) local i,j: if not (type(n,posint) and type(K,posint) and K<=binomial(n,2)) then print(`bad input`): RETURN(FAIL): fi: randcomb({seq(seq({i,j},j=i+1..n),i=1..n)},K): end: #STmtt(n,G): Given a simple graph G on n vertices outputs the set of spanning trees. It uses the Matrix Tree theorem STmtt:=proc(n,G) local i,j,M,e,lu,a,i1,j1: if not (type(n,integer) and n>0 and type(G,set)) then print(`bad input`): RETURN(FAIL): fi: for i from 1 to n-1 do for j from 1 to n-1 do M[i,j]:=0: od: od: for e in G do M[e[1],e[2]]:=M[e[1],e[2]]-a[e]: M[e[2],e[1]]:=M[e[2],e[1]]-a[e]: M[e[1],e[1]]:= M[e[1],e[1]]+a[e]: M[e[2],e[2]]:= M[e[2],e[2]]+a[e]: od: lu:=expand(det([seq([seq(M[i,j],j=1..n-1)],i=1..n-1)])): if lu=0 then RETURN({}): fi: if type(lu,`+`) then {seq({seq(op(1,op(i1,op(j1,lu))),i1=1..nops(op(1,lu)))},j1=1..nops(lu))}: elif type(lu,`*`) then {{seq(op(1,op(i1,lu)),i1=1..nops(lu))}}: else FAIL: fi: end: #STd(n,G,d): Given a simple graph G on n vertices and a degree sequence of length n, outputs the set of spanning trees with the degree sequence. Try: #STd(3,{{1,2},{1,3},{2,3}},[1,1,2]); STd:=proc(n,G,d) local i,j,M,e,lu,a,x,i1,j1: if not (type(n,integer) and n>0 and type(G,set) and nops(d)=n) and convert(d,`+`)=2*(n-1) then print(`bad input`): RETURN(FAIL): fi: for i from 1 to n-1 do for j from 1 to n-1 do M[i,j]:=0: od: od: for e in G do M[e[1],e[2]]:=M[e[1],e[2]]-a[e]*x[e[1]]*x[e[2]]: M[e[2],e[1]]:=M[e[2],e[1]]-a[e]*x[e[1]]*x[e[2]]: M[e[1],e[1]]:= M[e[1],e[1]]+a[e]*x[e[1]]*x[e[2]]: M[e[2],e[2]]:= M[e[2],e[2]]+a[e]*x[e[1]]*x[e[2]]: od: lu:=expand(det([seq([seq(M[i,j],j=1..n-1)],i=1..n-1)])): for i from 1 to n do lu:=coeff(lu,x[i],d[i]): od: if lu=0 then RETURN({}): fi: if type(lu,`+`) then {seq({seq(op(1,op(i1,op(j1,lu))),i1=1..nops(op(1,lu)))},j1=1..nops(lu))}: elif type(lu,`*`) then {{seq(op(1,op(i1,lu)),i1=1..nops(lu))}}: else FAIL: fi: end: #STmttF(n,G,F): Given a simple graph G on n vertices and a set of positive integers F, outputs all the spanning trees of G #where none of the degrees of the vertices belongs to F. Try #SFmttF(5,RG(5,10),{2,4}); STmttF:=proc(n,G,F) local i,j,M,e,lu,a,x,f,i1,j1: if not (type(n,integer) and n>0 and type(G,set) and type(F,set) and (F={} or {seq(type(f,posint),f in F)}={true})) then print(`bad input`): RETURN(FAIL): fi: for i from 1 to n-1 do for j from 1 to n-1 do M[i,j]:=0: od: od: for e in G do M[e[1],e[2]]:=M[e[1],e[2]]-a[e]*x[e[1]]*x[e[2]]: M[e[2],e[1]]:=M[e[2],e[1]]-a[e]*x[e[1]]*x[e[2]]: M[e[1],e[1]]:= M[e[1],e[1]]+a[e]*x[e[1]]*x[e[2]]: M[e[2],e[2]]:= M[e[2],e[2]]+a[e]*x[e[1]]*x[e[2]]: od: lu:=expand(det([seq([seq(M[i,j],j=1..n-1)],i=1..n-1)])): for i from 1 to n do for f in F do lu:=expand(lu-coeff(lu,x[i],f)*x[i]^f): od: od: lu:=subs({seq(x[i]=1,i=1..n)},lu): if lu=0 then RETURN({}): fi: if type(lu,`+`) then {seq({seq(op(1,op(i1,op(j1,lu))),i1=1..nops(op(1,lu)))},j1=1..nops(lu))}: elif type(lu,`*`) then {{seq(op(1,op(i1,lu)),i1=1..nops(lu))}}: else FAIL: fi: end: #GG(m,n,S): inputs positive integers m and n a subset S of [1,m]x[1,n] and outputs the graph in our data structure #in the from [N,E,C] where N is the number of vertices (alias m*n-nops(F)) followed by the set of edges E ( a set of pairs in {1,...,N}, followed by the code C #where C[n] is the actual grid point. Try: #GG(6,6,{[6,1],[6,6]}); GG:=proc(m,n,S) local V,E,i,j,v,Nei,nei: V:={seq(seq([i,j],j=1..n),i=1..m)} minus S: E:={}: for v in V do Nei:={v+[1,0],v-[1,0],v+[0,1],v-[0,1]} intersect V: E:=E union {seq({v,nei},nei in Nei)}: od: V,E: V:=convert(V,list): E:=subs({seq(V[i]=i,i=1..nops(V))},E): [nops(V),E,V]: end: #STfNu(n,G,F): Given a simple graph G on n vertices and a set of positive integers F, outputs the NUMBER of spanning trees of G #where none of the degrees of the vertices belongs to F. Try #SFfNu(5,RG(5,10),{2,4}); STfNu:=proc(n,G,F) local i,j,M,e,lu,x,f: if not (type(n,integer) and n>0 and type(G,set) and type(F,set) and (F={} or {seq(type(f,posint),f in F)}={true})) then print(`bad input`): RETURN(FAIL): fi: for i from 1 to n-1 do for j from 1 to n-1 do M[i,j]:=0: od: od: for e in G do M[e[1],e[2]]:=M[e[1],e[2]]-x[e[1]]*x[e[2]]: M[e[2],e[1]]:=M[e[2],e[1]]-x[e[1]]*x[e[2]]: M[e[1],e[1]]:= M[e[1],e[1]]+x[e[1]]*x[e[2]]: M[e[2],e[2]]:= M[e[2],e[2]]+x[e[1]]*x[e[2]]: od: lu:=expand(det([seq([seq(M[i,j],j=1..n-1)],i=1..n-1)])): for i from 1 to n do for f in F do lu:=expand(lu-coeff(lu,x[i],f)*x[i]^f): od: od: subs({seq(x[i]=1,i=1..n)},lu): end: #STnu(n,G): Given a simple graph G on n vertices. Finds the number of spanning trees #STnu(5,RG(5,10),{2,4}); #STnu(34,GG(6,6,{[6,1],[6,6]})[2]): STnu:=proc(n,G) local i,j,M,e: if not (type(n,integer) and n>0 and type(G,set)) then print(`bad input`): RETURN(FAIL): fi: for i from 1 to n-1 do for j from 1 to n-1 do M[i,j]:=0: od: od: for e in G do M[e[1],e[2]]:=M[e[1],e[2]]-1: M[e[2],e[1]]:=M[e[2],e[1]]-1: M[e[1],e[1]]:= M[e[1],e[1]]+1: M[e[2],e[2]]:= M[e[2],e[2]]+1: od: det([seq([seq(M[i,j],j=1..n-1)],i=1..n-1)]); end: #Kids1(n,G,T,E,L,a): given a pos. integer n, a graph G, a partial spanning tree with a set of vertices T and a set of edges E, and a subset of T, the current leaves #(it is implied by T and E, but it is convenient to have) and a member a of L, outputs the set of all "children" such partial trees #where a is no longer a leaf but has children. Try: #Kids1(4,{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}},{1,2,4},{{1,2},{1,4}},{2,4},2); Kids1:=proc(n,G,T,E,L,a) local AvN,v,s,gu,T1,E1,L1,i: if not member(a,L) then RETURN(FAIL): fi: AvN:={}: for v in {seq(i,i=1..n)} minus T do if member({a,v}, G minus E) then AvN:=AvN union {v}: fi: od: if AvN={} then RETURN({}): fi: AvN:=powerset(AvN) minus {{}}: gu:={}: for s in AvN do T1:=T union s: E1:=E union {seq({a,v}, v in s)}: L1:=(L minus {a}) union s: gu:=gu union {[n,G,T1,E1,L1]}: od: gu: end: #Kids(n,G,T,E,L): given a pos. integer n, a graph G, a partial spanning tree with a set of vertices T and a set of edges E, and a subset of T, the current leaves #(it is implied by T and E, but it is convenient to have) outputs the set of all "children" such partial trees #where one of the leaves gets children. Try: #Kids(4,{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}},{1,2,4},{{1,2},{1,4}},{2,4}); Kids:=proc(n,G,T,E,L) local a: {seq(op(Kids1(n,G,T,E,L,a)), a in L)}: end: #ST(n,G): Given a simple graph G on n vertices outputs the set of spanning trees, the fast way ST:=proc(n,G) local gu,cu,cuNew,cu1: cu:={[n,G,{1},{},{1}]}: gu:={}: cu:=Kids(op(cu[1])): for cu1 in cu do if nops(cu1[4])=n-1 then gu:=gu union {cu1[4]}: fi: od: while cu<>{} do cuNew:={}: for cu1 in cu do cuNew:=cuNew union Kids(op(cu1)): od: cu:=cuNew: for cu1 in cu do if nops(cu1[4])=n-1 then gu:=gu union {cu1[4]}: fi: od: od: gu: end: ###start with forbidden degrees #Kids1F(n,G,T,E,L,a,F): given a pos. integer n, a graph G, a partial spanning tree with a set of vertices T and a set of edges E, and a subset of T, the current leaves #(it is implied by T and E, but it is convenient to have) and a member a of L, and a set of forbidden number of children, outputs the set of all "children" such partial trees #where a is no longer a leaf but has children. Try: #Kids1F(4,{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}},{1,2,4},{{1,2},{1,4}},{2,4},2,{1,3}); Kids1F:=proc(n,G,T,E,L,a,F) local AvN,v,s,gu,T1,E1,L1,i: if not member(a,L) then RETURN(FAIL): fi: AvN:={}: for v in {seq(i,i=1..n)} minus T do if member({a,v}, G minus E) then AvN:=AvN union {v}: fi: od: if AvN={} then RETURN({}): fi: AvN:=powerset(AvN) minus {{}}: gu:={}: for s in AvN do if not member(nops(s),F) then T1:=T union s: E1:=E union {seq({a,v}, v in s)}: L1:=(L minus {a}) union s: gu:=gu union {[n,G,T1,E1,L1]}: fi: od: gu: end: #KidsF(n,G,T,E,L,F): given a pos. integer n, a graph G, a partial spanning tree with a set of vertices T and a set of edges E, and a subset of T, the current leaves #(it is implied by T and E, but it is convenient to have) and a forbidden number of children, outputs the set of all "children" such partial trees #where one of the leaves gets children. Try: #KidsF(4,{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}},{1,2,4},{{1,2},{1,4}},{2,4},{2,4}); KidsF:=proc(n,G,T,E,L,F) local a: {seq(op(Kids1F(n,G,T,E,L,a,F)), a in L)}: end: #STf(n,G,F): Given a simple graph G on n vertices, and a set of forbidden degrees, outputs the set of spanning trees, the fast way STf:=proc(n,G,F) local gu,cu,cuNew,cu1,F1,i1: if member(1,F) then RETURN({}): fi: cu:={[n,G,{1},{},{1}]}: gu:={}: cu:=KidsF(op(cu[1]),F): F1:={seq(i1-1,i1 in F)}: for cu1 in cu do if nops(cu1[4])=n-1 then gu:=gu union {cu1[4]}: fi: od: while cu<>{} do cuNew:={}: for cu1 in cu do cuNew:=cuNew union KidsF(op(cu1),F1): od: cu:=cuNew: for cu1 in cu do if nops(cu1[4])=n-1 then gu:=gu union {cu1[4]}: fi: od: od: gu: end: #GGsp(m,n,S,F): inputs positive integers m and n a subset S of [1,m]x[1,n], and a set of forbidden degrees F,and outputs # a list of length 3 consisisting of #(i) the set of vertices (as grid points [i,j]) using matrix notation [i,j] a subset of [1,m]x[1,n] #(ii) the set of all edges #(iii) the set of all spanning trees where the degrees are not allowed to be in F. Try: #GGsp(5,5,{[1,4],[1,5],[5,5]},{2,4}); GGsp:=proc(m,n,S,F) local gu,V,G,i,lu: gu:=GG(m,n,S): V:=gu[3]: G:=gu[2]: lu:=STf(gu[1],G,F): G:=subs({seq(i=V[i],i=1..nops(V))},G): lu:=subs({seq(i=V[i],i=1..nops(V))},lu): [{op(V)},G,lu]: end: #Solve66a(S): inputs a set of edges S, a subset of GG(6,6,{[1,6],[6,6]}), and outputs all the spanning trees with vertex-degrees either 1 or 3 #that contains it. To get one of the New York Times puzzles, Nov. ?, 2021, type: #Solve66a({{[2,3],[2,4]},{[2,3],[3,3]},{[3,1],[3,2]},{[3,3],[3,4]},{[3,5],[3,6]},{[3,3],[4,3]},{[3,4],[4,4]},{[4,4],[4,5]},{[4,2],[5,2]},{[4,5],[5,5]},{[5,3],[5,4]},{[5,5],[5,6]},{[5,2],[6,2]},{[5,4],[6,4]},{[6,2],[6,3]}}); Solve66a:=proc(S) local mu,gu,mu1: mu:=Nejad66a(): if S minus mu[2]<>{} then RETURN(FAIL): fi: gu:={}: for mu1 in mu[3] do if S minus mu1={} then gu:=gu union {mu1}: fi: od: gu: end: #Sq66a1(P): Given a puzzle P, finds one that still has a unique solution with one less edge less Sq66a1:=proc(P) local P1,i: for i from 1 to nops(P) do P1:=P minus {P[i]}: if nops(Solve66a(P1))=1 then RETURN(P1): fi: od: FAIL: end: #Sq66a(P): Given a puzzle P, finds a subset that still has a unique solution Sq66a:=proc(P) local P1,P2: P1:=P: P2:=Sq66a1(P1): while P2<>FAIL do P1:=P2: P2:=Sq66a1(P1): od: P1: end: #Sq66aE(P,K): Given a puzzle P, finds a subset with at most K edeges that still has a unique solution Sq66aE:=proc(P,K) local P1,P2: P1:=P: P2:=Sq66a1(P1): while P2<>FAIL and nops(P2)>=K do P1:=P2: P2:=Sq66a1(P1): od: P1: end: #MakePuz66a(): Makes a random Circuit Board puzzle, with a unique solution, on a 6 by 6 board, with cells [1,6] and [6,6] removed. It outputs the puzzle and solutionTry. #MakePuz6a(): MakePuz66a:=proc() local mu,sol,puz,puz1: mu:=Nejad66a()[3]: sol:=mu[rand(1..nops(mu))()]: puz:=sol: while nops(Solve66a(puz))=1 do puz1:=puz minus {puz[rand(1..nops(puz))()]}: if nops(Solve66a(puz1))>1 then RETURN([Sq66a(puz),sol]): else puz:=puz1: fi: od: FAIL: end: #MakePuz66aE(K): Makes an easy random Circuit Board puzzle, with a unique solution, on a 6 by 6 board, with cells [1,6] and [6,6] removed. It outputs the puzzle and solutionTry. #MakePuz66aE(K): MakePuz66aE:=proc(K) local mu,sol,puz,puz1: mu:=Nejad66a()[3]: sol:=mu[rand(1..nops(mu))()]: puz:=sol: while nops(Solve66a(puz))=1 do puz1:=puz minus {puz[rand(1..nops(puz))()]}: if nops(Solve66a(puz1))>1 then RETURN([Sq66aE(puz,K),sol]): else puz:=puz1: fi: od: FAIL: end: #MakePuz66b(): Makes a random Circuit Board puzzle, with a unique solution, on a 6 by 6 board, with cells [1,6] and [6,6] removed. It outputs the puzzle and solutionTry. #MakePuz6b(): MakePuz66b:=proc() local mu,sol,puz,puz1: mu:=Nejad66b()[3]: sol:=mu[rand(1..nops(mu))()]: puz:=sol: while nops(Solve66b(puz))=1 do puz1:=puz minus {puz[rand(1..nops(puz))()]}: if nops(Solve66b(puz1))>1 then RETURN([Sq66b(puz),sol]): else puz:=puz1: fi: od: FAIL: end: #MakePuz66bE(K): Makes an easy random Circuit Board puzzle, with a unique solution, on a 6 by 6 board, with cells [1,6] and [6,6] removed. It outputs the puzzle and solutionTry. #MakePuz66bE(K): MakePuz66bE:=proc(K) local mu,sol,puz,puz1: mu:=Nejad66b()[3]: sol:=mu[rand(1..nops(mu))()]: puz:=sol: while nops(Solve66b(puz))=1 do puz1:=puz minus {puz[rand(1..nops(puz))()]}: if nops(Solve66b(puz1))>1 then RETURN([Sq66bE(puz,K),sol]): else puz:=puz1: fi: od: FAIL: end: with(plots): #DrawG((m,n,S,E)):Draws the m by n grid with the members of S blackded out and the edges in E added Try #DrawG(6,6,{[1,6],[6,6]},{{[6,2],[6,3]}}) DrawG:=proc(m,n,S,E) local d,i,j,e,s: d:=plot([[0,0],[n,0]],axes=none,color=black,thickness=3, scaling=constrained): for i from 1 to m do d:=d,plot([[0,-i],[n,-i]],color=black, axes=none): od: for j from 0 to n do d:=d,plot([[j,0],[j,-m]],color=black, axes=none): od: for i from 1 to m do for j from 1 to n do if not member([i,j],S) then d:=d,plot({[j-0.5,-i+0.5]},style=point,symbol=circle,color=red): fi: od: od: for e in E do d:=d,plot([[e[1][2]-0.5,-e[1][1]+0.5], [e[2][2]-0.5,-e[2][1]+0.5]]): od: for s in S do d:=d,polygonplot([[s[2]-1,-s[1]],[s[2],-s[1]],[s[2],-s[1]+1],[s[2]-1,-s[1]+1],[s[2]-1,-s[1]]]): od: display(d); end: #Solve66b(S): inputs a set of edges S, a subset of GG(6,6,{[1,6],[2,6]}), and outputs all the spanning trees with vertex-degrees either 1 or 3 #that contains it. To get one of the New York Times puzzles, Nov. ?, 2021, type: Solve66b:=proc(S) local mu,gu,mu1: mu:=Nejad66b(): if S minus mu[2]<>{} then RETURN(FAIL): fi: gu:={}: for mu1 in mu[3] do if S minus mu1={} then gu:=gu union {mu1}: fi: od: gu: end: #Sq66b1(P): Given a puzzle P, finds one that still has a unique solution with one less edge less Sq66b1:=proc(P) local P1,i: for i from 1 to nops(P) do P1:=P minus {P[i]}: if nops(Solve66b(P1))=1 then RETURN(P1): fi: od: FAIL: end: #Sq66b(P): Given a puzzle P, finds a subset that still has a unique solution Sq66b:=proc(P) local P1,P2: P1:=P: P2:=Sq66b1(P1): while P2<>FAIL do P1:=P2: P2:=Sq66b1(P1): od: P1: end: #Sq66bE(P,K): Given a puzzle P, finds a subset with at most K edeges that still has a unique solution Sq66bE:=proc(P,K) local P1,P2: P1:=P: P2:=Sq66b1(P1): while P2<>FAIL and nops(P2)>=K do P1:=P2: P2:=Sq66b1(P1): od: P1: end: #Solve55a(S): inputs a set of edges S, a subset of GG(5,5,{[1,4],[1,5],[5,5]}), and outputs all the spanning trees with vertex-degrees either 1 or 3 #that contains it. To get one of the New York Times puzzles, Nov. ?, 2021, type: Solve55a:=proc(S) local mu,gu,mu1: mu:=Nejad55a(): if S minus mu[2]<>{} then RETURN(FAIL): fi: gu:={}: for mu1 in mu[3] do if S minus mu1={} then gu:=gu union {mu1}: fi: od: gu: end: #Sq55a1(P): Given a puzzle P, finds one that still has a unique solution with one less edge less Sq55a1:=proc(P) local P1,i: for i from 1 to nops(P) do P1:=P minus {P[i]}: if nops(Solve55a(P1))=1 then RETURN(P1): fi: od: FAIL: end: #Sq55a(P): Given a puzzle P, finds a subset that still has a unique solution Sq55a:=proc(P) local P1,P2: P1:=P: P2:=Sq55a1(P1): while P2<>FAIL do P1:=P2: P2:=Sq55a1(P1): od: P1: end: #MakePuz55a(): Makes a random Circuit Board puzzle, with a unique solution, on a 5 by 5 board, with cells [4,1] and [5,1] and [5,5] removed. It outputs the puzzle and solutionTry. #MakePuz55ab(): MakePuz55a:=proc() local mu,sol,puz,puz1: mu:=Nejad55a()[3]: sol:=mu[rand(1..nops(mu))()]: puz:=sol: while nops(Solve55a(puz))=1 do puz1:=puz minus {puz[rand(1..nops(puz))()]}: if nops(Solve55a(puz1))>1 then RETURN([Sq55a(puz),sol]): else puz:=puz1: fi: od: FAIL: end: #Solve65(S): inputs a set of edges S, a subset of GG(6,5,{}), and outputs all the spanning trees with vertex-degrees either 1 or 3 Solve65:=proc(S) local mu,gu,mu1: mu:=Nejad65(): if S minus mu[2]<>{} then RETURN(FAIL): fi: gu:={}: for mu1 in mu[3] do if S minus mu1={} then gu:=gu union {mu1}: fi: od: gu: end: #Sq651(P): Given a puzzle P, finds one that still has a unique solution with one less edge less Sq651:=proc(P) local P1,i: for i from 1 to nops(P) do P1:=P minus {P[i]}: if nops(Solve65(P1))=1 then RETURN(P1): fi: od: FAIL: end: #Sq65(P): Given a puzzle P, finds a subset that still has a unique solution Sq65:=proc(P) local P1,P2: P1:=P: P2:=Sq651(P1): while P2<>FAIL do P1:=P2: P2:=Sq651(P1): od: P1: end: #MakePuz65(): Makes a random Circuit Board puzzle, with a unique solution, on a 6 by 5 board, makes a puzzle #MakePuz65(): MakePuz65:=proc() local mu,sol,puz,puz1: mu:=Nejad65()[3]: sol:=mu[rand(1..nops(mu))()]: puz:=sol: while nops(Solve65(puz))=1 do puz1:=puz minus {puz[rand(1..nops(puz))()]}: if nops(Solve65(puz1))>1 then RETURN([Sq65(puz),sol]): else puz:=puz1: fi: od: FAIL: end: #Solve66c(S): inputs a set of edges S, a subset of GG(6,6,{[1,1],[6,5]}), and outputs all the spanning trees with vertex-degrees either 1 or 3 #that contains it. Solve66c:=proc(S) local mu,gu,mu1: mu:=Nejad66c(): if S minus mu[2]<>{} then RETURN(FAIL): fi: gu:={}: for mu1 in mu[3] do if S minus mu1={} then gu:=gu union {mu1}: fi: od: gu: end: #Sq66c1(P): Given a puzzle P, finds one that still has a unique solution with one less edge less Sq66c1:=proc(P) local P1,i: for i from 1 to nops(P) do P1:=P minus {P[i]}: if nops(Solve66c(P1))=1 then RETURN(P1): fi: od: FAIL: end: #Sq66c(P): Given a puzzle P, finds a subset that still has a unique solution Sq66c:=proc(P) local P1,P2: P1:=P: P2:=Sq66c1(P1): while P2<>FAIL do P1:=P2: P2:=Sq66c1(P1): od: P1: end: #MakePuz66c(): Makes a random Circuit Board puzzle, with a unique solution, on a 6 by 6 board, with cells [1,1] and [6,5] removed. It outputs the puzzle and solutionTry. #MakePuz66c(): MakePuz66c:=proc() local mu,sol,puz,puz1: mu:=Nejad66c()[3]: sol:=mu[rand(1..nops(mu))()]: puz:=sol: while nops(Solve66c(puz))=1 do puz1:=puz minus {puz[rand(1..nops(puz))()]}: if nops(Solve66c(puz1))>1 then RETURN([Sq66c(puz),sol]): else puz:=puz1: fi: od: FAIL: end: #MakePuz66cE(K): Makes an easy random Circuit Board puzzle, with a unique solution, on a 6 by 6 board, with cells [1,6] and [6,6] removed. It outputs the puzzle and solutionTry. #MakePuz66cE(K): MakePuz66ac:=proc(K) local mu,sol,puz,puz1: mu:=Nejad66c()[3]: sol:=mu[rand(1..nops(mu))()]: puz:=sol: while nops(Solve66c(puz))=1 do puz1:=puz minus {puz[rand(1..nops(puz))()]}: if nops(Solve66a(puz1))>1 then RETURN([Sq66cE(puz,K),sol]): else puz:=puz1: fi: od: FAIL: end: #Solve66d(S): inputs a set of edges S, a subset of GG(6,6,{[1,3],[3,4]}), and outputs all the spanning trees with vertex-degrees either 1 or 3 #that contains it. Solve66d:=proc(S) local mu,gu,mu1: mu:=Nejad66d(): if S minus mu[2]<>{} then RETURN(FAIL): fi: gu:={}: for mu1 in mu[3] do if S minus mu1={} then gu:=gu union {mu1}: fi: od: gu: end: #Sq66d1(P): Given a puzzle P, finds one that still has a unique solution with one less edge less Sq66d1:=proc(P) local P1,i: for i from 1 to nops(P) do P1:=P minus {P[i]}: if nops(Solve66d(P1))=1 then RETURN(P1): fi: od: FAIL: end: #Sq66d(P): Given a puzzle P, finds a subset that still has a unique solution Sq66d:=proc(P) local P1,P2: P1:=P: P2:=Sq66d1(P1): while P2<>FAIL do P1:=P2: P2:=Sq66d1(P1): od: P1: end: #MakePuz66d(): Makes a random Circuit Board puzzle, with a unique solution, on a 6 by 6 board, with cells [1,3] and [3,4] removed. It outputs the puzzle and solutionTry. #MakePuz66d(): MakePuz66d:=proc() local mu,sol,puz,puz1: mu:=Nejad66d()[3]: sol:=mu[rand(1..nops(mu))()]: puz:=sol: while nops(Solve66d(puz))=1 do puz1:=puz minus {puz[rand(1..nops(puz))()]}: if nops(Solve66d(puz1))>1 then RETURN([Sq66d(puz),sol]): else puz:=puz1: fi: od: FAIL: end: