Benutzer Diskussion:Eisenstein10
Übertrag von der Sudokuseite
So nun hab ich mich doch mal angemeldet ;-)
Okay das mit der 3 im 2. Quadranten hab ich übersehen. Das mit dem 267 hab ich durchaus auch gesehen aber es geht mir ja um die GPS Methode. Diesen Verschalteten Zellen, wie hier die 267, nachzuforschen würde ich als eine Art Kettenschluss-Methode bezeichnen wollen. Die Logik dahinter ist mir klar.
Nicht aber bei GPS. Ich verstehe das Verfahren nicht. Im Beispiel habe ich mit der 4 in Zeilen 6 und 8 angefangen und konnte so die 4 in 3/3 streichen. Hätte ich aber mit den Zeilen 3 und 6 angefangen, dann hätte ich die 4 in 8/3 streichen können, und hätte ich in den Zeilen 3 und 8 angefangen, dann hätte ich die 4 in 6/3 streichen können. Eine dieser 3 Streichungen MUSS aber falsch sein, weil das Sudoku - erwiesen durch probieren - eine eindeutige Lösung hat. Nur, ich komme nicht darauf, an welcher Stelle ich etwas gemacht habe, was nicht im GPS-Algorithmus beschrieben ist. Ich wäre dankbar, wenn mich jemand mit der Nase darauf stoßen könnte.
Ein genaues Verständnis des Algorithmus ist mir wichtig, weil ich versuche, einen Logik-Solver zu programmieren, der nach MENSCHLICH NACHVOLLZIEHBAREN logischen Zusammenhängen löst. Solange ich widersprüchliche Ergebnisse habe, je nachdem, an welcher Stelle ein Computerprogramm zu suchen anfängt, muss ich davon ausgehen, daß entweder der Algorithmus falsch angegeben ist oder falsch umgesetzt wurde. Bei einer Implementierung für den Computer bin ich noch nicht, der Roboter namens "Jürgen" allerdings, welcher sich stur an angegebene Einzelschritte im Vorgegebenen GPS-Algorithmus hält, liefert verschiedene Ergebnisse für das gleiche Ausgangsproblem. Das ist sehr, äh, unbefriedigend ;-)
Eine Web-Recherche nach dem GPS-Algorithmus liefert zu etwa (100 Prozent minus statistisch nicht Nachweisbar) Seiten, die sich allesamt auf diesen Wiki-Artikel beziehen, Teils wörtlich abgekupfert, teils ohne Namensnennung, teils sogar in Form einer wissenschaftlichen Arbeit, aber IMMER ohne kritische Betrachtung des Algorithmus selber. Deshalb habe ich die Diskussion hier an der Quelle gestartet, weil ich denke, daß ich bei der Kopie schlechter aufgehoben bin.
mfg
--Eisenstein10 (Diskussion) 20:43, 10. Apr. 2014 (CEST)
Übertrag Ende.
Hallo Eisenstein!
Zunächst eine Formfrage: da deine Frage nicht primär zur Verbesserung des Artikels beiträgt, müssen wir diese Diskussion ausserhalb des Artikels führen. Daher habe ich deine letzte Bemerkung übertragen ...
- Ich würde mich gerne "Stück für Stück" einer Antwort nähern, indem ich mich mit dir über die Grundlagen austausche. Daher zunächst etwas allgemeines: GPS versucht einen wichtigen Teil der logischen Verknüpfungen, die beim lösen von Sudokus möglich sind, in einem einfachen Kontext zusammen zu fassen. Der Kontext heißt "suche Paare" (Zeilenpaare, Zahlenpaare, ...) "und ziehe aus diesen Paaren verschiedene Schlußfolgerungen". Letztlich stecken viele der Methoden auch in anderen Methoden drin - und - mit GPS läßt sich auch nicht alles lösen. Der Vorteil bei GPS ist, das du - als der Rätselrater - immer nur nach Paaren suchst ... egal ob du dir 2 Methoden gemerkt hast oder deutlich mehr. Damit ist diese Methode sehr einprägsam.
- ... ist das bis dahin ungefähr auch dein Stand der Dinge?
- FG, --Friedrich Graf (Diskussion) 21:03, 10. Apr. 2014 (CEST)
Hallo Friedrich
Meinen "Stand der Dinge" würde ich als durchaus fortgeschritten betrachten. Begründung dafür folgt gleich, aber vorab: Du kannst mit mir gerne sehr fortschrittliche Konzepte diskutieren, und auch ein gewisser Grad an Abstraktion, auch mit etwas Mathematik / Logik, ist mir vertraut.
Nun möchte ich meinen Stand der Dinge erläutern. Das wird etwas weitschweifig werden. Ich bin primär daran interessiert, Logikregeln, die "menschlich nachvollbar" sind, soweit zu verallgemeinern und zu abstrahieren, daß ich es einem Computer erklären kann wie er es machen soll. Das erkläre ich am besten anhand von 2 Beispielen.
Beispiel 1: Ausschlussverfahren.
Bekanntermaßen sucht man hier nach Feldern, in denen nur noch ein Kandidat steht ("Naked Single"), oder in Einheiten (Zeile/Spalte/Kästchen), in denen ein Kandidat nur noch in einem Feld auftaucht ("Hidden Single"), oder auch nach 2 Feldern mit nur noch 2 Kandidaten die jeweils gleich sind ("Naked Double", zum Beispiel die Kandidaten 1,2 in 2 Feldern einer Einheit würden für alle anderen Felder dieser Einheit die Kandidaten 1,2 ausschließen), oder nach "Hidden Double", "Naked Triple", "Hidden Triple", .... allgemein gesagt, man sucht nach "Naked/Hidden k-Tupel mit gleichen Kandidaten in einer n-elementigen Menge", wobei k=1...n, n ist die Anzahl der noch nicht gesetzten Felder in der betrachteten Einheit.
Um dieses Suchkonzept zu abstrahieren genügt eine Feststellung: Ein Naked k-Tupel korrespondiert immer mit einem Hidden (n-k)-Tupel. Um also zum Beispiel in einer Einheit, in der noch kein einziges Feld gesetzt ist (n=9), ein "Hidden Single" zu finden, betrachtet man die anderen 8 Felder der Einheit und wenn dies dann ein "Naked 8-Tupel" ist, muss das 9. Feld ein Hidden Single sein.
Im Wesentlichen betrachte ich also Mengen und ihre Komplementärmengen und schließe gegebenenfalls Kandidaten aus. (( Deshalb sollte man die Ausschlussverfahren vielleicht auch in Mengensuch-Verfahren umtaufen )) Dieses Verfahren lässt sich auch auf Teilmengen erweitern, wobei in dem von mir angegebenen Sudoku gleich 2 gute Beispiele dienen können, eins von mir und das zweite von dir. Hier tauchen alle Kandidaten einer Zahl in einer Teilmenge auf, und diese Teilmenge ist zugleich Teilmenge einer anderen Einheit, also sind alle anderen Felder der Zweiten Einheit für diesen Kandidaten gesperrt. Das war dein Beispiel im 2. Kästchen mit der 3, was in der 3. Zeile alle anderen Felder, die nicht zum zweiten Kästchen gehören, für die 3 sperrt.
Bei diesen Ausschluß- oder auch Mengensuch-Verfahren bin ich vollkommen durchgestiegen und ein fertiges Computerprogramm liegt vor.
Ich stelle fest: Über das Konzept der Mengen und Komplementärmengen hängen die Kandidaten und ihre Ausschlüsse KAUSAL zusammen. Tauchen in einer k-elementigen Teilmenge einer Einheit genau k Kandidaten auf, so können diese k Kandidaten aus der (n-k)-elementigen Komplimentärmenge entfernt werden.
Beispiel 2: "Kettenschluß-Verfahren"
Den Namen habe ich so gewählt, weil sich durch wiederholte Anwendung Ketten aus Feldern ergeben, die man benutzen kann, um Schlussfolgerungen zu ziehen. Du würdest es vielleicht "Schaltketten" nennen, auch ein - für mich - selbsterklärender Name, denn schalte ich in so einer Schaltkette eine Möglichkeit ein, wird die andere Möglichkeit ausgeschaltet.
Simple Erklärung einer Schlussfolgerungs-Kette: Bei einem Kandidaten-Paar in einer Einheit schaltet die eine Zelle die andere Zelle. Und bei Zellen mit genau 2 Kandidaten schaltet der eine Kandidat ebenfalls den anderen Kandidaten. Mehrere solcher Schalt-Zellen bzw Schalt-Kandidaten hintereinander aufgereiht geben die Kette, woraus eventuell Schlussfolgerungen gezogen werden können.
Auch im Web findet man diese Verfahren, meist unter anderem Namen und nur spezialisiert, etwa "Double Impact Chain" oder auch "Feldeinfärbungs-Verfahren". Solche Verfahren lassen sich zu einem allgemeinen Kettenschluß-Verfahren abstrahieren. Die Schlussfolgerungen aus solchen Ketten sind vielfältig, zu viel um hier noch genauer zu erklären, ohne viele Beispiele parat zu haben. Ich möchte hier allerdings einen wesentlichen Grad an Unterschied zwischen den gezogenen Schlussfolgerungen herausstellen: Manche Schlussfolgerungen kann man ziehen, indem man nur eine Kette betrachtet. Andere Schlussfolgerungen lassen sich aus 2 Ketten ziehen, die sich in mindestens 2 Punkten "berühren" müssen, und es ist mir mittlerweile sogar gelungen, per Zettel und Bleistift ein Sudoku zu lösen, indem ich 3 Ketten betrachtete und aus den Berührungspunkten ein logisches Gleichungssystem ableitete, was ich dann mit mathematischen Methoden gelöst habe und dann auf diesem Weg die Lösung erhielt. Dieser 3-Ketten-Schluß war allerdings nicht mehr "menschlich nachvollziehbar" nach meinem Verständnis.
Soweit sogut, aber ich möchte hier sagen, daß sich viele Lösungsmethoden, auf die man im Web oder sonstwo stößt, auf ein Kettenschluß-Verfahren reduzieren lassen.
Ich bin bei diesem Verfahren inzwischen soweit, daß ich einen Algorithmus habe, der für 1-Ketten-Schlüsse 100%ig funktioniert, für 2-Kettenschlüsse würde ich mal sagen 80%, während bei 3- und Mehr-Kettenschlüssen vollkommen planlos bin ohne die Hilfe der Mathematik. Wenn man hier weiter recherchiert stößt man auf so wüste Themen wie Wahrheitstabellen, Schaltplan-Optimierer oder n-P-Vollständigkeit, und hier endet dann meine Zuständigkeit =)
Ich stelle fest: Die einzelnen Glieder einer Schaltkette hängen KAUSAL zusammen, da die jeweils verschalteten Kandidaten genau im jeweiligen Komplementär-Zustand sein müssen.
Ach ja, das Beispielsudoku konnte ich übrigens durch eine 2-Ketten-Schlussfolgerung lösen, völlig ohne Probieren. Wobei ich nicht ausschließen will daß es einfachere Methoden gibt ;-)
So und nun der Große Unterschied zum GPS-Verfahren, und zu dem Punkt, der mir einfach nicht in den Kopf will. Wie in Beispiel 1 erklärt, gibt es einen kausalen Zusammenhang zwischen Tupeln und ihren Komplementärtupeln, und wie in Beispiel 2 erklärt, gibt es einen kausalen Zusammenhang zwischen den einzelnen Gliedern einer Kette. Beim GPS Verfahren gibt es diesen kausalen Zusammenhang aber nur im 1. Schritt: "Suche nach Paaren". Es ist derselbe Zusammenhang wie bei 2 Gliedern einer Schaltkette. In einem Folgenden Schritt "Es werden sich neue Paare ergeben" fehlt mir aber genau dieser Zusammenhang.
Anhand des Beispielsudokus erläutert:
In Zeile 6 und 8 sind Paare von 4en. Klarer Zusammenhang innerhalb der betreffenden Zeilen. Der nächste Schritt ist nach meinem Verständnis aber nicht kausal: "Es ergibt sich ein neues Paar in der Spalte 3"
Und genau dieser Punkt betrifft mein Verständnisproblem.
Daß ich im Anschluss an das neue Paar in Spalte 3 andere Kandidaten der 4 gestrichen habe und so auf meine verschiedenen Lösungen abhängig vom Start gekommen bin, diente im Wesentlichen dem "Führen eines Gegenbeweises". Es geht mir wirklich nur um die Kausalität in der Spalte 3, wo der Zusammenhang - nach meinem Verständins - doch nur in den Zeilen gegeben ist.
Puuuh war lang und ich hoffe du bist Fachmann genug um dieses Geplapper überhaupt zu ertragen =)
mfg
--Eisenstein10 (Diskussion) 23:34, 10. Apr. 2014 (CEST)
- Hi. Ich wollte dich nicht mit "Primitiv-Logik" beleidigen. Diese hatte einen anderen Grund: ich würde mich mit dir zuerst über ein Axiom verständigen wollen. Auch dazu muß ich ausholen:
- wenn ein Mensch ein Sudoku anfängt und er hat nicht genügend Zeit, Lust, .. oder es ist ihm zu schwer, dann hört er einfach auf. Anders ein Computer. Bei ihm gibt es am Schluß entweder eine Lösung oder eine Fehlermeldung.
- ein Mensch erhält Sudokus i.d.R. über die zahlreichen Medienkanäle (Zeitung, Apps, ...). Bei diesem gibt es eine grobe Klassifizierung (leicht, mittel, schwer, ...). Danach richtet sich ein Mensch. Ausnahmslos.
- Die Zielgruppe von Lösungssoftware sind i.d.R. entweder sehr bequeme Menschen oder logikaffine Menschen. Beide brauchen eine 100%-Lösung.
- Das Axiom heißt: "die GPS-Methode kann keine 100% Lösungsgarantie liefern"
- ... im Alltag ist das kein Problem (s. oben), denn die meisten Menschen wollen ein Lösungshilfmittel, das leicht zu erfassen ist. Dafür ist GPS perfekt. Aber eine 100% ige Lösungsgarantie (die du aber brauchst, wenn ich dich richtig verstehe), gibt es nicht.
- Sind wir soweit beieinander? Dann können wir gerne weiterreden ... (dies ist sehr wichtig, da es das Ziel unseres Gespräches maßgeblich beeinflusst). FG, --Friedrich Graf (Diskussion) 09:50, 11. Apr. 2014 (CEST)
Ja, soweit sind wir beieinander =)
Einen 100%-Algorithmus hab ich nicht gefunden und erwarte auch nicht einen zu finden. Wäre die Methode mit den Mengenausschlüssen perfekt, dann wäre ich ja bereits fertig.
Aber mein Problem ist eben, daß durch meine Anwendug des GPS ich einmal auf die Lösung "nicht lösbar" komme, in einem von 3 Fällen für das Beispiel-Sudou, nämlich dann wenn ich falsch zu Suchen anfange.
Warum nur? Habe ich den Algorithmus falsch angewendet oder ist der Algorithmus selber falsch?
Das Ausschlussverfahren bleibt dann einfach stehen, indem es keine neuen Tupel mehr findet, und das Ketten-Verfahren bleibt stehen, indem es keine Berührungspunkte mehr findet. Beide liefern dann jedenfalls kein falsches Ergebnis.
--Eisenstein10 (Diskussion) 11:27, 11. Apr. 2014 (CEST)
- Ich habe jetzt Streß, eine Antwort wird wohl heute nichts mehr. Habe bitte Geduld. --Friedrich Graf (Diskussion) 13:51, 11. Apr. 2014 (CEST)
- Jetzt gehts weiter.
Du hast geschrieben: Meine Anwendung des GPS-Verfahrens:
- Zeile 6 Kandidatenpaar 4 in 6/3 und 6/5
- Zeile 8 Kandidatenpaar 4 in 8/2 und 8/3
- Dadurch ergibt sich ein Kandidatenpaar für 4 in Spalte 3, Zellen 6/3 und 8/3. Alle übrigen Kandidaten für 4 können in dieser Spalte gestrichen werden, also weg mit der 4 in 3/3
- Damit habe ich den Kandidaten für die richtige Lösungszahl gestrichen, einfach indem ich mit der Paarsuche zunächst in den Zeilen 6 und 8 angefangen habe.
Analog könnte ich die richtige Lösungszahl in den anderen möglichen Feldern für die 4 in Spalte 3 streichen, indem ich einfach mit anderen Zeilen das Suchen beginne, also verschiedene Startbedingungen für das GPS-Verfahren wähle.
Fazit: Wenn ich das GPS-Verfahren richtig angewendet habe, dann hängt das Ergebnis davon ab, in welcher Reihenfolge ich die Paarsuche beginne. Das kann nicht sein, also muss das GPS-Verfahren falsch sein.
... wenn du die GPS-Methode auf diese Art modifizierst, ist das falsch (daher auch die unterschiedlichen Ergebnisse). In der GPS-Anleitung steht etwas von der Ermittlung von Kandidatenpaaren - du hast dir dagegen aus einem Kandidatenkonglomerat willkürlich Kandidaten herausgenommen. Diese Auswahl hast du "Paare" genannt (obwohl "willkürliche Auswahl" besser wäre), aber genau in dieser willkürlichen Auswahl liegt dein Denkfehler.
FG, --Friedrich Graf (Diskussion) 11:33, 12. Apr. 2014 (CEST)