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 SAS

From sasCommunity
Jump to: navigation, search

Below is a Base SAS program to Solve Sudoku - New puzzles can be input into grid after Resetting - Watch the program Solve in under a minute - Always produces solution/s

Sample Puzzles included after Program

/**************************************************************************/
/***                     SUDOKU SOLVER in Base SAS                      ***/
/***                      Written by HAROON PAHAD                       ***/
/***                    in Feb 2009 - for Base SAS                      ***/
/***                 Optimised Code on 14/15 April 2012                 ***/
/***   The Program works with the Values as Numbers when Generating     ***/
/***   the Possibilities - Only later does it Convert the Values to     ***/
/***                Char when it does the Eliminations                  ***/ 
/***      The Solution or Solutions will be in Work.Sudoku_Final        ***/
/***                          THE GAME :---                             ***/
/***   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)  ***/
/**************************************************************************/  
/***                  This Program is Extremely Fast                    ***/
/***       Now Macro Variables for Previously Hard Coded Variables      ***/
/**************************************************************************/  
 
options /*MPRINT MLOGIC SYMBOLGEN NOERRORABEND*/  missing=' ';
 
/* Create (Read in) GRID that has to be solved */  
data grid;
     format ROW COL1  COL2  COL3  COL4  COL5  COL6  COL7  COL8  COL9 3.;
     infile datalines DLM='|' ;
     ROW=_N_;
     input  COL1  COL2  COL3  COL4  COL5  COL6  COL7  COL8  COL9 ; 
     /* SUDOKU to SOLVE is hereunder :----------- */
datalines;   
| |6| | |4| | | |1|
| | | |8| | | | |2|
|3| | |7| | | |9| |
| | | | |3| |9| | |
| |7| | | | | |4| |
| | |1| |5| | | | |
| |8| | | |6| | |5|
|4| | | | |9| | | |
|2| | | |1| | |3| |
;
run;
/* Can be used to RESET above 
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
*/
 
/********************************************* 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)
;
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 */
/* Values are Now Converted to Char from Num */
%macro posb_rows;
%do NO=1 %to 9;
  data ROW_&NO(keep=a&NO--i&NO);
    do a_&NO=&&GRID_&NO._1;                   /*  where for example &GRID_8_1 = 5,6,8,9  */
       do b_&NO=&&GRID_&NO._2;
          do c_&NO=&&GRID_&NO._3;
	     do d_&NO=&&GRID_&NO._4;
	        do e_&NO=&&GRID_&NO._5;
		   do f_&NO=&&GRID_&NO._6;
		      do g_&NO=&&GRID_&NO._7;
			 do h_&NO=&&GRID_&NO._8;
		            do i_&NO=&&GRID_&NO._9;
					    array nums{1:9} 8 a_&NO b_&NO c_&NO d_&NO e_&NO f_&NO g_&NO h_&NO i_&NO;
					    array chars{1:9} $1 a&NO b&NO c&NO d&NO e&NO f&NO g&NO h&NO i&NO;
						do j=1 to 9;
						  chars{j}=left(put(nums{j},1.));
						end;
						outStatus=1;
						do k=1 to 8 while (outStatus);
						  do l=k+1 to 9 while (outStatus);
						    if chars{k} = chars{l} 
							then outStatus=0;
						  end;
						end;
						if outStatus 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);
proc sql ;
   create view &T1._&T3. as
   select *
   from (
         select *
         from &T1 ,
              &T2 ,
              &T3 
         where %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_1,Row_2,Row_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);
%Possible_Subsets(Row_4,Row_5,Row_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);
%Possible_Subsets(Row_7,Row_8,Row_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);
 
/* 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_Fin as
   select *
   from (
         select *
         from Row_1_Row_3 ,
              Row_4_Row_6 ,
	      Row_7_Row_9 
         where %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_Final(drop=a1--i9);
  length a b c d e f g h i $1;
  set Sudoku_Fin;
  %do i=1 %to 9;
    a=a&i; b=b&i; c=c&i; d=d&i; e=e&i; f=f&i; g=g&i; h=h&i; i=i&i;
    output;
  %end;
  a=''; b=''; c=''; d=''; e=''; f=''; g=''; h=''; i='';
  output;
run;
%mend;
%final;
 
proc print data=Sudoku_Final;
run;

Sample Puzzles provided below - Each of these Puzzles run in under a minute

datalines;  
|9| |5| |6| | | | |
| | | | | |5|8| |6|
| | | | | |4| |5|9|
| | | | |5|1|3|4| |
| | |2| | | |6| | |
| |7|4|6|2| | | | |
|3|5| |1| | | | | |
|8| |9|3| | | | | |
| | | | |8| |7| |4|
;
run;
 
datalines;  
| | | | | | | | | |
| |4| |1| |6| |9| | 
| |7| |3| |9| |8| |
| |1|3| | | |7|5| |
|7| | |5| |1| | |8|
|5| | | | | | | |6|
|6| | | | | | | |1|
| |5|2| | | |8|4| |
|3| | |9| |4| | |5|
;
run;