\documentclass{bschlangaul-aufgabe}
\bLadePakete{java}
\begin{document}
\bAufgabenMetadaten{
  Titel = {rekursives Backtracking},
  Thematik = {Methode „fill()“},
  Referenz = AUD.Algorithmenmuster.Backtracking.Methode-fill,
  RelativerPfad = Module/30_AUD/60_Algorithmenmuster/50_Backtracking/Aufgabe_Methode-fill.tex,
  ZitatSchluessel = aud:pu:3,
  ZitatBeschreibung = {Seite 2, Aufgabe 2},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Backtracking, Rekursion},
}

Folgende Methode soll das Feld $a$ (garantiert der Länge $2n$ und beim
ersten Aufruf von außen mit $0$ initialisiert) mittels rekursivem
Backtracking so mit Zahlen $1 \leq x \leq n$ befüllen, dass jedes $x$
genau zweimal in $a$ vorkommt und der Abstand zwischen den Vorkommen
genau $x$ ist. Sie soll genau dann \mintinline{java}|true| zurückgeben,
wenn es eine Lösung gibt.
\footcite[Seite 2, Aufgabe 2]{aud:pu:3}
\index{Backtracking}
\index{Rekursion}

\bPseudoUeberschrift{Beispiele:}

\begin{compactitem}
\item \mintinline{java}|fill(2, [])| $\rightarrow$ \mintinline{java}|false|
\item \mintinline{java}|fill(3, [])| $\rightarrow$ \mintinline{java}|[3; 1; 2; 1; 3; 2]|
\item \mintinline{java}|fill(4, [])| $\rightarrow$ \mintinline{java}|[4; 1; 3; 1; 2; 4; 3; 2]|
\end{compactitem}

\begin{minted}{java}
boolean fill (int n , int[] a) {
  if (n <= 0) {
    return true;
  }
  // TODO
  return false;
}
\end{minted}

\begin{bAntwort}
\bJavaDatei[firstline=4,lastline=21]{aufgaben/aud/muster/backtracking/RekursivesBacktracking}

\begin{minted}{md}
fill(0, []):
fill(1, []): false
fill(2, []): false
fill(3, []): 3 1 2 1 3 2
fill(4, []): 4 1 3 1 2 4 3 2
fill(5, []): false
fill(6, []): false
fill(7, []): 7 3 6 2 5 3 2 4 7 6 5 1 4 1
fill(8, []): 8 3 7 2 6 3 2 4 5 8 7 6 4 1 5 1
fill(9, []): false
fill(10, []): false
fill(11, []): 11 6 10 2 9 3 2 8 6 3 7 5 11 10 9 4 8 5 7 1 4 1
\end{minted}

\bPseudoUeberschrift{Kompletter Code}

\bJavaDatei{aufgaben/aud/muster/backtracking/RekursivesBacktracking}

\end{bAntwort}
\end{document}