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;