% Feld = Damenproblem(N) versucht N Damen auf einem NxN Schachbrett aufzustellen
% Die Funktion versucht die übergebene Anzahl N Damen auf einem NxN Felder
% großen Schachbrett so aufzustellen, dass sie sich nicht gegenseitig
% schlagen können. Der Algorithmus arbeitet dabei mit Ausprobieren, was
% bedeutet das mit steigendem N der Rechaufwand exponentiell steigt. Sollte
% das aufstellen nicht möglich sein gibt die Funktion 0 zurück.
% Autor: Matthias Bosewitz
% 2. Übung zur Vorlesung CoMa I
% Aufgabe 3: "Damenproblem"

% Funktionsskizze:
%  _________
% |x        |   
% |      x  |
% |  x      |
% |        x|
% |____x____|
%  1 2 3 4 5  = X
% [1 3 5 2 4] = Y

function Feld = damenproblem(N)

Feld = 0;           % Startwert: 0
MaxY = ceil(N/2);   % Maximaler Wert der ersten Zeile

if N <= 0           % Fehlerhafte Größe ...
  return;           % Funktion beenden
end

Y = zeros(1,N);     % Y-Werte jeder Spalte an denen sich die Damen befinden
Y(1) = 1;           % Man beginnt mit oben links
X    = 2;           % zweites testen (wenn es das denn gibt)


while X <= N        % Solange man noch Damen unterbringen muss
  
  Y(X) = Y(X) + 1;  % Nächstes testen
  
  if X == 1 && Y(1) > MaxY      % Wenn man schon die obere Hälfte getestet hat ...
    return;                     % ... ist die andere Spiegelbildlich und muss ...
  end                           % nicht mehr getestet werden -> Unmöglich
  
  if Y(X) > N       % Unmöglich hohe Y-Position
    Y(X) = 0;       % Zurücksetzen
    X    = X-1;     % vorheriges X nochmal bearbeiten
    if X < 1        % Es gibt wohl keine Lösung ...
      return;       % ... Es wird die 0 (Unmöglich) zurückgegeben
    end

  % Vertikales Schlagen ist schon durch die Definition unmöglich
  elseif sum(Y(X) == Y(1:X)) == 1   % Wenn man nicht horizontal schlagen kann ...
    if (sum(Y(X)-X == Y(1:X)-(1:X)) == 1) && (sum(Y(X)+X == Y(1:X)+(1:X)) == 1) % Wenn man nicht diagonal schlagen kann ...
      X = X+1;      % Das geht, also geht man weiter
      % Y             % Ausgeben
    end
  end
  
end


Feld = zeros(N);     % leeres N x N - Feld erstellen
for i=1:N            % Muss man leider mit einer For-Schleife machen (Gehts auch anders?)
  Feld(Y(i),i) = 1;  % Die Damen (1) auf das Feld setzen 
end

end             % zwar optional aber doch von der Notation her logischer
