####################################################################### ## SuDoku Save this file as Sudoku. To use it, stay in the # ## same directory, get into Maple (by typing: maple ) # ## and then type: read SuDoku: # ## Then follow the instructions given there # ## # ## Written by Doron Zeilberger, Rutgers University , # ## zeilberg@math.rutgers.edu. # ####################################################################### print(`First Written: July 20, 2005: tested for Maple 8 and 9 `): print(`Version of July 20, 2005 `): print(): print(`This is SoDoku A Maple package`): print(`to solve SuDoku problems or arbitrary size (n^2 by n^2) `): print(): print(`The most current version is available on WWW at:`): print(` http://www.math.rutgers.edu/~zeilberg .`): print(`Please report all bugs to: zeilberg at math dot rutgers dot edu .`): print(): print(`For general help, and a list of the available functions,`): print(` type "ezra();". For specific help type "ezra(procedure_name);" `): print(): ezra:=proc() if args=NULL then print(`SuDoku`): print(`A Maple package for solving SuDoku problems`): print(): print(`The main procedure is: Su`): print(`For help type: ezra(Su);`): print(): elif nargs=1 and args[1]=Su then print(`Su(S): Given a Sudoku problem in terms of a list (of size n^2) of lists`): print(` (of size n^2), where the blanks are denoted by 0, finds the set of all solutions`): print(`For example try: Su([[0$4]$4]);`): print(`There are 3 examples, taken from Su Doku for Dummies (by A. Heron and E. James)`): print(`Problems 5, 239, 240`): print(` called here S5, S239, S240 `): print(`For example, to see S240, type: S240;`): print(`and to slove it, type: Su(S240);`): fi: end: ez:=proc():print(` Sec1(i,j,n)`): print(` RCS(S,n), Options1(S,n,i,j) , Opt(S,n)`): print(`NoGoodnick(S,n)`): print(`Children(S,i,j,n), IsLeaf(S,n), FindPlace(S,n), Su(S)`): end: T1:=[[0]]: T2:=[[0,0,0,0]$4]: S5:=[[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]]: S239:=[[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]]: S240:=[[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]]: #Sec1(i,j,n): the section of cell i,j Sec1:=proc(i,j,n) n*trunc((i-1)/n)+trunc((j-1)/n)+1: end: RCS:=proc(S,n) local R,C,S1,i,j: option remember: for i from 1 to n^2 do R[i]:={}: S1[i]:={}: C[i]:={}: od: for i from 1 to n^2 do for j from 1 to n^2 do if S[i,j]<>0 then R[i]:=R[i] union {S[i,j]}: C[j]:=C[j] union {S[i,j]}: S1[Sec1(i,j,n)]:=S1[Sec1(i,j,n)]union {S[i,j]}: fi: od: od: [seq(R[i],i=1..n^2)],[seq(C[i],i=1..n^2)],[seq(S1[i],i=1..n^2)]: end: #Options1(S,n,i,j): the options for cell i,j Options1:=proc(S,n,i,j) local gu,i1: if S[i,j]<>0 then RETURN({S[i,j]}): fi: gu:=RCS(S,n): {seq(i1,i1=1..n^2)} minus (gu[1][i] union gu[2][j] union gu[3][Sec1(i,j,n)]): end: #Opt(S,n): the option matrix Opt:=proc(S,n) local i,j: [seq([seq(Options1(S,n,i,j),j=1..n^2)],i=1..n^2)]: end: NoGoodnick:=proc(S,n) local S1,i,j: S1:=Opt(S,n): evalb(member({},{seq(seq(S1[i][j],i=1..n^2),j=1..n^2)})): end: #IsLeaf(S,n): Is S a leaf? (i.e. is it a good solution?) IsLeaf:=proc(S,n) local i,j: not evalb(member(0,{seq(seq(S[i][j],j=1..n^2),i=1..n^2)})): end: #Children(S,L,n): all the children of S from cell (i,j) Children:=proc(S,L,n) local S1,lu,k,gu,gu1,i,j: option remember: if L=FAIL then RETURN({}): else i:=L[1]: j:=L[2]: fi: S1:=Opt(S,n): lu:=S1[i,j]: gu:={}: for k from 1 to nops(lu) do gu1:=[op(1..i-1,S),[op(1..j-1,S[i]),lu[k],op(j+1..nops(S[i]),S[i])], op(i+1..nops(S),S)]: if not NoGoodnick(gu1,n) then gu:= gu union {gu1}: fi: od: gu: end: #FindPlace(S,n): Finds a good place to breed FindPlace:=proc(S,n) local S1,i,j,m,Efes: S1:=Opt(S,n): Efes:={}: for i from 1 to n^2 do for j from 1 to n^2 do if S[i,j]=0 then Efes:=Efes union {[i,j]}: fi: od: od: m:=min(seq(nops(S1[Efes[i][1]][Efes[i][2]]),i=1..nops(Efes))): for i from 1 to n^2 do for j from 1 to n^2 do if S[i][j]=0 and nops(S1[i][j])=m then RETURN([i,j]): fi: od: od: end: Su:=proc(S) local gu,i,lu,n: option remember: n:=sqrt(nops(S)): if IsLeaf(S,n) then RETURN({S}) fi: lu:=FindPlace(S,n): gu:=Children(S,lu,n): {seq(op(Su(gu[i],n)),i=1..nops(gu))}: end: