24-Stunden-Vorlesung 2006 revidiert: Grenzen des Computereinsatzes 1 Grenzen des Computereinsatzes oder Lutz Voelkel, Institut für Mathematik und Informatik

24-Stunden-Vorlesung 2006 revidiert: Grenzen des Computereinsatzes 1

Grenzen des Computereinsatzesoder

Lutz Voelkel, Institut für Mathematik und Informatik

der Universität Greifswald

(Der zweite Titel ist nicht von mir – er stammt aus dem Untertitel des Buches von Harel, siehe Folie 4)

Gliederung:1. Einführung (Folien 2 – 5)2. Allgemeine Probleme (Folie 6)3. Betrachtungen zur Komplexität und Effizienz (Folien 7 – 30) 3.1. Beispiel 2: Das Affenpuzzle (Folien 10 – 27) 3.2. Ausblick auf das P-NP-Problem (Folien 28 – 30)4. Schlußbemerkungen (Folie 31)Anhang 1: Ausblick auf die Kryptologie (Folien 32 – 33)Anhang 2: Mehr zum Sudoku-Spiel (Beispiel 3; Folien 34 – 40)

Bad news aus der Computerwelt


1. EinführungIn dem schönen Buch „Was ist Informatik?“ schreibt Peter Rechenberg im Abschnitt „Informatik als Schulfach?“ (Nr. 12.6, S. 292 in der 3. Auflage):

„Eine wünschenswerte Auswirkung der Beschäftigung mit Computern und Informatik in der Schule *) scheint mir vor allem in vier Dingen zu liegen:

– In der Einübung des algorithmischen Denkens,– in der Verwendung des Computers zur Simulation (als ausführbares Gedankenexperiment in den verschiedensten Fächern, das Einsichten vermittelt, die sich auf keine andere Weise vermitteln lassen),

– in der Erlernung der Ausnutzung von Standardprogrammen wie Textverarbeitung und Tabellenkalkulation und

– in der Beseitigung der Computermystik: Wenn jeder Mensch schon in seiner Jugend erfährt, wie Computer im Prinzip arbeiten und daß sie nichts als komplizierte Maschinen sind, daß sie nicht denken können und keine Aura des Geheimnisses sie umgibt, dann wäre viel Aufklärungsarbeit geleistet. ______________________

*) : auch (noch) zutreffend für die Hochschule! L.V.


Voraussetzung dafür, daß ein Problem aus irgendeinem Anwendungsgebietüberhaupt erfolgreich durch den Einsatz von Computern bearbeitet werdenkann, ist die Existenz eines mathematischen Modells für das Gebiet bzw.das spezielle Problem. Die Erstellung eines solchen Modells ist oft das größte Hindernis für denComputereinsatz. In den folgenden Betrachtungen wird aber auf solche „Modellierungsfragen“ gar nicht mehr eingegangen.

Auf den ersten (algorithmisches Denken) und dritten Punkt (Standardprogramme) wird hier nicht weiter eingegangen.

Demgegenüber hat es den Anschein, daß die Aufklärungsarbeit zur Beseitigung der Computermystik (vierter Punkt) bisher immer noch erst zu einem recht geringen Teil geleistet worden ist.

Gestützt wird dies durch die Zitate auf den beiden nächsten Seiten, und ich bin sicher, daß man ähnliche Aussagen auch aus den Jahren2000 bis 2005/6 finden dürfte.

Für den zweiten Punkt (Computersimulationen) ist folgendes zu beachten.


Die Hauptquelle für diesen Vortrag ist das lesenswerte Buch

D. Harel: „Das Affenpuzzle und weitere bad news aus der Computerwelt“Springer 2002, 207 Seiten, 19,95 Euro; ISBN 3-540-42307-9.

Originalausgabe: Computers Ltd. What They Really Can't Do. Oxford University Press 2000; 22,50 €; 240 Seiten, ISBN 0-19-850555-8;

Taschenbuch: 2003; 14,95 €, 222 Seiten, ISBN 0-19-860442-4.Zitat aus dem Vorwort:1984 brachte das TIME-Magazin eine Titelgeschichte über Computersoftware. In dem (sonst) ausgezeichneten Artikel wurde der Herausgeber einer Software-Zeitschrift zitiert: Geben Sie einem Computer die richtige Software, und er wird tun, was immer Sie wünschen. Die Maschine selbst mag ihre Grenzen haben, doch für die Möglichkeiten von Software gibt es keine Grenzen.

Das ist falsch. Vollkommen falsch.


Deutsches Analogon zu Harels „Aufhänger“;

aus „Spiegel Special“, Heft 3/1995 (Abenteuer Computer), Beitrag „Problemdesign” (von Peter Glaser); Seite 3, unter „Spots“.

Danny Hillis, Gründer der Supercomputer-Firma Thinking Machines in Cambridge (US-Staat Massachusetts), hatte eine bemerkenswerte Vision. In der von ihm gebauten Connection Machine führt die Zusammenarbeit einiger zehntausend herkömmlicher Mikroprozessoren zu einer nach heutigen Maßstäben atemberaubenden Rechenleistung („massiv parallel“). Es sei bereits heute technisch machbar, sagt Hillis, eine tausendmal größere Connection Machine zu bauen. Sie wäre wuchtig wie ein Haus, aber Eniac, der erste Röhrenrechner von 1946, hatte auch eine Grundfläche von 140 Quadratmetern.

Das eigentliche Problem sind die Probleme. Sämtliche derzeit computergerecht formulierten Probleme wären angesichts der Leistungsfähigkeit einer solchen Maschine trivial. Man könnte mit Urknallsimulationen spielen und wäre immer noch beschämt über die brachliegenden Ressourcen. ...

Auch dafür gilt: Das ist falsch. Vollkommen falsch.


In beiden Fällen haben die Journalisten gröblichst die Komplexität von Problemen unterschätzt! Beim Problemlösen mit dem Computer muß man immer auf folgende „Unglücksfälle“ bzw. „Widrigkeiten“ gefaßt sein:

A. Nicht jedes Problem, das formuliert werden kann, ist auch „effektiv“ (durch einen Algorithmus bzw. ein Programm) lösbar.

Darauf wird hier nicht weiter eingegangen; mehr findet sichbei Harel in Kapitel 2: „Manchmal können wir es nicht”.

B. Nicht jedes effektiv lösbare Problem kann auch „effizient“, d.h. mit vertretbarem Aufwand an Rechenzeit und Speicherplatz gelöst werden. Darauf kommen wir gleich zurück!C. Die Software-Produktion ist ein sehr komplexer Prozeß, derlängst noch nicht so gut beherrscht wird wie die „klassischen“Ingenieursdisziplinen.

Dies ist Gegenstand der Softwaretechnik (Software Engineering), einer Kerndisziplin der Praktischen Informatik. Als Einstieg in diesesei ein schöner Vortrag von Jochen Ludewig aus Stuttgart erwähnt.

2. Allgemeine Probleme


Nun konzentrieren wir uns auf die Rechenzeit als Maß der Effizienz und gehen von einem hypothetischen Computer aus, der seine

Grundoperationen in jeweils einer Mikrosekunde bewältigt.

Komplexitäts- | Rechenzeit für die Eingabegröße n = …, meist in SekundenFunktion | 10 20 30 40 50 60

Tlin 0,00001 0,00002 0,00003 0,00004 0,00005 0,00006Tquad 0,0001 0,0004 0,0009 0,0016 0,0025 0,0036Tkub 0,001 0,008 0,027 0,064 0,125 0,216

Texp 0,001 1 Sek. 17,9 Min. 12,7 Tage 35,7 Jahre 36533 Jahre

(Quelle – auch für die folgende Seite): Garey, M.; Johnson D.: Computers and Intractability. A Guide to the Theory of NP-Completeness. San Francisco, 1979, S.7/8

Die Funktionen seien Tlin(n) = n, Tquad(n) = n2, Tkub(n) = n3, Texp(n) = 2n .

Die folgende Übersicht zeigt die Zeiten, die dieser Computer für vier Algorithmen mit unterschiedlichen Zeitkomplexitätsfunktionen beiEingaben verschiedener Größen (n = 10, 20, 30, 40, 50, 60) benötigt.

3. Betrachtungen zur Komplexität und Effizienz


Möglicher Einwand: „Eine Mikrosekunde ist doch viel zu viel – eine verbesserte Rechnertechnologie führt sicher zu einem großen Zeitgewinn!“ Aber:

Maximale Größe für Eingaben, die noch in einer Stunde bearbeitet werden können

Komple-xitäts-funktion:Tlin

Tquad

Tkub

Texp

Angenomm. Wert für den „guten alten“Computer:Nlin

Nquad

Nkub

Nexp

Wert für einen hundertmal schnelleren Computer: 100 Nlin

10 Nqua

4,64 Nkub

Wert für einen tausendmal schnelleren Computer:1000 Nlin

31,6 Nquad

10 Nkub Nexp + 6,64 Nexp + 9,97.

Für den auf der vorigen Folie beschriebenen Computer gilt z.B.Tkub(50) = 0,125 s ==> Nkub = 1 440 000 (8503600)), aberTexp(30) = 17,9 Min. ==> Nexp ~ 32 .

der hundertmal schnellere Computer in einer Stunde nur knapp bis zur Größe 39,

Bei dem Algorithmus mit expontieller Komplexität kommt also

der tausendmal schnellere nur bis etwa 42 – wahrlich kein großer Zugewinn !


Hieran erkennt man leicht, daß zwischen den drei ersten Algorithmen, deren Schrittzahl jeweils polynomiell ist (d.h. durch ein Polynom in der Größe der Eingaben beschränkt wird), und dem vierten, dessen Schrittzahl exponentiell wächst, ein gewaltiger Qualitätsunterschied besteht.

Es gibt zahlreiche Probleme, von denen bekannt ist, daß es für sie keinen Lösungsalgorithmus gibt, dessen Schrittzahl schwächer als exponentiellwächst. Mehr bei Harel, Kapitel 3: „Manchmal ist es zu teuer“.

Beispiel 1: Die Türme von Hanoi – in der Literatur und im WWW vielfach behandelt !

Auf der anderen Seite gibt es eine Vielzahl von Problemenaus den verschiedensten Anwendungsgebieten, von denenman (immer noch!) nicht weiß, ob sie polynomiell lösbar sind.Mehr bei Harel, Kapitel 4: „Manchmal wissen wir es nicht“.

Beispiel 2: „Affenpuzzle” – kommt gleich (ab Folie 10),Beispiel 3: „Sudoku” – kann „bei Bedarf“ noch kurz vorgestellt werden (Folien 34 – 40 im Anhang 2).


3.1. Das Affenpuzzle (1) – hier als „Schweineknobelei“ mit Karten


Das Affenpuzzle (2) – allgemeine Beschreibung

__________________________________________________________Ziel des Spieles ist es, zu überprüfen, ob die Karten so zusammengelegt werden können, daß immer das Vorder- und das Hinterteil benachbarter Karten zusammenpassen. Ist das der Fall, so soll eine solche „zulässige“Anordnung auch angegeben werden.

Das Spiel besteht aus einer Anzahl von quadratischen Karten mit Mustern anallen vier Kanten. Die Anzahl ist eine Quadratzahl (n2 = 4, 9, 16, ...). Jedes Muster ist eines von je vier vorgegebenen Vorder- und Hinterteilen, z.B. von Affen – wie im Buch von Harel, daher stammt der (deutsche) Titel des Buches. Hexen1), Hunde, Katzen, Schildkröten- oder Schweine (hier verwendet!) sindebenfalls in gegenständlichen Realisierungen dieses Spieles mit n = 9 zu finden.

Die Reihenfolge, in der die Karten angelegt werden dürfen, ist beliebig.Jede Karte kann überdies noch (um 90°, 180° oder 270°) gedreht werden.

[Auch P f e i l e ( Titel des Buches „Algorithmik“) kommen vor!] 2)

__________________________________________________________________________________________

1) Unter „http://www.lsdonline.de/autoren/tube/hexenspiel.htm“ ist eine sehr schöne Beschreibung zum Hexenspiel zu finden, auch ein Simulator dazu.2) Nachtrag zum Vortrag: Folie 30!

http://www.lsdonline.de/autoren/tube/hexenspiel.htm

http://www.lsdonline.de/autoren/tube/hexenspiel.htm


Mit eine kleinen Kartenanzahl und einem spezielles Muster kann ein gewiefter Knobler recht schnell zu einer Lösung kommen. Eine auch für „ernsthafte“ Anwendungen wichtige Strategie ist als „Backtracking“ bekannt.

Die folgenden Seiten illustrieren das, wobei wir hier mit nur einem„Rückschritt“ auskommen – danach kommt bald das „happy end“.

Das Affenpuzzle (3) – Fortsetzung der Beschreibung

Dabei muß man die erreichten „Konfigurationen“, hier also die bisher erreichten zulässigen Teil-Anordnungen von Karten abspeichern.Wenn sich im weiteren Verlauf herausstellt, daß eine Konfigurationnicht zu einer zulässigen Gesamt-Anordnung aller Karten fortgesetztwerden kann, so muß man einige Schritte zurückgehen. Im schlimmsten Fall kann das einen ganz neuen Spielbeginn zur Folge haben.


Hier liegt schon eine Lösung für das(2 2)-Teilproblem vor; fünf Kartensind noch anzuordnen.


1. Diese Karte, um 90° im Uhrzeigersinn gedreht, soll rechts oben angefügt werden.


Das ist aber eine „Sackgasse“; dennes gibt keine Karte mit je einem „Frischlings-“Vorder- und -Hinterteil.

Also einen Schritt zurück !


Wir wählen zum Ansetzen an diesePosition nun die Karte (2) von rechts oben, die aber noch um 90° gegen den Uhrzeigersinn zu drehen ist.

2



Hierher paßt nun offenbar Karte 3 von links unten, um 90° im Uhrzeigersinn gedreht

3


Jetzt kann auch die letzte Reihe noch aufgefüllt werden.


4.


5.


6.


Zu dieser (3x3)-Schweineknobelei ist somit eine ……Lösung gefunden!


Das allgemeine Problem dagegen ist außerordentlich komplex !

Die Ursache dafür liegt nicht etwa an der Schwierigkeit, die Zulässigkeit einer

vorliegenden Anordnung zu überprüfen.

Es ist leicht zu sehen, daß dazu in einem (n n)-Spiel gerade 2n(n-1) solche Tests auszuführen sind.

Hier sei es am Beispiel der Schweineknobelei demonstriert:

Das geht sogar recht einfach – man muß dazu nur höchstens alle vorhandenen Grenzen zwischen

benachbarten Karten auf Übereinstimmung testen.


1 2

7 98

43

10 1211

5 6


Das sind aber wahrlich nicht wenige:Die Anzahl aller Anordnungen ergibt sich durch den Ausdruck

n2! 4n2-1,

Der hohe Zeitaufwand aller bisher bekannten Lösungen des Problems liegt vielmehr darin, daß noch keine wesentlich bessere Strategie bekannt ist, als die „brutale“, bei der alle möglichen Anordnungen der n2 Karten des allgemeinen (n n)-Affenpuzzles auf ihre Zulässigkeit untersucht werden.

dessen Wert mit wachsendem n ungeheuer schnell zunimmt.Schon in dem doch sehr übersichtlichen Fall n = 2 erhält man 4! 43 = 24 64 = 1 536.


das würde den Computer knapp 712 Millionen Jahre beschäftigen.

Für n = 3, also auch für die Schweineknobelei, sind das schon

unser „1sComputer“ von Folie 5 müßte 6:36 Stunden rechnen, um alle diese Kombinationen zu erzeugen.

23 781 703 680;

n = 4 führt zu der „Wahnsinnszahl“ 22 465 674 577 509 875 712 000,

Der Fall n = 5 (auch von Harel behandelt) würde das Testen von4,366 1039 Anordnungen erfordern;

daraus ergäbe sich eine Rechenzeit von 3,46 1025 Jahren. Dazu bemerkt Harel:

„Und denken Sie bitte daran, daß der Urknall gerade mal 12 bis 15 Milliarden Jahre her ist …“


Seit gut 30 Jahren sind zahlreiche (über 1000) Probleme bekannt, die aus verschiedenen Anwendungsgebieten stammen und alle mit dem Affenpuzzle folgendes gemeinsam haben.

Dabei wächst die Anzahl aller möglichen Kandidaten aber leidermindestens exponentiell mit der Eingabegröße an. Die naheliegende Strategie, alle Lösungskandidaten nacheinanderzu überprüfen, führt somit zu einer exponentiellen Schrittzahl .

Zu jeder Eingabe lassen sich einerseits auf effiziente Weise (d.h. polynomiell in der Eingabegröße!) „Lösungskandidaten“ erzeugen.Andererseits kann man für jeden dieser Kandidaten auf effiziente Weise entscheiden, ob er tatsächlich eine Lösung liefert.

3.2. Ausblick auf das P-NP-Problem


Diese Ungewißheit wird im wesentlichen ausgedrückt durch das

P-NP-Problem,das seit 1971 bekannt und immer noch ungelöst ist.

Es ist eines von sieben berühmten „Millenniums-Problemen“, für deren Lösung im Jahr 2000 anläßlich des hundertsten Jahrestages der Vorstellung

der Hilbertschen Probleme ein Preis von jeweils

Nähere Informationen dazu im WWW: http://www.claymath.org/millennium/P_vs_NP/

.

Die schlechte Nachricht dazu:Man weiß man von keinem dieser Probleme, ob es dafür

überhaupt ein polynomielles Lösungsverfahren gibt.

einer Million Dollarausgeschrieben wurde.

http://www.claymath.org/millennium/P_vs_NP


Noch aber winkt die Million denjenigen, die zuerst für ein NP-vollständiges Problem

entweder einen polynomiellen Algorithmus konstruieren

oder aber beweisen können, daß ein solcher nicht existiert.

Für diese Probleme hat sich die Bezeichnung „NP-vollständig“ eingebürgert,ihr Studium hat sich zu einem Kerngebiet der Theoretischen Informatik entwickelt

Interessant ist die folgende Tatsache: Wenn es gelingt, auch nur für ein einziges der auf Folie 28 erwähnten Probleme, z. B. das Affenpuzzle, ein polynomielles Lösungsverfahren zu finden, so kommt man dann auch für alle anderen dieser Probleme zu polynomiellen Lösungsalgorithmen.

============================================


Zur Fußnote 2) von Folie 9:Für das Verständnis dieser Animation ist es hilfreich, die Erzählung

Weitere VerweiseVerlags-Webseiten: zum Buch „Algorithmik“ von Uwe Schöning, zum Buch „Was ist Informatik“ von Peter Rechenberg, zum Buch „Das Affenpuzzle“; Webseite des Autors David Harel-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

„Aauch Pfeeeerde …“

von Manfred Krug auf der „Kult“-Platte bzw. -CD

„Jazz – Lyrik – Prosa“:

„Die Kuh im Propeller“ von M. Sostschenkozu kennen, am besten aus dem Vortrag

Ende des „offiziellen“ Teiles !

http://www.elsevier.de/artikel/711555&_sbid=&_sgid=

http://www.springeronline.com/sgw/cda/frontpage/0,10735,5-0-22-2166953-0,00.html

http://www.wisdom.weizmann.ac.il/~harel/

http://www.wisdom.weizmann.ac.il/~harel/


Aus dem Affenpuzzle, Kapitel 6: Schlechtes in Gutes verwandeln„Der modernen Kryptologie kommt in Hinblick auf dieses Buch eine besondere Bedeutung zu ...

Eine wichtige Rolle spielen dabei die sogenannten Einwegfunktionen. Eine solche Funktion sollte leicht (d.h. polynomiell) zu berechnen sein und außerdem eine Umkehrfunktion besitzen, für die aber kein polynomieller Algorithmus existieren bzw. bekannt sein darf.

Anhang 1

Sie nutzt nämlich geistreich und unverfroren die schlechten Nachrichten der Berechenbarkeitstheorie aus! Dies ist überraschend.“


Im Rahmen der „Public-Key-Krptographie” könnendann die Korrespondenzpartner Alice und Bob ...

ihre so verschlüsselten Botschaften weitgehend unbesorgt austauschen.

sollte nicht in der Lage sein, dasmit vertretbarem Aufwand zu tun!

=======================================================Das „Alice-Bob-Erich-Schema“ stammt aus dem Buch„Complexity Theory and Cryptology. An Introduction to Cryptocomplexity.“von Jörg Rothe, Springer 2005, ISBN: 3-540-22147-6.Webseiten zum Buch: Verlag und Autor . Einen guten Einstieg in die Kryptologie ermöglicht das Buch „Geheime Botschaften.Die Kunst der Verschlüsselung von der Antike bis in die Zeiten des Internet“von Simon Singh; DTV 2002; ISBN 3-423-33071-6.

Eine dritte Person, die ihren Dialog unbefugt mitverfolgen möchte, ...


Zum Sudoku-Spiel (1): Allgemeine Beschreibung(von der Webseite „SudokuMania”)

Sudoku (japan.: Su=Ziffer, Doku=einzeln) ist ein Zahlenpuzzle. Das Puzzlefeld besteht aus einem Quadrat, das in 3 3 Unterquadrate eingeteilt ist. Jedes Unterquadrat ist wieder in 3 3 Felder eingeteilt, so dass das Gesamtquadrat also 81 Felder (= 9 9 Felder) besitzt. In einige dieser Felder sind zu Beginn die Ziffern 1 bis 9 eingetragen. Je nach Schwierigkeitsgrad sind 22 bis 36 Felder von 81 möglichen vorgegeben.

Eine Vervollständigung, die diese Bedingungen erfüllt, wird im folgenden eine „zulässige Belegung” genannt.

Das Puzzle muss nun so vervollständigt werden, dass in jeder Zeile, in jeder Spalte und in jedem der neun Unter-quadrate jede Ziffer von 1 bis 9 genau einmal auftritt. ------------------------------------------------------------------------------------

Anhang 2

http://www.sudokumania.de/


Ursprung: Das Rätselspiel wurde unter dem Namen Carré latin vom Schweizer Mathematiker Leonhard Euler im 18. Jahrhundert erfunden.

Diese Rätselart ist seit 2005 über die britische Zeitschrift "The Times" auch in Europa populär geworden und gehört inzwischen zum Standard von vielen Rätselseiten in Zeitungen.--------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Seinen Durchbruch erlangte das Sudoku jedoch erst, als die japanische Zeitschrift Nikoli solche Rätsel regelmäßig abdruckte. Zu diesem Zeitpunkt erhielt das Zahlenrätsel seinen heutigen Namen.

Zum Sudoku-Spiel (2): Fortsetzung der Beschreibung

Wird dieses Spiel auf (n2 n2)-Felder mit n2 „Ziffern“ verallgemeinert, so erweist sich das Problem, zu entscheiden, ob eine vorgegebeneAnfangsbelegung zu einer zuläsigen Belegung erweitert werden kann,ebenfalls als NP-vollständig – wie das Affenpuzzle.

Näheres dazu ist in der Präsentation „FoSemPraes4neu.ppt “ zu finden.

http://www.timesonline.co.uk/section/0,,202,00.html

http://www.timesonline.co.uk/section/0,,202,00.html

http://www.nikoli.co.jp/en/


Zum Sudoku-Spiel (3): Beispiel – Feld mit 24 Anfangswerten.

\S 1 2 3|4 5 6 7 8 9Z ------------------1 |9 8|2 5 | |2 | 2 5| | 1|3 | 6 |7 | |4 | |8 2 |6 |5 | |6 | 3 |6 | | |9 5 8|7 | 3 | 1 | 7|8 | | 8| |9 |5 7 6| | |

Mit der „brutalen“ Strategie müßte man hier im schlimmsten Fall alle „Belegungen“der 57 (= 81-24) freien Felder mit den Werten 1, 2, ..., 9 durchgehen und auf ihre Zulässigkeit testen. Die Anzahl aller Belegungen ist leider aber „recht groß“:

957 (= 9 9 ... 9)> 2,4 1054 (!!)

(Hier könnte man noch – wie beim Affenpuzzle – mit Überlegungen über die Zeit, in der man eine Belegung erzeugen und testen kann, den gesamten Zeitaufwand schätzen!)


Zum Sudoku-Spiel (4): BeispielfortsetzungEin spielender Mensch wird aber mit sorgfältigen Analysen der jeweiligen Belegungen weit schneller an das Ziel gelangen, eine zulässige Belegung zu finden – falls eine solche überhaupt existiert.

\S 1 2 3|4 5 6 7 8 9Z ------------------1 |9 # 8|2 5 | |2 |7 2 5| | 1|3 |# 6 #|7 | |4 | |8 2 |6 |5 | |6 | 3 |6 | | |9 5 8|7 | 3 | 1 | 7|8 | | 8| |9 |5 7 6| | |

Als erstes kann z.B. das (schon fünffach bestückte) linke obere Teilquadrat untersucht werden: |9 8| | 2 5| | 6 | 7

Durch Ausschluß der dritten Zeile (s.o)und auch der mittleren Spalte zeigt sich, daß die dort noch fehlende Sieben ineindeutiger Weise eingetragen werden kann.


Zum Sudoku-Spiel (5): Beispielfortsetzung

Von diesem Zwischenresultat …

\S 1 2 3|4 5 6 7 8 9Z ------------------1 |9 8|2 5 | |2 |7 2 5| | 1|3 | 6 |7 | |4 | |8 2 |6 |5 | |6 | 3 |6 | | |9 5 8|7 | 3 | 1 | 7|8 | | 8| |9 |5 7 6| | |

... kommt man (überraschenderweise!) einen Schritt weiter, wenn man das leere Teilquadrat links in der Mitte daraufhin untersucht, wo dort die Sechs eingetragen werden könnte:

\S 1 2 3|4 5 6 7 8 9Z ------------------1 |9 8|2 5 | |2 |7 2 5| | 1|3 | 6 |7 | |4 |# # #|8 2 |6 |5 |# # #|6 | 3 |6 |6 # #| |9 5 8|7 | 3 | 1 | 7|8 | | 8| |9 |5 7 6| | |

===>



\S 1 2 3|4 5 6 7 8 9Z ------------------1 |9 8|2 5 | |2 |7 2 5| | 1|3 | 6 |7 | |4 | |8 2 |6 |5 | |6 | 3 |6 |6 | |9 5 8|7 | 3 | 1 | 7|8 | | 8| |9 |5 7 6| | |

\S|1 2 3|4 5 6|7 8 9|Z ------------------|1 |9 8|2 5 | |2 |7 2 5| 6 | 1|3 | 6 3|7 8 | |4 |3 5 |8 2 |6 |5 | 8 |6 5| 3 |6 |6 2| |9 5 8|7 |8 3 4| 1 6| 7|8 |2 9 1| 7 8| |9 |5 7 6| 2| |

Von dieser Belegung, in der nunschon 26 Felder besetzt sind,…

kommt manmit 16 weite-ren Schritten (die alle ein-deutig aus-führbar sind!)nach und nach zu ...

dieser Belegung, in der immer-hin schon 42 (von 81) Zahlen anzutreffen sind.


\S 1 2 3|4 5 6 7 8 9Z ------------------1 |9 1 8|2 5 4|3 7 6|2 |7 2 5|9 6 3|8 4 1|3 |4 6 3|7 8 1|5 2 9|4 |3 5 7|8 2 9|6 1 4|5 |1 8 9|6 4 5|7 3 2|6 |6 4 2|1 3 7|9 5 8|7 |8 3 4|5 1 6|2 9 7|8 |2 9 1|3 7 8|4 6 5|9 |5 7 6|4 9 2|1 8 3|

Für die fehlenden 39 Schritte ist zu beachten, daß in solchen Fällen, in denen mehrere Fortsetzungen möglich sind, vielleicht wieder ein „Backtracking”

ausgeführt werden muß. Die weiteren Schritte auf der Suche nach einer voll-ständigen zulässigen Belegung, also zu einer Lösung unseres Sudoku, wollen

wir nicht mehr im einzelnen darstellen. Wichtig ist aber:

Unser Beispiel ist (glücklicherweise) lösbar !


Documents

24-Stunden-Vorlesung 2006 revidiert: Grenzen des Computereinsatzes 1 Grenzen des Computereinsatzes oder Lutz Voelkel, Institut für Mathematik und Informatik