function AUSGABE = SudokuShort(input)
%Sudoku Solver (short), Version 2.1, Konstantin Kloos
%
%.d8888. db    db d8888b.  .d88b.  db   dD db    db 
%88'  YP 88    88 88  `8D .8P  Y8. 88 ,8P' 88    88 
%`8bo.   88    88 88   88 88    88 88,8P   88    88 
%  `Y8b. 88    88 88   88 88    88 88`8b   88    88 
%db   8D 88b  d88 88  .8D `8b  d8' 88 `88. 88b  d88 
%`8888Y' ~Y8888P' Y8888D'  `Y88P'  YP   YD ~Y8888P' 
%                                                   
%                                                   
%.d8888.  .d88b.  db      db    db d88888b d8888b. 
%88'  YP .8P  Y8. 88      88    88 88'     88  `8D 
%`8bo.   88    88 88      Y8    8P 88ooooo 88oobY' 
%  `Y8b. 88    88 88      `8b  d8' 88~~~~~ 88`8b   
%db   8D `8b  d8' 88booo.  `8bd8'  88.     88 `88. 
%`8888Y'  `Y88P'  Y88888P    YP    Y88888P 88   YD 
%
%- - - - - - - - - - - - - - - - - - - - - - - - - 
%                _                _   
%               | |              | |  
%            ___| |__   ___  _ __| |_ 
%           / __| '_ \ / _ \| '__| __|
%           \__ \ | | | (_) | |  | |_ 
%           |___/_| |_|\___/|_|   \__|
%
%- - - - - - - - - - - - - - - - - - - - - - - - -
%                  Version 2.1
%              by Konstantin Kloos  

%% GLOBALE VARIABLEN
global sudoku_work
global zeilen
global spalten
global kasten
global moeglichkeiten
%% ANFANGS DEFINITIONEN
sudoku_work = int8(input);
zeilen = ones(9,9,'int8'); %einsen an den Stellen, die noch eingesetzt werden kšnnen
spalten = ones(9,9,'int8');
kasten = ones(9,9,'int8');
moeglichkeiten = 9*ones(9,9,'int8');
%% ERSTEN ANALYSE DES SUDOKUS
analyse_komplett;
%% LOESE SUDOKUS!!
        step = int8(0);
        moeglichkeit=int8(0);
        while isempty(find(sudoku_work ==0,1))==0
            %beim naechsten mal naechste Moeglichket benutzen. Wenn keine
            %Moeglihckeiten mehr und Sudoku ungelöst, dann solange schritt
            %zurück bis wieder beides vorhanden.
            if isempty(find(moeglichkeiten,1))==1
                while moeglichkeit(step)==moegs(step)
                     step=step-1;
                end
                moeglichkeit(step+1:end)=zeros(1,length(moeglichkeit)-step);
                sudoku_work=sudoku_save(:,:,step);
                analyse_komplett;
            else
                step=step+1;
            end
            %Kleinste Anzahl an moeglichkeiten finden
            moegs(step) = 1;
            while isempty(find(moeglichkeiten ==moegs(step),1))==1
                moegs(step)=moegs(step)+1;
            end
            %Naechste Position finden mit wenigsten meoglichkeiten
            [zeile,spalte]=find(moeglichkeiten ==moegs(step),1);
            koord=[zeile,spalte];
            if length(moeglichkeit)<step
                moeglichkeit(step)=0;
            end
            moeglichkeit(step)=moeglichkeit(step)+1;
            %zahl eintragen und letztes Sudoku speicheren.
            ZW=find(zeilen(:,koord(1))+spalten(:,koord(2))+kasten(:,(ceil(koord(1)/3)-1)*3 + ceil(koord(2)/3)) ==3);            
            sudoku_save(:,:,step)=sudoku_work;
            %logische folgelösungen finden
            moeg_refresh(ZW(moeglichkeit(step)),koord);
        end
        AUSGABE=sudoku_work;
%% MOEGLICHKEITEN AKTUALISIEREN UND ZAHL EINTRAGEN
    function moeg_refresh(zahl,koord)
        sudoku_work(koord(1),koord(2))=zahl;
        zeilen(zahl,koord(1))=0;
        spalten(zahl,koord(2))=0;
        kasten(zahl,(ceil(koord(1)/3)-1)*3 + ceil(koord(2)/3))=0;
        for k = 1:9 %ZEILE, SPALTE, KASTEN
            update_moeg([koord(1),k])
            update_moeg([k,koord(2)])
            update_moeg([((ceil(koord(1)/3)*3)-3)+ceil(k/3),(ceil(koord(2)/3)*3)+k-(ceil(k/3)*3)])
        end
    end
%% MOEGLICHKEITEN AN EINER STELLE UPDATEN
    function update_moeg(pos)
        if sudoku_work(pos(1),pos(2))==0
            moeglichkeiten(pos(1),pos(2))=length(find(zeilen(:,pos(1))+spalten(:,pos(2))+kasten(:,(ceil(pos(1)/3)-1)*3 + ceil(pos(2)/3)) ==3));
        else
            moeglichkeiten(pos(1),pos(2))=0;
        end
    end
%% PRUEFEN, WELCHE ZAHLEN IM SPALTENVEKTOR BENUTZT WERDEN.
    function ergebniss=analys(spaltenvektor)
        ergebniss=ones(9,1);
        for n=1:9
            if spaltenvektor(n)~=0
                ergebniss(spaltenvektor(n))=0;
            end
        end
    end
%% AKTUALISIERT SPALTEN-VEKTOREN UND MOEGLICHKEITEN FUR GESAMTES SUDOKU
        function analyse_komplett
            for i=1:9 %Zeilen, Spalten und Kaesten
                zeilen(:,i)=analys(sudoku_work(i,:)');
                spalten(:,i)=analys(sudoku_work(:,i));
                koord=[ceil(i/3)*3-2,(i-ceil(i/3)*3 +3)*3-2];
                kasten(:,i)=analys([sudoku_work(koord(1):koord(1)+2,koord(2));sudoku_work(koord(1):koord(1)+2,koord(2)+1);sudoku_work(koord(1):koord(1)+2,koord(2)+2)]);
            end
            for i = 1:9
                for j=1:9
                    update_moeg([i,j])
                end
            end
        end
end