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

 Sudoku Forum » Wissenswertes » X-Gabel - eine neue Ausschlusstechnik » Threadansicht

Autor Thread - Seiten: -1-
000
05.10.2008, 12:24 Uhr
KODELA



Hallo Sudokufreunde in diesem Forum,

von Joe Meiler wurde ich auf eine Lösungsstrategie hingewiesen, die uns beiden bisher nicht bekannt war. Seine Grundüberlegung ist:

a)
gegeben sind eine Zeile und eine Spalte, in denen die gleiche Zahl nur jeweils 2- mal vorkommt.

b)
zwei Enden (aus Zeile und Spalte) liegen im gleichen Block (einzige Einschränkung: nicht auf einer Linie).

c)
Folgerung: im gemeinsamen Feld der beiden anderen Enden ausserhalb des gemeinsamen Blockes kann die Zahl ausgeschlossen werden.

So eine Stellung ist relativ leicht erkennbar und der Ausschluss kann sofort (ohne was wäre wenn, oder ohne Farbgebung) erfolgen.


Ich habe die Überlegung von Joe Meiler in eine Regel gegossen und diese "X-Gabel" genannt.

X-Gabel

1. Regel

Gibt es zwei Reihen, eine Zeile und eine Spalte (Zinken der Gabel), in denen jeweils ein Kandidat K genau in zwei Zellen vertreten ist und befinden sich sowohl von der Spalte wie auch von der Zeile (also von jedem Gabelzinken) je eine Zelle innerhalb eines gemeinsamen Blockes (Gabelbasis), dann kann am Schnittpunkt der beiden anderen Zellen (Gabelspitzen) ein Kandidat K sicher ausgeschlossen werden.


2. Definitionen:

Gabel-Zinken oder kurz Zinken:
die beiden Reihen, mit denen die X-Gabel gebildet wird

Gabel-Füße oder kurz Füße:
die beiden Zellen der X-Gabel mit dem Kandidaten K im gemeinsamen Block

Gabel-Spitzen oder kurz Spitzen:
die beiden Zellen der X-Gabel mit dem Kanidaten K außerhalb des gemeinsamen Blockes

Gabel-Basis oder kurz Basis:
der gemeinsame Block, in dem die Gabel-Füße stehen


3. Beweis:

a)
In jedem Gabelzinken ist der Kandidat K genau in zwei Zellen vertreten.

b)
Je eine Zelle eines jeden Gabelzinkens liegt im Block der Gabelbasis.

c)
Im Block der Gabel-Basis kann der Kandidat K nur einmal zugewiesen werden. Er kann daher mindestens einem der beiden Gabelfüße sicher nicht zugewiesen werden.

d)
Daraus folgt, dass in mindestens einer Gabelspitze der Kandidat K sicher zugewiesen werden kann.

e)
Wenn der Kandidat K in einer der beiden Gabelspitzen sicher ist, kann er am Schnittpunkt beider Gabelspitzen nicht vertreten sein und sicher ausgeschlossen werden.


Diese Lösungsstrategie kann in manchen Fällen die Ausschlussbegründung mit Hilfe der Farbtechniken überflüssig machen, ihre Voraussetzungen sind relativ leicht erkennbar, sie ist eindeutig und ohne "wenn-dann"-Überlegungen.

Es spielt übrigens keine Rolle, wie oft der Kandidat K in der Gabel-Basis vorkommt. Entscheidend ist, dass K in der Gabelbasis nur einmal vorkommen kann und daher mindestens in einem Fall in einer Gabelspitze vertreten sein muss.

Hier ein Beispiel für die Anwendungsmöglichkeit der X-Gabel:



In dieser Aufgabe ist der Kandidat 4 in der Spalte 4 ausschließlich in den beiden grün markierten Zellen und in der Zeile 8 ausschließlich in den beiden blau markierten Zellen vertreten. Nachdem von jeder dieser beiden Reihen genau eine Zelle innerhalb des selben Blockes liegt, im Block 8, steht fest, dass in mindestens einer der beiden Gabelspitzen (B4 und/oder H8) der Kandidat 4 sicher zugewiesen werden muss. Daher kann der Kandidat 4 am Schnittpunkt der beiden Gabelzellen in der rot markierten Zelle B2 mit Sicherheit ausgeschlossen werden.

Meine Frage an Euch: Kennt jemand diese Strategie, natürlich unter einem anderen Namen?

Mit freundlichen Grüßen,

Konrad (KODELA)

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
001
05.10.2008, 12:48 Uhr
KODELA



Berichtigung:

Die Erklärung zum Beispiel muss natürlich wie folgt lauten:

In dieser Aufgabe ist der Kandidat 4 in der Spalte 4 ausschließlich in den beiden grün markierten Zellen und in der Zeile 8 ausschließlich in den beiden blau markierten Zellen vertreten. Nachdem von jeder dieser beiden Reihen genau eine Zelle innerhalb des selben Blockes liegt, im Block 8, steht fest, dass in mindestens einer der beiden Gabelspitzen (B4 und/oder H9) der Kandidat 4 sicher zugewiesen werden muss. Daher kann der Kandidat 4 am Schnittpunkt der beiden Gabelzellen in der rot markierten Zelle B9 mit Sicherheit ausgeschlossen werden.

(H9 statt H8 und B9 statt B2)

Konrad (KODELA)

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
002
05.10.2008, 15:47 Uhr
KODELA



Hallo Sudoku-Freunde in diesem Forum,

dieser Beitrag wurde leider zu früh in dieses Forum gestellt und es war mir nicht möglich, daran noch etwas zu editieren, obwohl dies zwischenzeitlich funktionieren sollte. Es war mir auch nicht möglich, meinen eigenen Beitrag noch einmal zurück zu nehmen, was mir heute bei einem anderen Beitrag schon einmal gelungen ist. Deshalb hier noch ein zweiter wichtiger Nachtrag.

Im Beitrag selbst wurde bereits erwähnt, dass ich von Joe Meiler auf diese Lösungsstrategie hingewiesen wurde. Sie ist also nicht auf meinem Mist gewachsen.

Joe Meiler war es auch, der den schlüssigen Beweis dieser Regel als erster gefunden hat.

Mit freundlichen Grüßen

Konrad (KODELA)

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
003
05.10.2008, 15:53 Uhr
surbier



Hallo KODELA

Was du beschreibst kenne ich unter dem Namen Turbot-Fish,
ein Spezialfall einer nice loop mit fuenf Knotenpunkten.
Trotzdem sehr ausfuehrlich und schoen erklaert.


Gruss surbier

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
004
05.10.2008, 17:09 Uhr
KODELA



Hallo surbier,

herzlichen Dank für den Hinweis.

Schade, dass es "nur" ein Spezialfall einer nice loop ist, denn damit verbindet sich doch die Vorstellung, dass dies nur etwas für absolute Spezialisten ist. Die X-Gabel dagegen (und natürlich auch, wenn es ein Turbot Fish ist) ist so simpel und auch leicht zu erkennen, dass sie es meiner Meinung nach verdienen würde, etwas bekannter zu werden.

Mit freundlichem Gruß

Konrad (KODELA)

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
005
05.10.2008, 19:01 Uhr
KODELA



Hallo Sudoku-Freunde in diesem Forum,

surbier hat mich darauf hingewiesen, dass es die von Joe Meiler vermeintlich entdeckte Lösungsstrategie bereits unter der Bezeichnung "Turbot-Fish" zumindest den Sudoku-Spezialisten bekannt ist.

Die Strategie "Turbot-Fish" ist allerdings gegenüber der von mir beschriebenen X-Gabel universeller und beschränkt sich beim Basisbereich nicht nur auf einen Block, es kann auch eine Zeile oder Spalte sein.

Verändert man in der von mir formulierten Regel ein einziges Wort und setzt statt "Block" den umfassenden Begriff "Bereich", dann haben wir die Definition für eine wirklich vielseitige Ausschlussregel.

Hier der veränderte Wortlaut:

Gibt es zwei Reihen, eine Zeile und eine Spalte (Zinken der Gabel),
in denen jeweils ein Kandidat K genau in zwei Zellen vertreten ist und befinden sich sowohl von der Spalte wie auch von der Zeile (also von jedem Gabelzinken) je eine Zelle innerhalb eines gemeinsamen Bereiches (Block, Zeile oder Spalte -> Gabelbasis), dann kann am Schnittpunkt der beiden anderen Zellen (Gabelspitzen) ein Kandidat K sicher ausgeschlossen werden.

Darauf wollte ich noch hinweisen.

Mit freundlichem Gruß,

Konrad (KODELA)

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
006
05.10.2008, 22:52 Uhr
KODELA



Hallo Sudoku-Freunde in diesem Forum,

In meinem vorhergehenden Beitrag habe ich die Regel nicht korrekt verändert. Die Beschränkung der zwei Reihen mit den jeweils genau zwei Kandidaten K auf jeweils eine Reihe und eine Spalte muss natürlich auch raus, damit die Regel universell einsetzbar ist. Also noch einmal die Regel:

Gibt es zwei Reihen (Zeilen und/oder Spalten), in denen jeweils ein Kandidat K genau in zwei Zellen vertreten ist und befindet sich von jeder dieser beiden Reihen je eine Zelle innerhalb eines gemeinsamen Bereiches (Block, Zeile oder Spalte), dann kann am Schnittpunkt der beiden anderen Zellen dieser beiden Reihen ein Kandidat K sicher ausgeschlossen werden.

Ich hoffe, nicht wieder einen Bock geschassen zu haben.

Mit freundlichen Grüßen

Konrad (KODELA)

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
007
26.11.2008, 22:27 Uhr
AHR Sudoku



Hallo Kodela,
Deine X-Gabel kenne ich unter dem Namen 2-String Kite.

Grüße
Andreas
--
Sudoku oder nicht Sudoku.
Das ist hier die Frage!
Dieser Post wurde am 26.11.2008 um 22:28 Uhr von AHR Sudoku editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
008
30.11.2008, 22:59 Uhr
KODELA



Hallo Andreas,

in Deiner Beschreibung zu einem "2-String Kite" steht:


Zitat:
Beim Two-String Kite wird die Basis aus drei mit einander verbundenen starken Paaren gebildet, wobei je eines in einer Zeile, einem Block und einer Spalte vorkommen und der Block in der Mitte liegen muss.

Frage: Bist Du sicher, dass Du hier drei starke Paare benötigst und dass je eines in einer Zeile, einer Spalte und einem Block liegen muss? Ich sehe das anders.

Du hast natürlich Recht, wenn Du im Zusammenhang mit der X-Gabel auf andere Bezeichnungen verweist, hinter denen im Grunde der selbe Gedanke steckt.

Nun, zum einen wussten wir das zum dem Zeitpunkt, als ich dieses Thema hier eröffnete, noch nicht, zum zweiten habe ich die für mich ehemalige X-Gabel zur SM-Gabel erweitert.

Bei der X-Gabel war noch gefordert, dass es zwei Reihen sein müssten, in denen ein Kandidat K jeweils genau zweimal vertreten sei (also vermutlich in Deinem Sinne zwei starke Paare - google doch einmal nach einem "starken Paar" - das ist genau so eine freie Wortschöpfung wie meine X- oder SM-Gabel).

Bei der SM-Gabel gilt die Beschränkung auf Reihen nicht, es können zwei beliebige Bereiche sein, in denen ein Kandidat K jeweils genau zweimal vertreten ist. Wenn sich je eine Zelle dieser beiden Bereiche mit K gemeinsam innerhalb eines dritten Bereiches befinden, in dem K auch öfters als zweimal vertreten sein darf, dann kann K im Schnittbereich der außerhalb dieses verbindenden Bereiches liegenden Zellen mit K der beiden Bereiche sicher ausgeschlossen werden. Ein schrecklicher Satz.

Ich habe die beiden Bereiche mit den jeweils genau zwei Kandidaten die Zinken einer Gabel genannt, den Bereich, in dem sich von jedem der beiden Zinken eine Zelle mit K befindet nannte ich die Gabelbasis und die beiden außerhalb der Gabelbasis liegenden Zellen der Zinken, in denen K vertreten ist, die Gabelspitzen.

Im Schnittbereich der beiden Gabelspitzen kann K ausgeschlossen werden.

Zu meinen Bezeichnungen ein Wort: Ich habe festgestellt, dass es für viele, wenn nicht gar für alle mir bekannten Lösungsstrategien mehr als eine Bezeichnung gibt. Viele davon sind aus einer Laune heraus entstanden und oft genug vermisse ich auch einen logischen Zusammenhang. Als Beispiel will ich nur einmal auf den Fisch, oder wenn Du so willst, auf den Fish hinweisen, welch unterschiedliche Strategien verbergen sich nicht darunter.

Für meine Excel-Sudokuanwendung, die demnächst in der Version 4 zum Download zur Verfügung stehen wird, habe ich auch eine Hilfe- und Infodatei geschrieben, in der einige der wichtigsten Lösungsstrategien beschrieben werden. Dabei habe ich nicht an Profis wie Dich gedacht, sondern an ganz normale Menschen, die nur hin und wieder ein Sudoku lösen wollen und eventuell daran interessiert sind, nicht vor jeder etwas schwereren Aufgabe schlapp zu machen.

In dieser Hilfe- un Infodatei steckten anfänglich auch noch Bezeichnungen wie "Sword-Fish" und ähnliche. Als ich dann aber zum "Turbot-Fish" kam, habe ich all diese Begriffe entfernt und eigene gewählt, mit denen, wie ich hoffe, der Anwender auch etwas anfangen kann. Und diese Begriffe verwende ich auch hier, Name ist ja bekanntlich Schall und Rauch.

Soviel für heute. Es grüßt Dich

Konrad (KODELA)
Dieser Post wurde am 30.11.2008 um 23:10 Uhr von KODELA editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
009
10.12.2008, 19:53 Uhr
AHR Sudoku



Hallo Konrad,
meines Erachtens steckt da nicht der selbe Gedanke hinter, sondern es ist das Selbe. Und wenn man dem Kind nicht einen, sondern drei Namen gibt wird es Garantiert nicht besser.

Auch wenn die originalen Namen vielleicht nicht die Treffensden sind, so sind es doch die, die für mich die entscheidenden sind.

Wenn Du den '2-String Kite' auch unter dem Oberbegriff 'Turbot Fish' bekannt jetzt unbedingt 'X-Gabel' nennen musst und der nächste meint das vielleicht 'Kreuzreihenausschluss', 'Basiskette' oder sonstwas besser passt und ihn so nennt, trägt das mit Sicherheit zur leichteren Verständigung bei.

Wenn Du die im englischen gängigen Namen um jeden Preis ersetzen willst, dann beginne doch bitte damit, dass Du erst einmal eine Liste aller Techniken zusammenstellst und dann Deine Namen als Vorschlag gegenüber stellst. Vielleicht finden Deine Namen ja andere genauso unpassend oder es hat sich irgendwo schon ein anderer deutscher Name gefestigt, der nur bei Dir noch nicht angekommen ist.

Ich glaube es gibt so um die 80 verschiedene beschriebene Techniken. Wenn Du es in die Hand nehmen möchtest diese einem breiten Publikum zu vermitteln, finde ich das eine gute Sache. Aber bitte immer den originalen Namen (teilweise gibt es ja auch im Englischen mehrere) mit angeben.

Grüße
Andreas
--
Sudoku oder nicht Sudoku.
Das ist hier die Frage!
Dieser Post wurde am 11.12.2008 um 15:48 Uhr von AHR Sudoku editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
010
10.12.2008, 20:14 Uhr
AHR Sudoku




Zitat:
KODELA postete
in Deiner Beschreibung zu einem "2-String Kite" steht:


Zitat:
Beim Two-String Kite wird die Basis aus drei mit einander verbundenen starken Paaren gebildet, wobei je eines in einer Zeile, einem Block und einer Spalte vorkommen und der Block in der Mitte liegen muss.

Frage: Bist Du sicher, dass Du hier drei starke Paare benötigst und dass je eines in einer Zeile, einer Spalte und einem Block liegen muss? Ich sehe das anders.
Konrad (KODELA)

Ich gebe Dir Recht. Das ist etwas zu eng gefasst. Es reicht, wenn die starken Paare in der Zeile und Spalte vorhanden sind.

Danke für den Hinweis!
--
Sudoku oder nicht Sudoku.
Das ist hier die Frage!

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
011
10.12.2008, 20:14 Uhr
KODELA



Hallo Andreas,

es wäre schön gewesen, wenn Du auf meine Frage eingegangen wärst.

Du hattest geschrieben:

"Beim Two-String Kite wird die Basis aus drei mit einander verbundenen starken Paaren gebildet, wobei je eines in einer Zeile, einem Block und einer Spalte vorkommen und der Block in der Mitte liegen muss."

Meine Frage war: Bist Du sicher, dass Du hier drei starke Paare benötigst und dass je eines in einer Zeile, einer Spalte und einem Block liegen muss? Ich sehe das anders.

Wollen wir lieber um die Sache reden und nicht um Namen, die sind Schall und Rauch, was ich auch schon mehrfach betont habe. Namen werden aber auch nicht allein deshalb besser, weil sie englisch sind, also lassen wir das bitte. Hauptsache, wir wissen wovon wir reden.

Mit freundlichen Grüßen,

Konrad
Dieser Post wurde am 11.12.2008 um 17:36 Uhr von KODELA editiert.

Seitenanfang Seitenende
Profil || Private Message || Suche Zitatantwort || Editieren || Löschen || IP
012
10.12.2008, 22:24 Uhr
KODELA



Hallo Andreas,

da haben sich unsere Beiträge wohl überkreuzt.

Nur noch etwas zu "meiner" SM-Gabel, der erweiterten Form der "alten" X-Gabel:

Weder bei den beiden "starken Paare" muss es sich um eine Zeile und eine Spalte handeln und der gemeinsame Bereich muss auch kein Block sein. Jeder der drei Bereiche kann jeder Bereichsgruppe angehören.

Hier noch einmal die Definition:

Gibt es zwei Bereiche B1 und B2, in denen ein Kandidat K jeweils in genau zwei Zellen vertreten ist und liegen von diesen beiden Bereichen je eine Zelle mit K in einem gemeinsamen dritten Bereich B, dann kann in allen Zellen des Schnittbereiches der beiden außerhalb der Bereiches B liegenden Zellen von B1 und B2 der Kandidat K sicher ausgeschlossen werden.

Wie Freunde dieses Forums festgestellt haben, funktioniert die Regel selbst bei Sudokus, bei denen auch die beiden Diagonalen als Bereich definiert sind.

Übrigens hatte ich zu dem Zeitpunkt, als ich diesen Thread eröffnete, keine Ahnung von einem Turbot Fish. Erst surbier hat mich darauf aufmerksam gemacht. Zu diesem Zeitpunkt war ich auch noch der Meinung, die Ausschlussmöglichkeit setze je einen Strong Link, oder ist "starkes Paar" nicht genau so gut, in einer Zeile und einer Spalte voraus, die sich dann in einem Block "treffen". Als ich dann festgestellt habe, dass man diese Regel weiter fassen kann, habe ich sie, "für mich" in SM-Gabel umbenannt. SM steht hier für SchnittMenge.

Übrigens, in meiner Excel-Sudoku-Anwendung, auf die in diesem Forum auch hingewiesen wird, leider kein Sudoku Trainer der Extraklasse, wird in der mitgelieferten Info- und Hilfedatei ein Beispiel zur SM-Gabel gezeigt, in dem die beiden starken Paare in zwei Spalten und der gemeinsame Bereich in einer Zeile liegt.

Mit freundlichem Gruß,

Konrad
Dieser Post wurde am 10.12.2008 um 22:37 Uhr von KODELA editiert.

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


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