## [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 <etienne@isr.ist.utl.pt>.
##
## 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 <etienne@isr.ist.utl.pt>, 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