## [output,feasible] = sudoku (input) - Try to solve a sudoku problem ## ## This function applies brutish force and may or may not work properly. The ## method (1) excludes impossible values of cells within each group (row, ## column and 3x3 block), (2) deduces the value of a cell that is the only ## one to be able to assume that value within a group and (3) makes guesses ## and sees where they lead (depth-first search). Does not check for ## unicity. May or may not detect unsolvalble cases properly. ## ## Please report success/failure to me . ## ## input : 9 x 9 : initial grid w/ unknown values set to 0. ## ## output : 9 x 9 : final grid. ## feasible: true if a solution was found, 0 otherwise. ## Author: Etienne Grossmann , 2005/12/30 function [output,feasible] = sudoku (input) verbose = 1; # 0:quiet 1:waitbar 2:verbose if !isstruct (input) # If input is matrix ## m : 9 x 81. m(n,i) is true iff n is a possible value of i'th cell. ## found : 1 x 81. found(i) is true iff value of i'th cell is known, i.e. ## if there's a unique n s.t. m(n,i) is true. ## done : 1 x 81 : done(i) is true iff found(i) is true and exclusion has ## been performed, i.e. if n is the value of cell i, for all j ## in same row, column and 3x3 block as i, m(n,j) has been set to 0. [ii,jj,vv] = find (input(:)); m = ones (9,81); m(:,ii) = 0; m(sub2ind([9 81],vv,ii)) = 1; done = zeros(1,81); found = sum(!!m) == 1; else # Input is struct, used in recursive calls m = input.m; done = input.done; found = input.found; end feasible = 1; while ! all (found) output = sshow2(m); if verbose == 1, waitbar(sum(found)/81,"Fraction of determined cells"); elseif verbose>1, sshow2(m); end if !any ((found & !done)) if verbose>1 printf ("No more known cells. Performing deduction\n"); end known = sum (sum(m)==1); for i = 1:9, m = sdeduce (m,(i-1)*9+(1:9)); m = sdeduce (m,i:9:81); end; for r = 1:3 for c = 1:3 m = sdeduce (m,27*(r-1)+3*(c-1)+1+[0 1 2 9 10 11 18 19 20]); end end found = sum (!!m) == 1; if verbose>1, printf ("Deduction found %i cells\n",sum(found) - known); end if any(!sum(m)) # Reached a contradiction: no solution if verbose>1, printf ("Impossible! (deduction)\n"); end feasible = 0; output = sshow2(m); keyboard; return; end if known == sum (found) # Deduction doesn't help try guessing if verbose>1, printf ("deduction does no good. Guessing.\n"); end # Find cell w/ least remaining ambiguity sm = sum (!!m); sm(find(sm==1)) = 9; i = find (sm == min (sm))(1); m0 = m; vv = find (m(:,i))'; # Possible values st = struct ("m",m, "found",found, "done",done); st.found(i) = 1; for v = vv m(:,i) = 0; m(v,i) = 1; st.m = m; ##i, v, vv ##keyboard; [output, feasible] = sudoku (st); if feasible, return; end end end else # Eliminate possibilities from known cells i = find((found & !done))(1); v = find (m(:,i)); if length(v)!=1, printf ("Whoa! Incoherence!\n"); feasible = 0; v keyboard; return; end m1 = m; m = sexclude(m,i,v); if any(!sum(m)), if verbose>1, printf ("Whoa! Impossible! (sexclude)\n"); end feasible = 0; return; end ii = find (sum(!!m) == 1); found(ii) = 1; done(i) = 1; if verbose>1 printf ("Done cell %i: done: %i; found: %i\n",i,sum(done),sum(found)); end end endwhile output = sshow2(m); return function sshow (m) m += m.*(ones(9,1)*(sum(m)==1)); m = 32*(!m) + 35*(m==1) + 42*(m==2); m = [m, 10*ones(9,1)]'; m = char(m(:)); printf ("%s",m); endfunction function foo = sshow2 (m,r,c), ii = find(sum(m)==1); [i1,j1] = find (m(:,ii)); foo = zeros(9); foo(ii) = i1; if !nargout s = sprintf (" %i %i %i %i %i %i %i %i %i \n",foo'); s(find(s=="0"))="."; if nargin>=2 if nargin == 2 [r,c] = ind2sub([9 9],r); end for i = 1:length(r), s(20*(r(i)-1)+2*c(i)+[-1,1]) = "()";end end printf(s); end endfunction ## If a cell is the only one in the group m(:,ii) to possibly take a value, ## then this cell must have this value. function m = sdeduce (m,ii) n = m(:,ii); known = sum (sum(n)==1); # # of determined cells n += n .* ((sum(n') == 1)'*(sum(n) > 1)); n = n == (ones(9,1)*max(n)); if any ((n!=m(:,ii))(:)) ##printf ("sdeduce determines %i\n",sum(sum(n)==1)-known); #keyboard; end m(:,ii) = min (m(:,ii), n); endfunction ## If a cell m(:,i) is known to have value v, then no other cell in its row, ## column and block groups can take that value. function m = sexclude (m,i,v) m(:,i) = 0; mm = ones(9,1); mm(v) = 0; irow = rem(i-1,9)+1:9:81; icol = floor((i-1)/9)*9+(1:9); [r,c] = ind2sub([9 9],i); r = floor((r-1)/3)*3; c = floor((c-1)/3)*3; iblc = (9*c+r+1) + [0 1 2 9 10 11 18 19 20]; m(:,icol) = min (m(:,icol),mm*ones(1,9)); m(:,irow) = min (m(:,irow),mm*ones(1,9)); m(:,iblc) = min (m(:,iblc),mm*ones(1,9)); m(:,i) = 1-mm; endfunction