% SudokuFast von Philipp Zech 
%
%Funktionsweise: Das Programm sucht zunächst alle Nullstellen und speichert
%deren Koordinaten ab. Jetzt läuft die Funktion "eindeutig" darüber, falls
%es nur eine einzige Lösung des Sudokus gibt, dann wird es gelöst und die
%Lösung ausgegeben. Sind danach immer noch Nullstellen vorhanden,
%so steht fest, dass es sich um ein schwierigeres Sudoku handelt, es gibt also
%nur noch Nullstellen die nicht eindeutig sind (es gibt mehrere
%Möglichkeiten). In diesem Fall wird eine Schleife abgearbeitet, in der
%immer zuerst eine Zahl geraten wird(und zwar bei der Nullstelle mit den
%wenigsten Möglichkeiten),dann wieder mithilfe der Funktion "eindeutig"
%versucht zu Lösen. Im Fall eines Fehlers (eine Nullstelle mit 0
%Möglichkeiten) war die letzte geratene Zahl falsch und es wird die nächste
%probiert.
%
%Der Code ist etwas unordentlich und kaum kommentiert, dessen bin ich mir
%bewusst. 
%


function matrix=SudokuFast(matrix)

global leerstellen lsspeicher speichernummer speicherstand fehler


speicherstand = struct('Matrix',1,'Koords',1,'Moegliche',1,'Leerstellen',1);
speichernummer = 0;
fehler = 0;
lsspeicher = 0;
leerstellen = 0;



analyse(matrix);
matrix = worstcase(matrix);
analyse(matrix);

if leerstellen ~= 0
matrix = eindeutig(matrix);
end
if leerstellen > 0
while leerstellen > 0
 while leerstellen > 0 && fehler == 0
   
   
   aktuelle_nullstellen;
   
   matrix = raten(matrix);
  
  
   aktuelle_nullstellen;
  
   matrix = eindeutig(matrix);

  
   
   
  end
  if fehler == 1
      
      matrix = restaurieren(matrix);
      
  end
end
  
end
end



function analyse(matrix)
global leerstellen lsspeicher 
%Herausfinden und abspeichern der Koordinaten der Nullen.

leerstellen = 0;

for ii = 1:9
    for jj = 1:9
         if matrix(ii,jj) == 0
             leerstellen = leerstellen +1;
             lsspeicher (leerstellen,1) = ii;
             lsspeicher (leerstellen,2) = jj;
         end   
    end
end


end



function matrix = worstcase(matrix)
global leerstellen

if leerstellen == 81
    matrix = [8 3 6 4 7 5 2 9 1; 2 4 1 6 9 8 7 5 3; 9 7 5 3 2 1 4 8 6; 6 2 4 1 8 3 5 7 9; 5 1 9 7 6 4 3 2 8; 7 8 3 2 5 9 1 6 4; 3 9 8 5 4 7 6 1 2; 4 6 7 9 1 2 8 3 5; 1 5 2 8 3 6 9 4 7];
end
end


function matrix = eindeutig(matrix)
global leerstellen lsspeicher fehler


uebrige = leerstellen;
xkoord_untermatrix = 0;
ykoord_untermatrix = 0;


%Ermitteln aller Zahlen, die nicht in Frage kommen für die Nullstelle

%lsspeicher


% Im schlimmsten aller Fälle wird etwas geschummelt :-)






eindeutig = 1;

while uebrige > 0 && eindeutig == 1&& fehler == 0

    eindeutig = 0;


for kk = 1:leerstellen
    
%Zunächst die, die in der selben Untermatrix stehen    
 if lsspeicher(kk,1) ~= 0
    
x_ak = lsspeicher (kk,2);
y_ak = lsspeicher (kk,1);

    if y_ak < 4 
        ykoord_untermatrix = 1;
    elseif y_ak < 7
        ykoord_untermatrix = 4;
    else
        ykoord_untermatrix = 7;
    end
    
    
    if x_ak < 4 
        xkoord_untermatrix = 1;
    elseif x_ak < 7
        xkoord_untermatrix = 4;
    else
        xkoord_untermatrix = 7;
    end
  
    x_untergrenze = xkoord_untermatrix;
    x_obergrenze = xkoord_untermatrix + 2;
    y_untergrenze = ykoord_untermatrix;
    y_obergrenze = ykoord_untermatrix + 2;
    
    vorhandene = zeros(10,1);
    
    for mm = x_untergrenze : x_obergrenze
        for nn = y_untergrenze : y_obergrenze
            zahl = matrix(nn,mm)+1;
            vorhandene(zahl,1)=1;
        end
    end

    %Dann die in der selben Zeile und Spalte
    
   
    
    for oo = 1:9
        zeile = matrix(y_ak , oo)+1;
        spalte = matrix(oo, x_ak)+1;
        vorhandene(zeile,1)=1;
        vorhandene(spalte,1)=1;
    end
     
    
    
    anz_loesungen = 0;
    
    for pp = 2:10
        if vorhandene(pp,1) == 0
            loesung = pp-1;
            anz_loesungen = anz_loesungen + 1;
        end
    end
    
    
    
    if anz_loesungen == 1
        matrix(y_ak,x_ak) = loesung;
        lsspeicher(kk,1)= 0;
        uebrige = uebrige -1;
        eindeutig = 1;
    elseif anz_loesungen == 0
        fehler = 1;
        break
    end
    
    
    
 end
end

end

leerstellen = uebrige;


end






function aktuelle_nullstellen
global leerstellen lsspeicher

lsspeicher_intern = 0;
dimension_lsspeicher = size(lsspeicher);
zeilen = dimension_lsspeicher(1,1);
anzahl_ls=0;

for ii = 1:zeilen
    if lsspeicher(ii,1) ~= 0
        anzahl_ls = anzahl_ls +1;
        lsspeicher_intern(anzahl_ls,1) = lsspeicher(ii,1);
        lsspeicher_intern(anzahl_ls,2) = lsspeicher(ii,2);
    end
end

lsspeicher = lsspeicher_intern;
leerstellen = anzahl_ls;
end


function matrix = raten(matrix)
global lsspeicher speichernummer leerstellen speicherstand

speichernummer = speichernummer + 1;
moeglichkeiten = 0;

for kk = 1:leerstellen
    
%Zunächst die, die in der selben Untermatrix stehen    
    
x_ak = lsspeicher (kk,2);
y_ak = lsspeicher (kk,1);

    if y_ak < 4 
        ykoord_untermatrix = 1;
    elseif y_ak < 7
        ykoord_untermatrix = 4;
    else
        ykoord_untermatrix = 7;
    end
    
    
    if x_ak < 4 
        xkoord_untermatrix = 1;
    elseif x_ak < 7
        xkoord_untermatrix = 4;
    else
        xkoord_untermatrix = 7;
    end
  
    x_untergrenze = xkoord_untermatrix;
    x_obergrenze = xkoord_untermatrix + 2;
    y_untergrenze = ykoord_untermatrix;
    y_obergrenze = ykoord_untermatrix + 2;
    
    vorhandene = zeros(10,1);
    moeglichkeiten = zeros(81,9);
    
    for mm = x_untergrenze : x_obergrenze
        for nn = y_untergrenze : y_obergrenze
            zahl = matrix(nn,mm)+1;
            vorhandene(zahl,1)=1;
        end
    end

    %Dann die in der selben Zeile und Spalte
    
   
    
    for oo = 1:9
        zeile = matrix(y_ak , oo)+1;
        spalte = matrix(oo, x_ak)+1;
        vorhandene(zeile,1)=1;
        vorhandene(spalte,1)=1;
    end
     
    
    
    anz_loesungen = 0;
    
    for pp = 2:10
        if vorhandene(pp,1) == 0
            anz_loesungen = anz_loesungen + 1;
            moeglichkeiten(kk,pp-1) = pp-1;
        end
    end
    
    lsspeicher(kk,3) = anz_loesungen;
   
end

wenigste = 9;
ratestelle = [0 0 0];
index_lsspeicher = 0;


for ll = 1:leerstellen
    if lsspeicher(ll,3) <= wenigste && lsspeicher(ll,3) > 0
        ratestelle(1,1) = lsspeicher(ll,1); %zeile
        ratestelle(1,2) = lsspeicher(ll,2); %spalte
        ratestelle(1,3) = lsspeicher(ll,3); %anzahl möglichkeiten
        ratestelle(1,4) = ll; %standort in variable möglichkeiten
        index_lsspeicher = index_lsspeicher + 1;
    end
end


ratestelle;

lsspeicher(index_lsspeicher, 1) = 0;

zz = ratestelle(1,4);
kleinste = 9;

for ii=1:9
    if moeglichkeiten(zz,ii) < kleinste && moeglichkeiten(zz,ii) > 0
        kleinste = moeglichkeiten(zz,ii);
    end
end

moegl_speicher = moeglichkeiten(zz,:);
moegl_speicher(1, kleinste) = 0;


speicherstand(speichernummer).Matrix = matrix;
speicherstand(speichernummer).Koords = [ratestelle(1,1),ratestelle(1,2)];
speicherstand(speichernummer).Moegliche = moegl_speicher;
speicherstand(speichernummer).Leerstellen = lsspeicher;

matrix(ratestelle(1,1),ratestelle(1,2)) = kleinste;



end



function matrix = restaurieren(matrix)
global speicherstand speichernummer fehler lsspeicher

moeglichkeiten = speicherstand(speichernummer).Moegliche;
zeile = speicherstand(speichernummer).Koords(1,1);
spalte = speicherstand(speichernummer).Koords(1,2);
next = 0;

for ii = 1:9
    if moeglichkeiten(1,ii)~= 0
        next = moeglichkeiten(1,ii);
    end
end
next;
% für den fall das keine möglichkeiten mehr vorhanden sind
if next == 0
    matrix(zeile,spalte) = 0;
    speichernummer = speichernummer - 1;
    matrix = speicherstand(speichernummer).Matrix;
    %fehler = 0;
    lsspeicher = speicherstand(speichernummer).Leerstellen;
    
% oder eben die nächste Möglichkeit
else 
    moeglichkeiten(next) = 0;
    matrix = speicherstand(speichernummer).Matrix;
    matrix(zeile,spalte) = next;
    speicherstand(speichernummer).Moegliche(1,next) = 0;
    fehler = 0;
    lsspeicher = speicherstand(speichernummer).Leerstellen;
end

end