% Sudo = SolveSudoku(Sudo, Max, B, H) löst ein Sudoku durch ausprobieren.
% Sudo = Sudoku-Rätsel mit bekannten zahlen
% Max  = Maximale Zahl die eingesetzt werden kann.
% B    = Breite eines Blockes im Sudoku
% H    = Höhe eines Blockes im Sudoku
% Gibt ein fertiges Sudoku aus (eventuell sogar eindeutig)
% Autor:    Matthias Bosewitz
% Tutorium: Jan-Henning Hansen (Mo 10-12)
%
% Diese Art der Lösung ist zwar nicht sonderlich effektiv
% allerdings in der Aufgabe explizit so verlangt.

function Sudo = SolveSudoku(Sudo, Max, B, H)

% Sudoku aus der Aufgabe 2
% unbekannte Werte werden als 0 gesetzt.
% Sudo = [ 0 0 0  0 0 0  0 1 0
%          2 0 0  1 0 3  0 0 0
%          0 3 6  7 0 0  4 0 5
%          0 0 1  0 7 0  8 0 2
%          0 4 0  0 6 0  5 3 0
%          3 0 0  0 8 0  0 0 7
%          0 0 3  0 0 7  0 5 8
%          0 5 0  8 0 0  1 0 0
%          0 1 2  5 4 0  0 0 0 ];

% Mini-Testsudoku
% solvesudoku([ 1 0 0 ; 0 2 0 ; 0 0 3 ], 3, 1,1)

P = B-1;               % Breite - 1
Q = H-1;               % Höhe   - 1
Old = (Sudo ~= 0);     % Liste mit den Zahlen die unveränderlich (vorgegeben) sind.
                       % Diese ist nötig damit diese nicht vom Algoritmus
                       % durchprobiert werden.
X = 1;                 % Punkt an dem begonnen werden soll zu probieren ...
Y = 1;                 % ... ist die Linke obere Ecke
Counter = 0;           % Noch keine Schritte

while Old(Y,X)        % Gegebene Überspringen
  X = X+1;            % nächstes Feld probieren
  if X > size(Sudo,2) % X über die Zeile hinaus
    X = 1;            % X wieder erste Spalte
    Y = Y+1;          % Nächste Zeile
  end
end
Ux = fix((X-1)/B)*B + 1;      % A -> Ua : 1->1, 2->1, 3->1, 4->2, 5->2, usw.
Uy = fix((Y-1)/H)*H + 1;      % Hier festlegen spart Zeit beim vergleichen


while Y <= size(Sudo, 1)      % Solange man sich noch im Feld befindet
  
  Sudo(Y,X) = Sudo(Y,X)+1;    % Zu testende Zahl an der Stelle X,Y um 1 erhöhen
  Counter = Counter + 1;      % Zählen wie viele Schritte man braucht
  if mod(Counter, 10000) == 0
    Sudo                          % Testausgabe
  end

  if Sudo(Y,X) > Max          % Es darf nur 1-Max verwendet werden
  
    Sudo(Y,X) = 0;            % Zahl auf 0 (unbestimmt) zurücksetzen
    X = X-1;                  % Vorherige Zahl muss schon falsch gewesen sein.
    if X <= 0                 % Zu kleines X
      X = size(Sudo,2);       % X = letzte Spalte
      Y = Y-1;                % Y = vorherige Zeile
      if Y == 0                     % Sudoku unlösbar
        Sudo = zeros(size(Sudo));   % Fehlerausgabe
        return;                     % Funktion beenden
      end
    end
    while Old(Y,X)            % Alte Zahlen dürfen nicht verändert werden ...
      X = X-1;                % Vorherige Zahl wählen.
      if X <= 0               % Zu kleines X
        X = size(Sudo,2);     % X = letzte Spalte
        Y = Y-1;              % Y = vorherige Zeile
        if Y == 0                     % Sudoku unlösbar
          Sudo = zeros(size(Sudo));   % Fehlerausgabe
          return;                     % Funktion beenden
        end     
      end
    end
    Ux = fix((X-1)/B)*B + 1;      % A -> Ua : 1->1, 2->1, 3->1, 4->2, 5->2, usw.
    Uy = fix((Y-1)/H)*H + 1;      % Hier festlegen spart Zeit beim vergleichen
  
  elseif sum( Sudo(Y,X) == Sudo(Y,:) ) == 1  % mehrfach in einer Zeile vorkommt, noch ...
    if sum( Sudo(Y,X) == Sudo(:,X) ) == 1  % mehrfach in einer Spalte vorkommt, noch ...
      if sum(sum( Sudo(Y,X) == Sudo(Uy:Uy+Q, Ux:Ux+P) )) == 1  % mehrfach in einem Unterquadrat vorkommt ...
        X = X+1;                % Die Zahl ist OK, also nächstes Feld probieren
        if X > size(Sudo,2)     % X über die Zeile hinaus
          X = 1;                % X wieder erste Spalte
          Y = Y+1;              % Nächste Zeile
        end
        while Y <= size(Sudo,1) && Old(Y,X)        % Alte Zahlen dürfen nicht verändert werden ...
          X = X+1;            % nächstes Feld probieren
          if X > size(Sudo,2) % X über die Zeile hinaus
            X = 1;            % X wieder erste Spalte
            Y = Y+1;          % Nächste Zeile
          end
        end
        Ux = fix((X-1)/B)*B + 1;      % A -> Ua : 1->1, 2->1, 3->1, 4->2, 5->2, usw.
        Uy = fix((Y-1)/H)*H + 1;      % Hier festlegen spart Zeit beim vergleichen
      end
    end

  end
  
end

Counter  % Zahl ausgeben


% Ende: Da alle Felder mit Zahlen befüllt sind ist eine (die) Lösung gefunden und
% kann ausgegeben werden.
% Sudo        % Das gelöste Sudoku ausgeben

end