13-Loesung.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Minesweeper\n",
    "### - Lösung - "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Minesweeper\n",
    "\n",
    "In dieser Aufgabe sollt ihr einen Algorithmus entwickeln, der Minesweeper spielen kann. Hier findet ihr weitere Informationen zum Spiel: https://de.wikipedia.org/wiki/Minesweeper.\n",
    "\n",
    "Unter diesem Link könnt ihr das Spiel ausprobieren: http://minesweeperonline.com/#beginner.\n",
    "\n",
    "### Spielablauf\n",
    "\n",
    "<img src=\"https://cdn.windowsreport.com/wp-content/uploads/2012/10/minesweeper.png\" alt=\"Minesweeper\" width=\"600\"/>\n",
    "\n",
    "Minesweeper ist ein einfaches Denkspiel, das bekannt wurde, da es mit Microsoft Windows mitgeliefert wurde. Das Spielfeld ist in Zellen unterteilt; je nach Schwierigkeitsgrad gibt es mehr oder weniger Zellen. Im Spielfeld wird eine Anzahl Minen zufällig verteilt; auch diese Anzahl bestimmt den Schwierigkeitsgrad. Minesweeper wird mit der Maus gespielt: mit einem Linksklick deckt man eine Zelle auf und mit einem Rechtsklick markiert man eine Zelle mit einer Fahne.\n",
    "\n",
    "Wenn man eine Zelle aufdeckt, kann diese eine Mine enthalten, oder auch nicht. Deckt man eine Zelle auf, die keine Mine enthält, so wird eine Zahl sichtbar. Diese gibt an, wie viele Minen sich in der Nachbarschaft befinden. Die Zellen, in denen Minen versteckt sind, müssen nun durch Kombinatorik der aufgedeckten Zahlen gefunden und mit Fahnen markiert werden. Hat man alle Minen korrekt markiert, so ist das Spiel gewonnen. Deckt man jedoch eine Mine auf, so hat man sofort verloren.\n",
    "\n",
    "Beim ersten Klicken kann man niemals eine Mine aufdecken, da die Minen erst danach zufällig platziert werden.\n",
    "\n",
    "Oft kann man durch Kombinieren verschiedener Zahlen herausfinden, wo eine Mine sein muss, oder ob ein Feld minenfrei ist. Es kann jedoch auch vorkommen, dass man durch die Zahlen nicht zweifelsfrei feststellen kann, ob sich eine Mine unter einem Feld befindet. In diesem Fall muss man raten, doch dazu später mehr.\n",
    "\n",
    "Zellen in der Mitte des Spielfelds haben 8 Nachbarn und können somit 0 bis 8 Minen in der Umgebung haben. Zellen am Rand oder in der Ecke des Spielfelds haben weniger Nachbarn (5 oder 3) und können dementsprechend auch 0 bis 5 oder 0 bis 3 Minen in der Nachbarschaft haben. Das Spielfeld bei Minesweeper geht also ***nicht*** über die Ränder hinaus und ***nicht*** auf der anderen Seite weiter.\n",
    "\n",
    "### Installation\n",
    "\n",
    "Für diese Aufgabe verwenden wir wieder eine lokale Python-Installation, wie sie auch schon für die Aufgaben \"Breakout\" und \"Gravitationssimulation\" verwendet wurde. Die Installationsanleitung haben wir noch einmal hier angehängt:\n",
    "\n",
    "Möglicherweise funktioniert Python 3 auf deinem System bereits. Du musst Python 3 für diese Aufgabe verwenden, denn der Umgang mit Sonderzeichen (Umlaute etc.) ist in Python 2 nicht besonders komfortabel. Überprüfe zunächst deine Python Version; dazu musst du zunächst ein Terminal öffnen:\n",
    " - Windows: öffne das Startmenü, indem du die \"Windows\"-Taste drückst. Suche dann nach \"cmd\" und starte die \"Eingabeaufforderung\" (\"cmd.exe\").\n",
    " - MacOS: Öffne ein Terminal, indem du \"Command+Leertaste\" drückst und nach \"Terminal\" suchst. Starte das Terminal mit einem Doppelklick.\n",
    " - Linux: öffne ein Terminal (auf Ubuntu und ähnlichen Systemen mit \"Strg+Alt+T\", auf kde-Systemen mit \"Alt+F2\" und gib dann \"konsole\" ein).\n",
    "\n",
    "Führe dann den folgenden Befehl aus: \"python3 --version\" (oder wenn dies eine Fehlermeldung wirft, versuche es mit \"python --version\"). Wenn du bei einem der Befehle keine Fehlermeldung bekommst und in der Konsole etwas ähnliches steht wie \"Python 3.7.5\", kannst du den dazugehörigen Befehl ab nun zum Starten von Python 3 verwenden. Wichtig: wenn hier etwas wie \"Python 2.7.17\" steht, hast du eine Installation der Version 2, welche für die Aufgabe nicht verwendet werden kann. Wenn du beidesmal eine Fehlermeldung bekommst, gehe direkt zur Installation.\n",
    "\n",
    "Ab hier wird die Aufgabe mit dem Befehl \"python3\" gestellt, auf deinem System kann aber auch der Befehl \"python\" die korrekte Installation der Version 3 starten (wie zuvor beschrieben).\n",
    "\n",
    "Führe nun den folgenden Befehl aus, um zu testen, ob du das GUI-Toolkit Tkinter installiert hast: \"python3 -m tkinter\". Wenn du ein kleines Testfenster siehst, hast du Python und Tkinter bereits korrekt installiert.\n",
    "\n",
    "Wenn du eine Fehlermeldung bekommen hast, lade dir Python (mit Tkinter) kostenfrei hier herunter:\n",
    " - Windows: https://www.python.org/ftp/python/3.8.2/python-3.8.2-amd64.exe\n",
    " - MacOS: https://www.python.org/ftp/python/3.8.2/python-3.8.2-macosx10.9.pkg\n",
    " - Linux: auf den meisten Linux-Systemen ist Python bereits vorinstalliert. Jedoch fehlt meistens das Modul \"tkinter\". Auf Ubuntu-ähnlichen Systemen kannst du dieses mit diesem Befehl nachinstallieren: \"sudo apt-get install python3-tk\". Für andere Linux-Systeme, folge bitte diesen Lösungsvorschlägen: https://stackoverflow.com/questions/4783810/install-tkinter-for-python\n",
    "\n",
    "Jetzt sollte deine Python 3-Installation mit Tkinter funktionieren. Um dies zu testen, kopiere die folgende Vorlage in eine neue leere Datei \"minesweeper.py\". Achte darauf, dass du in deinem Editor zum Abspeichern \"UTF-8\" als Encoding verwendest, sonst funktionieren die Umlaute und Sonderzeichen in der deutschen Sprache nicht.\n",
    "\n",
    "Mögliche Editoren zum Bearbeiten von Python-Skripten sind etwa: PyCharm, Notepad++, Sublime Text, Atom Editor, Eclipse mit Python Plugins, vim (Linux und MacOS), gedit (Linux). Aber die Wahl deines Lieblingseditors steht dir frei.\n",
    "\n",
    "Auf Windows solltest du die Datei mit einem Doppelklick ausführen können. Auf anderen Systemen musst du mit dem Terminal in das Verzeichnis wechseln, in dem diese neue Datei liegt. Das kannst du mit dem Befehl \"cd </vollständiger/Pfad/zu/der/Datei>\" machen. Dann kannst du die Datei mit \"python3 breakout.py\" ausführen. Achte darauf, dass du Python 3 verwendest.\n",
    "\n",
    "Wenn alles richtig installiert ist, erscheint ein Fenster, in dem das Spiel dargestellt wird.\n",
    "\n",
    "Du musst den Code in der Datei \"minesweeper.py\" erweitern."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aufgabe\n",
    "In der Vorlage ist ein spielbares Minesweeper Spiel gegeben, das du auch zunächst ausprobieren und spielen kannst. Mit der Taste \"R\" kannst du ein neues Spiel starten und mit der Taste \"A\" die Funktion aufrufen, in der du den Algorithmus entwickeln sollst.\n",
    "\n",
    "### Dazu etwas Theorie\n",
    "Es gibt verschiedenste Situationen in Minesweeper, und oft ist es nicht klar, wo sich die Minen befinden.\n",
    "\n",
    "Ein wiederkehrendes Muster beim Spielen ist folgendes: eine Zelle muss eine Mine enthalten, da eine Nachbarzelle, die nur über eine Ecke verbunden ist, eine Zahl anzeigt, die eine Mine in dieser Zelle erzwingt.\n",
    "\n",
    "![Minesweeper-Ecke](http://caeze.bplaced.net/bwki/minesweeper-ecke.png)\n",
    "\n",
    "Da somit die Zahlen mancher der Nachbarzellen \"erfüllt\" sind, können auch diese aufgedeckt werden. Es muss also, so lange das Spiel nicht gewonnen wurde, für alle Zellen überprüft werden, ob sie sicher eine Mine sind, oder sicher aufgedeckt werden können. Die Regeln, die ein sicheres Markieren oder Aufdecken ermöglichen sollst du in dieser Aufgabe herausfinden und implementieren. Diese Aufgabe ist also wieder eine Knobelaufgabe, es gibt verschiedenste Wege, einen solchen Algorithmus zu entwickeln.\n",
    "\n",
    "Jedoch kann es auch Situationen geben, bei denen man raten muss. Schau dir dazu die folgenden Bilder an.\n",
    "\n",
    "![Minesweeper-Ecke](http://caeze.bplaced.net/bwki/minesweeper.png)\n",
    "\n",
    "In der untersten Reihe der Zellen kann man nur raten, welche der beiden Möglichkeiten (Minen in den roten oder gelben Zellen) die tatsächlich auftretende ist.\n",
    "![Minesweeper-Ecke](http://caeze.bplaced.net/bwki/minesweeper-1.png)\n",
    "![Minesweeper-Ecke](http://caeze.bplaced.net/bwki/minesweeper-2.png)\n",
    "\n",
    "Man muss also auf gut Glück eine Zelle aufdecken und danach wieder kombinatorisch weiter machen.\n",
    "\n",
    "In einem solchen Fall darf dein Algorithmus selber eine Entscheidung treffen oder aber einfach anhalten, so dass die Spielerin oder der Spieler die Entscheidung treffen muss. Die Entscheidung kann ja natürlich auch schief gehen, und dann ist das Spiel vorbei...\n",
    "\n",
    "Wir sind gespannt auf eure Ideen, aber wir schätzen die Aufgabe als nicht ganz so einfach ein. Viel Spaß beim Knobeln und Tüfteln! Ihr dürft beliebig Funktionen definieren, um euren Algorithmus zu strukturieren und euch die Arbeit zu erleichtern."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Das ist die Vorlage, die du in die neue leere Datei \"minesweeper.py\" kopieren kannst.\n",
    "\n",
    "# Hier kannst du eine Online-Version von Minesweeper ausprobieren:\n",
    "# http://minesweeperonline.com/#beginner\n",
    "\n",
    "# Das Encoding muss UTF-8 sein wegen der Sonderzeichen in der deutschen Sprache:\n",
    "# -*- coding: utf-8 -*-\n",
    "\n",
    "################################################################################\n",
    "## Unterhalb dieser Linie kannst du deinen Algorithmus implementieren.        ##\n",
    "################################################################################\n",
    "\n",
    "# Die Konstanten, wie groß das Spielfeld ist und wie viele Minen darin enthalten\n",
    "# sind, werden beim Start des Spiels in der Konsole ausgegeben.\n",
    "\n",
    "# In dieser Funktion soll dein Algorithmus zur automatischen Lösung von\n",
    "# Minesweeper implementiert werden.\n",
    "# Wenn du die Taste \"A\" im Spielfenster drückst, wird diese Funktion aufgerufen.\n",
    "# Das erste Feld kannst du zufällig aufdecken, da man beim ersten Zug nicht\n",
    "# verlieren kann. Danach musst du dir eine Strategie überlegen\n",
    "def automatische_lösung():\n",
    "    print(\"Jetzt löst der Algorithmus das Spiel.\")\n",
    "    \n",
    "    # dein Algorithmus kann Felder aufdecken und markieren\n",
    "    # welches Feld zuerst aufgedeckt wird, ist nicht wirklich entscheidend\n",
    "    \n",
    "    # beispielsweise:\n",
    "    s = spielfeld_zusammenfassung()\n",
    "    decke_auf(s[31])\n",
    "    markiere(s[63])\n",
    "        \n",
    "    # dein Algorithmus soll so lange weiter spielen, bis er gewonnen hat\n",
    "    # wenn er an eine Stelle kommt, an der man raten muss, kann das auch\n",
    "    # der Spielerin oder dem Spieler überlassen werden\n",
    "    \n",
    "    # beispielsweise:\n",
    "    while not bereits_gewonnen() and not bereits_verloren():\n",
    "        # mit der Funktion 'time.sleep(0.5)' kannst du eine halbe Sekunde warten,\n",
    "        # so dass du sehen kannst, wie dein Algorithmus arbeitet.\n",
    "        time.sleep(0.5)\n",
    "        \n",
    "        # du kannst den folgenden Hinweis entfernen, wenn du anfängst, deinen Algorithmus zu implementieren:\n",
    "        print(\"Achtung: wenn du noch nichts implementiert hast, ist das hier eine Dauerschleife!\")\n",
    "\n",
    "# Diese Funktion gibt eine Datenstruktur zurück, die nur das enthält, was\n",
    "# menschliche Spieler auch sehen können.\n",
    "# Nur mit dieser Funktion darf dein Algorithmus das Spielfeld betrachten!\n",
    "# Du darfst alle Attribute, die die Klasse \"ZelleAlgorithmus\" besitzt, verwenden.\n",
    "def spielfeld_zusammenfassung():\n",
    "    spielfeld = []\n",
    "    for zelle in zellen:\n",
    "        z = ZelleAlgorithmus(zelle.x, zelle.y, zelle.markiert, zelle.aufgedeckt, zelle.minen_in_nachbarschaft)\n",
    "        spielfeld.append(z)\n",
    "    return spielfeld\n",
    "\n",
    "# Mit dieser Funktion kannst dein Algorithmus auf eine Zelle \"klicken\"\n",
    "def decke_auf(zelle):\n",
    "    zelle.decke_auf()\n",
    "\n",
    "# Mit dieser Funktion kannst dein Algorithmus eine Zelle mit einer Flagge markieren\n",
    "def markiere(zelle):\n",
    "    zelle.markiere()\n",
    "\n",
    "# Mit dieser Funktion kann dein Algorithmus abfragen, ob er das Spiel bereits gelöst hat\n",
    "def bereits_gewonnen():\n",
    "    return gewonnen\n",
    "\n",
    "# Mit dieser Funktion kann dein Algorithmus abfragen, ob er bereits gescheitert ist\n",
    "def bereits_verloren():\n",
    "    return verloren\n",
    "\n",
    "################################################################################\n",
    "## Der Code unterhalb dieser Linie ist für deinen Algorithmus nicht sichtbar! ##\n",
    "## Du kannst natürlich nachvollziehen, wie das Spiel implementiert ist, aber  ##\n",
    "## du darfst für deinen Algorithmus nur die Funktionen oberhalb dieser Linie  ##\n",
    "## verwenden! Es wäre ja keine besonders schwere Aufgabe, wenn du nachschauen ##\n",
    "## könntest, ob in einer bestimmten Zelle eine Mine versteckt ist...          ##\n",
    "################################################################################\n",
    "\n",
    "# importiere benötigte Module\n",
    "from tkinter import *\n",
    "import random\n",
    "import math\n",
    "import time\n",
    "\n",
    "# einige Konstanten für benötigte Größen\n",
    "zellen_breite_px = 20\n",
    "zellen_höhe_px = 20\n",
    "anzahl_zellen_x = 8\n",
    "anzahl_zellen_y = 8\n",
    "fenster_breite = max(400, zellen_breite_px * anzahl_zellen_x)\n",
    "fenster_höhe = 50 + zellen_höhe_px * anzahl_zellen_y\n",
    "abstand_x = (fenster_breite - zellen_breite_px * anzahl_zellen_x) / 2\n",
    "abstand_y = 2\n",
    "\n",
    "# die Minen\n",
    "anzahl_minen = int(anzahl_zellen_x * anzahl_zellen_y / 8)\n",
    "zellen = []\n",
    "\n",
    "# worauf zeigt der Mauszeiger gerade?\n",
    "maus_über_zelle = None\n",
    "\n",
    "# der Zähler für die Spielzeit benötigt eine Variable\n",
    "startzeit = 0\n",
    "\n",
    "# wenn das Spiel verloren ist, wird diese Variable zu True\n",
    "verloren = False\n",
    "\n",
    "# wenn das Spiel gewonnen ist, wird diese Variable zu True\n",
    "gewonnen = False\n",
    "\n",
    "# wenn das Spiel gewonnen ist, beinhaltet diese Variable die\n",
    "# Zeit, die dafür gebraucht wurde\n",
    "gewonnen_zeit = -1\n",
    "    \n",
    "# zähle die markierten Zellen\n",
    "anzahl_markierte = 0\n",
    "    \n",
    "# zu Beginn gibt es noch keine Minen, so dass man nicht am Anfang gleich verlieren kann\n",
    "noch_nicht_geklickt = True\n",
    "\n",
    "# diese Klasse enthält die Information, die der Algorithmus über eine Zelle wissen darf\n",
    "# auch leiten die Funktionen \"decke_auf()\" und \"markiere()\" auf die Funktionen\n",
    "# der \"echten\" Zellen weiter\n",
    "class ZelleAlgorithmus:\n",
    "    def __init__(self, x, y, markiert, aufgedeckt, minen_in_nachbarschaft):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.markiert = markiert\n",
    "        self.aufgedeckt = aufgedeckt\n",
    "        self.minen_in_nachbarschaft = minen_in_nachbarschaft\n",
    "        \n",
    "    def decke_auf(self):\n",
    "        for zelle in zellen:\n",
    "            if zelle.x == self.x and zelle.y == self.y:\n",
    "                zelle.decke_auf()\n",
    "    \n",
    "    def markiere(self):\n",
    "        for zelle in zellen:\n",
    "            if zelle.x == self.x and zelle.y == self.y:\n",
    "                zelle.markiere()\n",
    "\n",
    "# diese Klasse enthält alle Informationen, die eine Zelle ausmachen\n",
    "class Zelle:\n",
    "    def __init__(self, x, y, mine):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.mine = mine\n",
    "        self.markiert = False\n",
    "        self.aufgedeckt = False\n",
    "        self.minen_in_nachbarschaft = 0\n",
    "        \n",
    "    def findeAlleNachbarn(self):\n",
    "        nachbarn = []\n",
    "        koordinaten_nachbarn_x = [self.x - 1, self.x, self.x + 1]\n",
    "        koordinaten_nachbarn_y = [self.y - 1, self.y, self.y + 1]\n",
    "        for y in koordinaten_nachbarn_y:\n",
    "            for x in koordinaten_nachbarn_x:\n",
    "                if not (x == self.x and y == self.y) and x >= 0 and y >= 0 and x < anzahl_zellen_x and y < anzahl_zellen_y:\n",
    "                    nachbarn.append(zellen[x + anzahl_zellen_y * y])\n",
    "        return nachbarn\n",
    "        \n",
    "    def berechneAnzahlMinenInNachbarschaft(self):\n",
    "        self.minen_in_nachbarschaft = 0\n",
    "        for nachbar_zelle in self.findeAlleNachbarn():\n",
    "            if nachbar_zelle.mine and not self.mine:\n",
    "                self.minen_in_nachbarschaft += 1\n",
    "    \n",
    "    # decke, wenn es eine Zelle ohne Minen in der Nachbarschaft ist,\n",
    "    # rekursiv auch benachbarte Zellen auf, die ebenfalls keine Mine in der\n",
    "    # Nachbarschaft haben\n",
    "    def decke_auf(self):\n",
    "        global verloren\n",
    "        global noch_nicht_geklickt\n",
    "        if self.markiert:\n",
    "            return\n",
    "        self.aufgedeckt = True\n",
    "        if noch_nicht_geklickt:\n",
    "            noch_nicht_geklickt = False\n",
    "            initialisiere_minen(self)\n",
    "        elif self.mine:\n",
    "            verloren = True\n",
    "        if self.minen_in_nachbarschaft == 0:\n",
    "            for nachbar_zelle in self.findeAlleNachbarn():\n",
    "                if not nachbar_zelle.aufgedeckt and not nachbar_zelle.mine:\n",
    "                    nachbar_zelle.decke_auf()\n",
    "    \n",
    "    def markiere(self):\n",
    "        global anzahl_markierte\n",
    "        if self.aufgedeckt:\n",
    "            return\n",
    "        if self.markiert:\n",
    "            self.markiert = False\n",
    "            anzahl_markierte -= 1\n",
    "        elif anzahl_markierte < anzahl_minen:\n",
    "            self.markiert = True\n",
    "            anzahl_markierte += 1\n",
    "\n",
    "def initialisiere():\n",
    "    # mache die benötigten Variablen sichtbar\n",
    "    global verloren\n",
    "    global gewonnen\n",
    "    global gewonnen_zeit\n",
    "    global anzahl_markierte\n",
    "    global noch_nicht_geklickt\n",
    "    global maus_über_zelle\n",
    "    \n",
    "    # beim Neustart ist das Spiel nicht verloren und nicht gewonnen\n",
    "    verloren = False\n",
    "    gewonnen = False\n",
    "    \n",
    "    # initialisiere weitere Variablen neu\n",
    "    gewonnen_zeit = -1\n",
    "    noch_nicht_geklickt = True\n",
    "    maus_über_zelle = None\n",
    "    anzahl_markierte = 0\n",
    "    \n",
    "    # leere die Liste der Zellen, um sie zunächst ohne Minen neu zu initialisieren\n",
    "    zellen.clear()\n",
    "    for y in range(anzahl_zellen_y):\n",
    "        for x in range(anzahl_zellen_x):\n",
    "            zelle = Zelle(x, y, False)\n",
    "            zellen.append(zelle)\n",
    "\n",
    "# in der Umgebung der zuerst angeklickten Zelle darf es keine Minen geben\n",
    "# nur so hat man einen Startpunkt\n",
    "def initialisiere_minen(zuerst_angeklickte_zelle):\n",
    "    global startzeit\n",
    "    # speichere die Unixzeit zu der Zeit, als das Spiel neu gestartet wurde\n",
    "    startzeit = time.time()\n",
    "\n",
    "    # erstelle eine Liste, so dass jede Zelle ein Element erhält\n",
    "    # setze die ersten Elemente darin auf 1, so dass insgesamt\n",
    "    # \"anzahl_minen\" Elemente den Wert 1 haben\n",
    "    minen_in_feld = []\n",
    "    for i in range(anzahl_zellen_x * anzahl_zellen_y):\n",
    "        if i < anzahl_minen:\n",
    "            minen_in_feld.append(1)\n",
    "        else:\n",
    "            minen_in_feld.append(0)\n",
    "            \n",
    "    def mine_in_umgebung(x, y):\n",
    "        umgebung = 2\n",
    "        for j in range(y - umgebung, y + umgebung):\n",
    "            for i in range(x - umgebung, x + umgebung):\n",
    "                if minen_in_feld[i + j * anzahl_zellen_y] == 1:\n",
    "                    return True\n",
    "    \n",
    "    # verteile die Minen zufällig\n",
    "    random.shuffle(minen_in_feld)\n",
    "    while mine_in_umgebung(zuerst_angeklickte_zelle.x, zuerst_angeklickte_zelle.y):\n",
    "        # verteile die Minen zufällig\n",
    "        random.shuffle(minen_in_feld)\n",
    "    \n",
    "    # leere die Liste der Zellen, um sie nun mit Minen neu zu initialisieren\n",
    "    zellen.clear()\n",
    "    for y in range(anzahl_zellen_y):\n",
    "        for x in range(anzahl_zellen_x):\n",
    "            zelle = Zelle(x, y, minen_in_feld[x + y * anzahl_zellen_y] == 1)\n",
    "            zellen.append(zelle)\n",
    "    \n",
    "    # berechne auch für alle Zellen, wie viele Minen sich in der Nachbarschaft bfinden\n",
    "    # das ist die Zahl, die auf der Zelle beim Aufdecken angezeigt wird\n",
    "    for z in zellen:\n",
    "        z.berechneAnzahlMinenInNachbarschaft()\n",
    "\n",
    "# diese Funktion wird jeden Zeitschritt aufgerufen,\n",
    "# das Spiel ist also eine Simulation\n",
    "def zeitschritt():\n",
    "    # mache die benötigten Variablen sichtbar\n",
    "    global gewonnen\n",
    "    global gewonnen_zeit\n",
    "    \n",
    "    # die Zeichenfläche leeren\n",
    "    zeichenfläche.delete(\"all\")\n",
    "    \n",
    "    # alle Zellen zeichen\n",
    "    for z in zellen:\n",
    "        x = z.x * zellen_breite_px + abstand_x\n",
    "        y = z.y * zellen_höhe_px + abstand_y\n",
    "        if not z.aufgedeckt:\n",
    "            zeichenfläche.create_rectangle(x, y, x + zellen_breite_px, y + zellen_höhe_px, fill='gray')\n",
    "        else:\n",
    "            zeichenfläche.create_rectangle(x, y, x + zellen_breite_px, y + zellen_höhe_px, fill='light gray')\n",
    "        \n",
    "        # zeichne aufgedeckte Felder\n",
    "        if z.aufgedeckt and z.minen_in_nachbarschaft > 0:\n",
    "            zeichenfläche.create_text(x + zellen_breite_px / 2, y + zellen_höhe_px / 1.5, text=str(z.minen_in_nachbarschaft), font=('Helvetica', 15, 'bold'), justify=CENTER)\n",
    "        \n",
    "        # zeichne minen\n",
    "        if verloren and z.mine:\n",
    "            zeichenfläche.create_text(x + zellen_breite_px / 2, y + zellen_höhe_px, text=\"*\", font=('Helvetica', 20, 'bold'), justify=CENTER)\n",
    "        \n",
    "        # zeichne markierte Felder\n",
    "        if z.markiert:\n",
    "            zeichenfläche.create_text(x + zellen_breite_px / 2, y + zellen_höhe_px / 1.5, text=\"~\", font=('Helvetica', 15, 'bold'), justify=CENTER)\n",
    "    \n",
    "    # male die Zelle, über der die Maus ist, in einer anderen Farbe\n",
    "    if maus_über_zelle != None:\n",
    "        x = maus_über_zelle.x * zellen_breite_px + abstand_x\n",
    "        y = maus_über_zelle.y * zellen_höhe_px + abstand_y\n",
    "        zeichenfläche.create_rectangle(x, y, x + zellen_breite_px, y + zellen_höhe_px, fill='snow3', stipple='gray25')\n",
    "    \n",
    "    # überprüfe, ob das Spiel gewonnen ist\n",
    "    korrekt_markierte_minen = 0\n",
    "    for z in zellen:\n",
    "        if z.mine and z.markiert:\n",
    "            korrekt_markierte_minen += 1\n",
    "\n",
    "    # ist das Spiel bereits gewonnen?\n",
    "    if not gewonnen and korrekt_markierte_minen == anzahl_minen:\n",
    "        gewonnen = True\n",
    "           \n",
    "    # überprüfe, ob das Spiel gewonnen ist\n",
    "    anzahl_aufgedeckter_felder = 0\n",
    "    for z in zellen:\n",
    "        if z.aufgedeckt:\n",
    "            anzahl_aufgedeckter_felder += 1\n",
    "\n",
    "    # ist das Spiel bereits gewonnen?\n",
    "    if not gewonnen and anzahl_aufgedeckter_felder == anzahl_zellen_x * anzahl_zellen_y - anzahl_minen:\n",
    "        gewonnen = True\n",
    "    \n",
    "    # wenn das Spiel gewonnen ist, löse es auf\n",
    "    if gewonnen and not verloren:\n",
    "        for z in zellen:\n",
    "            if not z.mine:\n",
    "                z.aufgedeckt = True\n",
    "            else:\n",
    "                z.markiert = True\n",
    "    \n",
    "    # zeige die Spielinformation an\n",
    "    spielzeit = 0\n",
    "    if not noch_nicht_geklickt:\n",
    "        spielzeit = int(time.time() - startzeit)\n",
    "    nachricht = str(anzahl_minen - anzahl_markierte) + \" Minen verbleiben | <R> für Neustart | Spielzeit: \" + str(spielzeit) + \" s\"\n",
    "    if verloren:\n",
    "        nachricht = str(anzahl_minen - anzahl_markierte) + \" Minen verbleiben | <R> für Neustart | Verloren!\"\n",
    "    if gewonnen:\n",
    "        if gewonnen_zeit < 0:\n",
    "            gewonnen_zeit = spielzeit\n",
    "        nachricht = str(anzahl_minen - anzahl_markierte) + \" Minen verbleiben | <R> für Neustart | >>>Gewonnen<<<: \" + str(gewonnen_zeit) + \" s\"\n",
    "    nachricht += \"\\n <A> zum Start der automatischen Lösung\"\n",
    "    zeichenfläche.create_text(fenster_breite / 2, fenster_höhe - 21, text=nachricht, font=('Helvetica', 10, 'bold'), justify=CENTER)\n",
    "    \n",
    "    # zeichne die Zeichenfläche neu\n",
    "    zeichenfläche.update()\n",
    "\n",
    "    # einen Timer starten, dass die Funktion \"zeitschritt\" nach einigen Millisekunden erneut aufgerufen wird\n",
    "    # das ist das Herzstück der Simulation\n",
    "    fenster.after(10, zeitschritt)\n",
    "\n",
    "# verschiebe das Fenster in die Bildschirmmitte\n",
    "def zentriereFenster(fenster):\n",
    "    fenster.update_idletasks()\n",
    "    b = fenster.winfo_width()\n",
    "    h = fenster.winfo_height()\n",
    "    x = (fenster.winfo_screenwidth() // 2) - (b // 2)\n",
    "    y = (fenster.winfo_screenheight() // 2) - (h // 2)\n",
    "    fenster.geometry('{}x{}+{}+{}'.format(b, h, x, y))\n",
    "\n",
    "# werte die auf der Tastatur gedrückte Taste aus\n",
    "def tastatur_event(event):\n",
    "    taste = event.keysym\n",
    "    if taste == 'r':\n",
    "        initialisiere()\n",
    "    if taste == 'a':\n",
    "        automatische_lösung()\n",
    "\n",
    "# werte die auf der Maus gedrückte Taste aus\n",
    "def maus_links_gedrückt(event):\n",
    "    pass\n",
    "\n",
    "# werte die auf der Maus gedrückte Taste aus\n",
    "def maus_links_losgelassen(event):\n",
    "    if maus_über_zelle != None and not verloren and not gewonnen:\n",
    "        maus_über_zelle.decke_auf()\n",
    "\n",
    "# werte die auf der Maus gedrückte Taste aus\n",
    "def maus_rechts_gedrückt(event):\n",
    "    pass\n",
    "\n",
    "# werte die auf der Maus gedrückte Taste aus\n",
    "def maus_rechts_losgelassen(event):\n",
    "    if maus_über_zelle != None and not verloren and not gewonnen:\n",
    "        maus_über_zelle.markiere()\n",
    "\n",
    "# bestimme, auf welche der Zellen die Maus gerade zeigt\n",
    "def maus_bewegung(event):\n",
    "    global maus_über_zelle\n",
    "    maus_über_zelle = None\n",
    "    x_pos_maus = event.x\n",
    "    y_pos_maus = event.y\n",
    "    for z in zellen:\n",
    "        x = z.x * zellen_breite_px + abstand_x\n",
    "        y = z.y * zellen_höhe_px + abstand_y\n",
    "        maus_darüber = True\n",
    "        maus_darüber = maus_darüber and x <= x_pos_maus\n",
    "        maus_darüber = maus_darüber and x_pos_maus <= x + zellen_breite_px\n",
    "        maus_darüber = maus_darüber and y <= y_pos_maus\n",
    "        maus_darüber = maus_darüber and y_pos_maus <= y + zellen_höhe_px\n",
    "        if maus_darüber:\n",
    "            maus_über_zelle = z\n",
    "            return\n",
    "\n",
    "# öffne das Fenster, in dem das Spiel dargestellt wird\n",
    "fenster = Tk(className = ' Minesweeper ')\n",
    "zeichenfläche = Canvas(fenster, width=fenster_breite, height=fenster_höhe)\n",
    "zeichenfläche.pack()\n",
    "zentriereFenster(fenster)\n",
    "\n",
    "# gebe die Information über die Spielgröße und Anzahl an Minen aus\n",
    "print(\"Spielfeldgröße: \" + str(anzahl_zellen_x) + \"x\" + str(anzahl_zellen_y))\n",
    "print(\"Anzahl an Minen: \" + str(anzahl_minen))\n",
    "\n",
    "# binde die Eventhandler-Funktionen an das Fenster,\n",
    "# so dass diese bei Tasten- und Mausevents aufgerufen werden\n",
    "fenster.bind('<Key>', tastatur_event)\n",
    "fenster.bind('<ButtonPress-1>', maus_links_gedrückt)\n",
    "fenster.bind('<ButtonRelease-1>', maus_links_losgelassen)\n",
    "fenster.bind('<ButtonPress-3>', maus_rechts_gedrückt)\n",
    "fenster.bind('<ButtonRelease-3>', maus_rechts_losgelassen)\n",
    "fenster.bind('<Motion>', maus_bewegung)\n",
    "\n",
    "# initialisiere\n",
    "initialisiere()\n",
    "\n",
    "# starte die Simulation\n",
    "zeitschritt()\n",
    "\n",
    "# Tkinter behandelt Timer- und Tastaturevents in der Funktion \"mainloop()\"\n",
    "mainloop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fragen & Feedback:\n",
    "\n",
    "**Wenn ihr Fragen oder Anregungen zu der Aufgabe (oder Lösung) habt, dann tauscht euch gerne im [Chat](https://spectrum.chat/bwki/aufgabenarchiv/) darüber aus oder schreibt uns eine E-Mail (an info@bw-ki.de).**\n",
    "\n",
    "Wir freuen uns auch immer über **Feedback** (auch unter info@bw-ki.de):\n",
    "\n",
    "- War diese Aufgabe zu leicht, zu schwer oder genau richtig?\n",
    "- Wie lang hast du für diese Aufgabe ungefähr gebraucht?\n",
    "- Welche Art von Aufgaben wünschst du dir in Zukunft?"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:bwki_env]",
   "language": "python",
   "name": "conda-env-bwki_env-py"
  },
  "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.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}