Untersuchung von Bereichen

Post Reply
Siegbert
Posts: 54
Joined: Friday 3. September 2010, 17:27

Untersuchung von Bereichen

Post by Siegbert » Friday 19. November 2010, 09:02

Untersuchung von Bereichen

Definitionen

Feld = eine einzelne Zelle in einem str8ts, in der jeweils nur eine Lösungszahl stehen kann. Zuvor stehen dort Kandidaten, die Lösungszahl werden können.

Bereich = 3 oder mehr zusammenhängende Felder in einem str8ts.

Zeile = Z

Spalte = S

Feld = F

Variablen (Statthalter) für Zahlen = abcde...

Variablen für Zeilen (Spalten) = MNOPQ...


Wenn bekannte Regeln nicht mehr greifen, sei es, dass ich sie nicht erkenne, sei es, dass sie nicht anwendbar sind, gibt es nach meiner Erkenntnis zwei Möglichkeiten, den Lösungsvorgang fortzusetzen. Konsequentes Backtracking oder genaue Untersuchung eines kleineren, eindeutig definierten Bereiches.

Beim Backtracking setze ich in ein Feld eine mir dafür vernünftig erscheinende Zahl als Lösungszahl und fahre in der Lösung fort, bis zum Widerspruch oder der Notwendigkeit, erneut raten zu müssen, usw.

Die genaue Untersuchung eines kleineren, eindeutig definierten Bereiches habe ich im Forum unter "Individuelle Lösungsstrategien" als "Partielles Backtracking" bezeichnet. Dort sind auch Beispiele beschrieben bzw. Fundstellen für Bespiele genannt.


Zu Extreme#19 fand ich für den Bereich CDE56 ebenfalls durch Probieren heraus, dass 1 und 4 als Kandidaten in C56 ausgeschlossen werden können und dass 2 sicherer Kandidat in C56 ist. (Bild unten)
Nach dem Stand der Diskussion ist das Rätsel erst dann "logisch" lösbar, wenn sich das Ergebnis für den untersuchten Teilbereich aus einer Regel ableiten lässt. Eine Regel könnte so aussehen:

Bedingungen
1. In einem Bereich der Größe 2x3 Felder kommen ausschließlich die Zahlen abcde vor.
2. Die Zahlen sind fortlaufend, a sei die kleinste (größte), e die größte (kleinste).
3. Kandidaten seien: abc in einer der 3 Zeilen (Spalten), "M", einer davon sei sicherer Kandidat, ac.. ist zulässig, abcde in der anderen, "N", ac.. ist zulässig, abcd in der dritten Zeile (Spalte), "O", als Paare, also entweder ab oder cd. abc in einer der beiden Spalten (Zeilen), 3 fortlaufende Kandidaten aus abcde in der anderen Spalte (Zeile).
4. Die Anordnung der Zeilen (Spalten) im Bereich sei beliebig.
Unter diesen Bedingungen, sind sichere Kandidaten in N:
Wenn a sicherer Kandidat in M ist, dann ist b sicherer Kandidat in N.
Wenn b sicherer Kandidat in M ist, dann ist c sicherer Kandidat in N.
Wenn c sicherer Kandidat in M ist, dann lässt sich mit dieser Regel ein sicherer Kandidat in N nicht bestimmen.
Schließlich noch:
Wenn die Bedingungen 1-4 gegeben sind, dann sind a und d nicht Kandidaten in N.

Diese Regel(n) ist(sind) direkt aus den drei Grundregeln ableitbar. Sie ist(sind) deshalb wahr.


Ein anderes Beispiel:

Im str8ts #412 habe ich den Bereich H34J234 untersucht (Bild unten). Aus dem Ergebnis lässt sich folgende Regel formulieren.

Bedingungen
1. Eine 3er Straße und eine 2er Straße, die auch Teil längerer Straßen sein können, seien so angeordnet, dass sie ein 4er Feld bilden.
2. Kandidaten seien 3 beliebige Zahlen.
3. 2 der Zahlen seien Kandidaten in jeder Zelle des 4er Feldes.
4. Die 3er Straße enthalte zusätzlich in der isolierten Zelle und in einer weiteren Zelle die 3. Zahl.
Wenn diese Bedingungen gegeben sind, dann ist die 3. Zahl einziger Kandidat in dem an die 2er Straße grenzenden Feld.

Diese Regel beschreibt die vorgefundenen Bedingungen. Sie ist wenig allgemein.

Allgemeiner ist diese:

Wenn in den 4 Schnittpunkten von 2 Zeilen und 2 Spalten (nur) 3 Zahlen Kandidaten sind, dann sind alle drei Zahlen sichere Kandidaten.

Für diese Regel kann ich mich auf den Bereich HJ34 beschränken. Allerdings müssen sich die Schnittpunkte nicht immer berühren.

Die Anzahl der Kandidaten in den untersuchten Feldern ist auch im nächsten Beispiel entscheidend.


Str8ts#888 von Ulrich. Untersuchter Bereich: E78F678 mit den Zahlen abde.

Bedingungen.
1. Ein geschlossener Bereich mit 5 oder 6 Feldern, angeordnet in 2 Zeilen(Spalten) und 3 Spalten(Zeilen).
2. Die Felder bildeten geschlossene Straßen oder würden durch Felder außerhalb des Bereichs zu geschlossenen Straßen ergänzt.
3. 4 Kandidaten abcd, fortlaufend von klein(groß) nach groß(klein).
Wenn im so definierten Bereich 4 Kandidaten enthalten sind, dann sind alle Kandidaten sichere Kandidaten.

Drei Kandidaten führen zum Widerspruch.

Die Mindestzahl an Kandidaten in einer Anzahl von Feldern ist eine spannende Erscheinung. Im Beispiel darüber waren es 3 Kandidaten für 4 Felder, die nicht zusammenhängen mussten. Wie sieht es mit 7, 8, 9 Feldern aus? Bzw. mit 3 Z(S) 3S(Z), 4 Z(S) 3 S(Z) ...?

Im speziellen Fall dieses str8ts ist noch zu beachten, dass E7 zwei Kandidatenpaare enthält, bd(68) und de(89). Für F7 gilt dann, dass eine Lösungszahl nur ein Kandidat aus dem gleichen Kandidatenpaar in E7 sein kann.


Insgesamt zeigen die Beispiele gut, wie brauchbar und praktisch die Untersuchung von kleineren Bereichen für den Lösungsfortschritt ist. Einerseits erkenne ich im Laufe der Untersuchung vielleicht eine bereits bekannte Regel, die ich vorher noch nicht gesehen habe. Zweitens habe ich, wenn der ausgewählte Bereich tauglich war, ein Ergebnis, das mich weiter führt (sichere Kandidaten oder vielleicht schon Lösungszahlen). Drittens habe ich die Chance, eine noch nicht bekannte Regel zu finden.

Wenn alle so gewonnenen Regeln logisch aus den Grundregeln ableitbar sind, wovon ich überzeugt bin, sind die Rätsel damit "logisch lösbar" geworden. Mit Probieren sind sie (noch) nicht "logisch" lösbar, obwohl das gleiche Ergebnis vorliegt wie bei der Anwendung der Regel.
Ich bin sicher, dass sich jedes widerspruchsfreie Ergebnis einer Untersuchung eines Bereiches daraus ergeben hat, dass eine deduktiv ableitbare Regel vorliegt, auch wenn diese noch nicht bekannt und formuliert ist.

Ich postulieren (behaupte): Wenn ein str8ts eindeutig ist, das heißt, wenn es nur eine Lösung hat, und wenn es widerspruchsfrei ist, immer dann ist es logisch so aufgebaut, dass Teilbereiche ebenso logisch aufgebaut sind, wie das Ganze. (Die formale Logik ist ein in sich geschlossenes widerspruchsfreies System.) Mit anderen Worten, der Aufbau der Teilbereiche gehorcht Regeln, die aus den Grundregeln deduzierbar sind. Daraus folgt, wenn man einen Teilbereich untersucht und die Untersuchung ausschließlich auf diesen Teilbereich beschränkt, dann beruht das Ergebnis rein auf Regeln, die aus den Grundregeln logisch deduzierbar sind. Ob diese Regeln bereits bekannt sind oder nicht, spielt dabei keine Rolle. Wenn sie nicht bekannt sind, können sie formuliert werden. Jedenfalls sind die "richtigen" (widerspruchfreien) Ergebnisse der Untersuchungen von Teilbereichen "logisch". Aus logischen Gründen.

Die Wahl der Untersuchungsmethode ist dabei unerheblich. "Probieren" hat den Vorteil, dass es bestechend praktisch ist, und ziemlich rasch zum Ergebnis führt. Wenn es zu einem widerspruchsfreien Ergebnis geführt hat, eröffnet es die Chance, noch nicht bekannte Regeln zu formulieren. Wenn sie kompliziert im Aufbau sind, werden sie in der Praxis des Rätsellösers keine Bedeutung haben. Für den Programmierer vielleicht schon.

In str8ts, die nicht "logisch" lösbar scheinen, habe ich also mit der Untersuchung eines dafür günstig erscheinenden Teilbereiches die Möglichkeit, mit Probieren mehr oder weniger schnell zu "logischen" Ergebnissen zu kommen. Ich muss nicht eine Lösungszahl setzen und, oft mühsam, weiterarbeiten, immer mit der Aussicht, nach viel Arbeit auf einen Widerspruch zu stoßen. Außerdem habe ich die Chance, eine noch unbekannte Regel zu finden.

Bei der Bereichsuntersuchung wird nicht die Auswirkung von gesetzten Lösungszahlen "probiert". Es werden ausschließlich Kandidaten untersucht und ihre Beziehungen zueinander. Konnten vielleicht Kandidaten ausgeschlossen, sichere Kandidaten ermittelt und evtl. auch Felder ermittelt werden, die nur noch einen Kandidaten enthalten? Erst wenn die Untersuchung abgeschlossen ist, werden Lösungszahlen gesetzt bzw. mit neuer Kandidatenkonstellation in anderen Breichen des Rätsels Lösungswege gefunden.
Attachments
Bereichsuntersuchungen.jpg
Bereichsuntersuchungen.jpg (58.63 KiB) Viewed 20395 times

Siegbert
Posts: 54
Joined: Friday 3. September 2010, 17:27

Re: Untersuchung von Bereichen

Post by Siegbert » Sunday 21. November 2010, 07:11

Im Beispiel zu Extreme#19, s.o., war ein Fehler. Die Regeln 2-4 sind falsch. Richtig ist es so.

Gegeben:
1. Bereich von 3 Z(S) x 2 S(Z) zusammenhängender weißer Felder.
2. Kandidaten: fortlaufende Zahlen abcde.
3. Kandidatenverteilung:
Z(S)M = abcde
Z(S)N = ab oder bc
Z(S)O = 1.) a und (b oder c), 2.) b und (a oder c), 3.) c und (a oder b)
S(Z)P = abc
S(Z)Q = abc oder bcd oder cde.

Wenn die Bedingungen 1.-3. gegeben sind, dann enthält Z(S)O die Kandidaten 1.) b und c oder e, 2.) abcde, 3.) abcde.

Nachweise siehe Bilder.
Attachments
Bereichsuntersuchungen2.jpg
Bereichsuntersuchungen2.jpg (113.95 KiB) Viewed 20392 times

Siegbert
Posts: 54
Joined: Friday 3. September 2010, 17:27

Re: Untersuchung von Bereichen

Post by Siegbert » Sunday 21. November 2010, 07:17

Um in Extreme#19 die "logische" Lösung zu finden, sind die Grundregeln 2 und 3 anzuwenden. Eine neue Regel, wie ich sie oben beschrieben habe, ist nicht erforderlich.

Kandidatenverteilungen siehe Bild 2.

MNO5 = abc --> MP -d-e, NP -5
NOP = a?? --> MP -a
MNOQ: a in NOQ kann mit d keine Straße bilden --> MQ -d, MP b
NOPQ = a?? --> MPQ b
--> MPQ = b?.

Oder in der Diktion von Extreme#19:

1 ist sicherer Kandidat in E56 und notwendiger Kandidat in D56. Deshalb sind 2 und 3 Kandidaten in C56. Weil 1 mit 4 keine Straße bilden kann, sind 2 und (3 oder 5) Kandidaten in C56. Also ist 2 sicherer Kandidat in C56.

Mit den Grundregeln 2 und 3 muss nicht geraten werden. Es ist unmittelbar zu erkennen, dass 1 notwendiger Kandidat in D56 ist, in E56 ist 1 sicherer Kandidat. Das schließt 1 in C56 aus und macht 2 und 3 dort zu notwendigen Kandidaten. Weiter ist unmittelbar zu erkennen, dass der notwendige Kandidat 4 in D6 1 in E6 und 1 in C56 ausschließt und 2 zum notwendigen Kandidaten in C5 macht. Zusammen mit der Erkenntnis im Satz zuvor ist erwiesen, dass 2 sicherer Kandidat in C56 ist.

Anders ausgedrückt, wenn ich bekannte abgeleitete Regeln verwende:

Die beiden versteckten Paare 12 und 34 in D56, ein verstecktes Doppelpaar sozusagen, schließen, zusammen mit dem sicheren Kandidaten in D56, 1 und 4 in C56 aus und machen 2 dort zum sicheren Kandidaten. Die 1 aus dem versteckten Paar 12 in D56 bildet mit 1 in E56 einen x-wing, einen versteckten x-wing gewissermaßen.
Attachments
Bereichsuntersuchungen3.jpg
Bereichsuntersuchungen3.jpg (32.73 KiB) Viewed 20392 times

Siegbert
Posts: 54
Joined: Friday 3. September 2010, 17:27

Re: Untersuchung von Bereichen

Post by Siegbert » Thursday 25. November 2010, 10:44

Extreme#19 (s.o.)

Mir ist aufgefallen, dass auch hier die Regel: "6 Felder, im Rechteck angeordnet, benötigen 4 Kandidaten. (Weniger führen zu Widerspruch und/oder Mehrdeutigkeit.)." zur "logischen" Lösung führen kann. Zusammen mit den Bedingungen in CDE56 (zwei Straßen in den Spalten 5 und 6) folgt aus der Regel von der Anzahl der notwendigen Kandidaten, dass die Lösung für D56 das Kandidatenpaar 34 ist.
Das Kandidatenpaar 12 in D56 führt in jeder möglichen Kombination der 3 Kandidaten 123 in E56 zu der Höchstzahl von 3 Kandidaten, was nach der Regel unzulässig ist.

Siegbert
Posts: 54
Joined: Friday 3. September 2010, 17:27

Re: Untersuchung von Bereichen

Post by Siegbert » Saturday 27. November 2010, 15:01

Ich habe nun auch etwas größere Bereiche hinsichtlich der notwendigen Anzahl an Kandidaten untersucht. Hier noch einmal alle zusammen:

Mindestzahl an Kandidaten (Lösungszahlen) im rechteckigen Bereich.

Z=Zeile, S=Spalte

2 Z x 2 S = 3

2 Z(S) x 3 S(Z) = 4

3 Z x 3 S, bei offenen Straßen (Abschnitte von größeren Straßen) = 4
3 Z x 3 S, bei geschlossenen Straßen = 5 (im Sudoku = 9)

4 Z(S) x 3 Z(S), bei offenen Straßen = 5
4 Z(S) x 3 Z(S), bei geschlossenen Straßen = 6

Weniger führen zu Widerspruch und/oder Mehrdeutigkeit.

Post Reply