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
Jump to: navigation, search

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;