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 Killer Solver using SAS

From sasCommunity
Jump to: navigation, search

This program solves any Sudoku Killer Puzzle – The only condition that has to be met, is 2 or more of the same Summation per Number of Cells cannot be adjacent to each other – by this is meant, if there is for example, 2 summation blocks of 20 for 3 cells, then these cannot be contiguous, they have to be disjointed – Sometimes this is not true, and there are exceptions, like in the program below, 8/2 & 9/2 are exceptions, and below program still resolves correctly - The script uses Macros, Arrays and Proc SQLs – The Program runs for anything between 1 minute to an hour, depending on the puzzle - Program always produces Solution/s, providing the condition is met, and puzzle is valid – Below program runs for about a minute with given Puzzle

Sample Puzzles included after Program

/*********************************************************************************/
/***                      SUDOKU KILLER Solver in Base SAS                     ***/
/***                          Written by HAROON PAHAD                          ***/
/***                         in Sep 2014 - for Base SAS                        ***/
/***                     KILLER SUDOKU Solver   THE GAME :---                  ***/
/***                 In addition to Below - There are Summations               ***/
/***                in Input Grid Below - Total / Number of Cells              ***/ 
/***                 where Total is the Summation of Those Cells               ***/
/***              and Number of Cells can be anything between 1 to 9           ***/
/***          In Each Summation, the Cells can contain the Digits 1 - 9,       ***/
/***  without Repeating Any Digit (A Digit occurs Once Only in Each Summation) ***/
/***       In Sudoku Each Grid comprises of 9 Rows, 9 Columns & 9 Blocks       ***/
/***               Each Row, Column & Block comprises of 9 Cells               ***/
/***                    Each Block spans 3 Rows & 3 Columns                    ***/
/***          Each Row, Column & Block contains all the Digits 1 - 9,          ***/
/***                        without Repeating Any Digit                        ***/
/***     (Every Digit 1 - 9 occurs Once Only in Every Row, Column & Block)     ***/
/*********************************************************************************/
/***              The Program computes Formulae for Rows, Columns,             ***/
/***                 Sets of 3 Rows and All Remaining Formulae                 ***/
/***         Program Applies the Formulae in the Same Respective Order         ***/
/***       but it processes either ROW or COLUMN (not both) to Begin With      ***/
/***            The Program can switch from ROW to COLUMN Processing           ***/
/***                   if more Columns than Rows Have Formulae                 ***/
/***        In Most Cases this is more Optimal, but not necessarily so         ***/
/***   COLUMN Processing is Done by Tranposing and then doing ROW Processing   ***/
/***   2 or more of the Same Summation Blocks CANNOT be ADJACENT/CONTIGUOUS    ***/
/***           and have to be Disjointed - There are some Exceptions           ***/
/***                   like the Program Below for 8/2 & 9/2                    ***/
/*********************************************************************************/
 
options noMPRINT noMLOGIC noSYMBOLGEN NOERRORABEND  missing=' ';
 
/* Create (Read in) GRID that has to be solved */  
data grid_;
     format ROW 3. COL1  COL2  COL3  COL4  COL5  COL6  COL7  COL8  COL9 $5.;
     infile datalines DLM='|' ;
     ROW=_N_;
     input  COL1  COL2  COL3  COL4  COL5  COL6  COL7  COL8  COL9 ; 
     /* SUDOKU to SOLVE is hereunder :----------- */       
datalines;   
|10/2 |10/2 |8/2  |8/2  |14/2 |14/2 |8/2  |20/3 |20/3 |
|11/2 |10/2 |22/4 |9/2  |9/2  |6/2  |8/2  |16/3 |20/3 |
|11/2 |10/2 |22/4 |22/4 |22/4 |6/2  |8/2  |16/3 |16/3 |
|32/6 |32/6 |9/2  |5/2  |5/2  |29/5 |8/2  |30/6 |30/6 |
|32/6 |32/6 |9/2  |29/5 |29/5 |29/5 |8/2  |30/6 |30/6 |
|32/6 |32/6 |13/2 |29/5 |11/2 |11/2 |8/2  |30/6 |30/6 |
|15/3 |15/3 |13/2 |15/2 |15/4 |15/4 |15/4 |9/2  |8/2  |
|12/3 |15/3 |9/2  |15/2 |11/2 |11/2 |15/4 |9/2  |8/2  |
|12/3 |12/3 |9/2  |9/2  |9/2  |16/2 |16/2 |7/2  |7/2  |
;
run;
/* Can be used to RESET above 
|     |     |     |     |     |     |     |     |     |
|     |     |     |     |     |     |     |     |     |
|     |     |     |     |     |     |     |     |     |
|     |     |     |     |     |     |     |     |     |
|     |     |     |     |     |     |     |     |     |
|     |     |     |     |     |     |     |     |     |
|     |     |     |     |     |     |     |     |     |
|     |     |     |     |     |     |     |     |     |
|     |     |     |     |     |     |     |     |     |
*/
 
/*options noQuoteLenMax;*/
%macro Evaluate_Formulae;	
 
%macro Row_Blk_All_Formulate;
data _null_ ;    /*  Evaluate Formulae -- Also Evaluates Row Formulae, Block Formulae & Full Formula */
  length formulae $500 formula $50;
  retain formulae '1' formula;
  set grid_  end=LObs;
  array to_add {1:9} $2 _TEMPORARY_;
  array add_coords {1:2,1:9}  _TEMPORARY_;        /* row & col co-ordinates */
  array rw_frm {1:9} $200 _TEMPORARY_;
  array blk_set{1:3} $300 _TEMPORARY_;
  array rw {1:9} COL1-COL9;
  array grd {1:9,1:9} $5  a1 b1 c1 d1 e1 f1 g1 h1 i1
                          a2 b2 c2 d2 e2 f2 g2 h2 i2
                          a3 b3 c3 d3 e3 f3 g3 h3 i3
                          a4 b4 c4 d4 e4 f4 g4 h4 i4
                          a5 b5 c5 d5 e5 f5 g5 h5 i5
                          a6 b6 c6 d6 e6 f6 g6 h6 i6
                          a7 b7 c7 d7 e7 f7 g7 h7 i7
			  a8 b8 c8 d8 e8 f8 g8 h8 i8
			  a9 b9 c9 d9 e9 f9 g9 h9 i9
                          ;
  retain a1--i9 '';
  do i=1 to 9;
    if scan(rw{i},2,'/') ne '1'
    then grd{row,i} = rw{i};
	rw_frm{i} = '1';
	do j=1 to 3;
	  blk_set{j}='1';
	end;
  end;
 
  if LObs;
  do i=1 to 9;
    do j=1 to 9;
	  if grd{i,j} ne ''
	  then do;
	         do k=1 to 9;
			   to_add{k}='';
			   do q=1 to 2;
			     add_coords{q,k}=.;
			   end;
		 end;
	         m=i;
		 n=j;
	         add_cnt=1;
	         prcs_cnt=1;
		 to_add{1}=vname(grd{i,j});
		 add_coords{1,1}=i;
                 add_coords{2,1}=j;
                 no_of_blks = input(scan(grd{i,j},2,'/'),2.);
 
                 do while (add_cnt<no_of_blks);
 
			   if n<9 and add_cnt<no_of_blks and grd{m,n} = grd{m,n+1}
			   then do;
			          find=1;
			          do f=1 to add_cnt;
					    if to_add{f}=vname(grd{m,n+1}) then find=0;
				  end;
			          if find then do;
                                                 add_cnt + 1;
                                                 to_add{add_cnt}=vname(grd{m,n+1});
						 add_coords{1,add_cnt}=m;
                                                 add_coords{2,add_cnt}=n+1;
					       end;
			        end;
                           if m>1 and add_cnt<no_of_blks and grd{m,n} = grd{m-1,n}
			   then do;
			          find=1;
			          do f=1 to add_cnt;
					    if to_add{f}=vname(grd{m-1,n}) then find=0;
			          end;
			          if find then do;
                                                 add_cnt + 1;
                                                 to_add{add_cnt}=vname(grd{m-1,n});
						 add_coords{1,add_cnt}=m-1;
                                                 add_coords{2,add_cnt}=n;
					       end;
			        end;
			   if n>1 and add_cnt<no_of_blks and grd{m,n} = grd{m,n-1}
			   then do;
			          find=1;
			          do f=1 to add_cnt;
					    if to_add{f}=vname(grd{m,n-1}) then find=0;
			          end;
			          if find then do;
                                                 add_cnt + 1;
                                                 to_add{add_cnt}=vname(grd{m,n-1});
						 add_coords{1,add_cnt}=m;
                                                 add_coords{2,add_cnt}=n-1;
					       end;
			        end;
			   if m<9 and add_cnt<no_of_blks and grd{m,n} = grd{m+1,n}
			   then do;
			          find=1;
			          do f=1 to add_cnt;
				            if to_add{f}=vname(grd{m+1,n}) then find=0;
				  end;
			          if find then do;
                                                 add_cnt + 1;
                                                 to_add{add_cnt}=vname(grd{m+1,n});
						 add_coords{1,add_cnt}=m+1;
                                                 add_coords{2,add_cnt}=n;
					       end;
			       end;
 
			   prcs_cnt+1;
			   m=add_coords{1,prcs_cnt};
			   n=add_coords{2,prcs_cnt};
 
                 end;  
 
			 formula=to_add{1};
			 in_row=1;
			 in_blks=1;
			 row_frm=substr(to_add{1},2,1);
			 select (row_frm);
			   when ('1' , '2' , '3')    blk_frm = '1';
			   when ('4' , '5' , '6')    blk_frm = '2';
			   when ('7' , '8' , '9')    blk_frm = '3';
			   otherwise;
			 end;
			 do p=2 to 9;
			   if to_add{p} ne ''
			   then do;
                                  formula=catx('+',formula,to_add{p});
			          if row_frm ne substr(to_add{p},2,1) 
				  then in_row=0;
				  select (substr(to_add{p},2,1));
			            when ('1' , '2' , '3')    cur_blk_frm = '1';
			            when ('4' , '5' , '6')    cur_blk_frm = '2';
			            when ('7' , '8' , '9')    cur_blk_frm = '3';
			            otherwise;
			          end;
			          if blk_frm ne cur_blk_frm
			          then in_blks=0;
				end;
			 end;
			 formula=catx('=',formula,scan(grd{i,j},1,'/'));
 
			 do x=1 to no_of_blks;
			   grd{add_coords{1,x},add_coords{2,x}}='';
			 end;
 
			 if in_row
	                 then rw_frm{input(row_frm,1.)} = catx(' and ' , rw_frm{input(row_frm,1.)} , formula);
			 else if in_blks
			      then blk_set{input(blk_frm,1.)} = catx(' and ' , blk_set{input(blk_frm,1.)} , formula);
                              else formulae=catx(' and ',formulae,formula); 
	      end;
    end;
  end;
  call symput('FORMULA',%str(strip(formulae)));  
  do x=1 to 9;
    call symput('rwfrm_'||left(put(x,1.)), %str(strip(rw_frm{x})));
  end;
  do x=1 to 3;
    call symput('blkfrm_'||left(put(x,1.)), %str(strip(blk_set{x})));
  end;
run;
%mend;
%Row_Blk_All_Formulate;
 
data _null_;                                     /* Evaluates Column Formulae */
  length element $2 formula $50 temp_string $600;
  array cl_frm {1:9} $200 _TEMPORARY_;
  array cols {9} $1  a b c d e f g h i   ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'); 
  retain a--i;
  do x=1 to 9;
     cl_frm{x} = '1';
  end;
  %do i=1 %to 4;
    %if &i = 4
    %then %do; temp_string=transtrn("&FORMULA",'and','#'); %end;
    %else %do; temp_string=transtrn("&&blkfrm_&i",'and','#'); %end;
    count=2;
    formula=strip(scan(temp_string,count,'#'));
    do while (formula ne '');
	  in_col=1;
	  ind=1;
          col_frm=substr(strip(scan(formula,1,'+')),1,1);
	  do until (element='');
	    ind+1;
	    element=strip(scan(formula,ind,'+'));
	    if element ne ''
	    then do;
		   if col_frm ne substr(element,1,1)
                   then in_col=0;
		 end;
	  end;
	  if in_col  
	  then do;
	         do j=1 to 9;
			   if cols{j} = col_frm     /* OR if vname(cols{j}) = col_frm  */
			   then cl_frm{j} = catx(' and ' , cl_frm{j} , formula);
		 end;
	       end;
	  count+1;
	  formula=strip(scan(temp_string,count,'#'));	
    end;
  %end;
  %do l=1 %to 9;
    %global clfrm_&l ;
  %end;
  do m=1 to 9;
    call symput('clfrm_'||left(put(m,1.)), %str(strip(cl_frm{m})));
  end;
run;
 
data _null_;
  %global Opt_Prcs;
  %do i=1 %to 9;
    if "&&rwfrm_&i" ne "1" then row_form_cnt + 1;
    if "&&clfrm_&i" ne "1" then col_form_cnt + 1;
  %end;
  row_col_diff = row_form_cnt - col_form_cnt;
  if row_col_diff < 0
  then call symput('Opt_Prcs','COLUMN');
  else call symput('Opt_Prcs','ROW');
run;
 
%if &Opt_Prcs = COLUMN
%then %do; 
         %put;
         %put Transpose Grid as Column Processing may be more Optimal!!!;
	 %put More Columns than Rows have Formulae;
         proc transpose data=grid_  out=grid_2(drop=_NAME_) prefix=COL;
           id ROW;
           var COL1-COL9;
         run;
 
         data grid_;
           format ROW 3.;
           set grid_2;
           ROW=_N_;
         run;
 
	 %put;
	 %put Reprocess Formulae for Transposed Grid;
	 %Row_Blk_All_Formulate;
	 %put Completed Re-evaluating Formulae for Transposed Grid;
	 %put;
      %end;
%else %do;
         %put;
	 %put Continuing with Row Processing!!!;
	 %put;
      %end;
 
%mend;
%Evaluate_Formulae;
/*options QuoteLenMax;*/
*%put _user_; 
 
/***************************************************** FACTORS ********************************************************/
/***          Computes Possible Values for All 9 x 9 = 81 Blocks --- Based on Summations                            ***/
data _NULL_;
  set grid_;
    length temp $50;
    array cols{1:9} $5 COL1-COL9;
    do c=1 to 9;
	  no_of_blks=scan(cols{c},2,'/');
	  sum=input(scan(cols{c},1,'/'),2.);
          if no_of_blks = '1'
	  then call symput('FCTS_'||left(put(ROW,1.))||'_'||left(put(c,1.)),left(put(scan(cols{c},1,'/'),1.)));
	  else do;
	         temp = '';
	         do l=1 to 9;
		   do m=1 to 9;
		      valid=1;
                      if l=m then valid=0;
		      if no_of_blks = '2' and not (index(temp,put(l,1.)))
		         and valid and l + m = sum
		      then temp = catx(',',temp,put(l,1.));
		      else if not (no_of_blks = '2') and valid 
		           then do n=1 to 9;
			          valid=1;
			          if l=n or m=n then valid=0;
				  if no_of_blks = '3' and not (index(temp,put(l,1.)))
                                     and valid and (l + m + n = sum) 
				  then temp = catx(',',temp,put(l,1.));
				  else if not (no_of_blks in ('2' , '3')) and valid 
				       then do o=1 to 9;
					      valid=1;
					      if l=o or m=o or n=o then valid=0;
				              if no_of_blks = '4' and not (index(temp,put(l,1.)))
                                                 and valid and (l + m + n + o = sum) 
				              then temp = catx(',',temp,put(l,1.));
					      else if not (no_of_blks in ('2' , '3' , '4')) and valid 
					           then do p=1 to 9;
						          valid=1;
							  if l=p or m=p or n=p or o=p then valid=0;
                                                          if no_of_blks = '5' and not (index(temp,put(l,1.)))
                                                             and valid and (l + m + n + o + p = sum) 
				                          then temp = catx(',',temp,put(l,1.));
					                  else if no_of_blks in ('6' , '7' , '8' , '9') 
                                                                  and valid 
					                       then do q=1 to 9;
							              valid=1;
								      if l=q or m=q or n=q or o=q or p=q then valid=0;
                                                                      if no_of_blks = '6' and not (index(temp,put(l,1.)))
                                                                          and valid and (l + m + n + o + p + q = sum) 
				                                      then temp = catx(',',temp,put(l,1.));
						                      else if no_of_blks in ('7' , '8' , '9') and valid 
						                           then do r=1 to 9;
										  valid=1;
										  if l=r or m=r or n=r or o=r or p=r or q=r 
                                                                                  then valid=0;
                                                                                  if no_of_blks = '7' 
                                                                                     and not (index(temp,put(l,1.)))
                                                                                     and valid and 
                                                                                     (l + m + n + o + p + q + r = sum) 
				                                                  then temp = catx(',',temp,put(l,1.));
						                                  else if no_of_blks in ('8' , '9') and valid  
						                                       then do s=1 to 9;
											      valid=1;
											      if l=s or m=s or n=s or o=s 
                                                                                                 or p=s or q=s or r=s 
                                                                                              then valid=0;
                                                                                              if no_of_blks = '8' and not
                                                                                                 (index(temp,put(l,1.)))
                                                                                                 and valid and 
                                                                                                 (l+m+n+o+p+q+r+s = sum) 
				                                                              then  
                                                                                                temp=catx(',',temp,put(l,1.));	
											      else if no_of_blks = '9' and 
                                                                                                       valid  
                                                                                                 then do t=1 to 9;
												      valid=1;
												      if l=t or m=t or n=t
                                                                                                         or o=t or p=t or q=t
                                                                                                         or r=t or s=t
                                                                                                      then valid=0;
                                                                                                      if /*no_of_blks = 
                                                                                                         '9' and*/ not
                                                                                                        (index(temp,put(l,1.)))
                                                                                                         and valid and
                                                                                                        (l+m+n+o+p+q+r+s+t = 
                                                                                                         sum)				                                                                          
                                                                                                      then temp =  
                                                                                                      catx(',',temp,put(l,1.));	
									  			     end;
                                                                                           end; 
                                                                                 end;
                                                                         end; 
                                                                end;
				                      end;
				            end;
			   end;
			 end;
                      call symput('FCTS_'||left(put(ROW,1.))||'_'||left(put(c,1.)),strip(temp));
		   end;
	end;
run;
*%put _user_;
 
/***                                Creates Grid - Only where 1 Possible Value                                    ***/
data grid(rename=(COL_1=COL1 COL_2=COL2 COL_3=COL3 COL_4=COL4 COL_5=COL5 COL_6=COL6 COL_7=COL7 COL_8=COL8 COL_9=COL9));
  set grid_;
  format COL_1-COL_9 3.;
  array col_{1:9} COL_1-COL_9;
  array cols{1:9} $4 COL1-COL9;
    do c=1 to 9;
      if scan(cols{c},2,'/') = '1'
      then col_{c} = input(scan(cols{c},1,'/'),1.);
      else col_{c} = .;
    end;
  keep ROW COL_1-COL_9;
run;
 
/********************************************* EXCLUSIONS **********************************************/
 
/* Make these Macro Vars GLOBAL & Initialise */
%macro Globalise_Macro_Vars;
data _null_;
%do i=1 %to 9;
  %global COL&i._EXC ROW&i._EXC BLK&i._EXC;
  call symput("COL&i._EXC",'0');
  call symput("ROW&i._EXC",'0');
  call symput("BLK&i._EXC",'0');
%end;
run;
%mend;
%Globalise_Macro_Vars;
 
/* Macro below evaluates all the Values to Exclude for Each Row, Column & Block  */
/* These are Values provided in Original Sudoku Grid - into Macro Vars Declared Above */
/* Called from 3 places: Generate_Cols_to_Exclude, Generate_Rows_to_Exclude, Generate_Blks_to_Exclude */
/* Call from Generate_Blks_to_Exclude does not have value for col= ,thus col=COL1 */ 
%macro Values_to_Exclude(tbl=,type=,col=COL1,seq=);
proc sql noprint;
select &col.
into :&type.&seq._EXC
separated by ','
from &tbl.
where &col. ne .
;
quit;
 
%mend;
 
/* Loops for All 9 Columns - Evaluating Values to Exclude for Each Column */
%macro Generate_Cols_to_Exclude;
%do i=1 %to 9;
  %Values_to_Exclude(tbl=grid,type=COL,col=COL&i.,seq=&i.);
  %put COL&i._EXC=&&COL&i._EXC ;
%end;
%mend;
%Generate_Cols_to_Exclude;
 
/* Need to Transpose Grid - To enable Evaluation of Values to Exclude for the Rows */
proc transpose data=grid(drop=ROW) out=grid_trps(drop=_NAME_);
run;
 
/* Loops for All 9 Rows - Evaluating Values to Exclude for Each Row */
%macro Generate_Rows_to_Exclude;
%do i=1 %to 9;
  %Values_to_Exclude(tbl=grid_trps,type=ROW,col=COL&i.,seq=&i.);
  %put ROW&i._EXC=&&ROW&i._EXC ;
%end;
%mend;
%Generate_Rows_to_Exclude;
 
/* Need to Split Grid by Columns - To enable Evaluation of Values to Exclude for the Blocks */
data COLS_1_3(drop=COL4-COL9) 
     COLS_4_6(drop=COL1-COL3 COL7-COL9 rename=(COL4=COL1 COL5=COL2 COL6=COL3)) 
     COLS_7_9(drop=COL1-COL6 rename=(COL7=COL1 COL8=COL2 COL9=COL3));
  set grid;
run;
 
/* Loops for All 9 Blocks (3 at each call) - Enable Evaluating Values to Exclude for Each Block using LAG Function */
/* This Macro also creates Macro Vars that Map the Rows & Columns to the Blocks */
/* Creates 3 Datasets at each call (9 Datasets in Total) */
%macro Blk_Values_to_Exclude(dtst=,BLK1=,BLK2=,BLK3=);
 
/* Declare Macro Vars to be GLOBAL - For Mapping Each Row & Column Combination (Cell) to a Block */
%do i=1 %to 9;
  %do j=1 %to 9;
    %global BLK_&i._&j;
  %end;
%end;
 
data &BLK1. &BLK2. &BLK3. ;
  set &dtst. ;
 
  /* Code below Maps Rows & Columns to the appropriate Blocks */
  select ;
    when (ROW<=3)    do; bl1='1'; bl2='2'; bl3='3'; end;
    when (4<=ROW<=6) do; bl1='4'; bl2='5'; bl3='6'; end;
    otherwise        do; bl1='7'; bl2='8'; bl3='9'; end;
  end;
  select ("&dtst.");
    when ('COLS_1_3')  do i=1 to 3;
                         call symput('BLK_'||left(put(ROW,1.))||'_'||left(put(i,1.)),bl1);
		       end;
    when ('COLS_4_6')  do i=4 to 6;
                         call symput('BLK_'||left(put(ROW,1.))||'_'||left(put(i,1.)),bl2);
	               end;
    when ('COLS_7_9')  do i=7 to 9;
                         call symput('BLK_'||left(put(ROW,1.))||'_'||left(put(i,1.)),bl3);
		       end;
    otherwise;
  end;
 
  /* 1st Step in Evaluating Values to Exclude in Each Block */
  COL1_lag1=lag(COL1);
  COL1_lag2=lag2(COL1);
  COL2_lag1=lag(COL2);
  COL2_lag2=lag2(COL2);
  COL3_lag1=lag(COL3);
  COL3_lag2=lag2(COL3);
 
  if ROW=3 then output &BLK1.;
  else if ROW=6 then output &BLK2.;
  else if ROW=9 then output &BLK3.;
  drop ROW bl1 bl2 bl3 i;
run;
%mend;
%Blk_Values_to_Exclude(dtst=COLS_1_3,BLK1=BLK_1,BLK2=BLK_4,BLK3=BLK_7);
%Blk_Values_to_Exclude(dtst=COLS_4_6,BLK1=BLK_2,BLK2=BLK_5,BLK3=BLK_8);
%Blk_Values_to_Exclude(dtst=COLS_7_9,BLK1=BLK_3,BLK2=BLK_6,BLK3=BLK_9);
 
/* Need to Transpose 9 Datasets having 1 Row each - To enable Evaluation of Values to Exclude for the Blocks */
%macro Transpose_Blocks;
%do i=1 %to 9;
  proc transpose data=BLK_&i. out=BLK_&i._trps(drop=_NAME_);
  run;
%end;
%mend;
%Transpose_Blocks;
 
/* Loops for All 9 Blocks - 2nd Step in Evaluating Values to Exclude for Each Block */
%macro Generate_Blks_to_Exclude;
%do i=1 %to 9;
  %Values_to_Exclude(tbl=BLK_&i._trps,type=BLK,seq=&i.);
  %put BLK&i._EXC=&&BLK&i._EXC ;
%end;
%mend;
%Generate_Blks_to_Exclude;
 
/********************************************* POSSIBILITIES **********************************************/
 
/* Creates Dataset having All Digits - 1 to 9 */
data All_Vals;
  set grid(keep=ROW rename=(ROW=VAL));
run;
 
/* This Macro is called 81 Times (9 x 9) for each Cell in Grid (Row-Column Combination) */
/* Creates 81 Macro Vars with Possible Values for Each Cell */
/* After excluding Values Already in that Row, Column & Block for the Particular Cell */ 
%macro Possible_Values(rw,cl,bk);
 
proc sql noprint;
select VAL
into : GRID_&rw._&cl.
separated by ','
from All_Vals
where VAL not in (&&ROW&rw._EXC)
and   VAL not in (&&COL&cl._EXC)
and   VAL not in (&&BLK&bk._EXC)
and   VAL in (&&FCTS_&rw._&cl.)
;
quit;
%mend;
 
/* Loops 81 Times - for each Row-Column (Cell) co-ordinate in Grid */
%macro Loop_Possible_Values;
%do i=1 %to 9;   * ROWS ;
  %do j=1 %to 9;   * COLUMNS ;
    %global GRID_&i._&j.;
    %Possible_Values(&i.,&j.,&&BLK_&i._&j.);
  %end;
%end;
%mend;
%Loop_Possible_Values;
 
/* Re-assigns Macro Vars that Already have Values in Grid */
data _null_;
  set grid;
    array cols{1:9} COL1-COL9;
    do c=1 to 9;
      if cols{c} ne .
      then call symput('GRID_'||left(put(ROW,1.))||'_'||left(put(c,1.)),left(put(cols{c},1.)));
    end;
run;
 
%put _user_;
 
/**************************************POSSIBILITIES / ELIMINATIONS ***************************************************/
 
/* Creates 9 Datasets (for each Row) - using Possible Values Macro Vars obtained Above */
/* Generating All Possible Combinations of the 81 Possible Values Evaluated Above */ 
/* This Macro ensures NO VALUE is REPEATED within a Row -- ROW ELIMINATION */
/* Each Dataset will have Possible Values for that Row */
%macro posb_rows;
%do NO=1 %to 9;
  data ROW_NO_&NO (drop=valid)      /* / view=ROW_&NO */ ;
      do a&NO=&&GRID_&NO._1;           /*  where for example &GRID_8_1 = 5,6,8,9  */
        do b&NO=&&GRID_&NO._2;
	  valid=1;
	  if a&NO=b&NO then valid=0;
	  if valid then
          do c&NO=&&GRID_&NO._3;
            valid=1;
	    if a&NO=c&NO or b&NO=c&NO then valid=0;
	    if valid then
	    do d&NO=&&GRID_&NO._4;
	      valid=1;
	      if a&NO=d&NO or b&NO=d&NO or c&NO=d&NO then valid=0;
	      if valid then
	      do e&NO=&&GRID_&NO._5;
		valid=1;
		if a&NO=e&NO or b&NO=e&NO or c&NO=e&NO or d&NO=e&NO then valid=0;
		if valid then
	        do f&NO=&&GRID_&NO._6;
		  valid=1;
		  if a&NO=f&NO or b&NO=f&NO or c&NO=f&NO or d&NO=f&NO or e&NO=f&NO then valid=0;
		  if valid then
		  do g&NO=&&GRID_&NO._7;
	            valid=1;
		    if a&NO=g&NO or b&NO=g&NO or c&NO=g&NO or d&NO=g&NO or e&NO=g&NO or f&NO=g&NO then valid=0;
		    if valid then
                    do h&NO=&&GRID_&NO._8;
	              valid=1;
		      if a&NO=h&NO or b&NO=h&NO or c&NO=h&NO or d&NO=h&NO or e&NO=h&NO or f&NO=h&NO or g&NO=h&NO then valid=0;
		      if valid then
		      do i&NO=&&GRID_&NO._9;
		        valid=1;
		        if a&NO=i&NO or b&NO=i&NO or c&NO=i&NO or d&NO=i&NO or e&NO=i&NO or f&NO=i&NO or g&NO=i&NO or h&NO=i&NO 
                        then valid=0;
		        if valid and &&rwfrm_&NO then output;
                      end;
	            end;
	          end;
                end;
              end;
	    end;
          end;
        end;
      end;
run;
%end;
%mend;
%posb_rows;
 
/*********************************************** ELIMINATIONS ***************************************************/
 
/* This Macro is called 3 Times - for Rows 1-3, 4-6 & 7-9 - Creating 3 Possible Subsets while Eliminating */
/*        a1 below refers to ROW 1 & COLUMN a            ---          e3 refers to ROW 3 & COLUMN e       */
/*                          Eliminating Within Same Blocks -- BLOCK ELIMINATION                           */
%macro Possible_Subsets(T1,T2,T3, b1_1,b1_2,b1_3,  b2_1,b2_2,b2_3,  b3_1,b3_2,b3_3,
                                  b1_4,b1_5,b1_6,  b2_4,b2_5,b2_6,  b3_4,b3_5,b3_6,
                                  b1_7,b1_8,b1_9,  b2_7,b2_8,b2_9,  b3_7,b3_8,b3_9, BlkForm);
proc sql ;
   create table &T1._&T3. as
   select *
   from (
         select *
         from &T1 ,
              &T2 ,
	      &T3 
         where   &BlkForm and
           %do i = 1 %to 6;                         /* Comparisons on same row are NOT Needed */
              %if %eval(&i.) < 4 %then %let j=4; %else %if %eval(&i.) < 7 %then %let j=7;
              %do k = %eval(&j.) %to 9;
		     &&b1_&i.. ne &&b1_&k.. and                                   
		     &&b2_&i.. ne &&b2_&k.. and 
		     &&b3_&i.. ne &&b3_&k.. and 
	      %end;
	   %end;
		 1);    /*  This 1 is to Accomodate and above  */
quit;
%mend;
%Possible_Subsets(Row_No_1,Row_No_2,Row_No_3, a1,b1,c1,  d1,e1,f1,  g1,h1,i1,
                                              a2,b2,c2,  d2,e2,f2,  g2,h2,i2,
                                              a3,b3,c3,  d3,e3,f3,  g3,h3,i3, &blkfrm_1);
%Possible_Subsets(Row_No_4,Row_No_5,Row_No_6, a4,b4,c4,  d4,e4,f4,  g4,h4,i4,
                                              a5,b5,c5,  d5,e5,f5,  g5,h5,i5,
                                              a6,b6,c6,  d6,e6,f6,  g6,h6,i6, &blkfrm_2);
%Possible_Subsets(Row_No_7,Row_No_8,Row_No_9, a7,b7,c7,  d7,e7,f7,  g7,h7,i7,
                                              a8,b8,c8,  d8,e8,f8,  g8,h8,i8,
                                              a9,b9,c9,  d9,e9,f9,  g9,h9,i9, &blkfrm_3);
 
/* Finally Solved - Each Solution/s in a Single Row - using 3 Subsets from Above while Eliminating */
/*                      Eliminating Within Same Column -- COLUMN ELIMINATION                       */
%macro Solve;
proc sql;
   create view Sudoku_Sum_Fin as
   select *
   from (
         select *
         from Row_No_1_Row_No_3 ,
              Row_No_4_Row_No_6 ,
	      Row_No_7_Row_No_9 
         where &FORMULA and
           %do i = 1 %to 6;                                /* Comparisons in Same Block are NOT Needed */
             %if %eval(&i.) < 4 %then %let j=4; %else %if %eval(&i.) < 7 %then %let j=7;
	       %do k = %eval(&j.) %to 9;
                         a&i. ne a&k. and                                            
			 b&i. ne b&k. and 
                         c&i. ne c&k. and
			 d&i. ne d&k. and
			 e&i. ne e&k. and
			 f&i. ne f&k. and
			 g&i. ne g&k. and
			 h&i. ne h&k. and
			 i&i. ne i&k. and
               %end;
	   %end;
         1);   /*  This 1 is to Accomodate last 'and' to give 'and 1' (always TRUE)  above  */
quit;
%mend;
%Solve;
 
/* Solved in Dataset SUDOKU_FINAL in WORK library - Could have Multiple Solutions */
/* Makes Solution/s from SUDOKU_FIN user Friendly */
 
%macro final;
data Sudoku_Sum_Final(drop=j a1--i9);
  set Sudoku_Sum_Fin;
  array grd {1:9,1:9} $5  a1 b1 c1 d1 e1 f1 g1 h1 i1
                          a2 b2 c2 d2 e2 f2 g2 h2 i2
                          a3 b3 c3 d3 e3 f3 g3 h3 i3
                          a4 b4 c4 d4 e4 f4 g4 h4 i4
                          a5 b5 c5 d5 e5 f5 g5 h5 i5
                          a6 b6 c6 d6 e6 f6 g6 h6 i6
                          a7 b7 c7 d7 e7 f7 g7 h7 i7
			  a8 b8 c8 d8 e8 f8 g8 h8 i8
			  a9 b9 c9 d9 e9 f9 g9 h9 i9
                          ;
  do j=1 to 9;
    if "&Opt_Prcs" = "COLUMN"    /* Transpose if COLUMN Processing was used */
	then do;
	       a=grd{1,j}; b=grd{2,j}; c=grd{3,j}; d=grd{4,j}; e=grd{5,j}; f=grd{6,j}; g=grd{7,j}; h=grd{8,j}; i=grd{9,j};
	       output;
             end; 
	else do;
	       a=grd{j,1}; b=grd{j,2}; c=grd{j,3}; d=grd{j,4}; e=grd{j,5}; f=grd{j,6}; g=grd{j,7}; h=grd{j,8}; i=grd{j,9};
	       output;
             end;
    format a--i 3.;
  end;
  a=.; b=.; c=.; d=.; e=.; f=.; g=.; h=.; i=.;
  output;
run;
%mend;
%final;
 
proc print data=Sudoku_Sum_Final;
run;

Below are 3 Sample Puzzle Grids that can be Run in Above Program - Each of these Run in just over a Minute

datalines;   
|10/2 |16/2 |16/2 |13/3 |4/2  |16/3 |3/2  |3/2  |15/2 |
|10/2 |17/3 |13/3 |13/3 |4/2  |16/3 |16/3 |20/3 |15/2 |
|30/6 |17/3 |3/2  |3/2  |10/2 |11/2 |11/2 |20/3 |28/6 |
|30/6 |17/3 |12/2 |12/2 |10/2 |13/2 |13/2 |20/3 |28/6 |
|30/6 |6/2  |6/2  |18/4 |18/4 |18/4 |15/2 |15/2 |28/6 |
|30/6 |15/2 |15/2 |17/5 |18/4 |17/5 |5/2  |5/2  |28/6 |
|30/6 |8/2  |15/2 |17/5 |17/5 |17/5 |13/2 |5/2  |28/6 |
|30/6 |8/2  |15/2 |22/3 |22/3 |22/3 |13/2 |5/2  |28/6 |
|45/9 |45/9 |45/9 |45/9 |45/9 |45/9 |45/9 |45/9 |45/9 |
;
run;
 
datalines;   
|21/4 |21/4 |21/4 |21/4 |21/5 |26/4 |16/2 |13/3 |11/3 |
|1/1  |16/3 |16/3 |16/3 |21/5 |26/4 |16/2 |13/3 |11/3 |
|10/2 |15/2 |21/5 |21/5 |21/5 |26/4 |26/4 |13/3 |11/3 |
|10/2 |15/2 |35/7 |4/1  |3/1  |8/2  |8/2  |14/2 |14/2 |
|35/7 |35/7 |35/7 |35/7 |35/7 |16/4 |16/4 |16/4 |16/4 |
|23/3 |3/2  |35/7 |14/2 |14/2 |1/1  |4/1  |10/2 |10/2 |
|23/3 |3/2  |15/5 |15/5 |15/5 |24/4 |24/4 |19/3 |2/1  |
|23/3 |20/3 |20/3 |20/3 |15/5 |24/4 |4/2  |19/3 |12/2 |
|24/4 |24/4 |24/4 |24/4 |15/5 |24/4 |4/2  |19/3 |12/2 |
;
run;
 
datalines;   
|11/3 |11/3 |17/3 |17/3 |6/2  |11/2 |10/2 |10/2 |9/1  |
|11/3 |14/2 |13/3 |17/3 |6/2  |11/2 |13/3 |12/2 |9/2  |
|8/2  |14/2 |13/3 |16/2 |16/2 |8/2  |13/3 |12/2 |9/2  |
|8/2  |6/2  |13/3 |13/2 |13/2 |8/2  |13/3 |8/2  |8/2  |
|3/1  |6/2  |16/3 |16/3 |16/3 |12/2 |12/2 |11/2 |5/2  |
|17/2 |17/2 |7/2  |4/2  |9/2  |7/1  |20/3 |11/2 |5/2  |
|15/2 |10/2 |7/2  |4/2  |9/2  |14/3 |20/3 |11/3 |8/1  |
|15/2 |10/2 |13/2 |13/2 |9/2  |14/3 |20/3 |11/3 |9/2  |
|5/1  |13/3 |13/3 |13/3 |9/2  |14/3 |3/1  |11/3 |9/2  |
;
run;