As the first step in the decommissioning of sasCommunity.org the site has been converted to read-only mode.

Here are some tips for How to share your SAS knowledge with your professional network.

# Sudoku Solver Using Proc SQL

From sasCommunity

This SAS Program uses PROC SQL to model three simple strategies for solving Sudoku Puzzles. It will solve only some Sudoku puzzles. This is an example from the SAS Global Forum 2007 paper

- DeVenezia,Richard A.; John R. Gerlach; Larry Hoyle; Talbot M. Katz; Rick Langston; “SAS® And Sudoku” Orlando, Florida, SAS Global Forum 2007.

The ODS output of the puzzle was not described in the paper.

### SAS Code

/* NewHoyleSolveSudokuPlusGraphics.sas */ /* solves a Sudoku puzzle */ /* using SAS Proc SQL */ /* outputs a sequence of the puzzle at each step in the solution */ /* Larry Hoyle May 2006 */ /* edit the next line to point to the location of the output pdf file */ %let GraphFile=C:\junk\SudokuSteps.pdf; /* many graphic calculations are based on 1/9 as a percentage */ %let ninth=11.11111111111; %let thinLine=.3; %let fatLine=1; %let possibleSize=3; %let valueSize=7; /* goptions targetdevice=pdfc chartype=11; */ %macro PlotPuzzle; * LH 8a ; /* merge all info about the puzzle */ data PuzzleProperties; merge mySudoku MyNots; by row col; run; * LH 8b ; /* output a graphic of the current state */ /* row and column numbers range from 1 to 9 */ data PuzzleAnno; set puzzleProperties; array notValue{9} not1-not9; /* declare variables */ length function color $ 8 style $ 20 text $ 1; retain hsys xsys ysys '3'; keep x y function text size style color hsys xsys ysys ; if _n_=1 then do; put "STEP = &step"; /* create observations to draw the horizontal grid lines */ do r=0 to 9; function='move'; x=0; y=&ninth*r; output; if mod(r,3)=0 then size=&fatLine; else size=&thinLine; function='draw'; x=100; y=&ninth*r; line=1; filledShade="CX"||put(step*3,hex2.)||put(step*3,hex2.)||put(step*3,hex2.); color='black'; output; end; /* create observations to draw the vertical grid lines */ do c=0 to 9; function='move'; x=&ninth*c; y=0; output; if mod(c,3)=0 then size=&fatLine; else size=&thinLine; function='draw'; x=&ninth*c; y=100; line=1; color='black'; output; end; end; /* if _n_=1 then do */ /* place possible values in each cell */ /* grid line locations for this cell */ topline=&ninth*(row-1); bottomline=&ninth*row; leftline=&ninth*(col-1); rightline=&ninth*col; /* placement of known value within the cell */ /* note that 0,0 is at lower left but row 1 is at top */ if value ne . then do; /* centered value is a little low */ /* nudge it up 2% */ vRow = 102 - (&ninth * ( row - .5 )); vCol = &ninth * ( col - .5 ); function='label'; x=vCol; y=vRow; position='5'; /* centered */ text=put(value,1.); style="CENTB" ; filledShade="CX"||"FF"||put(step*20,hex2.)||put(step*20,hex2.); if step = 0 then color='black'; else color=filledShade; size=&valueSize; output; end; /* if value ne . */ /* placement of possibles within the cell */ do p=1 to 9; if notValue(p) eq 0 then do; colIncrement = ( mod(p-1,3)+1 ) * .25; rowIncrement = 1 - (( int((p-1)/3)+1 ) * .25); pRow = 100 - (&ninth * ( row - rowIncrement )); pCol = &ninth * ( col-1 + colIncrement ); /* create observation to draw the possible value for the cell */ function='label'; x=pCol; y=pRow; position='5'; /* centered */ text=put(p,1.); style="SWISSB"; color='CX649F44'; size=&possibleSize; output; /* put p= pRow= pCol=; */ end; /* if not(p) eq . */ end; /* do p=1 to 9 */ /* put _all_; */ run; %mend PlotPuzzle; ods pdf file="&GraphFile"; * LH 1 ; /* Enter your puzzle below */ data PuzzleEntered; retain cell 0; do row=1 to 9; do col=1 to 9; input value 1. @@; cell=cell+1; sqRow = int((row+2)/3); sqCol = int((col+2)/3); output; end; format value row col sqRow sqCol 1.; format cell 2.; input; end; datalines; ......... .4.1.6.9. .7.3.9.8. .13...75. 7..5.1..8 5.......6 6.......1 .52...84. 3..9.2..5 ; run; * LH 2 ; proc sql; create table mySudoku as select *, case value when 1 then 1 else 0 end as v1 format=1., case value when 2 then 1 else 0 end as v2 format=1., case value when 3 then 1 else 0 end as v3 format=1., case value when 4 then 1 else 0 end as v4 format=1., case value when 5 then 1 else 0 end as v5 format=1., case value when 6 then 1 else 0 end as v6 format=1., case value when 7 then 1 else 0 end as v7 format=1., case value when 8 then 1 else 0 end as v8 format=1., case value when 9 then 1 else 0 end as v9 format=1., 0 as step format=2. from PuzzleEntered; * LH 3 ; data PuzzleStatus; step=0; run; * LH 4 ; %macro fillCells(mySudoku=mySudoku); %DO %UNTIL (&upVals=0 or &step>65); * LH 5 ; proc sql noprint; select step into :step from PuzzleStatus; * LH 6 ; /* join the sudoku table to itself to find excluded values (from b) */ create table ExcludedValues as select a.cell, a.row, a.col, a.sqRow, a.sqCol, b.row as rowb, b.col as colb, b.sqRow as sqRowb, b.sqCol as sqColb, b.value as valueb, b.v1 as not1, b.v2 as not2, b.v3 as not3, b.v4 as not4, b.v5 as not5, b.v6 as not6, b.v7 as not7, b.v8 as not8, b.v9 as not9, &step as step format=2. from &mySudoku. as a, &mySudoku. as b where /* empty cells (a) */ (a.value = .) and /* match filled cells (b) */ (b.value ne .) and /* not themselves */ (a.cell ne b.cell) and /* Sudoku rules */ /* same row */ (a.row=b.row or /* same column */ a.col=b.col or /* same square */ (a.sqRow=b.sqRow and a.sqCol=b.sqCol)) order by row,col; * LH 7 ; /* for the empty cells, count cells */ create table myNots as select cell, row, col, sqRow, sqCol, /* in the same square and row, */ sum(row=rowb and sqRow=sqRowb and sqCol=sqColb) as nSameSqRow format=1., /* in the same square and col,*/ sum(col=colb and sqRow=sqRowb and sqCol=sqColb) as nSameSqCol format=1., /* and count and list the values that the cell cannot be */ sum(max(not1),max(not2),max(not3), max(not4),max(not5),max(not6), max(not7),max(not8),max(not9)) as nSet format=1., max(not1) as not1 format=1., max(not2) as not2 format=1., max(not3) as not3 format=1., max(not4) as not4 format=1., max(not5) as not5 format=1., max(not6) as not6 format=1., max(not7) as not7 format=1., max(not8) as not8 format=1., max(not9) as not9 format=1. from ExcludedValues group by cell, row, col, sqRow, sqCol; * LH 8 ; update PuzzleStatus set step=step + 1; select step into :step from PuzzleStatus; %IF &step eq 1 %THEN %DO; %PlotPuzzle proc ganno annotate=PuzzleAnno(where=(color ne "CX649F44")); run; proc ganno annotate=PuzzleAnno; run; %END; proc sql noprint; * STRATEGY 1 LH 9 ; create table mustN as select cell, int((row+2)/3) as sqRow, int((col+2)/3) as sqCol, row, col, case when not (not1) then 1 when not (not2) then 2 when not (not3) then 3 when not (not4) then 4 when not (not5) then 5 when not (not6) then 6 when not (not7) then 7 when not (not8) then 8 when not (not9) then 9 else . end as value, 1 as v1, 1 as v2, 1 as v3, 1 as v4, 1 as v5, 1 as v6, 1 as v7, 1 as v8, 1 as v9, &step as step from myNots where nSet = 8; * STRATEGY 2 LH 10 ; /* Within a Square, if an empty cell has two values filled in the same column and the other two columns have a common value not in the square then the empty cell must have that common value */ create table compCols as select myNots.cell, myNots.row, myNots.col, &mySudoku..value, &mySudoku..col as colv from myNots, &mySudoku. where /* 2 values same square and col */ nSameSqCol=2 and /* filled cells in the same column of squares but not the same square */ ((myNots.col ne &mySudoku..col and myNots.sqCol = &mySudoku..sqCol and myNots.sqRow ne &mySudoku..sqRow and &mySudoku..value ne .) or /* filled square in same column */ (myNots.col = &mySudoku..col and &mySudoku..value ne .) ) order by row,col,value; * LH 11 ; create table mustC as select cell, int((row+2)/3) as sqRow, int((col+2)/3) as sqCol, row, col, value, 1 as v1, 1 as v2, 1 as v3, 1 as v4, 1 as v5, 1 as v6, 1 as v7, 1 as v8, 1 as v9, &step as step from compCols group by row, col, value having count(value) = 2 /* exclude the two cells in the same square */ except select cell, int((row+2)/3) as sqRow, int((col+2)/3) as sqCol, row, col, value, 1 as v1, 1 as v2, 1 as v3, 1 as v4, 1 as v5, 1 as v6, 1 as v7, 1 as v8, 1 as v9, &step as step from compCols where col=colv; * STRATEGY 3 LH 12 ; /* Same logic as Strategy 2 but applied to rows instead of columns */ create table compRows as select myNots.cell, myNots.row, myNots.col, &mySudoku..value, &mySudoku..row as rowv from myNots, &mySudoku. where nSameSqRow=2 and ((myNots.row ne &mySudoku..row and myNots.sqRow = &mySudoku..sqRow and myNots.sqCol ne &mySudoku..sqCol and &mySudoku..value ne .) or (myNots.row = &mySudoku..row and &mySudoku..value ne .) ) order by row,col,value; * LH 13 ; create table mustR as select cell, int((row+2)/3) as sqRow, int((col+2)/3) as sqCol, row, col, value, 1 as v1, 1 as v2, 1 as v3, 1 as v4, 1 as v5, 1 as v6, 1 as v7, 1 as v8, 1 as v9, &step as step from compRows group by row, col, value having count(value) = 2 except select cell, int((row+2)/3) as sqRow, int((col+2)/3) as sqCol, row, col, value, 1 as v1, 1 as v2, 1 as v3, 1 as v4, 1 as v5, 1 as v6, 1 as v7, 1 as v8, 1 as v9, &step as step from compRows where row=rowv ; * LH 14 ; proc sql; title "Cells Determined by Exclusion Step &step "; select row, col, value from mustN; * LH 15 ; title "Cells Determined by Columns in Square Step &step "; select row, col, value from mustC; * LH 16 ; title "Cells Determined by Rows in Square Step &step "; select row, col, value from mustR; * LH 17 ; create table MustAll as select * from mustN union select * from mustC union select * from mustR ; * LH 18 ; update &mySudoku. set value=(select value from mustAll where &mySudoku..cell= mustAll.cell ), step = &step where cell in(select cell from mustAll); * LH 19 ; update &mySudoku. set v1 = case value when 1 then 1 else 0 end , v2 = case value when 2 then 1 else 0 end , v3 = case value when 3 then 1 else 0 end , v4 = case value when 4 then 1 else 0 end , v5 = case value when 5 then 1 else 0 end , v6 = case value when 6 then 1 else 0 end , v7 = case value when 7 then 1 else 0 end , v8 = case value when 8 then 1 else 0 end , v9 = case value when 9 then 1 else 0 end ; * LH 20 ; Title "Puzzle after Step &step"; * LH 21 ; proc sql noprint; select count(row) into :upVals from mustALL; quit; %put upVals=&upVals; %PlotPuzzle proc ganno annotate=PuzzleAnno; run; %END; %mend fillCells; %fillCells(mysudoku=mysudoku) ods pdf close;