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.
[edit] 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;
