###################################################################### ##PICAPIX: Save this file as PICAPIX # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read PICAPIX # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg at math dot rutgers dot edu # ###################################################################### #Created: Jan. 11, 2009 print(`Created: Jan. 11, 2009`): print(` This is PICAPIX `): print(`To solve picapix puzzles`): print(`and also available from Zeilberger's website`): print(``): print(`Please report bugs to zeilberg at math dot rutgers dot edu`): print(``): print(`The most current version of this package and paper`): print(` are available from`): print(`http://www.math.rutgers.edu/~zeilberg/ .`): print(`For a list of the procedures type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): with(combinat): #Yedioth Jan. 9, 2009 R1s:=[[12],[1,1,4,2,1]$3,[1,10,1],[1,1],[1,11,1],[1,2,2,1,1], [1,8,1,1],[1,2,2,1,1],[1,8,1,1],[1,2,2,1,1],[1,11,1],[1,1],[13]]: C1s:=[[13],[1,1],[5,7,1],[1,1,7,1],[1$7],[5,1$5]$3,[5,7,1],[1,1,7,1], [5,1,1,1]$2,[1,7,1],[1,1],[12]]: P1:=[R1s,C1s]: ka:=Tirgum(R1s,C1s): R1st:=ka[1]: C1st:=ka[2]: #sample R2s:=[[2],[3,1],[4],[4],[1,1]]: C2s:=[[1],[5],[4],[2],[4]]: ka:=Tirgum(R2s,C2s): R2st:=ka[1]: C2st:=ka[2]: P2:=[R2s,C2s]: #Yedioth Jan. 23, 2009 R3s:=[[7],[11],[1,1],[1,1],[1,1,1],[1,5,1,3],[7,1,1],[1,1,1,1],[12,1], [1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,2],[1,1,1,1],[9]]: C3s:=[ [2,6], [1,3,2,1], [2,1,1,1,1], [2,2,1,1,1,1],[2,2,1,1,1], [2,3,2,1],[2,2,1,1,2],[2,2,2,1,1],[2,1,1,2],[1,3,2,1],[2,6], [3,1],[1,1],[1,4],[2]]: P3:=[R3s,C3s]: ezra1:=proc() if args=NULL then print(` The supporting procedures are: Compo, HaBa, IsColCompatible, LC `): print(` Optiot, PartiallyFill, Prof, Ptor1, Purge, Sader, Targem, Tirgum `): print(` UnTargem, VecToFreq `): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: DrawPuzzle, DrawSolution,`): print(` MakeBook, MakePuzzle, Ptor, PtorY, PtorK `): print(` `): elif nops([args])=1 and op(1,[args])=Compo then print(`Compo(N,r): all vectors of non-negative integers of length r`): print(`that add-up to N. For example, try: Comp(5,2);`): elif nops([args])=1 and op(1,[args])=DrawPuzzle then print(`DrawPuzzle(P): draws the puzzle P.`): print(`For example, try:`): print(`DrawPuzzle(P2);`): elif nops([args])=1 and op(1,[args])=DrawSolution then print(`DrawSolution(S): draws the solution S`): print(`For example, try:`): print(`DrawSolution(Ptorf(P2),.1);`): elif nops([args])=1 and op(1,[args])=HaBa then print(`HaBa(R,C,u): The next-in-line to try, for example, try:`): print(`HaBa(R1st,C1st,[1$15]);`): elif nops([args])=1 and op(1,[args])=IsColCompatible then print(`IsColCompatible(M,v,j,B): Is placing v at the j-th column`): print(`compatible with the partially-filled matrix M`): print(`(where blanks are denoted by B). For example, try`): print(`IsColCompatible([[B,1],[0,B]],[1,0],2,B);`): elif nops([args])=1 and op(1,[args])=LC then print(`LC(p): a loaded coin of prob. p. For example, try: LC(1/2);`): elif nops([args])=1 and op(1,[args])=MakeBook then print(`MakeBook(m,n,p,K): makes K puzzles of type (m,n,p)`): print(`with a unique solution`): print(`For example, try:`): print(`MakeBook(10,10,2/5,5);`): elif nops([args])=1 and op(1,[args])=MakePuzzle then print(`MakePuzzle(m,n,p): makes an m by n puzzle with prob. `): print(`of a 0 being p. For example,`): print(`try: MakePuzzle(5,5,1/2);`): elif nops([args])=1 and op(1,[args])=Optiot then print(`Optiot(a,L): Given a vector of pos. integers a and a pos.`): print(`integer L, outputs the list all the pairs [a,b] such that`): print(`Targem([a,b]) has length L. For example, try:`): print(`Optiot([13],15);`): elif nops([args])=1 and op(1,[args])=PartiallyFill then print(`PartiallyFill(R1,u):Given a list of rows R1, and a vector`): print(`u such that nops(u)<=nops(R1) and 1<=u[i]<=nops(R1[i])`): print(`creates the partial matrix (with Blanks). For example, try:`): print(`PartiallyFill([[[0,1,1,0],[1,1,0,0]],[[0,1,1,0],[1,0,0,1]]],[1,2]);`): elif nops([args])=1 and op(1,[args])=Prof then print(`Prof(v): the profile of v. For example try Prof([1,1,1]);`): elif nops([args])=1 and op(1,[args])=Ptor then print(`Ptor([R,C]): given two lists of lists of pos. integers`): print(`outputs a 0-1 matrix with the row descriptions`): print(`given by R and the column-restictions given by C.`): print(`if none exists, it returns FAIL`): print(`For example, to solve the puzzle from Yediot, Jan. 9, 2009, try`): print(`R1:=[[12],[1,1,4,2,1]$3,[1,10,1],[1,1],[1,11,1],[1,2,2,1,1],`): print(`[1,8,1,1],[1,2,2,1,1],[1,8,1,1],[1,2,2,1,1],[1,11,1],[1,1],[13]]:`): print(`C1:=[[13],[1,1],[5,7,1],[1,1,7,1],[1$7],[5,1$5]$3,[5,7,1],[1,1,7,1],`): print(`[5,1,1,1]$2,[1,7,1],[1,1],[12]];`): print(`Ptor([R1s,C1s]);`): print(``): elif nops([args])=1 and op(1,[args])=PtorK then print(`PtorK([R,C]): given two lists of lists of pos. integers`): print(`outputs all 0-1 matrices with the row descriptions`): print(`given by R and the column-restictions given by C.`): print(`if none exists, it returns FAIL`): print(`For example, to solve the puzzle from Yediot, Jan. 9, 2009, try`): print(`R1:=[[12],[1,1,4,2,1]$3,[1,10,1],[1,1],[1,11,1],[1,2,2,1,1],`): print(`[1,8,1,1],[1,2,2,1,1],[1,8,1,1],[1,2,2,1,1],[1,11,1],[1,1],[13]]:`): print(`C1:=[[13],[1,1],[5,7,1],[1,1,7,1],[1$7],[5,1$5]$3,[5,7,1],[1,1,7,1],`): print(`[5,1,1,1]$2,[1,7,1],[1,1],[12]];`): print(`PtorK([R1s,C1s]);`): print(``): elif nops([args])=1 and op(1,[args])=PtorY then print(`PtorY([R,C],B): given two lists of lists of pos. integers`): print(`and a symbol B,`): print(`outputs a picture where B denotes a black square`): print(` with the row descriptions`): print(`given by R and the column-restictions given by C.`): print(`if none exists, it returns FAIL`): print(`For example, to solve the puzzle from Yediot, Jan. 9, 2009, try`): print(`R1:=[[12],[1,1,4,2,1]$3,[1,10,1],[1,1],[1,11,1],[1,2,2,1,1],`): print(`[1,8,1,1],[1,2,2,1,1],[1,8,1,1],[1,2,2,1,1],[1,11,1],[1,1],[13]]:`): print(`C1:=[[13],[1,1],[5,7,1],[1,1,7,1],[1$7],[5,1$5]$3,[5,7,1],[1,1,7,1],`): print(`[5,1,1,1]$2,[1,7,1],[1,1],[12]];`): print(`PtorY([R1s,C1s],B);`): print(``): elif nops([args])=1 and op(1,[args])=Ptor1 then print(`Ptor1(OpR,OpC): given two lists of lists of `): print(`options to be rows and colums`): print(`where OpR[i] is the list of 0-1 vectors`): print(`that may be the i-th row, and OpC[j] is`): print(`the list of o-1-vectors that may be the j-th column`): print(`outputs a 0-1 matrices compatible with it, or returns FAIL`): print(`For example, try:`): print(`Ptor1([[[0,0],[0,1]],[[1,0],[1,1]]],[[[0,0],[0,1]],[[1,0],[1,1]]]);`): elif nops([args])=1 and op(1,[args])=Purge then print(`Purge(R1,u,C1): Given a list of lists of possible rows,`): print(` a choice vector`): print(`u (nops(u)<=nops(R1)), and a list of sets of possible columns`): print(`trims down the possible columns by purging those that conflict`): print(`with the first nops(u) rows are those given by u.`): print(`For example, try:`): print(`Purge(R2st,[1,1],C2st);`): elif nops([args])=1 and op(1,[args])=Sader then print(`Sader(OpR): Finds the sorting permutation`): print(`that arranges the rows of OpR in increasing order`): print(`For example, try:`): print(`Sader(C1st);`): elif nops([args])=1 and op(1,[args])=Targem then print(`Targem(p): Given a pair [a,b]`): print(`of vector of pos. integers a and a vector`): print(`of non-negative integers b, (nops(b)-nops(a)=1)`): print(` outputs the 0-1 vector`): print(`[0^b[1]1^a[1] 0^(b[2]+1)1^a[2] 0^(b[3]+1)... 1^a[nops(a)]0^b[nops(b)]`): print(`For example,try:`): print(`Targem([[13],[1,1]]);`): elif nops([args])=1 and op(1,[args])=Tirgum then print(`Tirgum(R,C): given two lists of lists of pos. integers`): print(`translates to the options`): print(`For example, to solve the puzzle from Yediot, Jan. 9, 2009, try`): print(`R1:=[[12],[1,1,4,2,1]$3,[1,10,1],[1,1],[1,11,1],[1,2,2,1,1],`): print(`[1,8,1,1],[1,2,2,1,1],[1,8,1,1],[1,2,2,1,1],[1,11,1],[1,1],[13]]:`): print(`C1:=[[13],[1,1],[5,7,1],[1,1,7,1],[1$7],[5,1$5]$3,[5,7,1],[1,1,7,1],`): print(`[5,1,1,1]$2,[1,7,1],[1,1],[12]];`): print(`Tirgum(R1,C1);`): print(``): elif nops([args])=1 and op(1,[args])=UnTargem then print(`UnTargem(v): converts a 0-1 vector to a pair [a,b]`): print(`For example, try:`): print(`UnTargem([0,0,1,1,0,0,1,1,0]);`): elif nops([args])=1 and op(1,[args])=VecToFreq then print(`VecToFreq(v): given a 0-1 vector writes it as `): print(`0^a1 1^b1 0^a2 1^b2 ... 0^an 1^bn 0^a(n+1)`): print(`For example, do: VecToFreq([0,1,1,1,0,0,1,1]);`): else print(`There is no ezra for`,args): fi: end: #Targem(p): Given a pair [a,b] #of vector of pos. integers a and a vector #of non-negative integers b, (nops(b)-nops(a)=1) outputs the 0-1 vector #[0^b[1]1^a[1] 0^(b[2]+1)1^a[2] 0^(b[3]+1)... 1^a[nops(a)]0^b[nops(b)] #For example,try: #Targem([[13],[1,1]]); Targem:=proc(p) local a,b,i: a:=p[1]: b:=p[2]: if nops(b)-nops(a)<>1 then RETURN(FAIL): fi: if a=[] then RETURN([0$b[1]]): fi: [0$b[1],seq( op([1$a[i],0$(b[i+1]+1)]),i=1..nops(a)-1),1$a[nops(a)], 0$b[nops(b)]]: end: #Compo(N,r): all vectors of non-negative integers of length r #that add-up to N. For example, try: Comp(5,2); Compo:=proc(N,r) local gu,mu,i,m: option remember: if r=0 then if N=0 then RETURN({[]}): else RETURN({}): fi: fi: gu:={}: for i from 0 to N do mu:=Compo(N-i,r-1): gu:=gu union {seq([op(m),i],m in mu)}: od: gu: end: #Optiot(a,L): Given a vector of pos. integers a and a pos. #integer L, outputs the list all the pairs [a,b] such that #Targem([a,b]) has length L. For example, try: #Optiot([13],15); Optiot:=proc(a,L) local gu,b: gu:=Compo(L-convert(a,`+`)-nops(a)+1,nops(a)+1): [seq([a,b], b in gu)]: end: UnTargem:=proc(v) local a,i,v1: if v=[] then RETURN(v): fi: a:=v[1]: for i from 1 to nops(v) while v[i]=a do od: i:=i-1: v1:=[op(i+1..nops(v),v)]: [[a,i],op(UnTargem(v1))]: end: #VecToPair(v): converts a 0-1 vector to a pair [a,b] #For example, try: #VecToPair([0,0,1,1,0,0,1,1,0]); VecToPair:=proc(v) local gu,a,b,i: gu:=UnTargem(v): if gu[1][1]=1 then gu:=[[0,0],op(gu)]: fi: if gu[nops(gu)][1]=1 then gu:=[op(gu),[0,0]]: fi: a:=[seq(gu[2*i][2],i=1..nops(gu)/2)]: b:=[seq(gu[2*i+1][2],i=0..nops(gu)/2)]: b:=[b[1],seq(b[i]-1,i=2..nops(b)-1),b[nops(b)]]: [a,b]: end: #Tirgum(R,C): given two lists of lists of pos. integers #outputs all 0-1 matrices with the row descriptions #given by R and the column-restictions given by C. #For example, to solve the puzzle from Yediot, Jan. 9, 2009, try #R1:=[[12],[1,1,4,2,1]$3,[1,10,1],[1,1],[1,11,1],[1,2,2,1,1], #[1,8,1,1],[1,2,2,1,1],[1,8,1,1],[1,2,2,1,1],[1,11,1],[1,1],[13]] #C1:=[[13],[1,1],[5,7,1],[1,1,7,1],[1$7],[5,1$5]$3,[5,7,1],[1,1,7,1], #[5,1,1,1]$2,[1,7,1],[1,1],[12]]; #Tirgum(R1,C1); Tirgum:=proc(R,C) local r,c,OpR,OpC,p,i: r:=nops(R): c:=nops(C): OpR:=[seq([seq(Targem(p), p in Optiot(R[i],c))],i=1..r)]: OpC:=[seq([seq(Targem(p), p in Optiot(C[i],r))],i=1..c)]: [OpR,OpC]: end: #Ptor([R,C]): given two lists of lists of pos. integers #outputs all 0-1 matrices with the row descriptions #given by R and the column-restictions given by C. #For example, to solve the puzzle from Yediot, Jan. 9, 2009, try #R1:=[[12],[1,1,4,2,1]$3,[1,10,1],[1,1],[1,11,1],[1,2,2,1,1], #[1,8,1,1],[1,2,2,1,1],[1,8,1,1],[1,2,2,1,1],[1,11,1],[1,1],[13]] #C1:=[[13],[1,1],[5,7,1],[1,1,7,1],[1$7],[5,1$5]$3,[5,7,1],[1,1,7,1], #[5,1,1,1]$2,[1,7,1],[1,1],[12]]; #Ptor([R1,C1]); Ptor:=proc(Zug): Ptor1(op(Hafokh(Zug))): end: #Ptorf([R,C]): given two lists of lists of pos. integers #outputs all 0-1 matrices with the row descriptions #given by R and the column-restictions given by C. #For example, to solve the puzzle from Yediot, Jan. 9, 2009, try #R1:=[[12],[1,1,4,2,1]$3,[1,10,1],[1,1],[1,11,1],[1,2,2,1,1], #[1,8,1,1],[1,2,2,1,1],[1,8,1,1],[1,2,2,1,1],[1,11,1],[1,1],[13]] #C1:=[[13],[1,1],[5,7,1],[1,1,7,1],[1$7],[5,1$5]$3,[5,7,1],[1,1,7,1], #[5,1,1,1]$2,[1,7,1],[1,1],[12]]; #Ptorf([R1,C1]); Ptorf:=proc(Zug): Ptor1f(op(Hafokh(Zug))): end: #IsColCompatible(M,v,j,B): Is placing v at the j-th column #compatible with the partially-filled matrix M #(where blanks are denoted by B). For example, try #IsColCompatible([[B,1],[0,B]],[1,0],2); IsColCompatible:=proc(M,v,j) local v1,i1: v1:=[seq(M[i1][j],i1=1..nops(M))]: for i1 from 1 to nops(v) do if (v1[i1]=0 and v[i1]=1) or (v1[i1]=1 and v[i1]=0) then RETURN(false): fi: od: true: end: #PartiallyFill(R1,u):Given a list of rows R1, and a vector #u such that nops(u)<=nops(R1) and 1<=u[i]<=nops(R1[i]) #creates the partial matrix (with Blanks). For example, try: #PartiallyFill([[[0,1,1,0],[1,1,0,0]],[[0,1,1,0],[1,0,0,1]]],[1,2]); PartiallyFill:=proc(C1,u) local i1: [seq(C1[i1][u[i1]],i1=1..nops(u))]: end: #Purge(R1,u,C1): Given a list of lists of possible rows, a choice vector #u (nops(u)<=nops(R1)), and a list of sets of possible columns #trims down the possible columns by purging those that conflict #with the first nops(u) rows are those given by u. #For example, try: #Purge(R2st,[1,1],C2st); Purge:=proc(R1,u,C1) local C2,C3,M,c2,i1,j,lu: option remember: if u=[] then RETURN(C1): fi: C2:=Purge(R1,[op(1..nops(u)-1,u)],C1): M:=PartiallyFill(R1,u): C3:=[]: for j from 1 to nops(C2) do lu:={}: for c2 in C2[j] do if [seq(M[i1][j],i1=1..nops(M))]=[op(1..nops(M),c2)] then lu:=lu union {c2}: fi: od: C3:=[op(C3),lu]: od: C3: end: #HaBa(R,C,u): The next-in-line to try, for example, try: #HaBa(R1st,C1st,[1$15]); HaBa:=proc(R,C,u,L) local i,j: if u=L then if not member({},Purge(R,u,C)) then RETURN([0,u]): else RETURN(FAIL): fi: fi: for i from 1 to nops(u) while not member({},Purge(R,[op(1..i,u)],C)) do od: if i=1 then if u[1]=L[1] then RETURN(FAIL): else RETURN([1,[u[1]+1,1$(nops(u)-1) ] ]): fi: fi: if i=nops(u)+1 then RETURN([0,u]): fi: for j from i by -1 to 1 while u[j]=L[j] do od: if j=0 then RETURN(FAIL): fi: [1, [op(1..j-1,u),u[j]+1, 1$(nops(u)-j)]]: end: #Ptor1(OpR,OpC): given two lists of lists of #options to be rows and colums #where OpR[i] is the list of 0-1 vectors #that may be the i-th row, and OpC[j] is #the list of o-1-vectors that may be the j-th column #outputs all the 0-1 matrices compatible with it. #For example, try: #Ptor1([[[0,0],[0,1]],[[1,0],[1,1]]],[[[0,0],[0,1]],[[1,0],[1,1]]]); Ptor1:=proc(OpR,OpC) local u,L,i: u:=[1,[1$(nops(OpR))]]: L:=[seq(nops(OpR[i]),i=1..nops(OpR))]: while u[1]=1 do u:=HaBa(OpR,OpC,u[2],L): od: if u=FAIL then RETURN(FAIL): else RETURN( PartiallyFill(OpR,u[2]) ): fi: end: #PtorK([R,C]): given two lists of lists of pos. integers #outputs all 0-1 matrices with the row descriptions #given by R and the column-restictions given by C. #For example, to solve the puzzle from Yediot, Jan. 9, 2009, try #R1:=[[12],[1,1,4,2,1]$3,[1,10,1],[1,1],[1,11,1],[1,2,2,1,1], #[1,8,1,1],[1,2,2,1,1],[1,8,1,1],[1,2,2,1,1],[1,11,1],[1,1],[13]] #C1:=[[13],[1,1],[5,7,1],[1,1,7,1],[1$7],[5,1$5]$3,[5,7,1],[1,1,7,1], #[5,1,1,1]$2,[1,7,1],[1,1],[12]]; #PtorK([R1,C1]); PtorK:=proc(Zug): Ptor1K(op(Hafokh(Zug))): end: #PtorKf([R,C]): given two lists of lists of pos. integers #outputs all 0-1 matrices with the row descriptions #given by R and the column-restictions given by C. #For example, to solve the puzzle from Yediot, Jan. 9, 2009, try #R1:=[[12],[1,1,4,2,1]$3,[1,10,1],[1,1],[1,11,1],[1,2,2,1,1], #[1,8,1,1],[1,2,2,1,1],[1,8,1,1],[1,2,2,1,1],[1,11,1],[1,1],[13]] #C1:=[[13],[1,1],[5,7,1],[1,1,7,1],[1$7],[5,1$5]$3,[5,7,1],[1,1,7,1], #[5,1,1,1]$2,[1,7,1],[1,1],[12]]; #PtorKf([R1,C1]); PtorKf:=proc(Zug): Ptor1Kf(op(Hafokh(Zug))): end: #Grab(v,a): the first string of a's in v. #For example, try Grab([1,1,1,0,0],1): Grab:=proc(v,a) local i: for i from 1 to nops(v) while v[i]=a do od: i-1: end: #VtoF(v):changes vector to frequency notation VtoF:=proc(v) local v1,i,a,gu1: if v=[] then RETURN([]): fi: a:=v[1]: i:=Grab(v,a): v1:=[op(i+1..nops(v),v)]: gu1:=VtoF(v1): [[a,i],op(gu1)]: end: #Prof(v): the profile of v. For example try Prof([1,1,1]); Prof:=proc(v) local u,gu,i: u:=VtoF(v): gu:=[]: for i from 1 to nops(u) do if u[i][1]=1 then gu:=[op(gu),u[i][2]]: fi: od: gu: end: #LC(p): a loaded coin of prob. p. For example, try: LC(1/2); LC:=proc(p) local m,n,d: m:=numer(p): n:=denom(p): d:=rand(1..n)(): if d<=m then RETURN(0): else RETURN(1): fi: end: #MakePuzzle(m,n,p): makes an m by n puzzle with prob. #of a 0 being p. For example, #try: MakePuzzle(5,5,1/2); MakePuzzle:=proc(m,n,p) local i,j,M,i1,R,C: M:=[seq([seq(LC(p),i=1..n)],j=1..m)]: R:=[seq(Prof(M[i]),i=1..m)]: if member([],R) then RETURN(FAIL): fi: C:=[seq(Prof([seq(M[i1][j],i1=1..m)]),j=1..n)]: if member([],C) then RETURN(FAIL): fi: [M,[R,C]]: end: #PtorY([R,C],B): given two lists of lists of pos. integers #outputs all 0-1 matrices with the row descriptions #given by R and the column-restictions given by C. #the output is a matrix with the black squares denoted by B #For example, to solve the puzzle from Yediot, Jan. 9, 2009, try #R1:=[[12],[1,1,4,2,1]$3,[1,10,1],[1,1],[1,11,1],[1,2,2,1,1], #[1,8,1,1],[1,2,2,1,1],[1,8,1,1],[1,2,2,1,1],[1,11,1],[1,1],[13]] #C1:=[[13],[1,1],[5,7,1],[1,1,7,1],[1$7],[5,1$5]$3,[5,7,1],[1,1,7,1], #[5,1,1,1]$2,[1,7,1],[1,1],[12]]; #PtorY([R1,C1],B); PtorY:=proc(Zug,B) local M: M:=Ptor(Zug): M:=subs({0=` `, 1=B},M): convert(M,matrix): end: #PtorYf([R,C],B): given two lists of lists of pos. integers #outputs all 0-1 matrices with the row descriptions #given by R and the column-restictions given by C. #the output is a matrix with the black squares denoted by B #For example, to solve the puzzle from Yediot, Jan. 9, 2009, try #R1:=[[12],[1,1,4,2,1]$3,[1,10,1],[1,1],[1,11,1],[1,2,2,1,1], #[1,8,1,1],[1,2,2,1,1],[1,8,1,1],[1,2,2,1,1],[1,11,1],[1,1],[13]] #C1:=[[13],[1,1],[5,7,1],[1,1,7,1],[1$7],[5,1$5]$3,[5,7,1],[1,1,7,1], #[5,1,1,1]$2,[1,7,1],[1,1],[12]]; #PtorYf([R1,C1],B); PtorYf:=proc(Zug,B) local M: M:=Ptorf(Zug): M:=subs({0=` `, 1=B},M): convert(M,matrix): end: #HaBa1(R,C,u): The next-in-line to try after a succesful one #HaBa1(R1st,C1st,[1$15]); HaBa1:=proc(L,u) local j: if u=L then RETURN([0,L]): fi: for j from nops(u) by -1 to 1 while u[j]=L[j] do od: [op(1..j-1,u),u[j]+1,1$(nops(u)-j)]: end: #Ptor1a(OpR,OpC,sta): given two lists of lists of #options to be rows and colums #where OpR[i] is the list of 0-1 vectors #that may be the i-th row, and OpC[j] is #the list of o-1-vectors that may be the j-th column #and a starting vector a #outputs all the 0-1 matrices compatible with it. #For example, try: #Ptor1a([[[0,0],[0,1]],[[1,0],[1,1]]],[[[0,0],[0,1]],[[1,0],[1,1]]],[1$15]); Ptor1aOld:=proc(OpR,OpC,sta) local u,L,i: u:=[1,sta]: L:=[seq(nops(OpR[i]),i=1..nops(OpR))]: while u[1]=1 do u:=HaBa(OpR,OpC,u[2],L): od: if u=FAIL then RETURN(FAIL): else RETURN( PartiallyFill(OpR,u[2]),u[2] ): fi: end: #Ptor1K(OpR,OpC): given two lists of lists of #options to be rows and colums #where OpR[i] is the list of 0-1 vectors #that may be the i-th row, and OpC[j] is #the list of o-1-vectors that may be the j-th column #outputs the set pf 0-1 matrices compatible with it. #For example, try: #Ptor1K([[[0,0],[0,1]],[[1,0],[1,1]]],[[[0,0],[0,1]],[[1,0],[1,1]]]); Ptor1K:=proc(OpR,OpC) local L,i,mu,sta,gu: sta:=[1$(nops(OpR))]: L:=[seq(nops(OpR[i]),i=1..nops(OpR))]: gu:={}: while mu<>FAIL do mu:=Ptor1a(OpR,OpC,sta): if mu<>FAIL then gu:=gu union {mu[1]}: if mu[2]=L then RETURN(gu): else sta:=HaBa1(L,mu[2]): fi: fi: od: gu: end: #Ptor1a(OpR,OpC,sta): given two lists of lists of #options to be rows and colums #where OpR[i] is the list of 0-1 vectors #that may be the i-th row, and OpC[j] is #the list of o-1-vectors that may be the j-th column #outputs all the 0-1 matrices compatible with it. #For example, try: #Ptor1([[[0,0],[0,1]],[[1,0],[1,1]]],[[[0,0],[0,1]],[[1,0],[1,1]]]); Ptor1a:=proc(OpR,OpC,sta) local u,L,i: u:=[1,sta]: L:=[seq(nops(OpR[i]),i=1..nops(OpR))]: while u[1]=1 do u:=HaBa(OpR,OpC,u[2],L): od: if u=FAIL then RETURN(FAIL): else RETURN( PartiallyFill(OpR,u[2]), u[2] ): fi: end: ####new stuff (2/7/09) #Hafokh([R,C]): converts to the more general format of options #Hafokh([R1,C1]); Hafokh:=proc(Zug) local R,C,r,c,OpR,OpC,p,i: R:=Zug[1]: C:=Zug[2]: r:=nops(R): c:=nops(C): OpR:=[seq([seq(Targem(p), p in Optiot(R[i],c))],i=1..r)]: OpC:=[seq([seq(Targem(p), p in Optiot(C[i],r))],i=1..c)]: [OpR,OpC]: end: #Sader(OpR): Finds the sorting permutation #that arranges the rows of OpR in increasing order #For example, try: #Sader(C1st); Sader:=proc(OpR) local L,pi,katan,S,i: L:=[seq(nops(OpR[i]),i=1..nops(OpR))]: S:={op(L)}: pi:=[]: while S<>{} do katan:=min(S): for i from 1 to nops(L) do if L[i]=katan then pi:=[op(pi),i]: fi: od: S:=S minus {katan}: od: pi: end: #Ptor1Kf(OpR,OpC): given two lists of lists of #options to be rows and colums #where OpR[i] is the list of 0-1 vectors #that may be the i-th row, and OpC[j] is #the list of o-1-vectors that may be the j-th column #outputs the set pf 0-1 matrices compatible with it. #For example, try: #Ptor1Kf([[[0,0],[0,1]],[[1,0],[1,1]]],[[[0,0],[0,1]],[[1,0],[1,1]]]); Ptor1Kf:=proc(OpR,OpC) local pi,OpR1,OpC1,i,j,c,lu,T,gu,g: pi:=Sader(OpR): OpR1:=[seq(OpR[pi[i]],i=1..nops(OpR))]: OpC1:=[]: for j from 1 to nops(OpC) do lu:=[]: for c in OpC[j] do lu:=[op(lu), [seq(c[pi[i]],i=1..nops(c))] ]: od: OpC1:=[op(OpC1),lu]: od: gu:=Ptor1K(OpR1,OpC1): for i from 1 to nops(pi) do T[pi[i]]:=i: od: {seq([seq(g[T[i]],i=1..nops(g))], g in gu)}: end: #Ptor1f(OpR,OpC): given two lists of lists of #options to be rows and colums #where OpR[i] is the list of 0-1 vectors #that may be the i-th row, and OpC[j] is #the list of o-1-vectors that may be the j-th column #outputs the set pf 0-1 matrices compatible with it. #For example, try: #Ptor1f([[[0,0],[0,1]],[[1,0],[1,1]]],[[[0,0],[0,1]],[[1,0],[1,1]]]); Ptor1f:=proc(OpR,OpC) local pi,OpR1,OpC1,i,j,c,lu,T,g: pi:=Sader(OpR): OpR1:=[seq(OpR[pi[i]],i=1..nops(OpR))]: OpC1:=[]: for j from 1 to nops(OpC) do lu:=[]: for c in OpC[j] do lu:=[op(lu), [seq(c[pi[i]],i=1..nops(c))] ]: od: OpC1:=[op(OpC1),lu]: od: g:=Ptor1(OpR1,OpC1): for i from 1 to nops(pi) do T[pi[i]]:=i: od: [seq(g[T[i]],i=1..nops(g))]: end: with(plots): #DrawPuzzle(P): draws the puzzle P. #For example, try: #DrawPuzzle([R2s,Cs2]); DrawPuzzle:=proc(P) local i,j,d,m,n,k1,k2,i1,j1,ka: m:=nops(P[1]): n:=nops(P[2]): k1:=max(seq(nops(P[1][i]),i=1..m) ): k2:=max(seq(nops(P[2][i]),i=1..n) ): d:=plot([[-k1,0],[n,0]],thickness=4,axes=none,numpoints=3000,color=black): for i from 1 to m do if not i mod 5 =0 then d:=d,plot([[-k1,-i],[n,-i]],color=black): else d:=d,plot([[-k1,-i],[n,-i]], thickness=4, color=black): fi: od: for j from 0 to n do if not j mod 5 = 0 then d:=d,plot([[j,k2],[j,-m]], color=black): else d:=d,plot([[j,k2],[j,-m]],thickness=4, color=black): fi: od: for i from 1 to m do ka:=nops(P[1][i]): for j1 from 1 to ka do d:=d,textplot([-ka-1+j1,-i+.4,P[1][i][j1]]): od: od: for j from 1 to n do ka:=nops(P[2][j]): for i1 from 1 to ka do d:=d,textplot([j-1/2,ka+1/2-i1 ,P[2][j][i1]]): od: od: display(d): end: #DrawSolution(S): draws the solution S #For example, try: #DrawSolution(Ptorf(P2),.1); DrawSolution:=proc(S,eps) local i,j,d,m,n,k,kak: m:=nops(S): n:=nops(S[1]): d:=plot([[0,0],[n,0]],thickness=4,axes=none,numpoints=3000,color=black): for i from 1 to m do if not i mod 5 =0 then d:=d,plot([[0,-i],[n,-i]],color=black): else d:=d,plot([[0,-i],[n,-i]], thickness=4, color=black): fi: od: for j from 0 to n do if not j mod 5 = 0 then d:=d,plot([[j,0],[j,-m]], color=black): else d:=d,plot([[j,0],[j,-m]],thickness=4, color=black): fi: od: for i from 1 to nops(S) do for j from 1 to nops(S[i]) do if S[i][j]=1 then #d:=d, textplot([j-1/2,-i+1/2,B]): kak:=trunc(0.5/eps): for k from 1 to kak do d:=d, plot([[j-1/2-k*eps,-i+1/2-k*eps ], [j-1/2-k*eps,-i+1/2+k*eps ], [j-1/2+k*eps,-i+1/2+k*eps ], [j-1/2+k*eps,-i+1/2-k*eps ], [j-1/2-k*eps,-i+1/2-k*eps ]], color=black): od: fi: od: od: display(d): end: #MakeBook(m,n,p,K): makes K puzzles of type (m,n,p) #with a unique solution #For example, try: #MakeBook(10,10,2/5,5); MakeBook:=proc(m,n,p,K) local gu ,P , lu: gu:={}: while nops(gu)<=K do P:=MakePuzzle(m,n,p): lu:=PtorKf(P[2]): if nops(lu)=1 then if P[1]<>lu[1] then ERROR(`Something is very wrong`): fi: gu:=gu union {P}: fi: od: gu: end: