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 in DATA Step with Recursion

From sasCommunity
Jump to: navigation, search

This solver was not presented at SGF 2007.

The code solves the puzzle using the process of elimination. It will branch when a guess is needed. When a branch is made the state of crucial DATA Step variables need to be pushed onto a stack. If the branch results in a dead-end, the state needs to be popped off the stack.

The state stack is implemented as a Hash object. Most of the state is stored in arrays. The PEEKC function allows an array to be captured in a character variable which is also a data element of the hash. When popping an array off the stack, the CALL POKE routine moves the array information from the memory address of character string to the memory address of the array.

SAS Code

data solution; * / debug;
/* Richard A. DeVenezia
 * Sudoku solver
 * April 26, 2007
 */

  set sasuser.sudokus;
  where id = 8;

/*
 * A [ d, r, c ] - Available candidate items
 * N [    r, c ] - Number of available candidates
 * S [    r, c ] - Placed items
 * M - relative offsets for other cells in block 
 */

  array A[9,9,9] a1-a729 (81*1,81*2,81*3,81*4,81*5,81*6,81*7,81*8,81*9);
  array N[9,9]   n1-n81  (81*9);
  array S[9,9]   s1-s81  (81*.);
  array M[0:2,2] _temporary_ (-2,-1,+1,+2,-1,+1);

  index = 0;
  do r = 1 to 9;
  do c = 1 to 9;
    index + 1;
    length vc $1;
    vc = substr(puzzleString,index);
    if verify (vc,'123456789') then continue;
    vn = input (vc,1.);
    row = r;
    col = c;
    digit = vn;
    link SetCell;
    if status = -1 then do;
      put "Invalid puzzle string detected at " row= col= digit=;
      link renderPuzzleString;
      stop;
    end;
  end;
  end;

  put 'Initial conditions:';
  put (s[*]) (9*3. /) /;

  length _A $5832;
  length _N $729;
  length _S $729;

  declare hash stack ();
  stack.defineKey('level');
  stack.defineData('_A','_N','_S','row','col','digit','remain');
  stack.defineDone();

  level = 1;

  set_on_remain = 1;

Eliminate:

  do until (status < 0);

    status = -2;

    maxRemain = 0;
    minRemain = 10;

    do row = 1 to 9 while (status = -2);
    do col = 1 to 9 while (status = -2);

      remain = N [ row, col ]; 

      if remain = set_on_remain then do;

*       if remain > 1 then put remain= row= col= level= ;

        digit = 0;

        do until (status=0 or level<1);

          do while (digit < 9);
            digit + 1;

            if A [ digit, row, col ] eq . then continue;

            if remain > 1 then link pushState;

            link SetCell;

            if status = 0 then
              leave;

            link popState;
          end;

          if status = -1 then
            link popState;
        end;
      end;
      else do;
        if     remain > maxRemain then maxRemain = remain;
        if 0 < remain < minRemain then minRemain = remain;
      end;

    end;
    end;

    set_on_remain = 1;
  end;

  if level < 1 then do;
    put / 'No Solution!';
    put (n[*]) (9*3. /) /;
    put (s[*]) (9*3. /) /;
    put pushCount= popCount= /;
    stop;
  end;

  if status = -2 and maxRemain = 0 then do;
    put / 'Solution:';
*   put (n[*]) (9*3. /) /;
    put (s[*]) (9*3. /) /;
    put pushCount= popCount= /;
    stop;
  end;

* put 'Determined cells exhausted at ' setcount=;
* put (a[*]) (9*3. /) /;
* put (n[*]) (9*3. /) /;
* put (s[*]) (9*3. /);

  set_on_remain = minRemain;

  goto Eliminate;
return;


SetCell:
* put digit= row= col= n[row,col]= level=;

  status = -1;

  if A [ digit, row, col ] = . then return;

  setcount + 1;

  * clear cell possibilities;
  do _d = 1 to 9;
    if A [ _d, row, col ] = . then continue;
    A [ _d, row, col ] = .;
    N [     row, col ] + (-1);
  end;

  * clear row possibilities;
  do _c = 1 to 9;
    if A [ digit, row, _c ] = . then continue;
    if N [ row, _c ] = 1 and S [ row, _c ] = . then do;
*     put "Invalid elimination (r): " digit= row= _c=;
      return;
    end;

    A [ digit, row, _c ] = .;
    N [        row, _c ] + (-1);
  end;

  * clear col possibilites;
  do _r = 1 to 9;
    if A [ digit, _r, col ] = . then continue;
    if N [ _r, col ] = 1 and S [ _r, col ] = . then do;
*     put "Invalid elimination (c): " digit= _r= col=;
      return;
    end;

    A [ digit, _r, col ] = .;
    N [        _r, col ] + (-1);
  end;

  * clear block possibilities;
  _rm = mod (row,3);
  _cm = mod (col,3);

  do _ro = M[_rm,1] , M[_rm,2]; _r = row + _ro;
  do _co = M[_cm,1] , M[_cm,2]; _c = col + _co;
    if A [ digit, _r, _c ] = . then continue;
    if N [ _r, _c ] = 1 and S [ _r, _c ] = . then do;
*     put "Invalid elimination (b): " digit= _r= _c=;
      return;
    end;

    A [ digit, _r, _c ] = .;
    N [        _r, _c ] + (-1);
  end;
  end;

  * set cell;
  S [ row, col ] = digit;

  status = 0;
return;

renderPuzzleString:
  index = 0;
  do r = 1 to 9;  if mod(r,3)=1 then put;
  do c = 1 to 9;  if mod(c,3)=1 then put ' ' @;
    index + 1;
    length vc $1;
    vc = substr(puzzleString,index);
    put vc @;
  end; put;
  end; put;
return;

pushState:
  pushCount + 1;

  _A = peekc (addr(A[1,1,1]),5832);
  _N = peekc (addr(N[1,1]),729);
  _S = peekc (addr(S[1,1]),729);
  level + 1;
  rc = stack.replace();
return;

popState:
  popCount + 1;

  rc = stack.find();
  call poke (_A,addr(A[1,1,1]),5832);
  call poke (_N,addr(N[1,1]),729);
  call poke (_S,addr(S[1,1]),729);
  level + (-1);
return;

  keep s1-s81;
run;