Selbst wenn wir es nun geschafft haben, das Problem für die acht Damen zu lösen, beginnt unsere eigentliche Arbeit erst jetzt. Das Problem ist nämlich gut geeignet, die grundsätzliche Bedeutung der Frage der Lösbarkeit zu untersuchen und die reicht weiter als die Frage zur Lösung dieses einen Problems. Stellen wir die Frage nämlich etwas anders ...
Lassen sich auf einem quadratischen Spielfeld mit der Kantenlänge n, also n × n = n2 Feldern n Damen so platzieren, dass sie sich nicht gegenseitig bedrohen ? |
... dann bekommt das Problem eine ganz andere Bedeutung !
Im Programm ist der Schritt sehr leicht getan. Wir ersetzen zunächst überall die Zahl 8 durch eine Variable Maximal-Zahl , die wir im Programm dann global definieren. Ohne eines der Programme zu bemühen, kann man durch einfache Überlegungen herausbekommen, dass es für Werte von Maximal-Zahl unter 4 keine Lösung geben kann. Für Maximal-Zahl = 4 liefert aber auch unser allerschlechtestes Programm eine Lösung in akzeptabler Zeit, nur - wie wir gesehen haben - aber für Maximal-Zahl = 8 eben nicht mehr.
Dafür stellt sich aber die Frage nach der Lösbarkeit des Problems mit unserem optimierten Programm neu. Wir müssen auch für dieses neu austesten, ob es für größere Werte von Maximal-Zahl als 8 immer noch eine Lösung liefert ! Das Ergebnis dieser Untersuchung ist vielleicht enttäuschend oder unbefriedigend, aber es ist auch bedeutungsvoll. Es fordert nach einer Untersuchung des Laufzeitverhaltens der Verfahren und zu einer Neudefinition des Begriffes der Lösbarkeit.
Eine Kette von Programmen mit steigender Effizienz
für das Problem der Acht Damen