% Code löst ein Sudoku durch ausprobieren.
% 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.


clear all;      % Alte Variablen freigeben um sicherzugehen, dass sie nicht aus versehen
                % verwendet werden

% Sudoku aus der Aufgabe übernehmen
% 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 ];

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
Ux = 1;                % Linke obere Ecke eines Unterquadrates
Uy = 1;                % Wird für Bedingung d (Jede Ziffe 1x pro Unterquadrat) benötigt

% Vorsicht: Programm funktioniert nur mit Sudokus bei denen die linke obere
% Zahl nicht gegeben ist. Außerdem müssen die Sudokus lösbar sein sonst
% treten Fehler auf.

while Y <= 9           % 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
  
  if Sudo(Y,X) > 9            % Es darf nur 1-9 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 = 9;                  % X = letzte Spalte
      Y = Y-1;                % Y = vorherige Zeile (Anmerkung *)
    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 = 9;                % X = letzte Spalte
        Y = Y-1;              % Y = vorherige Zeile (Anmerkung *)
      end
    end
    Ux = fix((X-1)/3)*3 + 1;      % A -> Ua : 1->1, 2->1, 3->1, 4->2, 5->2, usw.
    Uy = fix((Y-1)/3)*3 + 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+2, Ux:Ux+2))) == 1  % mehrfach in einem Unterquadrat vorkommt ...
        X = X+1;                % Die Zahl ist OK, also nächstes Feld probieren
        if X > 9                % X über die Zeile hinaus
          X = 1;                % X wieder erste Spalte
          Y = Y+1;              % Nächste Zeile
        end
        if Y <= 9               % Wenn man noch in einer Zeile ist ...
          while Old(Y,X)        % Alte Zahlen dürfen nicht verändert werden ...
            X = X+1;            % nächstes Feld probieren
            if X > 9            % X über die Zeile hinaus
              X = 1;            % X wieder erste Spalte
              Y = Y+1;          % Nächste Zeile
            end
          end
        end
        Ux = fix((X-1)/3)*3 + 1;      % A -> Ua : 1->1, 2->1, 3->1, 4->2, 5->2, usw.
        Uy = fix((Y-1)/3)*3 + 1;      % Hier festlegen spart Zeit beim vergleichen
      end
    end

  end
  
end

% 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


% Anmerkungen:
% (*)
% Für ein lösbares Sudoku wird Y niemals kleiner als 1, sodass man dies nicht testen
% muss. Für allgemeine Rätsel müsste man an dieser Stelle eine Überpfüfung einfügen
% damit das Programm in diesem Fall abbricht. Allgemeingültigkeit ist aber nicht gefordert.

% Auch eine Repeat-Schleife wäre wirklich praktisch, da diese einem in
% vielen Fällen ein unötiges doppelt aufschreiben erspart.