topic Re: N-Queens Problem in SAS Programming

N-Queens Problem

skjhzzang — Fri, 29 May 2020 06:56:04 GMT

Re: N-Queens Problem

ed_sas_member — Wed, 27 May 2020 15:44:07 GMT

Please have a look at the following resource, which tries to solve the N-Queens problems using several programming languages: https://rosettacode.org/wiki/N-queens_problem#SAS

You can easily put the '8' in a macrovariable inside a macro-program.

Hope this helps,

Best,

Re: N-Queens Problem

RichardDeVen — Wed, 27 May 2020 17:59:46 GMT

'Pure' macro is really not the environment for typical recursion and fundamental computation. Regardless, it's not impossible.

Example:

%* translated to SAS macro - Richard DeVenezia
%* Based on code at https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/;
%* contributed by Princi Singh ;

%macro logBoard(N);
  %* requires: macro symbols BOARD_1_1 to BOARD_<N>_<N> to exist in callers scope;
  %local i j row;

  %put NOTE: ------------- &=N;

  %do i = 1 %to &N;
    %let row = ;
    %do j = 1 %to &N;
      %let row = &row &&BOARD_&I._&J.;
    %end; 
    %put NOTE: &row;
  %end;

  %put NOTE: -------------;
%mend;

%macro isSafePlace(row, col, N);
  %* requires: macro symbols BOARD_1_1 to BOARD_<N>_<N> to exist in callers scope;
  %local i j index;
  %do j = 1 %to &col;
    %if &&BOARD_&ROW._&J. %then %do;
      0 /* not safe */
      %return;
    %end;
  %end;

  %let i = &row;
  %let j = &col;
  %do index = 1 %to &N;
    %if &&BOARD_&I._&J. %then %do;
      0 /* not safe */
      %return;
    %end;
    
    %let i = %eval(&i-1); %if &i < 1 %then %goto leave1;
    %let j = %eval(&j-1); %if &j < 1 %then %goto leave1;
  %end;
%leave1:

  %let i = &row;
  %let j = &col;
  %do index = 1 %to &N;
    %if &&BOARD_&I._&J. %then %do;
      0 /* not safe */
      %return;
    %end;
    
    %let i = %eval(&i+1); %if &i > &N %then %goto leave2;
    %let j = %eval(&j-1); %if &j <  1 %then %goto leave2;
  %end;
%leave2: 

  1 /* is safe */
%mend;

%macro queensRecursion(col, N);
  %local i j;
  %if &col > &N %then %do; 
    1  /* solution found */
    %return;
  %end;

  %do i = 1 %to &N;
    %if %isSafePlace(&i, &col, &N) %then %do;
      %let BOARD_&I._&COL. = 1;

      %if %queensRecursion(%eval(&col+1), &N) %then %do;
        1
        %return;
      %end;

      /* backtrack */
      %let BOARD_&I._&COL. = 0;
    %end;
  %end;

  0 /* could not be placed safely */
%mend;


%macro queens(N);
  %local i j;
  %do i = 1 %to &N;
  %do j = 1 %to &N;
    %local BOARD_&I._&J;
    %let BOARD_&I._&J = 0;
  %end;
  %end;
  
  %if not %queensRecursion(1, &N) %then %do;
    %put WARNING: No Queens solution found for &=N;
    %return;
  %end;

  %logBoard(&N)
%mend;

options mprint nomlogic nosymbolgen;

%queens(6)

Log

758  %queens(6)
      ------------- N=6
NOTE: 0 0 0 1 0 0
NOTE: 1 0 0 0 0 0
NOTE: 0 0 0 0 1 0
NOTE: 0 1 0 0 0 0
NOTE: 0 0 0 0 0 1
NOTE: 0 0 1 0 0 0
      -------------

Re: N-Queens Problem

Ksharp — Sat, 30 May 2020 12:28:01 GMT

When n=6 , there are four solutions .

EDITED.

EDITED again.

%let n=6 ;


data have;
 do i=1 to &n;
   do j=1 to &n;
      output;
   end;
 end;
run;
 
data want(keep=path);
 set have(obs=&n);
if _n_=1 then do;
  array row{%eval(&n*&n)} _temporary_;
  array col{%eval(&n*&n)} _temporary_;
  array flag{%eval(&n*&n)} _temporary_;

  length path _path  $ 400 temp $ 20;
  declare hash pa(ordered:'y');
  declare hiter hi_path('pa');
  pa.definekey('n');
  pa.definedata('n','path');
  pa.definedone();
end;

count=1;n=1;path=catx(' ',i,j);pa.add();
do while(hi_path.next()=0);
 if n ne 1 then pa.remove(key:_n);_n=n;

  idx=0;
  do i=1 to &n;
   do j=1 to &n;
     idx+1;row{idx}=i;col{idx}=j;flag{idx}=0;
   end;
  end;

  do k=1 to countw(path,'|');
   temp=scan(path,k,'|');
   first=input(scan(temp,1),best.);
   second=input(scan(temp,-1),best.);
   /*Remove - | / \ nodes*/
   do idx=1 to &n*&n;
     if first=row{idx} or second=col{idx} or 
        abs(first-row{idx})=abs(second-col{idx}) then flag{idx}=1;
   end;
  end;

  _path=path;   
   do idx=1 to &n*&n;
     if row{idx}=k and flag{idx}=0 then do;
       count+1;n=count;
	   path=catx('|',path,catx(' ',row{idx},col{idx}));
       pa.add(); 	
       if countw(path,'|')=&n then output;
       path=_path;
     end;
   end;
end;
pa.clear();	
run; 

data temp;
 set want;
 array var{&n} $ 20;
 do k=1 to &n;
   var{k}=scan(path,k,'|');
 end;
 keep var1-var&n ;
run;

data _null_;
 set temp end=last;
 call execute(catt("data solution_",_n_,";array var{&n};do i=1 to &n;do j=1 to &n;
 if findw('",catx('|',of var1-var&n),"',catx(' ',i,j),'|') then var{j}=1;else var{j}=0;end;
 output;end;drop i j;run;"));
run;

Re: N-Queens Problem

Ksharp — Fri, 29 May 2020 11:49:26 GMT

Better using PROC OPTMODEL .and calling @RobPratt

Re: N-Queens Problem

RobPratt — Fri, 29 May 2020 15:29:23 GMT

Please see this documentation example for the constraint programming solver in PROC OPTMODEL.

You can change the value of n to whatever you want. If you want to find all solutions, use the FINDALLSOLNS in the SOLVE statement.