Du musst es dann ja nur ausprobieren 
Eigentlich ja und nein. 
In Teil (b) geht es ja so, wie es formuliert ist, nur um die „positiven“ Fälle. Allerdings steht ja in (a) das ⇔-Zeichen, und da hilft Nichtdeterminismus ja nicht.
Nun, im Zusammenhang unserer Vorlesung sind wir ja zuerst besonders daran interessiert gewesen, welche Probleme entscheidbar sind und welche nicht. Daß das 17x17-Problem (auch schon vor seiner Lösung im Frühjahr dieses Jahres) entscheidbar ist, war natürlich aus „theoretischer“, d.h. BFS-Sicht klar, da man einen deterministischen Algorithmus schreiben kann, der in endlicher (aber leider eben nicht erlebbarer) Zeit die richtige Antwort ausgibt. Bloß die Antwort der Entscheidungs-Turing-Maschine war unbekannt.
Ich stelle die Aufgabe gerne deswegen, weil man für ein winziges Problem sieht, daß man auch mit der tollsten Rechenpower nicht zu einem Ergebnis kommt, wenn man nicht über das Problem nachdenkt. Also, wie die Pädagogen sagen, man lernt, daß auch der Betriebsmitteleinsatz (hier die Rechenzeit im „Sekunden“-Sinn) und damit die Effizienz eines Algorithmus wichtig ist. Zusätzlich werden Sie erneut auf die Asymmetrie von Ja und Nein hingewiesen. Es ist ja kein Geheimnis (mehr ), daß bis 18 die Antwort Ja ist, ab dann muß sie Nein sein. Bei diesem Problem ist es nun so, daß Sie die Lösung für 16 vergleichsweise schnell finden, und sich dann an 17 und 18 die Zähne ausbeißen. Aber wie wollen Sie zeigen, daß die Formel Φ_{19} (aus (a)) nicht erfüllbar ist? Hier sind sie wieder in der Umgebung der P-NP-Frage, oder, genauer, der NP-CoNP-Frage. Das erste Bild dieses Threads zeigt die Lösung für 17, die können Sie ziemlich schnell als korrekt verifizieren (nur, wie kommen Sie drauf?). Sie sollen ja Ihre Lösungen (vermutlich bis 16) an Manuel Schmitt schicken, der hat einen Verifizierer geschrieben, der ganz schnell zeigt, ob ihre angebliche Lösung eine tatsächliche Lösung ist. Aber wie hilft Ihnen und uns allen das für den Fall 19? Nun, leider gar nicht. Man muß eben doch nachdenken, bzw. Forschung betreiben.
Wenn Ihr evolutionärer Algorithmus eine Lösung für 18 findet, dann muß der wirklich gut sein. Mit solchen Ansätzen hatte man es ja auch schon versucht. Das ist dann jedenfalls eine „Realisierung“ einer nichtdeterministischen Maschine, die versucht, „clever“ zu raten. In vielen Fällen bei hartnäckigen Problemen setzt man ja derartige Heuristiken ein, um Lösungen zu finden. Aber noch einmal: Den Nein-Fall kann ein evolutionärer Algorithmus nicht erkennen, der Antwort Nein des Algorithmus, wenn Sie ihn denn überhaupt terminieren lassen, kann man nicht glauben! Aber wie ja schon oben geschrieben, die Frage ist so formuliert, daß man weiß, daß es eine Lösung gibt, und eine solche soll berechnet werden.
Wenn Ihr Verfahren bis 16 (und vielleicht bis 17 oder 18) Lösungen berechnet, ist das eine „korrekte“ Abgabe! Daß Sie sich solche Gedanken machen, finde ich sehr gut! Diese Aufgabe hat eine ganz starke echte Forschungskomponente.
Wenn Sie mehr über evolutionäre Algorithmen erfahren wollen: Im kommenden Sommersemester biete ich die Vorlesung Organic Computing an, in der ein ganz großer Teil über natur-inspirierte Optimierung geht. In dem Teil stelle ich die sog. Partikelschwarm-Optimierung, Ameisen-Kolonie-Optimierung und eben evolutionäre/genetische Algorithmen vor. In den Übungen werde die auch implementiert und auf NP-vollständige Problem losgelassen.
Ich wünche ein frohes Fest!
Rolf Wanka
hrm, momentan brauch ich für 13x13 noch über eine Minute, das wird wohl erstmal nix mit 16x16