Registrieren || Einloggen || Hilfe/FAQ || Suche || Memberlist || Home || Statistik || Kalender || Staff Willkommen Gast!

 Sudoku Forum » Sudoku-Hilfe » immer 2 Möglichkeiten - Hilfe!!!! » Threadansicht

Autor Thread - Seiten: -1-
000
15.11.2009, 09:03 Uhr
laubis



Hallo,
ich komme bei einigen Sudokus immer an den Punkt, wo es 2 oder 3 Möglichkeiten gibt. Gibt es da eine Strategie, die ich noch nicht kenne oder hilft hier wirklich nur Ausprobieren? Bin gerade bei Heines Auslese mit 17 Vorgaben. Heft 7/09 Rätsel 35. Ich schreibe mal auf, wie weit ich gekommen bin (die Zahlen stimmen auch), vielleicht kann mir ja jemand sagen, wie es dann weiter geht.
Die Zahlen in Klammern zeigen euch an, welche Möglichkeiten ich hier noch sehe, vielleicht liegt darin ja das Problem)
7(35)9 8(135)2 6(135)4
182 (35)46 97(35)
4(35)6 9(1357)(137) (1358)(1358)2

695 1 (38)(38) 427
(38)71 624 (358)9(35)
(38)24 795 (138)(138)6

248 (35)69 7(35)1
51(37) 4(378)(378) 269
96(37) 2(1357)(137) (35)48

Ich bin sooo gespannt auf eure Antworten!
Danke

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
001
15.11.2009, 09:25 Uhr
surbier



Hi laubis,

Ja, man kommt auch ohne Ausprobieren weiter:
Es gibt da eine Methode namens nice loops, hier in diesem Beispiel speziell ein
x-cycle oder auch x-Kette genannt. Mehr Informationen
hierzu findest (in deutsch) in diesem Forum
unter
x-cycle,
Gabel,
nice loops


oder in der Anleitung von Sudokuprogrammen.

Schau dir hierzu mal den Kandidaten 3 oder 5 an:


Quellcode:
+----------------------+--------------------------+----------------------+
|  >7<   35      >9<   |  >8<      135      >2<   |  >6<    135     >4<  |
|  >1<    >8<    >2<   | 35         >4<     >6<   |  >9<     >7<   35    |
|  >4<   35      >6<   |  >9<      1357    137    | 1358    1358    >2<  |
+----------------------+--------------------------+----------------------+
|  >6<    >9<    >5<   |  >1<      38      38     |  >4<     >2<    >7<  |
| 38      >7<    >1<   |  >6<       >2<     >4<   | 358      >9<   35    |
| 38      >2<    >4<   |  >7<       >9<     >5<   | 138     138     >6<  |
+----------------------+--------------------------+----------------------+
|  >2<    >4<    >8<   | 35         >6<     >9<   |  >7<    35      >1<  |
|  >5<    >1<   37     |  >4<      378     378    |  >2<     >6<    >9<  |
|  >9<    >6<   37     |  >2<      1357    137    | 35       >4<    >8<  |
+----------------------+--------------------------+----------------------+


surbier
Dieser Post wurde am 15.11.2009 um 15:07 Uhr von surbier editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
002
15.11.2009, 16:13 Uhr
KODELA



Hallo zusammen,

neben den von surbier angebotenen Möglichkeiten möchte ich noch eine weitere beisteuern. Eine Ausschlussmöglichkeit, die sehr leicht zu erkennen ist. Hier also noch einmal der aktuelle Stand:

Quellcode:
*-----------------------------------------------------------*
| 7     35    9     | 8     135   2     | 6     135   4     |
| 1     8     2     | 35    4     6     | 9     7     35    |
| 4     35    6     | 9     1357  137   | 1358  1358  2     |
|-------------------+-------------------+-------------------|
| 6     9     5     | 1     38    38    | 4     2     7     |
| 38    7     1     | 6     2     4     | 358   9     35    |
| 38    2     4     | 7     9     5     | 138   138   6     |
|-------------------+-------------------+-------------------|
| 2     4     8     | 35    6     9     | 7     35    1     |
| 5     1     37    | 4     378   378   | 2     6     9     |
| 9     6     37    | 2     1357  137   | 35    4     8     |
*-----------------------------------------------------------*

In Zeile 4 Spalten 5 und 6 haben wir noch zwei ungelöste Zellen, einer von beiden muss die 3, der anderen die 8 zugewiesen werden.

In der Zeile 8, ebenfalls in den Spalten 5 und 6 sind auch diese beiden Kandidaten 3 und 8 vertreten, außerdem noch die 7.

Da man in einem gültigen Sudoku davon ausgehen kann, dass es nur eine Lösung und nicht mehrere gibt, kann es nicht sein, dass in vier Zellen, von denen je zwei in zwei Zeilen, zwei Spalten und zwei Blöcken liegen, nur zwei verschiedene Werte zugewiesen werden, denn in einem solchen Fall wären diese beiden Werte austauschbar.

Die vier von mir angesprochenen Zellen erfüllen nun genau diese Voraussetzungen. Sie liegen in zwei Zeilen, den Zeilen 4 und 8, in zwei Splaten, den Spalten 5 und 6 und in zwei Blöcken, den Blöcken 5 und 8.

Es kann also nicht sein, dass diesen vier Zellen ausschließlich die beiden Kandidaten 3 und 8 zuzuweisen sind. Mindestens einer Zelle muss ein anderer Wert zugewiesen werden.

In Betracht kommt hier nur der zusätzliche Kandidat 3 in den beiden Zellen in Zeile 8 Spalten 5 und 6.

Wenn aber mit Sicherheit die 7 einer dieser beiden Zellen zuzuweisen ist, kann sie aus allen Zellen, die mit diesen beiden Zellen in einem gemeinsamen Bereich liegen, sicher ausgeschlossen werden.

Dies trifft zu für die 7 in Z8S3 und für die 7 in Z9S5 und Z9S6.

Ich hoffe, damit geholfen zu haben.

Mit freundlichem Gruß,

KODELA
Dieser Post wurde am 15.11.2009 um 16:16 Uhr von KODELA editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
003
15.11.2009, 17:14 Uhr
laubis



Sehr sogar, danke schön!

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
004
15.11.2009, 17:26 Uhr
surbier



Hi laubis,

Neben der nice loop, mit der nur ein Kandidat faellt,
und dem von KODELA vorgeschlagenen Eindeutigkeitsviereck,
faellt mit noch Farbzuweisung ein (coloring).

Steht in Zeile 5 Spalte 9 eine 3 (+A),
kann in Zeile 2 Spalte 9 keine 3 stehen (-A),
dann muss in Zeile 2 Spalte 4 eine 3 stehen (+A)
und in Zeile 7 Spalte 4 kann keine 3 stehen;
dann muss in Zeile 7 Spalte 8 eine 3 stehen (+A).
[edit]
Das Ganze gilt auch umgekehrt:
Steht in Zeile 5 Spalte 9 keine 3 (+A) ...

3er, die sowohl ein +A als auch ein -A sehen,
und selbst kein +-A sind, koennen gestrichen werden.


Quellcode:
.
   1   2   3   4   5   6   7   8   9
   ---------------------------------
   0 +D3   0   0   3   0   0  *3   0 | 1
   0   0   0 +A3   0   0   0   0 -A3 | 2
   0 -D3   0   0   3   3   3  *3   0 | 3
   0   0   0   0 +B3 -B3   0   0   0 | 4
.+C3   0   0   0   0   0  *3   0 +A3 | 5
.-C3   0   0   0   0   0  *3   3   0 | 6
   0   0   0 -A3   0   0   0 +A3   0 | 7
   0   0 +E3   0   3   3   0   0   0 | 8
   0   0 -E3   0   3   3 -A3   0   0 | 9

Die 3 in Z1S8 sieht -A in Z1S9 als auch +A in Z7S8
Die 3 in Z3S8 sieht -A in Z1S9 als auch +A in Z7S8
Die 3 in Z5S7 sieht -A in Z9S7 als auch +A in Z5S9
Die 3 in Z6S7 sieht -A in Z9S7 als auch +A in Z5S9

Die anderen sich gegenseitig ausschliessenden
Netze von 3ern, hier mit B, C, D und E markiert,
tragen zu keinem Kandidatenausschluss bei.

Wiederholt man die Uebung fuer den Kandidaten 5,
koennen sogar 6 Kandidaten in einem Zug
ausgeschlossen werden.

Egal welchen Weg du einschlaegst: danach wirds wieder leichter.

surbier

PS: die Punkte '.' sind nur wegen der Formatierung in der 'code'-Umgebung
Dieser Post wurde am 15.11.2009 um 19:28 Uhr von surbier editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
005
16.11.2009, 09:55 Uhr
surbier



Noch einfacher als coloring und nice loop ist der

skyscraper.

In diesem Beispiel zeigen die beiden Hochhaeuser nach rechts:
3[B9] 3[B4] 3[G4] 3[G8]


Quellcode:
skyscraper (Wolkenkratzer)

+-------+-------+-------+
|   3   |   3   |  -3   | A
|       | 3XXXXXXXXXXX3 | B
|   3   | X 3 3 | 3-3   | C
+-------+-X-----+-------+
|       | X 3 3 |       | D
| 3     | X     | 3   3 | E
| 3     | X     | 3 3   | F
+-------+-X-----+-------+
|       | 3XXXXXXXXX3   | G
|     3 |   3 3 |       | H
|     3 |   3 3 | 3     | I
+-------+-------+-------+
  1 2 3   4 5 6   7 8 9

Die 3 in Z1S8 sieht die Hochhausspitze in Z1S9 und die in Z7S8
Die 3 in Z3S8 sieht die Hochhausspitze in Z1S9 und die in Z7S8
Dieser Post wurde am 16.11.2009 um 09:58 Uhr von surbier editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
006
16.11.2009, 10:25 Uhr
KODELA



Hallo surbier,

darauf habe ich eigentlich gewartet. Allerdings ziehe ich hier die SM-Gabel als Begründung vor. Diese Regel ist universeller. Sie deckt Turbot-Fish, 2-String Kite und Sky Scraper ab.

Es ist doch einfacher, wenn man sich nur eine Regel merken muss und nicht drei.

Ergänzend darf ich noch hinzufügen: Was Du hier für die 3 feststellst, gilt natürlich auch für die 5. In jeder der betroffenen Zellen sind ja genau diese beiden Kandidaten vertreten.

Mit freundlichem Gruß,

KODELA

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
007
16.11.2009, 14:40 Uhr
surbier




Zitat:
KODELA postete
darauf habe ich eigentlich gewartet. Allerdings ziehe ich hier die SM-Gabel als Begründung vor. Diese Regel ist universeller. Sie deckt Turbot-Fish, 2-String Kite und Sky Scraper ab.

Es ist doch einfacher, wenn man sich nur eine Regel merken muss und nicht drei.

Ja, KODELA so hat jeder seine Vorlieben. Ich finde skyscraper ein einpraegsames Muster.


Zitat:
Ergänzend darf ich noch hinzufügen: Was Du hier für die 3 feststellst, gilt natürlich auch für die 5. In jeder der betroffenen Zellen sind ja genau diese beiden Kandidaten vertreten.

Ja, stimme ich dir bei.

Wenn man noch etwas tiefer graben will und sich coloring mit der 5 genauer anschaut, sieht
man die seltene Formation, dass in Spalte 7 zweimal eine 5 der
gleichen Farbe steht, was im Widerspruch zur Sudokuregel steht. Damit
kann man alle 5er dieser Farbe, hier mit -A markiert, das sind vier Stueck, streichen.


Quellcode:
Farbzuweisung Typ 2

   0 +B5   0   0   5   0   0  -5   0
   0   0   0 +A5   0   0   0   0 -A5
   0 -B5   0   0   5   0   5  -5   0
   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0 -A5   0 +A5
   0   0   0   0   0   0   0   0   0
   0   0   0 -A5   0   0   0 +A5   0
   0   0   0   0   0   0   0   0   0
   0   0   0   0 +A5   0 -A5   0   0


also zwei 5er mit skyscraper (oder coloring mit Kandidaten ausserhalb des Netzes = Typ 1), und vier 5er mittels coloring mit Kandidaten als Teil des Netzes (= Typ 2), was die ungewoehnlich grosse Anzahl von sechs eliminierten Kandidaten erklaert.

Gruss, surbier
Dieser Post wurde am 16.11.2009 um 14:51 Uhr von surbier editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
008
16.11.2009, 15:07 Uhr
KODELA



Hallo surbier,

ich weiß, jeder hat seine Vorlieben und das ist auch gut so. Es ist auch richtig, dass der skyscraper ein einprägsames Muster darstellt. Keine Frage.

Man muss sich aber dann auch noch das Muster vom Turbot Fish und das vom 2-String Kite einprägen.

Bei der SM-Gabel, die alle drei dieser Methoden abdeckt, suche ich, ob es für einen Kandidaten zwei Bereiche gibt, in denen er ausschließlich in zwei Zellen vertreten ist. Ob es sich bei den Bereichen um Zeilen, Spalten oder Blöcke handelt, ist belanglos. Es ist auch belanglos, ob es zwei gleichartige oder zwei verschiedene Bereiche sind.

Habe ich zwei solcher Bereiche gefunden, ist zu prüfen, ob von jedem dieser Bereiche eine Zelle mit dem betreffenden Kandidaten in einem gemeinsamen dritten Bereich liegt.

Ist auch das der Fall, dann prüft man den Schnittbereich der beiden außerhalb des gemeinsamen Bereiches liegenden Zellen, ob es hier etwas zum Ausschließen gibt.

Aber wie gesagt, dass sind alles Möglichkeiten, die sehr individuell bevorzugt oder abgelehnt werden können.

Mit freundlichem Gruß,

KODELA

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
009
16.11.2009, 15:39 Uhr
laubis



ICh finde euer Engagement wirklich bewundernswert und klasse, vielen Dank für die vielen Antworten aber ehrlich? ICh verstehe nur noch Bahnhof!!! :-)
Das ist mir echt zu ohch, diese ganzen Fachbegriffe....

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
010
16.11.2009, 17:59 Uhr
surbier



Hi laubis,

Das ist immer etwas schwierig die Frage und die Kenntnisse des
Fragestellers richtig einzuschaetzen. Ich kenne das AusgangSudoku nicht,
und weiss auch deshalb nicht wie leicht die 39 Zahlen einzutragen
waren. Du hast ja schon Kandidaten eingetragen, und kennst den
Unterschied zwischen Ausprobieren und logisch Ausschliessen. Wenn du
nicht ausprobieren willst, kommst du an den hier genannten Methoden
nicht vorbei. Vielleicht haben dich die vielen neuen Begriffe etwas
abgeschreckt, das sollte dich aber nicht davon abhalten dich selber
ein wenig in die Materie einzulesen; wenn du willst. Denn hinter den
Begriffen und Namen verbergen sich eigentlich ganz simple logische Tricks.

surbier
Dieser Post wurde am 16.11.2009 um 18:00 Uhr von surbier editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
011
16.11.2009, 18:38 Uhr
laubis



werde ich machen, surbier ... Danke

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
012
16.11.2009, 18:47 Uhr
KODELA



Hallo laubis,

ja, dass Du nur noch Bahnhof verstehst, kann ich gut nachvollziehen. Deshalb meine Empfehlung, solch relativ schwere Sudokus zumindest in der Anfangsphase lieber erst gar nicht anrühren. Im Laufe der Zeit wird man erfahrener und kann sich so Schritt für Schritt auch einmal mit einer etwas schwierigeren Lösungsmethode vertraut machen und wenn man damit Erfolg hat, ist die Freude groß.

Ich will Dir trotzdem einmal etwas ausführlicher erklären, worum es hier in den letzten Beiträgen schwerpunktmäßig ging.

Wenn Du Dir die Aufgabe ansiehst, so wie sie zuletzt war, kommst Du auch nach dem Ausschluss der 7 in Z8S3 (steht für Zeile 8 Spalte 3) und in Z9S5 und Z9S6 nicht so recht weiter. Gut, Du kannst in Z8S3 die 3 und darunter die 7 zuweisen, aber das war es dann auch schon.

Also müssen wir die Aufgabe weiter prüfen. Sehr wichtig sind dabei Bereiche (das sind Zeilen, Spalten und Blöcke), in denen ein Kandidat genau zwei Mal vertreten ist.

Solche gibt es hier doch eine ganze Menge: die 1 z. B. in den Zeilen 1, 6 und 9, in den Spalten 6 und 7 sowie in den Blöcken 6 und 8.

Die 3 ist in den Zeilen 2, 4 und 7, den Spalten 1, 2, 4 und 9 und in den Blöcken 1, 4, 5 und 9 jeweils nur in zwei Zellen vertreten.

Bleiben wir bei der 3. Wie surbier schon aufgezeigt hat, gibt es zwei der hier genannten Bereiche, die Zeilen 2 und 7, in denen jeweils eine Zelle mit der 3 in der Spalte 4 liegt.

Wie wir wissen, kann ein Wert in einem Bereich nur einmal zugewiesen werden. Daher kann die 3 in der Spalte 4 auch nur einmal zugewiesen werden. So banal diese Aussage klingt, so wichtig ist sie doch. Selbst wenn die 3 in der Spalte 4 öfters als zweimal vertreten wäre, sie könnte immer nur einer einzigen Zelle zugewiesen werden.

Welcher Zelle die 3 dabei zuzuweisen ist, kann uns auch völlig egal sein. Entscheidend ist nur, dass mit Sicherheit die 3 nicht in Z2S4 und gleichzeitig auch in Z7S4 zugewiesen werden kann.

Welche Bedeutung hat diese wohl einleuchtende Feststellung?

Wir wissen damit, dass in den Zeilen 2 und 7 die 3 mit Sicherheit einmal nicht in der Spalte 4 zugewiesen werden kann.

Da aber in diesen beiden Zeilen die 3 genau so sicher jeweils einmal zuzuweisen ist, muss in einem Fall die Zuweisung außerhalb der Spalte 4 erfolgen. Dafür kommt in der Zeile 2 nur die Zelle in Spalte 9 (Z2S9) und für die Zeile 7 die in Spalte 8 (Z7S8) in Betracht.

Ja gut, was hilft uns dieses Wissen? Sehr viel, denn wenn die 3 entweder der Zelle in Z2S9 oder der Zelle in Z7S8 zugewiesen werden muss, dann kann die 3 keiner Zelle zugewiesen werden, die mit beiden genannten Zellen in einem gemeinsamen Bereich liegt.

Die Zelle in Z2S9 liegt auch im Block 3. Die Zelle in Z7S8 liegt auch Spalte 8. Die Spalte 8 läuft durch Block 3. Und im Block 3 gibt es drei Zellen, die auch zur Spalte 8 gehören. In zwei dieser drei Zellen ist die 3 vertreten, die Zellen in Z2S8 und in Z3S8.

surbier hat dies sehr schön markiert.

In diesen beiden Zellen kann die 3 sicher ausgeschlossen werden, denn entweder ist die 3 der Zelle in Z7S8 oder in Z2S9 zuzuweisen. In keinem Fall kann dann aber die 3 weder in Z1S8 noch in Z3S8 auch noch zugewiesen werden.

Ich habe dies so detailliert begründet, dass Du wenigstens eine Ahnung davon bekommst, um was es hier ging. Wie man eine solche Ausschlussmöglichkeit nennt, braucht Dich nicht zu interessieren. Name ist bekanntlich Schall und Rauch. Viel wichtiger erscheint mir, zu verstehen, warum hier ein Kandidatenausschluss begründet werden kann, zu erkennen, welche Bedeutung Kandidaten bekommen können, die in einem Bereich nur in zwei Zellen vertreten sind, auch zu erkennen, wie wichtig es ist, Wirkungen, die von einer Zelle, einem Kandidaten ausgehen, zu verfolgen und auch zu kombinieren.

Das alles kommt nicht von alleine. Man muss sich damit schon intensiv befassen. Also überlege es Dir gut, ob es nicht besser ist, bei leichteren Aufgaben zu bleiben.

Übrigens, was wir hier für die 3 durchexerziert haben, lässt sich haargenau auch für die 5 nachvollziehen. Damit bekommst Du sicher wieder festen Boden unter die Füße.

Mit freundlichem Gruß,

KODELA
Dieser Post wurde am 16.11.2009 um 23:32 Uhr von KODELA editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
013
29.01.2010, 18:37 Uhr
Carinthia



Hallo Sudoku Profis und Fans,

zuletzt vor ca. 2 Jahren habe ich mich sehr intensiv mit Software Sudoku Generator/Solver beschäftigt.
Kenntnis über exotische Methoden habe ich auch heute noch nur dem Namen nach.

Damals entstand eine Methode die ich für mich als Gruppenmethode bezeichnete.
Profis berichten bitte welche exotische Methode dieser ähnelt oder sogar gleichzusetzen ist.

Das im Thema besprochene Sudoku ist ein gutes Beispiel.
Um mir unnötige Arbeit für verwirrende Beschreibungen zu ersparen ein Link auf eine Bitmap.

http://www.pictureupload.de/originals/pictures/290110165800_Sudoku.bmp

In Z5 gibt es eine Dreier-Gruppe "358" dessen Zellen willkürlich mit Lösungen x1, x2 und x3 bezeichnet sind.
Die möglichen Zweier Untergruppen ("35","38" und "58") sind farblich markiert. ("58" existiert nicht - wäre mit Lima markiert)

Ausgehend von Z5S9 (x1) folgt
Z2S9 ist nicht x1; Z2S4 muß x1 sein
Z7S4 ist nicht x1; Z7S8 muß x1 sein
Z9S7 ist nicht x1 und nicht x3 - muß somit x2 sein --> x1x2 = "35".

x1x2x3 = "358"; x1x2 = "35" --> x3(Z5S7) = "8"

Ab hier bis zum Ende weiter mit Standard Methoden.

Ob diese Methode auch für den Kopf praktikabel ist ? - für meinen jedenfalls nicht !.

Mit Sudoku Grüßen

Carinthia
Dieser Post wurde am 29.01.2010 um 20:50 Uhr von Carinthia editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
014
30.01.2010, 01:35 Uhr
KODELA



Hallo Carinthia,

gleich vorweg, das Programm, welches Du hier verwendest, gefällt mir gar nicht. Genauer gesagt, es gefällt mir nicht, dass hier Kandidaten entfernt und dafür sehr eigenartige Bezeichznungen (X1, X2, x123 etc.) gezeigt werden.

Versuche es doch einmal mit einem der hier im Forum besprochenen Programme, die sind alle ausnahmslos besser.

Nun aber zu Sache:

Für alle, die Dein Bild nicht gesehen haben, hier noch einmal die Stellung:


Quellcode:
*-----------------------------------------------------------*
| 7     35    9     | 8     135   2     | 6     135   4     |
| 1     8     2     | 35    4     6     | 9     7     35    |
| 4     35    6     | 9     1357  137   | 1358  1358  2     |
|-------------------+-------------------+-------------------|
| 6     9     5     | 1     38    38    | 4     2     7     |
| 38    7     1     | 6     2     4     | 358   9     35    |
| 38    2     4     | 7     9     5     | 138   138   6     |
|-------------------+-------------------+-------------------|
| 2     4     8     | 35    6     9     | 7     35    1     |
| 5     1     37    | 4     378   378   | 2     6     9     |
| 9     6     37    | 2     1357  137   | 35    4     8     |
*-----------------------------------------------------------*

Wenn wir uns die Kandidatenliste ansehen, dann finden wir mehrere Ausschlussmöglichkeiten. Die einfachste wäre wohl über eine von mir so genannte SM-Gabel. Besser bekannt ist diese Technik als Skyscraper.

In der Spalte 4 gibt es nur noch zwei ungelöste Zellen, eine in Zeile 2, die andere in Zeile 7. In diesen beiden Zellen sind nur noch die beiden Kandidaten 3 und 5 möglich, was man selbst ohne Kandidatenliste erkennen kann. Damit können wir allerdings noch nichts anfangen.

Wir können aber, und auch das ohne Kandidatenliste, erkennen, dass die 3 und 5 in den Zeilen 2 und 7 auch nur jeweils in zwei Zellen noch möglich sind.

Daraus können wir zum Beispiel für den Kandidaten 3 Folgendes schließen:

In Spalte 4 kann die 3 mit Sicherheit nur in einer der beiden Zellen zugewiesen werden, entweder in Zeile 2 oder in Zeile 7. Das bedeutet, dass in einer der beiden Zeilen 2 oder 7 die 3 außerhalb der Spalte 4 zugewiesen werden muss. In Betracht kommen nur die beiden Zellen in Z2S9 oder in Z7S8.

Einer dieser beiden Zellen muss also mit Sicherheit die 3 zugewiesen werden. Das bedeutet aber, dass die 3 mit Sicherheit keiner Zelle zugewiesen werden kann, die zu jeder dieser beiden Zellen in einem gemeinsamen Bereich liegt, oder anders ausgedrückt, die diese beiden Zellen sehen kann.

Welche Zellen liegen nun sowohl mit der Zelle in Z2S9 wie auch mit der in Z7S8 in einem gemeinsamen Bereich?

Es sind die ersten drei Zellen der Spalte 8 (Z1S8, Z2S8 und Z3S8). Diese drei Zellen liegen im selben Block wie die Zelle in Z2S9 und in der selben Spalte wie die Zelle in Z7S8.

In zwei dieser drei Zellen ist die 3 vertreten, die für diese Zellen sicher ausgeschlossen werden kann.

Was wir hier für die 3 festgestellt haben, gilt auch für die 5. Auch die kann aus den ersten drei Zellen der Spalte 8 ausgeschlossen werden.

Damit dürftest Du für den Rest dieser Aufgabe keine Probleme mehr haben.

Nun aber noch ein Wort zu der von Dir angesprochen Situation. Ich erkenne hier eine Ausschlussmöglichkeit über eine Zweierkette oder auch Remote Pair.

Ausgehend von der Zelle in Z5S9 haben wir mit den Zellen in Z2S9, Z2S4, Z7S4, Z7S8 und Z9S7 eine durchgehende Kette von Zellen, in denen jeweils genau die Kandidaten 3 und 5 vertreten sind. Jede dieser Zellen ist mit der jeweils nächsten Zelle über einen gemeinsamen Bereich verbunden.

Daraus folgt: Wenn in Z5S9 die 3 richtig wäre, müsste die 3 in der nächsten Zelle, hier in Z2S9 ausgeschlossen erden. In der nächsten Zelle der Kette, hier in Z2S4 wäre die 3 dann wieder zuzuweisen, in Z7S4 auszuschließen, in Z7S8 zuzuweisen und in Z9S7 wieder zuzuweisen.

Das gleiche gilt umgekehrt für den Kandidaten 5.

Betrachten wir jetzt nur einmal zwei Zellen dieser Kette, die erste und die letzte Zelle, dann sehen wir, dass, wenn in der ersten (Z5S9) die 3 richtig wäre, in der letzten (Z9S7) die 5 richtig wäre und umgekehrt.

Das bedeutet aber, dass in allen Zellen, die sowohl mit der Zelle in Z5S9 wie auch mit der in Z9S7 in einem Bereich liegen, die 3 wie auch die 5 ausgeschlossen werden kann.

Vorsicht, das gilt nur dann, wenn zwei Zellen dieser Kette durch eine ungerade Anzahl von Verbindungen zusammenhängen. Das ist hier der Fall, um von der Zelle in Z5S9 zu Zelle in Z9S7 zu kommen, brauchen wir fünf Verbindungen.

Es müssen aber nicht immer die Anfangs- und Endzellen einer Zweierkette sein, über die ein Ausschluss zu begründen ist. Hier in unserem Fall hängen auch die beiden Zellen in Z2S9 und in Z7S8 über eine ungerade Zahl von Verbindungen, nämlich drei, zusammen. Daher kann auch im Schnittbereich dieser beiden Zellen die 3 und 5 ausgeschlossen werden.

Solche Konstrukte sind allerdings ohne Kandidatenliste wohl nur noch sehr schwer zu erkennen.

Ich hoffe, das alles einigermaßen verständlich erklärt zu haben.

Mit freundlichem Gruß,

KODELA
Dieser Post wurde am 30.01.2010 um 01:44 Uhr von KODELA editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
015
30.01.2010, 11:38 Uhr
Carinthia



Hallo KODELA,
merci für die schnelle Antwort.

Das Programm ist seinerzeit von mir selbst geschrieben worden und dient ausschließlich experimentellen Zwecken.
Implementiert sind Standard Methoden (auch Try and Error) und die beschriebene "Gruppenmethode". Ich habe versucht Sudokus mittels linearer Gleichungssysteme (Problem: zumeist zu viele Unbekannte, zu wenig Gleichungen) zu lösen. War ein Sudoku damit aber lösbar so blieb am Ende ein Gleichungssystem mit 3 Unbekannten übrig. Daraus ergab sich die Frage: Kann in einem Problem Sudoku ein Gleichungssystem mit 3 Unbekannten gefunden werden das zu einer Lösung führt ?. Das ist nicht selten der Fall. Von 36628 Minimalsudokus aus dem Internet sind 5361 Problem Sudokus (mit Standard Methoden unlösbar) - davon immerhin 1331.

Die Zellbezeichnungen sind nur in der Kette zur Lösung korrekt eingetragen und mit der Lösung einer Zelle nachträglich nicht geändert.
X123 bedeutet nur: zu diesen Untergruppen gibt es ausgehend von der Dreier Gruppe in Z5 keine Verbindung.

"Vorsicht, das gilt nur dann, wenn zwei Zellen dieser Kette durch eine ungerade Anzahl von Verbindungen zusammenhängen"
Die "Gruppenmethode" führt auch nur dann zu einer Lösung wenn es eine ungerade Kettenanzahl zurück in die Ausgangs Dreier Gruppe gibt.

Bei weitem nicht alle Problem Sudokus führten mit nur einer einfachen Kette zur Lösung - wie im Beispiel.

Letztlich geht es darum Sudokus mittels Logik zu lösen und dazu gehört auch die "Gruppenmethode" (Ob praktikabel ist eine andere Sache).
Mich würde schon interessieren welche exotischen Methoden mit dieser nicht abgedeckt sind.
Die von Dir beschriebene Logik für das Beispiel ist jedenfalls abgedeckt.
Hast Du evtl. zu Testzwecken kompliziertere Sudokus ?

Mit Sudoku Grüßen

Carinthia.

P.S.:
Nachvollziehen konnte ich das Streichen der 7 - diese Logik allerdings allgemein zu implementieren ist eine andere Sache.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
016
30.01.2010, 13:20 Uhr
KODELA



Hallo Carinthia,

tut mir leid, dass ich Dir Dein eigenes Programm schlecht gemacht habe. Ich wusste ja nicht, dass es von Dir ist. Dann verstehst Du natürlich, was mit den einzelnen Eintragungen gemeint ist. Als Aussenstehender hat man damit aber Probleme.

Eine Frage: Du schreibst, dass Du das Streichen der 7 nachvollziehen könntest. Wo ist davon die Rede? In meinem Beitrag und in Deinem vorletzten finde ich davon jedenfalls nichts.

Du beschäftigst Dich anscheinend mit der Frage, in wie weit Sudokus über lineare Gleichungssysteme zu lösen sind. Da kann ich nicht mitreden. Ich kann nur sagen, dass es für kein Computer-Programm ein Problem sein dürfte, jedes Sudoku zu lösen und zwar im Bereich von wenigen tausendstel Sekunden. Damit ist aber dem Anwender im Allgemeinen nicht geholfen.

Ein Programm muss sich der menschlichen Logik anpassen, der Logik, wie sie ein Sudoku-Freund auch anwendet oder zumindest anwenden könnte. Ich kann mir nicht vorstellen, dass irgend jemand, es sei denn zu mathematischen Studien, lineare Gleichungssysteme dafür heranziehen wird. Aber vielleicht irre ich mich da ja auch.

Superschwere Sudokus könnte ich Dir sicher liefern. Ob das aber für Dich hilfreich wäre, ist eine andere Frage. Ich glaube auch, dass ein Forum wie dieses dafür nicht gedacht ist. Ich empfehle Dir eines der hier vorgestellten Programme, die können alle extrem schwere Sudokus kreieren. Man kann auch im Internet bei etwas Suche entsprechende Aufgaben finden.

Mit freundlichem Gruß,

KODELA
Dieser Post wurde am 30.01.2010 um 13:29 Uhr von KODELA editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
017
30.01.2010, 15:05 Uhr
Carinthia



Hallo KODELA,
zunächst - ich bin nicht empfindlich - und Du konntest dies auch nicht wissen.

Das Streichen der 7 hast Du in Deinem Beitrag vom 15.11.2009 beschrieben.

Lösungsversuche mit Gleichungssystemen habe ich längst wieder eingestellt - übrig geblieben ist eben nur die "Gruppenmethode". Ich denke schon daß Du in der Lage bist - falls es Dich interessiert - nachzuvollziehen wie die Lösung Z5S7 = "8" zustandekommt. Kenntnis über Gleichungssysteme sind jedenfalls nicht erforderlich - logisches Denken reicht. Und falls Dich das interessiert - ich bin gerne bereit die Kurzbeschreibung des Weges in meinem ersten Beitrag ausführlicher zu erklären. Daß die "Gruppenmethode" eine praktische Bedeutung hat bezweifle ich - zu vieles müßte man sich merken. Mit Papier und Buntstifte sollte es aber möglich sein.

Mit Sudoku Grüßen

Carinthia

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
018
30.01.2010, 15:48 Uhr
surbier




Zitat:
Ausgehend von Z5S9 (x1) folgt
Z2S9 ist nicht x1; Z2S4 muß x1 sein
Z7S4 ist nicht x1; Z7S8 muß x1 sein
Z9S7 ist nicht x1 und nicht x3 - muß somit x2 sein --> x1x2 = "35".

x1x2x3 = "358"; x1x2 = "35" --> x3(Z5S7) = "8"

Hallo Carinthia

Die erste Schlussfolgerung ist deshalb eindeutig,
weil in Z2 nur zwei Zellen unbelegt sind; waeren
in Zeile 2 noch drei Zellen frei, waere die
Folgerung fuer Z2S4 nichtmehr eindeutig.

Ich wuerde sagen, deine Methode orientiert sich an den
starken Links, und ist deshalb mit coloring, Farbzuweisung
verwandt.
Dieser Post wurde am 30.01.2010 um 15:50 Uhr von surbier editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
019
30.01.2010, 16:10 Uhr
Carinthia



Die gelb markierten Zellen beinhalten allesamt Kandidaten "35"
Wenn eine Zelle x1 beinhaltet dann beinhaltet die andere nicht x1
In der Umkehrung: Wenn eine Zelle nicht x1 beinhaltet dann beinhaltet die andere x1
Hoffe es geht so weiter bis Z7S8

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
Seiten: -1-     [ Sudoku-Hilfe ]  


Kontakt | Impressum | powered by ThWboard 3 Beta 2.84-php5 © by Paul Baecher & Felix Gonschorek