## [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
## Define
## 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.
if !isstruct (input) # If input is matrix
[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 = stomat(m);
if verbose == 1, waitbar(sum(found)/81,"Fraction of determined cells");
elseif verbose>1, sshow2(output); 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 = stomat(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
m = sexclude(m,i,v);
if any(!sum(m)),
if verbose>1, printf ("Whoa! Impossible! (sexclude)\n"); end
feasible = 0;
return;
end
found(find (sum(!!m) == 1)) = 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 = stomat(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 sshow2 (foo,r,c)
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
end
function foo = stomat (m),
ii = find(sum(m)==1);
[i1,j1] = find (m(:,ii));
foo = zeros(9); foo(ii) = i1;
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