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;