380_backtracking.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Backtracking\n",
    "\n",
    "### 8-Damen Problem\n",
    "Wieviele Möglichkeiten gibt es, 8 Damen auf einem Schachbrett so zu positionieren, dass sie sich gegenseitig nicht bedrohen?\n",
    "- die Frage wurde 1848 in der Berliner Schachzeitung veröffentlicht.\n",
    "- 1850 wurde erstmals die richtige Antwort gegeben:  92\n",
    "\n",
    "\n",
    "Für 4 Damen stellen wir uns die Lösung dar als eine Liste x der Länge 4 vor, mit der\n",
    "Bedeutung: \n",
    "$x[i]$ ist die Spalte, in der wir die Dame in der i-ten Zeile\n",
    "plazieren.\n",
    "\n",
    "<img src=\"./img/backtrack1.png\" width=\"500\">\n",
    "\n",
    "\n",
    "$x = [1,3,0,2] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~   x = [2,0,3,1]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Backtracking\n",
    "\n",
    "**Backtracking** ist ein systematisches Ausprobieren. Wenn wir in eine\n",
    "Sackgasse geraten sind, gehen wir zurück (backtrack) und probieren\n",
    "die nächste Variante aus. Meistens sind alle möglichen Lösungen gefragt.\n",
    "\n",
    "Um festzustellen, ob ein Problem mit backtracking lösbar ist, sollten folgende Punkte\n",
    "geprüft werden.\n",
    "\n",
    "* Eine Lösung kann durch eine Liste $x$ repräsentiert werden.\n",
    "* Eine Lösung kann schrittweise aufgebaut werden $x[0], x[1], x[2], ....$\n",
    "* Im Moment k können wir alle Kandidaten für $x[k]$ aufzählen und testen, ob $x[k]$ zu einer Problemlösung führt, wenn die Werte\n",
    "$x[0], ..., x[k-1]$ bereits bestimmt wurden.\n",
    "* Wir können erkennen, ob $x[0],.....x[k]$ eine Problemlösung darstellt.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Struktur des rekursiven Backtracking Algorithmus\n",
    "\n",
    "```\n",
    " back(x, k): \n",
    "     für alle möglichen Kandidaten der Stufe k:\n",
    "         if kandidat ist gut (= er erweitert die Teillösung x[0]...x[k-1])\n",
    "             x.append(kandidat)\n",
    "             wenn fertig:         \n",
    "                 x als Lösung ausgeben\n",
    "             sonst:           \n",
    "                 back(x, k + 1)  # Teillösung um eins erweitern\n",
    "             x.pop()             # Platz für den nächsten Kandidaten\n",
    "             \n",
    "             \n",
    " Aufruf:\n",
    " back([],0)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Lösung des 8-Damen Problems\n",
    "\n",
    "<img src=\"./img/backtrack2.png\" width=\"400\">\n",
    "\n",
    "Damit die Damen sich nicht senkrecht bedrohen, muss gelten: $i \\ne j \\Rightarrow  x[i] \\ne x[j]$\n",
    "\n",
    "Damit die Damen sich nicht diagonal bedrohen, muss gelten: $ \\left| i-j\\right| \\ne \\left|x[i]-x[j]\\right|$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1. Loesung\n",
      "\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "2. Loesung\n",
      "\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "3. Loesung\n",
      "\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "4. Loesung\n",
      "\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "5. Loesung\n",
      "\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "6. Loesung\n",
      "\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "7. Loesung\n",
      "\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "8. Loesung\n",
      "\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "9. Loesung\n",
      "\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "10. Loesung\n",
      "\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "11. Loesung\n",
      "\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "12. Loesung\n",
      "\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "13. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "14. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "15. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "\n",
      "16. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "17. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "18. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "19. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "20. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "21. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "\n",
      "22. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "\n",
      "23. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "\n",
      "24. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "25. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "26. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "27. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "28. Loesung\n",
      "\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "29. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "30. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "\n",
      "31. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "\n",
      "32. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "33. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "\n",
      "34. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "35. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "36. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "\n",
      "37. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "\n",
      "38. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "39. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "\n",
      "40. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "41. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "42. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "\n",
      "43. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "\n",
      "44. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "45. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "46. Loesung\n",
      "\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "47. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "48. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "49. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "50. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "\n",
      "51. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "\n",
      "52. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "53. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "54. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "\n",
      "55. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "56. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "\n",
      "57. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "\n",
      "58. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "59. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "60. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "\n",
      "61. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "62. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "\n",
      "63. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "\n",
      "64. Loesung\n",
      "\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "65. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "66. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "67. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "68. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "69. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "70. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "\n",
      "71. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "\n",
      "72. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "\n",
      "73. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "74. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "75. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "76. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "77. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "78. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "\n",
      "79. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "80. Loesung\n",
      "\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "\n",
      "81. Loesung\n",
      "\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "82. Loesung\n",
      "\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "83. Loesung\n",
      "\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "84. Loesung\n",
      "\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "85. Loesung\n",
      "\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "86. Loesung\n",
      "\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "87. Loesung\n",
      "\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n",
      "88. Loesung\n",
      "\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "89. Loesung\n",
      "\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "90. Loesung\n",
      "\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "\n",
      "91. Loesung\n",
      "\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "\n",
      "92. Loesung\n",
      "\n",
      "|_|_|_|_|_|_|_|X|\n",
      "|_|_|_|X|_|_|_|_|\n",
      "|X|_|_|_|_|_|_|_|\n",
      "|_|_|X|_|_|_|_|_|\n",
      "|_|_|_|_|_|X|_|_|\n",
      "|_|X|_|_|_|_|_|_|\n",
      "|_|_|_|_|_|_|X|_|\n",
      "|_|_|_|_|X|_|_|_|\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def back(x,k):\n",
    "    '''\n",
    "    versucht die Teillösung in x, die aus den Elementen x[0] ... x[k-1] besteht,\n",
    "    um das Element x[k] zu erweitern\n",
    "    '''\n",
    "    for cand in range(anzahl_damen):\n",
    "        if isGood(x,k,cand):\n",
    "            x.append(cand)\n",
    "            if k == anzahl_damen-1:\n",
    "                loesungen.append(x[:])\n",
    "            else:\n",
    "                back(x,k+1)\n",
    "            x.pop()   # Platz für den nächsten Kandidaten\n",
    "\n",
    "def isGood(x,k,cand):\n",
    "    '''\n",
    "    prüft, ob der Kandidat cand die Teillösung x[0] ... x[k-1]\n",
    "    um ein Element erweitert.\n",
    "        '''\n",
    "    for j in range(k):\n",
    "        if x[j] == cand: return False\n",
    "        if k - j == abs(cand-x[j]): return False\n",
    "    return True\n",
    "\n",
    "def printLoesung(x):\n",
    "    '''\n",
    "    x:  Liste mit der Lösung\n",
    "    '''\n",
    "    n = len(x)   # Anzahl Damen\n",
    "    for j in range(n):\n",
    "        for i in range(n):\n",
    "            if x[j] == i: zeichen = 'X'\n",
    "            else: zeichen = '_'\n",
    "            print(\"|{0:s}\".format(zeichen),end='')\n",
    "        print('|')\n",
    "    print()\n",
    "\n",
    "\n",
    "loesungen = []             # Globale Variable zum sammeln der Lösungen\n",
    "anzahl_damen = 8\n",
    "back([],0)\n",
    "\n",
    "nr = 0\n",
    "for x in loesungen:\n",
    "    nr += 1\n",
    "    print(\"{}. Loesung\\n\".format(nr))\n",
    "    printLoesung(x)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Programmieraufgaben\n",
    "\n",
    "* *Türme*: Es sei ein quadratisches Schachbrett mit nxn Feldern gegeben. Bestimme alle\n",
    "  Möglichkeiten, wie man n Türme auf diesem Schachbrett positionieren kann,\n",
    "  so dass sich keine zwei Türme gegenseitig bedrohen.\n",
    "  \n",
    "* *Lagerfeuer*: In einer Jugendherberge organisiert man jeden Abend ein Lagerfeuer.\n",
    "Am ersten Abend setzen sich alle Jugendlichen\n",
    "rund ums Feuer. Am zweiten Abend nehmen sie so Platz, dass die,\n",
    " die am ersten Abend Nachbarn waren,\n",
    "diesmal nicht mehr Nachbarn sind. Bestimme alle Möglichkeiten,\n",
    "wie sie sich am zweiten Abend setzen können.\n",
    "\n",
    "* *Nikolaus*: Wieviele Möglichkeiten gibt es, das Haus vom Nikolaus zu zeichnen, wenn man\n",
    "unten links anfängt?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}