Extreme#13

Daniel
Site Admin
Beiträge: 10
Registriert: Mittwoch 30. September 2009, 09:12

Extreme#13

Beitrag von Daniel » Sonntag 26. September 2010, 02:44

Diskussion zum Weekly Extreme #13

Siegbert
Beiträge: 54
Registriert: Freitag 3. September 2010, 17:27

Re: Extreme#13

Beitrag von Siegbert » Sonntag 26. September 2010, 06:06

Zu Ulrich, vorletzter Beitrag: ..."Dass aber eine 6 in J8 stehen muss, weil dort die gemeinsame Zelle zweier 2x2-Felder ist, sehe ich nicht." (2x2 und 3x3-Feld)
Ganz richtig. Ist auch eine Hypothese, die sich hier allerdings bewährt hat. In späteren Fällen mag sie sich als falsch erweisen, es sei denn, sie kann mathematisch (formal-logisch) bewiesen werden.
Im übrigen bin ich ganz froh, dass du mir meine schlampige Begriffswahl nicht um die Ohren gehauen hast. Der Begriff "x-wing" ist bereits besetzt. Hier führt er zur Begriffsverwirrung. Denn x-wings können per Definition nicht verschachtelt werden, meine ich.
Hier also die neue Formulierung mit (hoffentlich unkritischer) Begriffswahl:

Bedingungen:
1. Es gibt ein Rechteck X aus 3x3 Zellen, von denen nur 2 mit sicheren Zahlen bereits besetzt sind.
2. Diese beiden eingetragenen Zahlen sind so angeordnet, dass im Rechteck X ein weiteres Rechteck Y aus 2x2 freien Zellen entsteht.
3. Alle freien Zellen enthalten 2 oder mehr sichere Kandidaten.

Hypothese:
Wenn in dem Rechteck X nur die Zahl a in allen freien Zellen sicherer Kandidat ist und a in allen übrigen Zellen der 3 Zeilen und Spalten des Rechtecks X als Kandidat gestrichen werden kann,
dann ist die gemeinsame Eckzelle der beiden Rechtecke X und Y = a.

Ob diese Hypothese Bedeutung gewinnen wird, ist zweifelhaft. Ihre Bedingungen dürften nur selten gegeben sein. In den Extremes 1-12 fand ich sie jedenfalls nicht.

Benutzeravatar
Ulrich
Beiträge: 86
Registriert: Montag 24. Mai 2010, 20:05
Wohnort: Region Augsburg München

Re: Extreme#13

Beitrag von Ulrich » Sonntag 26. September 2010, 07:16

@Siegbert: Im Extreme#13 hat deine Hypothese zur richtigen Lösung geführt, leider beweist das aber nichts. Das ist das unerfreuliche an der Logik: ein zutreffendes Beispiel beweist keine Hypothese, ein nicht zutreffendes widerlegt die Hypothese aber. Eigentlich ungerecht...

Richtig ist aber: Es gibt keine verschachtelten X-Wings. Eine X-Wing-Situation kann es mit 2 Ziffern in 2 Zeilen/Spalten oder auch mit 3 (oder 4) Ziffern in 3 (oder 4) Zeilen/Spalten geben.
Ulrich
Str8ts addicted

Benutzeravatar
Ulrich
Beiträge: 86
Registriert: Montag 24. Mai 2010, 20:05
Wohnort: Region Augsburg München

Re: Extreme#13

Beitrag von Ulrich » Sonntag 26. September 2010, 17:55

Jens hat seinen Lösungsansatz so beschrieben:
Die drei Spalten 1, 4 und 5 haben je drei mal eine sichere 6. Davon wird eine definitiv dort erscheinen. Andererseits gibt es nur die drei Zeilen B, C und F in denen dies passiert. Die Zeile C hat also entweder in C1, C4 oder in C5 eine 6, deshalb kann die 6 in C2 eliminiert werden. In C2 verbleiben dann die Kandidaten 579 und in A2 die 6, die als einzige 6 der Spalte 2 zu A2=6 führt.
Hier mal die Ausgangslage (es gibt keine weitere 6 in den hier nicht sichtbaren Zeilen bzw. Spalten:
Ex13-a.png
Ex13-a.png (7.76 KiB) 9500 mal betrachtet
Ich habe dann in der Zeile B die sichere 6 auf ihre möglichen Positionen gesetzt. Es beginnt mit der 6 in B1. Die zweite 6 kommt in die C4, die dritte dann in F5. Damit wird A4 = 78 und A2 = 6, wie von Jens beschrieben.

Setzt man dann die 6 systematisch an alle möglichen Positionen, so gibt es weitere Konstellationen: die meisten liefern das gleiche Ergebnis. Aber es gibt auch die folgende:
Ex13-h.png
Ex13-h.png (9.51 KiB) 9500 mal betrachtet
A2 = 6 muss also nicht sein. Im Extreme#13 ist zwar tatsächlich A2 = 6, dies kann man aber nicht aus der beschriebenen "verschachtelten X-Wing" ableiten. Eine echte 3x3-X-Wing liegt hier leider nicht vor.

Wo steckt hier der Fehler? Jens hatte die Ausgangslage so beschrieben:
Die drei Spalten 1, 4 und 5 haben je drei mal eine sichere 6.
Das stimmt nicht. In den Straßen der Spalten 1,4 und 5 ist die 6 tatsächlich sichere Ziffer. Sie kommt aber nicht, wie es eine 3x3-X-Wing erfordern würde, in nur 3 Zeilen vor, sondern tatsächlich in vier: ABCF.
Es ist tatsächlich wichtig, bei der Betrachtung von sicheren Ziffern nach den beiden Richtungen Zeile oder Spalte zu unterscheiden. Es gibt Ziffern, die in einer Richtung sicher, in der anderen aber nur möglich sind.
Hier im Beispiel gilt das für die 6 in A2 und A4.
Ulrich
Str8ts addicted

Jens
Beiträge: 154
Registriert: Sonntag 25. Juli 2010, 14:55
Wohnort: Puchheim

Re: Extreme#13, X-Wing

Beitrag von Jens » Sonntag 26. September 2010, 20:24

Ulrich, danke für Deine Analyse, die für sich spricht. Man kommt so also nicht weiter.
Ich glaube, inzwischen erscheint aber bei Siegberts Hypothese Licht am Horizont. Ich benutze jetzt bewußt eine ähnliche Formulierung wie er und hoffe auf seine Zustimmung.

Hier also die neue Formulierung:

Bedingungen:
1. Es gibt ein Rechteck X aus 3x3 Zellen, von denen nur 2 mit sicheren Zahlen bereits besetzt sind.
2. Diese beiden eingetragenen Zahlen sind so angeordnet, dass im Rechteck X ein weiteres Rechteck Y aus 2x2 freien Zellen entsteht.
3. Alle freien Zellen enthalten 2 oder mehr sichere Kandidaten.

Hypothese (geändert am 26.10.2010 von Jens):
"Wenn im Rechteck X nur die Zahl a in allen freien Zellen sicherer Kandidat ist und a in allen übrigen Zellen der 3 Zeilen und Spalten des Rechtecks X als Kandidat gestrichen werden kann, dann enthalten die Rechtecke X und Y an je zwei gegenüberliegenden Eckpunkten die Zahl a gemäß der X-Wing-Regel. Die Einhaltung der X-Wing-Regel ist im beschriebenen Fall nur möglich, wenn die gemeinsame Eckzelle der beiden Rechtecke X und Y als Lösung gilt (X = Y = a) und gleichzeitig die beiden gegenüberliegenden Eckzellen ebenfalls als Lösung gelten."

Im Extremes 13 sind damit folgenden Zellen bekannt: G6=6, H7=6 und J8=6.
Gruß von Jens

Jens
Beiträge: 154
Registriert: Sonntag 25. Juli 2010, 14:55
Wohnort: Puchheim

Re: Extreme#13, XY-Wing

Beitrag von Jens » Montag 27. September 2010, 10:07

Hoffentlich paßt die Definition des XY-Wing (Siegberts Hypothese) jetzt besser.
Bei dem von mir bekanntgegebenen Lösungsweg für EX13 ändert sich die Reihenfolge der gefundenen Zellen im Bereich der Schritte 24-34 und würde danach folgendermaßen aussehen:

c8z,c9c,a8s,b8c,b9z,b7c,a7z,a9c,d9z,d7c,
g9s,h6s,g5s,h1x,j2p,j1x,j3c,f3z,h3c,h2c,
g2c,g1c,f4z,
und dann: j8x,h7x,g6x,g8c,h8z,h9c,f9c,
f8c,f7z,j7c,j6c,
danach weiter: f1z,c2z,a2z,d2c,e6z,f6z,
d6c,e4z,e5c,f5c,b4z,c4z,a4c,a3c,c3c,b5z,
b1c,c5z,d5c,d1c,c1c,e1c.

Jetzt fehlt noch ein prägnanter Name für dieses Zweiflügel-Monster. X-Moth (X-Motte), X-Butterfly, X-Fly, X-Bird, usw.
Gruß von Jens

Benutzeravatar
Ulrich
Beiträge: 86
Registriert: Montag 24. Mai 2010, 20:05
Wohnort: Region Augsburg München

Re: Extreme#13

Beitrag von Ulrich » Montag 27. September 2010, 19:29

Zur neuen Hypothese hier mal die drei möglichen Verteilungen der 6 in den drei Zeilen GHJ. In den drei Zeilen ist die 6 jeweils sichere Ziffer und sie kommt nur in den Spalten 678 vor.

Hier passt noch alles:
X3-Wing_1.png
X3-Wing_1.png (4.48 KiB) 9497 mal betrachtet
Hier passt die Hypothese nicht:
X3-Wing_2.png
X3-Wing_2.png (4.61 KiB) 9497 mal betrachtet
Und hier auch nicht:
X3-Wing_3.png
X3-Wing_3.png (4.61 KiB) 9497 mal betrachtet
Es handelt sich ganz einfach um eine 3x3-X-Wing in Zeilen, die weitere 6er in den gleichen Spalten eliminiert. Es folgt also lediglich: keine 6 in F678.

Aber "G6=6, H7=6 und J8=6" kann, muss aber nicht stimmen.
Ulrich
Str8ts addicted

Jens
Beiträge: 154
Registriert: Sonntag 25. Juli 2010, 14:55
Wohnort: Puchheim

Re: Extreme#13

Beitrag von Jens » Dienstag 28. September 2010, 12:58

Die Frage, welche Regeln sind bei Str8ts anwendbar, wie sind sie definiert und in welcher Reihenfolge werden sie wirksam, kann ein erfahrener Programmersteller wie Ulrich traumhaft sicher beurteilen. Eine Diskussion darüber ist für normale Str8ts-Anwender bestimmt nützlich, gehört aber in eine andere Forum-Rubrik. Weil die Sache mit den X-Wings aber noch nicht in Ulrichs Grundregeln eingeflossen ist und hier bereits wurzelt, blüht, gedeiht und fruchtet, möchte ich noch ausnahmsweise hier in dieser Ex13-Rubrik beitragen gute Früchte von Fallobst zu unterscheiden.

Was ein X-Wing ist, steht im Wikipedia, aber hier gilt es ihn anzuwenden. Ein X-Wing erfaßt die vier Zellen, die sowohl auf zwei Zeilen als auch auf zwei Spalten auf deren Kreuzungen liegen. Diese Zellen müssen denselben Kandidaten X beinhalten, der nur genau zweimal in entweder zwei Zeilen oder Spalten als sichere Kandidaten vorkommen und nicht höherwertigen Bedingungen unterliegen darf. Eine höherwertige Bedingung wäre beispielsweise der mögliche Ausschluß von X in einer der vier Zellen bei Anwendung anderer Str8ts-Regeln. Als Resultat einer X-Wing-Anordnung können die X-Werte der restlichen Zellen dieser Zeilen bzw. Spalten eliminiert werden.

Als Ausnahme der Regel zweimal in entweder zwei Zeilen oder Spalten kann eine X-Wing-Kaskade gelten, bei der mehrere X-Wings mit gleicher Ziffer dieselbe Eckzelle verwenden. Im Gegensatz zum einfachen X-Wing können die X-Werte wegen der Bestätigung durch mehrere X-Wings in der gemeinsamen Eckzelle eingesetzt werden und gleichzeitig in alle diagonal gegenüberliegenden X-Wing-Zellen.

Dies wird eindrucksvoll sichtbar in den Analysen von Ulrich. Die Bilder Ex13-a.png und X3-Wing_1.png zeigen die korrekte Anordnung mehrerer X-Wings mit der folgerichtigen Zellzuordnung der X-Werte, die obige Denkvorstellung bestätigen.

Beim Bild Ex13-h.png gibt es jedoch nur einen sicheren X-Wing B1-F5 und keine gemeinsame Eckzelle mit dem übrigens unsicheren X-Wing A2-C4. Diese Anordnung ist daher zum Sturz der Hypothese nicht relevant.

Bei Bild X3-Wing_2.png gibt es nur einen X-Wing H7-J8 und damit ebenfalls keine gemeinsame Eckzelle . Bei Bild X3-Wing_3.png mit X-Wing G6-J8 gilt dasselbe. In diesen Fällen können beide gegenüber liegenden Eckzellen die Lösung tragen. Auch diese Anordnungen sind daher nicht relevant.

Fazit ist, daß die Hypothese von Siegbert standhält und angewendet werden darf, solange es nichts Besseres gibt.
Gruß von Jens

Benutzeravatar
Ulrich
Beiträge: 86
Registriert: Montag 24. Mai 2010, 20:05
Wohnort: Region Augsburg München

Re: Extreme#13

Beitrag von Ulrich » Dienstag 28. September 2010, 21:37

Sorry, ich verstehe die Argumentation leider nicht. Die drei Bilder sind drei mögliche Lösungen der gleichen Situation.
Aus genau dieser Situation war das Ergebnis der Hypothese die Folgerung: G6=6, H7=6 und J8=6. Wie man aus den beiden anderen Lösungen sieht, ist dies aber nicht ableitbar. Die Hypothese ist klar widerlegt.
Jens, du sagst, dass Bild X3-Wing_1 die "Denkvorstellung bestätigt", dass aber die Bilder _2 und _3 nicht relevant seien. Wieso nicht? Sie sind, wie man sieht, gültige Lösungen. Du kannst doch nicht argumentieren, die Lösung, die der Hypothese entspricht, sei die einzig relevante und damit sei die Hypothese bestätigt. Woran ist die Relevanz zu erkennen?
Ich denke, wir werden früher oder später weitere solche Anordnungen finden und dann erkennen, was an Schlussfolgerungen funktioniert.
Immerhin, es ist eine 3x3 X-Wing, das ist sicher. Gibt's die eigentlich bei Sudoku? Ich habe nirgends etwas darüber gelesen, habe mich aber auch nicht so intensiv mit den komplexeren Sudoku-Strategien befasst.
Ulrich
Str8ts addicted

Jens
Beiträge: 154
Registriert: Sonntag 25. Juli 2010, 14:55
Wohnort: Puchheim

Re: Extreme#13 @Ulrich

Beitrag von Jens » Mittwoch 29. September 2010, 00:52

Überhaupt ein X-Wing zu erkennen, wenn noch viele Kandidaten zur Auswahl stehen, ist nicht leicht. Der Zweifel nagt am Halbwissen: "Vielleicht ist es ja doch keines?"
Mit den drei Bildern hast Du gezeigt, daß ohne 3x3 X-Wing-Ansatz auch andere Lösungen denkbar wären. Im Fall Ex13 führen diese anderen Lösungsansätze jedoch zu falschen Ergebnissen. Du hast gezeigt, wie gut die Hypothese im Vergleich zu anderen Ansätzen zur richtigen Lösung führt. Ein Scheitern der Hypothese daraus abzuleiten, empfinde ich als neben der Wahrheit stehend.
Du hast Alternativen zur Hypothese aufgezeigt. Sachdienlicher wäre, genau diesen 3x3-Wingeinsatz auf den Prüfstand zu nehmen, um mögliche Schwachstellen aufzudecken. Dies ist noch nicht geschehen. Die Prüfergebnisse wären relevant, wenn sie sich auf das Prüfobjekt selbst beziehen und nicht auf Ersatzobjekte.
Ich vermute, daß in Deinem Fundus einige passende Beispiele für Wingsituationen stecken, die in Wirklichkeit keine sind. Das gestrige Str8ts s680 hätte ohne die vorgegebene 9 in Zelle F8 ein 3x3-Feld für die 7 haben können. Aber ohne diese 9 wäre das Rätsel vermutlich in Richtung 3x3-Wing und damit anders ausgegangen oder nicht lösbar gewesen, wer weiß?
Bei Sudoku kenne ich mich nicht gut genug aus, um über Strategien diskutieren zu können, bin aber dafür mehr als offen.
Gruß von Jens

Antworten