###################################################################### #CAPSULES.txt: Save this file as CAPSULES.txt # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read CAPSULES.txt # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg at math dot rutgers dot edu # ###################################################################### #Created: print(`Created: Dec. 25, 2016`): print(` This is CAPSULES.txt `): print(`To solve Capsules puzsles, for example the one in the New Times magazine, Dec. 25, 2016. By Wei-Hwa Huang`): print(`---------------------------------------`): print(`For a list of the Supporting procedures type ezra1();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`---------------------------------------`): print(`---------------------------------------`): print(`For a list of the MAIN procedures type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`---------------------------------------`): with(combinat): ezra1:=proc() if args=NULL then print(` The supporting procedures are: Del, Efo, Efo1, IsLegal, LO, Neis, NicePar, P1, P2, P3, P4, SOLall, Yels `): print(``): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: SOL, SOLv `): print(` `): elif nops([args])=1 and op(1,[args])=Del then print(`Del(P,c): inputs a puzzle P and a cell c, creates another puzzle with the cell replaced by 0. Try`): print(`Del(P2(),[1,3]);`): elif nops([args])=1 and op(1,[args])=Efo then print(`Efo(P): Inputs a puzzle finds`): print(`the legal places [entry, cell] that it can be extended by`): print(`Efo(P2());`): elif nops([args])=1 and op(1,[args])=Efo1 then print(`Efo1(P,i): Inputs a puzzle and a capusle number i, for each of the remaninig labels, finds`): print(`the legal places it can reside. Try:`): print(`Efo(P2();`): elif nops([args])=1 and op(1,[args])=IsLegal then print(`IsLegal(P): inputs a Capsule puzzle, and decides whether it is legal. Try:`): print(`IsLegal(P1());`): elif nops([args])=1 and op(1,[args])=LO then print(`LO(P,i): given a puzzle, and a posivive integer, i, finds a label with the propery that the`): print(`there is only one way of placing it legally, if there is no such thing it returns 0. It is all`): print(`filled it returns FAIL. Try`): print(`LO(P1(),4);`): elif nops([args])=1 and op(1,[args])=Neis then print(`Neis(c,m,n): all the neighbors of the cell c=[i,j] in an m by n grid`): print(`Try:`): print(` Neis([5,6],7,7); `): elif nops([args])=1 and op(1,[args])=NicePar then print(`NicePar(m,n,a,b): partitions the m by n grid into a by b rectangles. Try: `): print(` NicePar(6,6,2,2); `): elif nops([args])=1 and op(1,[args])=P1 then print(`P1()"`): print(`The Capsule puzzle published in the New York Times magazine, Dec. 25, 2016, composed by We-Hwa Huang`): elif nops([args])=1 and op(1,[args])=P2 then print(`P2();`): print(`The Capsule puzzle published in the New York Times magazine, Jan. 1, 2017, composed by We-Hwa Huang`): elif nops([args])=1 and op(1,[args])=P3 then print(`P3();`): print(`The Capsule puzzle published in the New York Times magazine, Feb. 5, 2017, composed by We-Hwa Huang`): elif nops([args])=1 and op(1,[args])=P4 then print(`P4();`): print(`The Capsule puzzle published in the New York Times magazine, March 19, 2017, composed by We-Hwa Huang`): elif nops([args])=1 and op(1,[args])=SOL then print(`SOL(P): The (unique) solution of the puzzle P (or else it tells you so). Try:`): print(``): print(`For the Dec. 25, 2016 New York Times Capsule Puzzle:`): print(`SOL(P1()); `): print(`For the Jan. 1, 2017 New York Times Capsule Puzzle:`): print(`SOL(P2());`): print(`For the Feb. 5, 2017 New York Times Capsule Puzzle:`): print(`SOL(P3());`): print(`For the March 19, 2017 New York Times Capsule Puzzle:`): print(`SOL(P4());`): elif nops([args])=1 and op(1,[args])=SOLv then print(`Verbose form of SOL(P) (q.v.)`): print(``): print(`SOLv(P): The (unique) solution of the Capsule puzzle P (or else it tells you so). Try:`): print(``): print(`For the Dec. 25, 2016 New York Times Capsule Puzzle:`): print(`SOLv(P1()); `): print(`For the Jan. 1, 2017 New York Times Capsule Puzzle:`): print(`SOLv(P2());`): print(`For the Feb. 5, 2017 New York Times Capsule Puzzle:`): print(`SOLv(P3());`): print(`For the March 19, 2017 New York Times Capsule Puzzle:`): print(`SOLv(P4());`): elif nops([args])=1 and op(1,[args])=SOLall then print(`SOLall(P): All the solutions of the puzzle. Try:`): print(`For the Dec. 25, 2016 New York Times Capsule Puzzle:`): print(`SOLall(P1()); `): print(`For the Jan. 1, 2017 New York Times Capsule Puzzle:`): print(`SOLall(P2());`): print(`For the Feb. 5, 2017 New York Times Capsule Puzzle:`): print(`SOLall(P3());`): print(`For the March 19, 2017 New York Times Capsule Puzzle:`): print(`SOLall(P4());`): elif nops([args])=1 and op(1,[args])=Yels then print(`Yels(P): given a puzzle P, finds its descendants. Try:`): print(`Yels(P2());`): else print(`There is no ezra for`,args): fi: end: #P1(): The New York Times Magazine Capsule puzzle of Dec. 25, 2016 P1:=proc(): [ [[3,0,2,0,0,0,0], [5,7,0,0,0,5,0], [0,0,0,5,3,0,0], [1,6,0,0,0,7,2], [0,0,5,2,0,0,0], [0,2,0,0,0,6,2], [0,0,0,0,5,0,7]], [ {[1,1],[1,2],[1,3],[1,4],[2,2],[2,4],[2,5]}, {[1,5],[1,6],[2,6],[2,7],[3,5],[3,6],[4,6]}, {[1,7]}, {[2,1],[2,3],[3,1],[3,2],[3,3],[4,1],[5,1]}, {[3,4],[4,3],[4,4],[4,5],[5,4]}, {[3,7],[4,7]}, {[4,2],[5,2],[5,3],[6,1],[6,2],[7,2],[7,3]}, {[5,5],[5,6],[5,7],[6,5],[6,7]}, {[6,3],[6,4],[7,4],[7,5],[7,6],[6,6],[7,7]}, {[7,1]}] ]: end: #P2(): The New York Times Magazine Capsule puzzle of Jan. 1, 2017 P2:=proc(): [ [[0,0,4,0,5,0,4], [1,0,0,0,0,3,0], [0,0,0,0,0,0,1], [0,0,3,2,1,0,0], [4,0,0,0,0,0,0], [0,5,0,0,0,0,3], [3,0,4,0,3,0,0]], [{[1,1],[2,1] }, {[1,2],[1,3],[1,4],[1,5],[2,3] }, { [1,6],[1,7],[2,5],[2,6],[3,5]}, { [2,2],[3,1],[3,2],[3,3],[4,3]}, {[2,4],[3,4],[4,4],[5,4],[6,4]}, {[2,7],[3,7] }, {[3,6],[4,5],[4,6],[4,7],[5,5]}, {[4,1],[4,2],[5,1],[5,2],[6,1]}, {[5,3],[6,2],[6,3],[7,1],[7,2] }, {[5,6],[5,7],[6,6],[6,7],[7,7]}, {[6,5],[7,3],[7,4],[7,5],[7,6] }] ]: end: #P3(): The New York Times Magazine Capsule puzzle of Feb. 5, 2017 P3:=proc(): [ [[0,1,0,5,0,0,0], [2,0,0,3,0,0,4], [0,0,0,0,0,0,0], [7,5,0,0,0,6,5], [0,0,0,0,0,0,0], [3,0,0,7,0,0,5], [0,0,0,2,0,3,0]], [ #startint at row 1 {[1,1],[1,2],[2,1] }, {[1,3],[1,4],[2,2],[2,3],[3,1],[3,2],[4,1] }, { [1,5],[1,6],[2,5]}, { [1,7],[2,6],[2,7],[3,5],[3,6]}, #startint at row 2 {[2,4],[3,3],[3,4],[4,2],[4,3]}, #startint at row 3 {[3,7]}, #startint at row 4 {[4,4],[4,5],[5,4]}, {[4,6],[4,7],[5,5],[5,6],[6,4],[6,5],[7,4] }, #startint at row 5 {[5,1],[5,2],[6,1]}, {[5,3],[6,2],[6,3],[7,1],[7,2]}, {[5,7],[6,6],[6,7],[7,5],[7,6]}, #startint at row 6 #startint at row 7 {[7,3]}, {[7,7]} ] ]: end: #P4(): The New York Times Magazine Capsule puzzle of March 18, 2017 P4:=proc(): [ [[0,0,0,0,0,0,3], [0,0,0,0,2,0,0], [0,0,0,0,0,6,0], [0,0,0,0,0,0,0], [0,4,0,0,0,0,0], [0,0,3,0,0,0,0], [2,0,0,2,0,0,0]], [ #startint at row 1 {[1,1],[1,2],[2,1],[2,2] }, {[1,3],[1,4],[2,3],[2,4]}, { [1,5],[2,5],[2,6],[3,5],[3,6],[3,7]}, { [1,6],[1,7],[2,7]}, #startint at row 2 #startint at row 3 {[3,1],[3,2],[4,1],[4,2]}, {[3,3],[3,4],[4,3],[4,4]}, #startint at row 4 {[4,5],[5,4],[5,5]}, {[4,6],[4,7],[5,6],[5,7] }, #startint at row 5 {[5,1],[5,2],[5,3],[6,1],[6,2]}, #startint at row 6 {[6,3],[7,1],[7,2],[7,3]}, {[6,4],[6,5],[7,4],[7,5]}, {[6,6],[6,7],[7,6],[7,7]} #startint at row 7 ] ]: end: #Neis(c,m,n): all the neighbors of the cell c=[i,j] in an m by n grid Neis:=proc(c,m,n) local i,j,lu,i1,j1: i:=c[1]: j:=c[2]: lu:={[i+1,j],[i-1,j], [i, j-1], [i, j+1], [i+1,j+1],[i+1,j-1],[i-1,j+1],[i-1,j-1]}: lu:= lu intersect {seq(seq([i1,j1],j1=1..n),i1=1..m)}: lu: end: #IsLegal(P): inputs a Capsule puzzle, and decides whether it is legal. Try: #IsLegal(P1()); IsLegal:=proc(P) local M,gu,mu,m,n,mu1,i,j,lu,lu1,lu2,i1: M:=P[1]: gu:=P[2]: if not type(M,list) then print(`The first component is not a list`): RETURN(false): fi: for i from 1 to nops(M) do if not type(M[i],list) then print(` The `, i, `-th entry of the first component is not a list`): RETURN(false): fi: od: if nops({seq(nops(M[i]),i=1..nops(M))})<>1 then print(`The grid is not a rectangle`): RETURN(false): fi: for i from 1 to nops(gu) do for j from i+1 to nops(gu) do if gu[i] intersect gu[j]<>{} then print(` The `, i, `-th capsule and the`, j, `-th calsule have the following elements in common`, gu[i] intersect gu[j]): RETURN(false): fi: od: od: mu:={seq(op(gu[i]),i=1..nops(gu))}: m:=nops(M): n:=nops(M[1]): mu1:={seq(seq([i,j],j=1..n),i=1..m)}: if mu1<>mu then lu:=mu1 minus mu: if lu<>{} then print(`The following cells do not belong to any capsule`, lu): RETURN(false): fi: lu:=mu minus mu1: if lu<>{} then print(` The following cells do not belong to the grid`, lu): RETURN(false): fi: fi: for i from 1 to nops(gu) do lu:=gu[i]: lu1:=[seq( M[lu[i1][1]][lu[i1][2]], i1=1..nops(lu))]: if max(op(lu1))>nops(lu) then print(` The `, i, `-th capsule contains an entry larger than its cardinality`): RETURN(false): fi: lu2:=[]: for i1 from 1 to nops(lu1) do if lu1[i1]<>0 then lu2:=[op(lu2),lu1[i1]]: fi: od: if nops(convert(lu2,set))<>nops(lu2) then print(` The `, i, `-th capsule contains repetitions`): RETURN(false): fi: od: for i from 1 to m do for j from 1 to n do lu:=Neis([i,j],m,n): if M[i][j]<>0 then for lu1 in lu do if M[lu1[1]][lu1[2]]=M[i][j] then print(`the cell`, [i,j], `and its neighbor`, lu1, `have the same number`): RETURN(false): fi: od: fi: od: od: true: end: #LO(P,i): given a puzzle, and a posivive integer, i, finds a label with the propery that the #there is only one way of placing it legally, if there is no such thing it returns 0. It is all #filled it returns FAIL. Try #LO(P1(),4); LO:=proc(P,i) local M,gu,lu,lu1,c,n,FAIL1,i1,mu1: M:=P[1]: gu:=P[2]: if not 1<=i and i<=nops(gu) then RETURN(FAIL1): fi: lu:=gu[i]: n:=nops(lu): mu1:={seq(i1,i1=1..n)} minus {seq(M[c[1]][c[2]], c in lu)}: if mu1={} then RETURN({},{}): fi: lu1:={}: for c in lu do if M[c[1]][c[2]]=0 then lu1:=lu1 union {c}: fi: od: mu1,lu1: end: #Efo1(P,i): Inputs a puzzle and a capusle number i, for each of the remaninig labels, finds #the legal places it can reside. Try: #Efo1(P2(),1); Efo1:=proc(P,i) local m,n,gu,mu1,lu1,c,T,k,sak,c1,M: M:=P[1]: m:=nops(M): n:=nops(M[1]): gu:=LO(P,i): mu1:=gu[1]: lu1:=gu[2]: for k in mu1 do T[k]:={}: for c in lu1 do sak:=Neis(c,m,n): if not member(k,{seq(M[c1[1]][c1[2]], c1 in sak)}) then T[k]:=T[k] union {c}: fi: od: od: {seq([k,T[k]], k in mu1)}: end: #Efo(P): Inputs a puzzle #the legal places that it can be extended #Efo(P2()); Efo:=proc(P) local i,lu,gu: gu:=P[2]: lu:={}: for i from 1 to nops(gu) do if LO(P,i)[1]<>{} then lu:=lu union Efo1(P,i): fi: od: lu: end: #Yels(P): given a puzzle P, finds its descendants. Try: #Yels(P2()); Yels:=proc(P) local M,i1,j1,lu,lu1,c,k,M1,katan,gu,kv,mu,i: M:=P[1]: gu:=P[2]: if not member(0,convert(ListTools[Flatten](M),set)) then print(`Puzzle completed`): RETURN({M}): fi: lu:=Efo(P): katan:=min(seq(nops(lu1[2]),lu1 in lu)): if katan=1 then M1:=M: for lu1 in lu do if nops(lu1[2])=1 then k:=lu1[1]: c:=lu1[2][1]: i1:=c[1]: j1:=c[2]: M1:=[op(1..i1-1,M1),[op(1..j1-1,M1[i1]),k,op(j1+1..nops(M1[i1]),M1[i1])],op(i1+1..nops(M1),M1)]: fi: od: RETURN({[M1,gu]}): else for i from 1 to nops(lu) while nops(lu[i][2])>katan do od: k:=lu[i][1]: mu:=lu[i][2]: kv:={}: for c in mu do i1:=c[1]: j1:=c[2]: M1:=[op(1..i1-1,M),[op(1..j1-1,M[i1]),k,op(j1+1..nops(M[i1]),M[i1])],op(i1+1..nops(M),M)]: kv:=kv union {[M1,gu]}: od: RETURN(kv): fi: end: #Yels1(P): given a puzzle P, finds its descendants. Try: #Yels1(P2()); Yels1:=proc(P) local M,i1,j1,lu,lu1,c,k,M1,katan,gu,kv,mu,i: M:=P[1]: gu:=P[2]: if not member(0,convert(ListTools[Flatten](M),set)) then RETURN({P}): fi: lu:=Efo(P): katan:=min(seq(nops(lu1[2]),lu1 in lu)): if katan=1 then M1:=M: for lu1 in lu do if nops(lu1[2])=1 then k:=lu1[1]: c:=lu1[2][1]: i1:=c[1]: j1:=c[2]: M1:=[op(1..i1-1,M1),[op(1..j1-1,M1[i1]),k,op(j1+1..nops(M1[i1]),M1[i1])],op(i1+1..nops(M1),M1)]: fi: od: RETURN({[M1,gu]}): else for i from 1 to nops(lu) while nops(lu[i][2])>katan do od: k:=lu[i][1]: mu:=lu[i][2]: kv:={}: for c in mu do i1:=c[1]: j1:=c[2]: M1:=[op(1..i1-1,M),[op(1..j1-1,M[i1]),k,op(j1+1..nops(M[i1]),M[i1])],op(i1+1..nops(M),M)]: kv:=kv union {[M1,gu]}: od: RETURN(kv): fi: end: #SOLall(P): All the solutions of the puzzle. Try #SOLall(P1()); #SOLall(P2()); #SOLall(P3()); #SOLall(P4()); SOLall:=proc(P) local Gu,Gu1,Gu2,p: Gu:={P}: Gu1:={seq(op(Yels1(p)),p in Gu)}: while Gu<>Gu1 do Gu2:={seq(op(Yels1(p)),p in Gu1)}: Gu:=Gu1: Gu1:=Gu2: od: Gu1: end: #Del(P,c): inputs a puzzle P and a cell c, creates another puzzle with the cell replaced by 0. Try #Del(P2(),[1,3]); Del:=proc(P,c) local M,gu,m,n,M1,i,j: M:=P[1]: gu:=P[2]: m:=nops(M): n:=nops(M[1]): i:=c[1]: j:=c[2]: if M[i][j]=0 then RETURN(FAIL): fi: M1:=[op(1..i-1,M),[op(1..j-1,M[i]),0,op(j+1..n,M[i])],op(i+1..m,M)]: [M1,gu]: end: #Add1(P,c,k): inputs a puzzle P and a cell c, creates another puzzle with the cell,c, currently 0 replaced by i. Try #Add1(P2(),[1,1],1); Add1:=proc(P,c,k) local M,gu,m,n,M1,i,j: M:=P[1]: gu:=P[2]: m:=nops(M): n:=nops(M[1]): i:=c[1]: j:=c[2]: if M[i][j]<>0 then RETURN(FAIL): fi: M1:=[op(1..i-1,M),[op(1..j-1,M[i]),k,op(j+1..n,M[i])],op(i+1..m,M)]: [M1,gu]: end: #NicePar(m,n,a,b): partitions the m by n grid into a by b rectangles. Try #NicePar(6,6,2,2); NicePar:=proc(m,n,a,b) local i,j,gu,i0,j0,ku,i1,j1: gu:=[]: for i from 1 to trunc(m/a) do for j from 1 to trunc(n/b) do i0:=1+(i-1)*a: j0:=1+(j-1)*b: ku:={seq(seq([i0+i1,j0+j1],j1=0..b-1),i1=0..a-1)}: gu:=[op(gu),ku]: od: od: gu: end: #SOL(P): The one and only solutions of the puzzle Capsule puzzle P SOL:=proc(P) local gu,i: gu:=SOLall(P): if gu={} then print(`There are no solutions. `): RETURN(FAIL): fi: if nops(gu)>1 then print(`There are`, nops(gu), `solutions, here they are`): for i from 1 to nops(gu) do print(matrix(gu[i][1])): od: fi: matrix(gu[1][1]): end: #SOLv(P): A verbose version of SOL(P) SOLv:=proc(P) local gu,i: print(`You have a 7 by 7 rectangle with the following clues`): print(``): print(matrix(P[1])): print(``): print(`There are `, nops(P[2]), `capsules , here they are `): print(``): print(`We now list the capsules, where the cells are indicated by pairs [i,j], where [i,j] means the the cell that is in the i-th row and`): print(`j-th column, as in matrix notation (reading from left to right and top to bottom`): print(``): for i from 1 to nops(P[2]) do print(`The `, i, `-th capsule consists of the cells `): print(``): print(P[2][i]): print(``): od: gu:=SOLall(P): if gu={} then print(`There are no solutions`): elif nops(gu)>1 then print(`There are more than one solution`): else print(`The solutions is`): print(``): print(matrix(gu[1][1])): print(``): fi: end: