##################################################################### ##SixySudoku.txt: Save this file as SixySudoku.txt # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read SixySudoku.txt # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #DoronZeil at gmail dot com # ###################################################################### #Created: Oct. 2019 #print(`Created: Oct. 2019`): #print(` This is SixySudoku.txt `): #print(`It is a Maple package to create and solve SixySudoku puzzles and their generalized versions `): #print(``): #print(`Please report bugs to DoronZeil at gmail dot com `): #print(``): # print(`The most current version of this package and paper`): # print(` are available from`): # print(`http://sites.math.rutgers.edu/~zeilberg/ .`): #print(`---------------------------------------`): # print(`For a list of the new approach type ezraNew();, for help with`): # print(`a specific procedure, type ezra(procedure_name); .`): # print(``): #print(`---------------------------------------`): #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): with(plots): with(plottools): ezraNew:=proc() if args=NULL then print(` The new approach (that is slower!) procedures are: FillIn, IsLegal, IsLegal1, KamaN, PtorNP, SolveNP, Yels, Yels1 `): print(``): else ezra(args): fi: end: ezra1:=proc() if args=NULL then print(` The supporting procedures are: CheckP, DRegs, Ex32a, Ex32b,Ex33a,Ex33b,Ex33c Kids, Kids1, Reg32a, StA, StA1, StickIn, WhichRegs `): print(``): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: DrawPu, MakePuz, PtorP, SolveP `): print(` `): elif nops([args])=1 and op(1,[args])=CheckP then print(`CheckP(P): Inputs an (a,b) Sixy Soduku puzzle P=[a,b,Regs,Da] with additional regions Regs, and the initial matrix, Da, finds its solution(s). Try:`): print(`CheckP(Ex32a());`): print(`CheckP(Ex32b());`): elif nops([args])=1 and op(1,[args])=DrawPu then print(`DrawPu(P,Pols):Draws the puzzle P, with polygons Pols. Try:`): print(`DrawPu(Ex32a(),Reg32a());`): elif nops([args])=1 and op(1,[args])=DRegs then print(`DRegs(a,b): The default regions for an (a,b) a*b-duku, like the Sixy Suduku.`): print(`i.e. the rows columns, and the a*b b by a rectangles. For the usual (New York Times magazine kind), Try:`): print(`DRegs(3,2);`): print(``): elif nops([args])=1 and op(1,[args])=Ex32a then print(`Ex32a(): the Oct. 6, 2019 Problem`): elif nops([args])=1 and op(1,[args])=Ex32b then print(`Ex32b(): the Oct. 13, 2019 Problem`): elif nops([args])=1 and op(1,[args])=Ex32c then print(`Ex32c(): the Oct. 20, 2019 eProblem`): elif nops([args])=1 and op(1,[args])=Ex32ce then print(`Ex32ce(): the Oct. 20, 2019 example`): elif nops([args])=1 and op(1,[args])=Ex33a then print(`Ex33a(): a sample usual (3,3) Sudoku puzzle`): elif nops([args])=1 and op(1,[args])=Ex33b then print(`Ex33b(): a sample usual (3,3) Sudoku puzzle`): elif nops([args])=1 and op(1,[args])=Ex33c then print(`Ex33c(): a sample usual (3,3) Sudoku puzzle`): elif nops([args])=1 and op(1,[args])=FillIn then print(`FillIn(a,b,R,M): Given a region R in an (a,b) puzzle with partially filled puzzle M`): print(`finds all the ways if filling the blanks try:`): print(`FillIn(3,2,DRegs(3,2)[1],Ex32a()[4]);`): elif nops([args])=1 and op(1,[args])=IsLegal then print(`IsLegal(Regs,M), is M legal for all the regions in Regs. Try: `): print(`IsLegal(Ex32a()[3] union DRegs(3,2),Ex32a()[4]);`): elif nops([args])=1 and op(1,[args])=IsLegal1 then print(`IsLegal1(R,M), is M legal with region R? Try`): print(`IsLegal1({[1,1],[1,2]},[[1,1],[2,1]]);`): elif nops([args])=1 and op(1,[args])=KamaN then print(`KamaN(R,M): Given a region R, and a partially filled (a,b) puzzle finds how many 0's (blanks). Try:`): print(`KamaN(Ex32a()[3][1],Ex32a()[4] ); `): elif nops([args])=1 and op(1,[args])=Kids then print(`Kids(a,b,Regs,SM): Given a set of partially filled (a,b,Regs)-generalized Suduku puzzles, SM, finds all its children from the "weakest link". Try:`): print(`Kids(3,2,Ex32a()[3] union DRegs(3,2), {Ex32a()[4]} ); `): elif nops([args])=1 and op(1,[args])=Kids1 then print(`Kids1(a,b,Regs,M): Given a partially filled (a,b,Regs)-generalized Suduku puzzle, M, finds all its children from the "weakest link". Try:`): print(`Kids1(3,2,Ex32a()[3] union DRegs(3,2), Ex32a()[4] );`): print(`Kids1(3,2,Ex32b()[3] union DRegs(3,2), Ex32b()[4] );`): elif nops([args])=1 and op(1,[args])=MakePuz then print(`MakePuz(a,b,Regs,K): Makes a random (a,b)-puzzle with the given extra regions. Try: `): print(`MakePuz(3,2,Ex32a()[3],100);`); elif nops([args])=1 and op(1,[args])=PtorNP then print(`PtorNP(a,b,Regs,Da): Inputs an (a,b) Sixy Soduku puzzle with additional regions Regs, and data Da, findsthe set its solution(s). `): print(`It may be empty or has more than one element. Uses the New approach.`): print(`For example, to solve the Sixy Suduku puzzle of the New York Times magazine for Oct. 6, 2019, type:`): print(`PtorNP(Ex32a()); `): print(`PtorNP(Ex32b()); `): elif nops([args])=1 and op(1,[args])=PtorP then print(`PtorP(P): Inputs an (a,b) Sixy Soduku puzzle P=[a,b,Regs,Da], with additional regions Regs, and data Da, findsthe set its solution(s). `): print(`It may be empty or has more than one element`): print(`For example, to solve the Sixy Suduku puzzle of the New York Times magazine for Oct. 6, 2019, type:`): print(`PtorP(Ex32a()); `): print(`PtorP(Ex32b()); `): elif nops([args])=1 and op(1,[args])=Reg32a then print(`Reg32a(): The regions and the bounding polygons for Ex32a(). `): print(` Try:`): print(`Reg32a();`): elif nops([args])=1 and op(1,[args])=SolveP then print(`SolveP(P): Inputs an (a,b) Sixy Soduku puzzle P=[a,b,Regs,Da], with additional regions Regs, and data Da, findsthe set its solution(s). `): print(`otherwise it returns FAIL`): print(`For example, to solve the Sixy Suduku puzzle of the New York Times magazine for Oct. 6, 2019, type:`): print(`SolveP(Ex32a()); `): print(`For example, to solve the Sixy Suduku puzzle of the New York Times magazine for Oct. 13, 2019, type:`): print(`SolveP(Ex32b()); `): print(`For example, to solve the Sixy Suduku puzzle of the New York Times magazine for Oct. 20, 2019, type:`): print(`SolveP(Ex32c()); `): print(`For example, to solve the Sixy Suduku puzzle given as a sample, type:`): print(`SolveP(Ex32ce()); `): print(`For example, to solve another Sixy Suduku puzzle given as a sample, type:`): print(`SolveP(Ex32d()); `): print(`For example, to solve the usual kind, 9 by 9, Suduku puzzles, taken from somewher, type:`): print(`SolveP(Ex33a()); `): print(`SolveP(Ex33b()); `): print(`SolveP(Ex33c()); `): print(`To solve the usual Sudoku puzzle given in Yedioth Akharonot, Nov. 1, 2019, labelled "difficult", type`): print(`SolveP(Ex33d()); `): elif nops([args])=1 and op(1,[args])=SolveNP then print(`SolveNP(a,b,Regs,Da): Like SolveP(a,b,Regs,Da) but using the new approach. Try:`): print(`SolveNP(Ex32a()); `): print(`SolveNP(Ex32b()); `): print(`SolveNP(Ex3()); `): print(`SolveNP(Ex33b()); `): print(`SolveNP(Ex33c()); `): elif nops([args])=1 and op(1,[args])=StA then print(`StA(a,b,Regs,M,v): given a puzzle (a,b,M,Regs) and a location v for which M[v]=0 outputs the`): print(`set of possible values it can take. Try:`): print(`StA(3,2,,Ex32a()[3] union DRegs(3,2), Ex32a()[4],[1,1]);`): elif nops([args])=1 and op(1,[args])=StA1 then print(`StA1(a,b,M,R): Inputs a partially filled matrix of an (a,b)-Suduko puzzle, and a region R, outputs the set of still available integers`): print(`that the unoccupied members of R can take. Try:`): print(`StA1(3,2,[[0,4,2,0,0,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,a,0,0,0],[0,0,0,0,0,0],[0,0,0,5,0,0]],{[1,1],[1,2],[1,3],[1,4],[1,5],[1,6]});`): elif nops([args])=1 and op(1,[args])=StickIn then print(`StickIn(M,v,a): Given a matrix M and a location v currently with 0, sticks in a in location v. Try: `): print(`StickIn([[1,0],[2,0]],[1,2],3);`): elif nops([args])=1 and op(1,[args])=WhichRegs then print(`WhichRegs(v,Regs): Given a location v, and a set of regions Regs, outputs the subset of Regs that contain v. Try:`): print(`Regs:={{[1,1],[1,2],[1,3],[2,1],[3,1],[4,1]},`): print(`{[1,4],[1,5],[1,6],[2,6],[3,6],[4,6]}, {[2,1],[2,3],[3,2],[4,2],[5,1],[5,2]},{[2,4],[2,5],[3,5],[4,5],[5,5],[5,6]},`): print(`{[3,3],[4,3],[5,3],[6,1],[6,2],[6,3]},{[3,4],[4,4],[5,4],[6,4],[6,5],[6,6]}}:`): print(`Regs:=Regs union DRegs(3,2):`): print(`WhichRegs([1,1],Regs); `): elif nops([args])=1 and op(1,[args])=Yels then print(`Yels(a,b,Regs,SetM): input (a,b), the set of regions and a set of partially-filled puzzles M, outputs`): print(`all their legal "chidren". Try:`): print(`Yels(3,2,Ex32a()[3] union DRegs(3,2),{Ex32a()[4]});`): elif nops([args])=1 and op(1,[args])=Yels1 then print(`Yels1(a,b,Regs,M): input (a,b), the set of regions and a partially-filled puzzle M, outputs`): print(`all the legal "chidren" by picking a region that has fewest blank cells. Try:`): print(`Yels1(3,2,Ex32a()[3] union DRegs(3,2),Ex32a()[4]);`): else print(`There is no ezra for`,args): fi: end: #UnitRec(a,b): The a by b unit rectangle; Try: #UnitRec(3,2) UnitRec:=proc(a,b) local i,j: {seq(seq([i,j],j=1..a),i=1..b)}: end: #TranS(S,v0): inputs a set of locations S, and a pair v0, adds to them v0. #Try #TransS(UnitRec(3,2),[1,4]); TranS:=proc(S,v0) local s: {seq(s+v0, s in S)}: end: #DRegs(a,b): The default regions for an (a,b) a*b-duku, like the sixy suduku. #i.e. the rows columns, and the a*b b by a rectangles. Try: #DRegs(3,2); DRegs:=proc(a,b) local i,j,i1,j1: {seq({seq([i,j],j=1..a*b)},i=1..a*b),seq({seq([i,j],i=1..a*b)},j=1..a*b)} union{seq(seq(TranS(UnitRec(a,b),[b*i1,a*j1]),i1=0..a-1),j1=0..b-1)}; end: #CheckP([a,b,Regs,Da]): Inputs an (a,b) Sixy Soduku puzzle with additional regions Regs, and data Da, checks that it is OK. Try: #CheckP(3,2, #{{[1,1],[1,2],[1,3],[2,1],[3,1],[4,1]}, #{[1,4],[1,5],[1,6],[2,6],[3,6],[4,6]}, #{[2,1],[2,3],[3,2],[4,2],[5,1],[5,2]}, #{[2,4],[2,5],[3,5],[4,5],[5,5],[5,6]}, #{[3,3],[4,3],[5,3],[6,1],[6,2],[6,3]}, #{[3,4],[4,4],[5,4],[6,4],[6,5],[6,6]}}, #[[0,4,2,0,0,0],[0,0,0,0,1,0],,[0,0,0,0,0,0],[0,0,6,0,0,0],[0,0,0,0,0,0],[0,0,0,5,0,0]]); CheckP:=proc(P) local a,b,Regs,Da, i,j,S,U: if not (type(P,list) and nops(P)=4) then print(`Bad input`): RETURN(FAIL): fi: a:=P[1]: b:=P[2]: Regs:=P[3]: Da:=P[4]: U:={seq(seq([i,j],i=1..a*b),j=1..a*b)}: if not type(Regs,set) then print(Regs, `is not a set `): RETURN(false): fi: for S in Regs do if not type(S,set) then print(S, `is not a set `): RETURN(false): fi: if nops(S)<>a*b then print(S, `does not have`, a*b, `elements `): RETURN(false): fi: if S minus U<>{} then print(S, `has elements that are not in the puzzle, namely`, S minus U): RETURN(false): fi: od: for i from 1 to nops(Regs) do for j from i+1 to nops(Regs) do if Regs[i] intersect Regs[j]<>{} then print(Regs[i], `has common elements with`, Regs[j]): RETURN(false): fi: od: od: if not type(Da,list) then print(Da, `should be a list`): RETURN(false): fi: if nops(Da)<>a*b then print(Da, `should be a list of length`, a*b): RETURN(false): fi: for i from 1 to nops(Da) do if not type(Da[i],list) then print(Da[i], `should be a list`): RETURN(false): fi: od: if {seq(op(Da[i]),i=1..a*b)} minus {0,seq(i,i=1..a*b)}<>{} then print(`The entries of`, Da ,`should be a subset of`, {0,seq(i=1..a*b)}): RETURN(false): fi: true: end: Ex32a:=proc(): [3,2, {{[1,1],[1,2],[1,3],[2,1],[3,1],[4,1]}, {[1,4],[1,5],[1,6],[2,6],[3,6],[4,6]}, {[2,2],[2,3],[3,2],[4,2],[5,1],[5,2]}, {[2,4],[2,5],[3,5],[4,5],[5,5],[5,6]}, {[3,3],[4,3],[5,3],[6,1],[6,2],[6,3]}, {[3,4],[4,4],[5,4],[6,4],[6,5],[6,6]}} , [[0,4,2,0,0,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,6,0,0,0],[0,0,0,0,0,0],[0,0,0,5,0,0]]]: end: Ex32b:=proc(): [3,2, {{[1,1],[1,2],[1,3],[2,1],[2,2],[3,2]}, {[1,4],[1,5],[1,6],[2,5],[2,6],[3,5]}, {[2,3],[2,4],[3,3],[3,4],[4,3],[4,4]}, {[3,1],[4,1],[4,2],[5,1],[5,2],[6,1]}, {[3,6],[4,5],[4,6],[5,5],[5,6],[6,6]}, {[5,3],[5,4],[6,2],[6,3],[6,4],[6,5]}}, [[0,5,0,0,0,0],[0,0,0,0,0,0],[0,0,4,2,0,0],[0,0,0,0,0,0],[0,0,0,0,3,0],[0,6,0,0,0,0]]] : end: Ex32c:=proc(): [3,2, {{[1,1],[1,2],[1,3],[2,1],[2,2],[3,1]}, {[1,4],[1,5],[1,6],[2,5],[2,6],[3,6]}, {[2,3],[3,2],[3,3],[4,2],[4,3],[5,3]}, {[2,4],[3,4],[3,5],[4,4],[4,5],[5,4]}, {[4,1],[5,1],[5,2],[6,1],[6,2],[6,3]}, {[4,6],[5,5],[5,6],[6,4],[6,5],[6,6]}}, [[2,0,0,1,0,0],[0,0,0,0,6,0],[0,2,0,0,0,0],[0,0,0,0,0,0],[0,5,0,0,0,4],[0,0,0,0,0,0]] ]: end: Ex32ce:=proc(): [3,2, {{[1,1],[1,2],[1,3],[2,1],[2,2],[3,1]}, {[1,4],[1,5],[1,6],[2,5],[2,6],[3,6]}, {[2,3],[3,2],[3,3],[4,2],[4,3],[5,3]}, {[2,4],[3,4],[3,5],[4,4],[4,5],[5,4]}, {[4,1],[5,1],[5,2],[6,1],[6,2],[6,3]}, {[4,6],[5,5],[5,6],[6,4],[6,5],[6,6]}}, [[0,0,0,2,0,0],[0,0,0,0,0,0],[0,0,0,1,0,0],[0,6,0,0,0,0],[0,0,0,5,4,0],[3,0,0,0,0,0]]] : end: Ex33a:=proc(): [3,3,{}, [[0,6,0,7,0,2,0,3,0],[0,8,0,0,0,0,0,5,0],[2,0,3,0,0,0,6,0,7], [0,0,8,6,0,3,7,0,0],[0,2,0,0,0,0,0,1,0],[0,0,6,4,0,9,5,0,0], [1,0,2,0,0,0,4,0,5],[0,5,0,0,0,0,0,8,0],[0,4,0,5,0,7,0,6,0]]]: end: Ex33b:=proc(): [3,3,{}, [[0,4,7,0,0,1,0,0,2],[5,0,0,0,0,0,4,0,0],[9,0,0,0,4,0,0,1,5], [0,3,0,0,5,2,0,0,0],[0,0,0,7,0,4,0,0,0],[0,0,0,1,8,0,0,9,0], [2,7,0,0,6,0,0,0,1],[0,0,1,0,0,0,0,0,4],[3,0,0,2,0,0,5,7,0]]]: end: Ex33c:=proc(): [3,3,{}, [[6,0,3,0,0,0,2,0,4],[0,0,0,9,0,2,0,0,0],[0,1,0,0,0,0,0,6,0], [0,0,1,6,8,9,7,0,0],[0$9],[0,0,6,2,4,7,5,0,0], [0,9,0,0,0,0,0,5,0],[0,0,0,5,0,8,0,0,0],[5,0,4,0,0,0,6,0,1]]]: end: Ex33d:=proc(): [3,3,{}, [[0,2,0,0,0,5,9,0,0], [1,0,6,9,0,0,0,8,0], [0,8,0,0,0,0,0,0,4], [0,5,0,2,0,0,6,0,1], [0,0,0,0,0,0,7,0,0], [6,0,7,0,0,9,0,5,0], [3,0,0,0,0,0,0,1,0], [0,7,0,0,0,3,5,9,6], [0,0,8,6,0,0,0,2,0]]]: end: #StA1(a,b,M,R): Inputs a partially filled matrix of an (a,b)-Suduko puzzle, and a region R, outputs the set of still available integers #that the unoccupied members of R can take. Try: #StA1(3,2,[[0,4,2,0,0,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,6,0,0,0],[0,0,0,0,0,0],[0,0,0,5,0,0]],{[1,1],[1,2],[1,3],[1,4],[1,5],[1,6]}); StA1:=proc(a,b,M,R) local gu,v,i: gu:={}; for v in R do if M[v[1]][v[2]]<>0 then gu:=gu union {M[v[1]][v[2]]}: fi: od: {seq(i,i=1..a*b)} minus gu: end: #StA1(a,b,M,R): Inputs a partially filled matrix of an (a,b)-Suduko puzzle, and a region R, outputs the set of still available integers #that the unoccupied members of R can take. Try: #StA1(3,2,[[0,4,2,0,0,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,6,0,0,0],[0,0,0,0,0,0],[0,0,0,5,0,0]],{[1,1],[1,2],[1,3],[1,4],[1,5],[1,6]}); StA1:=proc(a,b,M,R) local gu,v,i: gu:={}; for v in R do if M[v[1]][v[2]]<>0 then gu:=gu union {M[v[1]][v[2]]}: fi: od: {seq(i,i=1..a*b)} minus gu: end: #StA1(a,b,M,R): Inputs a partially filled matrix of an (a,b)-Suduko puzzle, and a region R, outputs the set of still available integers #that the unoccupied members of R can take. Try: #StA1(3,2,[[0,4,2,0,0,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,6,0,0,0],[0,0,0,0,0,0],[0,0,0,5,0,0]],{[1,1],[1,2],[1,3],[1,4],[1,5],[1,6]}); StA1:=proc(a,b,M,R) local gu,v,i: gu:={}; for v in R do if M[v[1]][v[2]]<>0 then gu:=gu union {M[v[1]][v[2]]}: fi: od: {seq(i,i=1..a*b)} minus gu: end: #WhichRegs(v,Regs): Given a location v, and a set of regions Regs, outputs the subset of Regs that contain v. Try: #Regs:={{[1,1],[1,2],[1,3],[2,1],[3,1],[4,1]}, #{[1,4],[1,5],[1,6],[2,6],[3,6],[4,6]}, #{[2,1],[2,3],[3,2],[4,2],[5,1],[5,2]}, #{[2,4],[2,5],[3,5],[4,5],[5,5],[5,6]}, #{[3,3],[4,3],[5,3],[6,1],[6,2],[6,3]}, #{[3,4],[4,4],[5,4],[6,4],[6,5],[6,6]}}: #Regs:=Regs union DRegs(3,2): #WhichRegs([1,1],Regs): WhichRegs:=proc(v,Regs) local gu,R: gu:={}; for R in Regs do if member(v,R) then gu:=gu union {R}: fi: od: gu: end: #StA(a,b,Regs,M,v): given a puzzle (a,b,M,Regs) and a location v for which M[v]=0 outputs the #set of possible values it can take. Try: #StA(Ex32a()[1],Ex32a()[2],Ex32a()[3] union DRegs(3,2), Ex32a()[4],[1,1]); StA:=proc(a,b,Regs,M,v) local gu,mu,i: if M[v[1]][v[2]]<>0 then RETURN(FAIL): fi: gu:=WhichRegs(v,Regs): gu:=convert(gu,list): if gu=[] then RETURN(FAIL): fi: mu:=StA1(a,b,M,gu[1]): for i from 2 to nops(gu) do mu:=mu intersect StA1(a,b,M,gu[i]): od: mu: end: #StickIn(M,v,a): Given a matrix M and a location v currently with 0, sticks in a in location v. Try #StickIn([[1,0],[2,0]],[1,2],3); StickIn:=proc(M,v,a) local A,B: if M[v[1]][v[2]]<>0 then RETURN(FAIL): fi: A:=v[1]: B:=v[2]: [ op(1..A-1,M), [op(1..B-1, M[A]), a, op(B+1..nops(M[A]),M[A]) ], op(A+1..nops(M),M) ]: end: #StickInZero(M,v): Given a matrix M and a location v currently with 0, sticks in a in location v. Try #StickInZero([[1,0],[2,0]],[1,2]); StickInZero:=proc(M,v) local A,B: if M[v[1]][v[2]]=0 then RETURN(FAIL): fi: A:=v[1]: B:=v[2]: [ op(1..A-1,M), [op(1..B-1, M[A]), 0, op(B+1..nops(M[A]),M[A]) ], op(A+1..nops(M),M) ]: end: #Kids1(a,b,Regs,M): Given a partially filled (a,b,Regs)-generalized Suduku puzzle, M, finds all its children from the "weakest link". Try: #Kids1(3,2,Ex32a()[3] union DRegs(a,b), Ex32a()[4] ): Kids1:=proc(a,b,Regs,M) local i1,j1,gu,aluf,si,hale,gu1: if not member(0,{seq(seq(M[i1][j1],i1=1..a*b),j1=1..a*b)}) then RETURN({M}): fi: si:=a*b: for i1 from 1 to a*b do for j1 from 1 to a*b do if M[i1][j1]=0 then hale:=nops(StA(a,b,Regs,M,[i1,j1])): if hale{} and gu1<>gu2 do gu3:=Kids(a,b,Regs1,gu2): gu1:=gu2: gu2:=gu3: od: gu2: end: SolveP:=proc(P) local gu,gu1: gu:=PtorP(P): if gu={} then print(`No solutions!`): RETURN(FAIL): fi: if nops(gu)>1 then print(nops(gu), `solutions , here there are `): for gu1 in gu do print(matrix(gu1)): od: RETURN(FAIL): fi: matrix(gu[1]): end: SolveP1:=proc(P) local gu,gu1: gu:=PtorP(P): if gu={} then print(`No solutions!`): RETURN(FAIL): fi: if nops(gu)>1 then print(nops(gu), `solutions , here there are `): for gu1 in gu do print(matrix(gu1)): od: RETURN(FAIL): fi: [op(1..3,P),gu[1]]: end: #KamaN(R,M): Given a region R, and a partially filled (a,b) puzzle finds how many 0's (i.e. blank) they have try: KamaN:=proc(R,M) local co,v: co:=0: for v in R do if M[v[1]][v[2]]=0 then co:=co+1: fi: od: co: end: #IsLegal1(R,M), is M legal with region R? Try #IsLegal1({[1,1],[1,2]},[[1,1],[2,1]]); IsLegal1:=proc(R,M) local v,gu: gu:=[]: for v in R do if M[v[1]][v[2]]<>0 then gu:=[op(gu),M[v[1]][v[2]]]: fi: od: if nops(gu)=nops({op(gu)}) then true: else false: fi: end: #IsLegal(Regs,M), is M legal for all the regions in Regs. Try IsLegal:=proc(Regs,M) local R: for R in Regs do if not IsLegal1(R,M) then RETURN(false): fi: od: true: end: #FillIn(a,b,R,M): Given a region R in an (a,b) puzzle with partially filled puzzle M #finds all the ways if filling the blanks try: FillIn:=proc(a,b,R,M) local gu,mu,v,i,ku,M1,ku1,lu,i1: mu:=[]: gu:={}: for v in R do if M[v[1]][v[2]]=0 then mu:=[op(mu),v]: else gu:=gu union {M[v[1]][v[2]]}: fi: od: gu:={seq(i,i=1..a*b)} minus gu: ku:=permute(gu): lu:={}: for ku1 in ku do M1:=M: for i1 from 1 to nops(mu) do M1:=StickIn(M1,mu[i1],ku1[i1]): od: lu:=lu union {M1}: od: lu: end: #Yels1(a,b,Regs,M): input (a,b), the set of regions and a partially-filled puzzle M, outputs #all the legal "chidren" by picking a region that has fewest blank cells. Try: Yels1:=proc(a,b,Regs,M) local i1,j1, R,aluf,si,hal,gu,gu1,mu: si:=a*b: if not member(0,{seq(seq(M[i1][j1],i1=1..a*b),j1=1..a*b)}) then RETURN({M}): fi: for R in Regs do hal:=KamaN(R,M): if hal<>0 and hal{} and gu1<>gu2 do gu3:=Yels(a,b,Regs1,gu2): gu1:=gu2: gu2:=gu3: od: gu2: end: SolveNP:=proc(a,b,Regs,Da) local gu,gu1: gu:=PtorNP(a,b,Regs,Da): if gu={} then print(`No solutions!`): RETURN(FAIL): fi: if nops(gu)>1 then print(nops(gu), `solutions , here there are `): for gu1 in gu do print(matrix(gu1)): od: RETURN(FAIL): fi: matrix(gu[1]): end: #Reg32a(): A data base for Regions for (3,2)-Sixy Sudoku puzzles. It is a list of pairs. #Each entry is a set of pairs [Region,Bounding polygon]. Try: #Reg32a(); Reg32a:=proc(): [ [{[1,1],[1,2],[1,3],[2,1],[3,1],[4,1]}, [[0,6],[3,6],[3,5],[1,5],[1,2],[0,2],[0,6]] ], [{[1,4],[1,5],[1,6],[2,6],[3,6],[4,6]}, [[3,6],[6,6],[6,2],[5,2],[5,5],[3,5],[3,6]] ], [{[2,2],[2,3],[3,2],[4,2],[5,1],[5,2]}, [[0,1],[2,1],[2,4],[3,4],[3,5],[1,5],[1,2],[0,2],[0,1]] ], [{[2,4],[2,5],[3,5],[4,5],[5,5],[5,6]}, [[3,5],[5,5],[5,2],[6,2],[6,1],[4,1],[4,4],[3,4],[3,5]] ], [{[3,3],[4,3],[5,3],[6,1],[6,2],[6,3]}, [[2,4],[3,4],[3,0],[0,0],[0,1],[2,1],[2,4]] ], [{[3,4],[4,4],[5,4],[6,4],[6,5],[6,6]}, [[3,0],[6,0],[6,1],[4,1],[4,4],[3,4],[3,0]] ] ]: end: #Reg32b(): A data base for Regions for (3,2)-Sixy Sudoku puzzles. It is a list of pairs. #Each entry is a set of pairs [Region,Bounding polygon]. Try: #Reg32b(); Reg32b:=proc(): [ [{[1,1],[1,2],[1,3],[2,1],[2,2],[3,2]}, [[0,6],[3,6],[3,5],[2,5],[2,3],[1,3],[1,4],[0,4],[0,6]] ], [{[1,4],[1,5],[1,6],[2,5],[2,6],[3,5]},[[3,6],[6,6],[6,4],[5,4],[5,3],[4,3],[4,5],[3,5],[3,6]] ], [{[2,3],[2,4],[3,3],[3,4],[4,3],[4,4]},[[2,5],[4,5],[4,2],[2,2],[2,5]] ], [{[3,1],[4,1],[4,2],[5,1],[5,2],[6,1]},[[0,4],[1,4],[1,3],[2,3],[2,1],[1,1],[1,0],[0,0],[0,4]] ], [{[3,6],[4,5],[4,6],[5,4],[5,6],[6,6]}, [[4,3],[5,3],[5,4],[6,4],[6,0],[5,0],[5,1],[4,1],[4,3]] ], [{[5,3],[5,4],[6,2],[6,3],[6,4],[6,5]},[[2,2],[4,2],[4,1],[5,1],[5,0],[1,0],[1,1],[2,1],[2,2]] ] ]: end: Ex32c:=proc(): [3,2, {{[1,1],[1,2],[1,3],[2,1],[2,2],[3,1]}, {[1,4],[1,5],[1,6],[2,5],[2,6],[3,6]}, {[2,3],[3,2],[3,3],[4,2],[4,3],[5,3]}, {[2,4],[3,4],[3,5],[4,4],[4,5],[5,4]}, {[4,1],[5,1],[5,2],[6,1],[6,2],[6,3]}, {[4,6],[5,5],[5,6],[6,4],[6,5],[6,6]}}, [[2,0,0,1,0,0],[0,0,0,0,6,0],[0,2,0,0,0,0],[0,0,0,0,0,0],[0,5,0,0,0,4],[0,0,0,0,0,0]] ]: end: Ex32ce:=proc(): [3,2, {{[1,1],[1,2],[1,3],[2,1],[2,2],[3,1]}, {[1,4],[1,5],[1,6],[2,5],[2,6],[3,6]}, {[2,3],[3,2],[3,3],[4,2],[4,3],[5,3]}, {[2,4],[3,4],[3,5],[4,4],[4,5],[5,4]}, {[4,1],[5,1],[5,2],[6,1],[6,2],[6,3]}, {[4,6],[5,5],[5,6],[6,4],[6,5],[6,6]}}, [[0,0,0,2,0,0],[0,0,0,0,0,0],[0,0,0,1,0,0],[0,6,0,0,0,0],[0,0,0,5,4,0],[3,0,0,0,0,0]]] : end: Ex33a:=proc(): [3,3,{}, [[0,6,0,7,0,2,0,3,0],[0,8,0,0,0,0,0,5,0],[2,0,3,0,0,0,6,0,7], [0,0,8,6,0,3,7,0,0],[0,2,0,0,0,0,0,1,0],[0,0,6,4,0,9,5,0,0], [1,0,2,0,0,0,4,0,5],[0,5,0,0,0,0,0,8,0],[0,4,0,5,0,7,0,6,0]]]: end: Ex33b:=proc(): [3,3,{}, [[0,4,7,0,0,1,0,0,2],[5,0,0,0,0,0,4,0,0],[9,0,0,0,4,0,0,1,5], [0,3,0,0,5,2,0,0,0],[0,0,0,7,0,4,0,0,0],[0,0,0,1,8,0,0,9,0], [2,7,0,0,6,0,0,0,1],[0,0,1,0,0,0,0,0,4],[3,0,0,2,0,0,5,7,0]]]: end: Ex33c:=proc(): [3,3,{}, [[6,0,3,0,0,0,2,0,4],[0,0,0,9,0,2,0,0,0],[0,1,0,0,0,0,0,6,0], [0,0,1,6,8,9,7,0,0],[0$9],[0,0,6,2,4,7,5,0,0], [0,9,0,0,0,0,0,5,0],[0,0,0,5,0,8,0,0,0],[5,0,4,0,0,0,6,0,1]]]: end: #StA1(a,b,M,R): Inputs a partially filled matrix of an (a,b)-Suduko puzzle, and a region R, outputs the set of still available integers #that the unoccupied members of R can take. Try: #StA1(3,2,[[0,4,2,0,0,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,6,0,0,0],[0,0,0,0,0,0],[0,0,0,5,0,0]],{[1,1],[1,2],[1,3],[1,4],[1,5],[1,6]}); StA1:=proc(a,b,M,R) local gu,v,i: gu:={}; for v in R do if M[v[1]][v[2]]<>0 then gu:=gu union {M[v[1]][v[2]]}: fi: od: {seq(i,i=1..a*b)} minus gu: end: #StA1(a,b,M,R): Inputs a partially filled matrix of an (a,b)-Suduko puzzle, and a region R, outputs the set of still available integers #that the unoccupied members of R can take. Try: #StA1(3,2,[[0,4,2,0,0,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,6,0,0,0],[0,0,0,0,0,0],[0,0,0,5,0,0]],{[1,1],[1,2],[1,3],[1,4],[1,5],[1,6]}); StA1:=proc(a,b,M,R) local gu,v,i: gu:={}; for v in R do if M[v[1]][v[2]]<>0 then gu:=gu union {M[v[1]][v[2]]}: fi: od: {seq(i,i=1..a*b)} minus gu: end: #StA1(a,b,M,R): Inputs a partially filled matrix of an (a,b)-Suduko puzzle, and a region R, outputs the set of still available integers #that the unoccupied members of R can take. Try: #StA1(3,2,[[0,4,2,0,0,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,6,0,0,0],[0,0,0,0,0,0],[0,0,0,5,0,0]],{[1,1],[1,2],[1,3],[1,4],[1,5],[1,6]}); StA1:=proc(a,b,M,R) local gu,v,i: gu:={}; for v in R do if M[v[1]][v[2]]<>0 then gu:=gu union {M[v[1]][v[2]]}: fi: od: {seq(i,i=1..a*b)} minus gu: end: #WhichRegs(v,Regs): Given a location v, and a set of regions Regs, outputs the subset of Regs that contain v. Try: #Regs:={{[1,1],[1,2],[1,3],[2,1],[3,1],[4,1]}, #{[1,4],[1,5],[1,6],[2,6],[3,6],[4,6]}, #{[2,1],[2,3],[3,2],[4,2],[5,1],[5,2]}, #{[2,4],[2,5],[3,5],[4,5],[5,5],[5,6]}, #{[3,3],[4,3],[5,3],[6,1],[6,2],[6,3]}, #{[3,4],[4,4],[5,4],[6,4],[6,5],[6,6]}}: #Regs:=Regs union DRegs(3,2): #WhichRegs([1,1],Regs): WhichRegs:=proc(v,Regs) local gu,R: gu:={}; for R in Regs do if member(v,R) then gu:=gu union {R}: fi: od: gu: end: #StA(a,b,Regs,M,v): given a puzzle (a,b,M,Regs) and a location v for which M[v]=0 outputs the #set of possible values it can take. Try: #StA(Ex32a()[1],Ex32a()[2],Ex32a()[3] union DRegs(3,2), Ex32a()[4],[1,1]); StA:=proc(a,b,Regs,M,v) local gu,mu,i: if M[v[1]][v[2]]<>0 then RETURN(FAIL): fi: gu:=WhichRegs(v,Regs): gu:=convert(gu,list): if gu=[] then RETURN(FAIL): fi: mu:=StA1(a,b,M,gu[1]): for i from 2 to nops(gu) do mu:=mu intersect StA1(a,b,M,gu[i]): od: mu: end: #StickIn(M,v,a): Given a matrix M and a location v currently with 0, sticks in a in location v. Try #StickIn([[1,0],[2,0]],[1,2],3); StickIn:=proc(M,v,a) local A,B: if M[v[1]][v[2]]<>0 then RETURN(FAIL): fi: A:=v[1]: B:=v[2]: [ op(1..A-1,M), [op(1..B-1, M[A]), a, op(B+1..nops(M[A]),M[A]) ], op(A+1..nops(M),M) ]: end: #StickInZero(M,v): Given a matrix M and a location v currently with 0, sticks in a in location v. Try #StickInZero([[1,0],[2,0]],[1,2]); StickInZero:=proc(M,v) local A,B: if M[v[1]][v[2]]=0 then RETURN(FAIL): fi: A:=v[1]: B:=v[2]: [ op(1..A-1,M), [op(1..B-1, M[A]), 0, op(B+1..nops(M[A]),M[A]) ], op(A+1..nops(M),M) ]: end: #Kids1(a,b,Regs,M): Given a partially filled (a,b,Regs)-generalized Suduku puzzle, M, finds all its children from the "weakest link". Try: #Kids1(3,2,Ex32a()[3] union DRegs(a,b), Ex32a()[4] ): Kids1:=proc(a,b,Regs,M) local i1,j1,gu,aluf,si,hale,gu1: if not member(0,{seq(seq(M[i1][j1],i1=1..a*b),j1=1..a*b)}) then RETURN({M}): fi: si:=a*b: for i1 from 1 to a*b do for j1 from 1 to a*b do if M[i1][j1]=0 then hale:=nops(StA(a,b,Regs,M,[i1,j1])): if hale{} and gu1<>gu2 do gu3:=Kids(a,b,Regs1,gu2): gu1:=gu2: gu2:=gu3: od: gu2: end: SolveP:=proc(P) local gu,gu1: gu:=PtorP(P): if gu={} then print(`No solutions!`): RETURN(FAIL): fi: if nops(gu)>1 then print(nops(gu), `solutions , here there are `): for gu1 in gu do print(matrix(gu1)): od: RETURN(FAIL): fi: matrix(gu[1]): end: SolveP1:=proc(P) local gu,gu1: gu:=PtorP(P): if gu={} then print(`No solutions!`): RETURN(FAIL): fi: if nops(gu)>1 then print(nops(gu), `solutions , here there are `): for gu1 in gu do print(matrix(gu1)): od: RETURN(FAIL): fi: [op(1..3,P),gu[1]]: end: #KamaN(R,M): Given a region R, and a partially filled (a,b) puzzle finds how many 0's (i.e. blank) they have try: KamaN:=proc(R,M) local co,v: co:=0: for v in R do if M[v[1]][v[2]]=0 then co:=co+1: fi: od: co: end: #IsLegal1(R,M), is M legal with region R? Try #IsLegal1({[1,1],[1,2]},[[1,1],[2,1]]); IsLegal1:=proc(R,M) local v,gu: gu:=[]: for v in R do if M[v[1]][v[2]]<>0 then gu:=[op(gu),M[v[1]][v[2]]]: fi: od: if nops(gu)=nops({op(gu)}) then true: else false: fi: end: #IsLegal(Regs,M), is M legal for all the regions in Regs. Try IsLegal:=proc(Regs,M) local R: for R in Regs do if not IsLegal1(R,M) then RETURN(false): fi: od: true: end: #FillIn(a,b,R,M): Given a region R in an (a,b) puzzle with partially filled puzzle M #finds all the ways if filling the blanks try: FillIn:=proc(a,b,R,M) local gu,mu,v,i,ku,M1,ku1,lu,i1: mu:=[]: gu:={}: for v in R do if M[v[1]][v[2]]=0 then mu:=[op(mu),v]: else gu:=gu union {M[v[1]][v[2]]}: fi: od: gu:={seq(i,i=1..a*b)} minus gu: ku:=permute(gu): lu:={}: for ku1 in ku do M1:=M: for i1 from 1 to nops(mu) do M1:=StickIn(M1,mu[i1],ku1[i1]): od: lu:=lu union {M1}: od: lu: end: #Yels1(a,b,Regs,M): input (a,b), the set of regions and a partially-filled puzzle M, outputs #all the legal "chidren" by picking a region that has fewest blank cells. Try: Yels1:=proc(a,b,Regs,M) local i1,j1, R,aluf,si,hal,gu,gu1,mu: si:=a*b: if not member(0,{seq(seq(M[i1][j1],i1=1..a*b),j1=1..a*b)}) then RETURN({M}): fi: for R in Regs do hal:=KamaN(R,M): if hal<>0 and hal{} and gu1<>gu2 do gu3:=Yels(a,b,Regs1,gu2): gu1:=gu2: gu2:=gu3: od: gu2: end: SolveNP:=proc(a,b,Regs,Da) local gu,gu1: gu:=PtorNP(a,b,Regs,Da): if gu={} then print(`No solutions!`): RETURN(FAIL): fi: if nops(gu)>1 then print(nops(gu), `solutions , here there are `): for gu1 in gu do print(matrix(gu1)): od: RETURN(FAIL): fi: matrix(gu[1]): end: with(plots): #DrawPu(P,Pols):Draws the puzzle P, with polygons Pols. Try: #DrawPu(Ex32a(),Reg32a()); DrawPu:=proc(P,Pols) local a,b,Regs,M,d,i,j,ka: if not CheckP(P) then RETURN(FAIL): fi: a:=P[1]: b:=P[2]: Regs:=P[3]: M:=P[4]: d:=plot([[0,0],[a*b,0]],axes=none,color=black,thickness=3, scaling=constrained): d:=d,plot([[0,a*b],[a*b,a*b]],axes=none,color=black,thickness=3, scaling=constrained): for i from 1 to a*b-1 do d:=d,plot([[0,i],[a*b,i]],color=black, axes=none): od: d:=d,plot([[0,0],[0,a*b]],thickness=3, color=black, axes=none): d:=d,plot([[a*b,0],[a*b,a*b]],thickness=3, color=black, axes=none): for j from 1 to a*b-1 do d:=d,plot([[j,0],[j,a*b]],color=black, axes=none): od: for i from 1 to nops(Pols) do d:=d,plot(Pols[i][2],axes=none,color=black,thickness=3, scaling=constrained): od: for i from 1 to a*b do for j from 1 to a*b do if M[i][j]<>0 then ka:=M[i][j]: d:=d,textplot([j-1/2,a*b-i+1/2,ka]): fi: od: od: for j from 0 by 2 to b-1 do for i from 1 by 2 to a-1 do d:=d,plots[display](polygon([[j*a,i*b], [a+j*a,i*b],[a+j*a,(i+1)*b], [j*a,(i+1)*b],[j*a,i*b]]),color=gray, axes=none): od: od: for j from 1 by 2 to b-1 do for i from 0 by 2 to a-1 do d:=d,plots[display](polygon([[j*a,i*b], [a+j*a,i*b],[a+j*a,(i+1)*b], [j*a,(i+1)*b],[j*a,i*b]]),color=gray, axes=none): od: od: display(d); end: #Shrink(P): Given a puzzle with a unique solution, deletes one of its entries so that it is still a puzzle with #a unique solutin. Try: #P:=SolveP1(Ex32a()); Shrink(P); Shrink:=proc(P) local i,j,P1: if nops(PtorP(P))<>1 then RETURN(FAIL): fi: for i from 1 to P[1]*P[2]do for j from 1 to P[1]*P[2] do if P[4][i][j]<>0 then P1:=[op(1..3,P),StickInZero(P[4],[i,j])]: if nops(PtorP(P1))=1 then RETURN(P1): fi: fi: od: od: FAIL: end: MakePuz:=proc(a,b,Regs) local P,P1,P2,gu: P:=[a,b,Regs,[randperm(a*b),[0$(a*b)]$(a*b-1) ]]: gu:=PtorP(P): P1:=gu[rand(1..nops(gu))()]: P1:=[op(1..3,P),P1]: P2:=Shrink(P1): while P2<>FAIL do P1:=P2: P2:=Shrink(P1): od: P1: end: #MakePuz1(S): starting with a solved puzzle, creates a random puzzle with unique solution. Try: #MakePuz1(SolveP1(Ex32a())): MakePuz1:=proc(S) local P1,P2: P1:=S: P2:=Shrink(P1): while P2<>FAIL do P1:=P2: P2:=Shrink(P1): od: P1: end: