Diskussion:Sudoku

Wie wird Sudoku richtig geschrieben?

Hallo Chrkl, warum hast du Sudoku umbenannt? In meinen Zeitungen (Zeit, Süddeutsche, Tagesspiegel) heißt ein Sudoku Sudoku. Deine Schreibweise kann ich nicht lesen, da bei mir nur eine Ersatzzeichen an der zweiten Stelle erscheint. Ich vermute, dass du da ein japanisches Zeichen eingefügt hast, das sicher richtig ist, aber in einer deutschen Enzeklopädie? Meinst du irgendjemand tippt das ein? Kannst du den Artikel nicht wieder Sudoku nennen? --Matze12 17:33, 1. Aug 2005 (CEST)

Ich stimme auch dafür den Artikel wieder in Sudoku umzunennen. Das scheint mir der weit gebräuchlichere Name zu sein. --212.9.163.11 11:35, 6. Aug 2005 (CEST)

Im Moment steht an zweiter Stelle ein u mit Überstrich, denn im Japanischen spricht man das Wort mit langem U. Wenn dein Computer den nicht anzeigt dürften Browser oder Betriebssystem ziemlich alt sein.

Die international übliche Umschrift mit lateinischen Buchstaben wäre Suudoku, die deutschen Japanwissenschaften sind aber fest in der Hand der Überstrichler ;-)

Mir ist das Lemma ja fast egal. Aber! Wenn "Otto-Normal-Wikileser" momentan unter www.google.de "define: sudoku" eintippt, landet er grundsätzlich auf der englischen Seite. www.wikipedia.de ist aber eine deutschsprachige Seite. Das mag mit dem vielleicht richtigen japanischen Lemma zusammenhängen. Wäre es nicht besser, den Artikel unter www.wikipedia.de Sudoku zu nennen?

Die (japanisch) richtige Schreibe mag ja zutreffend sein, aber genauso wie z.B. Japaner deutsche Wörter einjapanischt haben wie arubaito ( Japanisch) können auch wir mal ein japanisches Wort eindeutschen. Niemand weiß heutzutage, was Sudoku in 50 Jahren im deutschen bedeuten wird... Ich bin mir mir aber sicher, dass das Wort irgendwann im Duden stehen wird. Genauso kann passieren, dass irgendein Fernsehkomiker Sudoku bei einem guten Witz benutzt, Millionen deutschsprachige Zuschauer den verstehen und das Wort Sudoku übernehmen. U.U. ist das Wort auch nächstes Jahr vergessen....

Keiner weiß es. Aber wenn es im Deutschen landet wird es ganz sicher Sudoku geschrieben und gesprochen und ganz sicher nicht Sūdoku oder wie erwähnt Suudoku.

2 Beispiele zum Thema:

Es heißt in deutschen Lexika nicht Praha, was genauso richtig wäre wie Sūdoku sondern Prag. Benutzer:Chrkl wäre wohl eher für Praha als Lemma, wenn ich das Problem zu Ende denke....

Die Englischsprachigen sagen zu München Munich. Dürfen die das? Die Tschechische Wiki schreibt Mnichov. Warum übernehmen die die Punkte über dem U nicht?

Im Vergleich ist Sudoku nicht mal im Ansatz so weit weg, obwohl es eigentlich Sūdoku heißen sollte, zumindest würde Benutzer:Chrkl das so sehen.

Ich denke wirklich drüber nach, ob das alles lustig oder traurig ist....

Mein Vorschlag ist: Die Begriffserklärung unter Sudoku mit Sūdoku zu tauschen und entsprechend unter S%C5%ABdoku die Begriffserklärung zu schreiben. Gunter 13:11, 27. Aug 2005 (CEST)

Ich stimme dir zu und bitte dich die Änderung endlich durchzuführen. Der japanologische Teil kann ja mit Lautschrift in den Artikel eingearbeitet werden. -- Matze12 01:44, 31. Aug 2005 (CEST)

Ich plädiere gleichfalls für den deutschen Namen "Sudoku". Die japanisierte Schreibweise ist mir bislang noch nie untergekommen und kann ja im Text erwähnt werden. Unser Wikipedia -Mirror hat Probleme mit dem Unicode Zeichen "ū", das der Perl-Bibliothek "Unicode::String" offenbar unbekannt ist. Meine Bitte: Den Titel in "Sudoku" ändern! --joma 13:25, 12. Okt 2005 (CEST)

Waere nett gewesen, wenn mich jemand auf die Diskussion hier hingewiesen haette. Die Vergleiche mit den Staedtenamen hinken, da diese Staedte deutsche/fremdsprachliche Eigennamen haben, das hier ist aber ein japanisches Wort, ohne vorhandene deutsche Uebersetzung. Fuer weitere Argumente fuer den Makron bitte ich Diskussion:Judo#Jūdō zu lesen. Ich bin das Thema naemlich leid.

Zwei Dinge noch: Erstens; eine Weiterleitung (nicht Begriffsklaerung) unter dem korrekt transkribierten Lemma macht keinen Sinn, da niemand es eintippen wird/kann. Zweitens; Google unterscheidet bei seinen Ergebnissen prinzipiell nicht zwischen u mit und ohne Makron, wie am ersten bzw. zweiten Treffer zu sehen, die Unterschiede kommen nur dadurch zustande, dass Seiten die den Makron enthalten bei entsprechender Anfrage etwas hoeher gewichtet werden. --chris 論 11:18, 25. Okt 2005 (CEST)

Was soll das mit "Waere" und "haette"? Sind das deutsche Wörter? Oder kann dein Computer die noch nicht? Es tut uns leid, dass wir dir nicht bescheid gegeben haben! :-)) Wer sagt denn, dass es keine "deutsche Übersetzung" für Sudoku gibt? Hast du schon mal Die Zeit gelesen? Oder die BZ oder den Tagesspiegel oder oder oder ... ? Alle benutzen das deutsche Wort Sudoku! Sprache lebt! Und in Internetzeiten sogar etwas schneller! Warum sollte in einer deutschen Enzeklopedie ein Wort japanisch geschrieben werden? Du musst weiter leiden. P.S. Den zweiten Teil deiner Einwände verstehe ich nicht. Warum sollte man eine Weiterleitung einrichten, wenn sie sowieso kein deutschsprachiger suchen würde? -- Matze12 00:42, 26. Okt 2005 (CEST)

Ist Sudoku eine japanische Erfindung?

Nein, sicher nicht, denn das Spiel gab es in China schon vor mehr als 2'000 Jahren unter dem Begriff 九宮格 (oder jiugongke)! Dies scheint mir einfach wichtig zu sein, wenn es darum geht, den Diebstahl von chinesischem geisitgen Eigentums zu japanisieren!

Falsche Mutmaßungen unter "Algorithmisch"

Die aktuelle Beschreibung zur Lösung von Sudokus wird diesem Rätsel nicht gerecht, sie ist weitestgehend nicht korrekt. Nur ganz einfache Sudokus lassen sich mit der beschriebenen "Schnittmengenmethode" (im Englischen "scanning" genannt) lösen. Es gibt noch eine ganze Menge weiterer logischer Methoden, um die möglichen Ziffern pro Feld einzugrenzen. Eine Ziffer kann z.B. auch dann zwingend einem Feld zugeordnet werden, wenn dieses Feld der noch einzige mögliche Platz in einer Zeile für diese Ziffer ist (obwohl in dem Feld auch noch andere Ziffern nach der Schnittmengenbildung möglich wären); ganz zu schweigen von Strategien wie "X-Wing", "Sword-fish", ... Die Sudoku-Seite im englischen Wikipedia beschreibt das Rätsel, Voraussetzungen und Lösungsansätze übrigens ganz gut!

Ich löse Sudokus auf meinem Computer mit der Backtracking-Methode. Hast du deinen Algorithmus auch programmiert? Wie ist deine Performance? --Matze12 00:08, 7. Aug 2005 (CEST)

Ich habe mir nur einen relativ einfachen "Sudoku-Assistant" gebastelt, der einem das einfache Mitführen der Möglichkeiten pro Feld abnimmt und mittels Farbe einfache Hinweise gibt. Kompliziertere Überlegungen (Paare, X-Wings, etc.) muss man noch selber einbringen, womit der Spaß am Lösen bleibt! -- 7.8.05

Algorithmus zum Erstellen

Wie ich ein Spielfeld erstelle, welches nicht die Regeln verletzt, ist mir klar (und recht trivial). Wann gilt jedoch ein Spielfeld als schwer, bzw. als einfach? Welche Felder (wie viele Felder, wenn man jede Lösung als gleichberechtigt betrachtet) muss ich rausnehmen? Möglichst viele? Möglichst wenige? So, dass es nur eine Lösung geben kann, aber jedes Feld zu Anfang möglichst viele potentielle Kandidaten hat?

Ist ein Sudoku nur dann gültig, wenn es genau eine Lösung dafür gibt?

Ist der Algorithmus vollständig?

Wenn ich mir das Sudoku-Wiki-Bild anschaue, dann bekomme ich nach der beschriebenen Formel folgende Kandidatenmenge für Zeile 6, Spalte 7:

$K_{6,7}=\{4\ 5\ 8\ 9\}$

Meine Logik sagt mir aber, dass hier nur eine 8 stehen kann wegen der 8-en in den beiden Blöcken links und dem Block unterhalb sowie den noch übrigen freien Felder im eigenen Block. Muss man deshalb die Formel für die Kandidatenmenge nicht erweitern? Ist die angegebene Iterationsformel nicht zu einfach gestrickt? --212.9.163.11 11:35, 6. Aug 2005 (CEST)

Der Text wurde am 8. Aug 2005 um die folgende Passage erweitert: "Das Rätsel muss, um eindeutig lösbar zu sein, so gestellt sein, dass nun mindestens ein Feld eine einelementige Kandidatenmenge besitzt, oder dass ein Element aus einer Kandidatenmenge eines Feldes nicht in den Kandidatenmengen aller anderen Felder der selben Spalte oder Zeile oder des selben Quadrats vorkommt." Die zweite Hälfte der Bedingung erfasst den Fall in obigem Beispiel: Das Feld in Zeile 6, Spalte 7 ist das Einzige seines Blockes, das die 8 in seiner Kandidatenmenge enthält. In diesem Fall wird nun ebenfalls die 8 als einzig korrekte Ziffer für das Feld erkannt.

Ich frage mich allerdings dennoch, ob der Algorithmus vollständig ist, also ob es nicht ein eindeutig lösbares Sudoku gibt, bei dem die obige Bedingung nicht zutrifft. Kann jemand beweisen, dass der Algorithmus vollständig ist, oder ein Gegenbeispiel finden? --84.152.180.150 22:33, 24. Aug 2005 (CEST)

Hier ist eines von vielen Gegenbeispielen:

. . . . 1 . 7 8.
5 . . . . 9 . . .
. . . . . . . 4 .
. 2 6 . . . . . .
. . . 6 . . . . 3
. 7 4 . 8 . . . .
. . . . . 3 . . 2
. 8 . . 4 . . 1 .
6 . . 5 . . . . .

die einzige Lösung ist:
2 6 9 3 1 4 7 8 5
5 4 8 7 6 9 2 3 1
7 3 1 8 5 2 6 4 9
1 2 6 4 3 7 9 5 8
8 9 5 6 2 1 4 7 3
3 7 4 9 8 5 1 2 6
4 5 7 1 9 3 8 6 2
9 8 3 2 4 6 5 1 7
6 1 2 5 7 8 3 9 4

Dein "Gegenbeispiel" ist etwas schwer verständlich. Die mathematischen Mengenbeschreibungen sind richtig. Und mit der Versuch-und-Irrtum-Methode im letzten Absatz findest du auch immer so eine Lösung. Ich frage mich nur bei jedem Sudoku, welches ich löse, ob es noch weitere mathematische Aussagen gelten? An alle Mathematiker: Fügt noch eure Regeln hinzu! --Matze12 01:44, 31. Aug 2005 (CEST)

Tag alle Hier mal meine Meinung zum Thema (habe ein sudoku-lösprogramm geschrieben). Ist der Algorithmus vollständig? Ganz klar nein! Das wird im Artikel aber auch erwähnt. Der Vorschlag, wie man trotzdem zu einer Lösung kommt ist im Artikel: "In diesen Fällen müssen z.B. Paare oder Tripel von Kandidaten gemeinsam betrachtet werden, um die Kandidatenmengen in einem ersten Schritt zu verkleinern." 1. ist dies schwierig (relativ) zu programmieren 2. ist meiner Meinung nach ein anderer Algorithmus da viel effektiver Kommt nämlich ein Kandidat in einer Zeile, Spalte oder Quadrat nur einmal vor, kann er gesetzt werden. Damit können aber immer noch nicht alle Sudokus gelöst werden. Setzt man an dieser Stelle dann auf ein sog. "Try & Error"-Verfahren (Versuch & Irrtum), gestützt auf die beiden anderen Algorithmen, kommt man ganz schnell zum Ziel (wesentlich schneller als ein reines "try & error"-Verfahren). Übrigens können alle diese Algorithmen rekursiv programmiert werden (rekursiv = funktion ruft sich selbst wieder auf) und so mit relativ wenig Programmieraufwand ein hübsches Progrämmchen geschrieben werden. So, hoffe dieser Beitrag hilft irgendwem. Maraca

Ich habe (mal zum Üben) einen genetischen Algorithmus programmiert, der dann aber nicht so toll war. Danach habe ich's mit klassischem Backtracking wie gelernt versucht. Der Algorithmus ist in Java auf einem 2,4 GHz Rechner auch bei "schweren" Sudokus (von http://www.sudokumeister.com/download/pod.html) immer in <1 sec fertig. Dann steht der Aufwand, um "richtige" Lösungsstrategien zu programmieren, eigentlich in keinem Verhältnis mehr. --Rat 02:51, 15. Okt 2005 (CEST)

Grundlagen

Ich habe einige grundlegende Fragen zur Mathematik der Sudokus:

• Wieviel verschiedene Kombinationsmöglichkeiten gibt es?
• Worauf muss man (wenn man selbst ein S. bastelt) achten, damit das Sudoku nicht irgendwo "zweideutig" bleibt?
• Was kennzeichnet ein "schweres" Rätsel im Vergleich zu einem "leichten"? (Wer es lösen will, der merkt es, aber ich habe nach Kennzeichen gefragt.)
• Ab wann ist ein Sudoko lösbar (d.h. wieviele Zahlen muss man vorgeben, wo müssen sie sitzen, darf man eine Zahl in der Vorgabe auslassen usw.)?

--CarstenH 17:03, 7. Sep 2005 (CEST)

Zur ersten und zur letzte Frage hilft dieses Zitat von http://mathworld.wolfram.com/Sudoku.html vielleicht weiter:

Analysis of classic Sudoku has revealed 6670903752021072936960 possible completed grids, and 5472730538 essentially different grids (Felgenhauer et al. 2005). 450 non-equivalent examples are known where 17 givens leads to a unique solution (Royle 2005).

--213.196.210.2 11:15, 8. Sep 2005 (CEST)

Weblinks

Ich finde, es sind zu viele Weblinks. Zudem weiß ich nicht, ob eine Top-50-Linkliste und (rein)kommerzielle Angebote hier hingehören. Und wenn bald jede Zeitung in ihrem Online-Angebot ein Sudoku anbietet ist es auch nicht mehr sinvoll, alle hier zu verlinken. Zwieback 01:34, 15. Aug 2005 (CEST)

Ich habe alle nicht deutschsprachigen, kommerzielle Seiten sowie Linklisten aus den Weblinks rausgenommen. -- Zwieback 02:31, 16. Aug 2005 (CEST)

Ich habe auch nochmal ausgemistet. Nur jeweils einen Generator und ein Programm zum Lösen von Sudokus habe ich drin gelassen. Dazu den Artikel aus der Welt am Sonntag. Schön wären mehr Seiten mit weitergehenden Informationen. --Kurt Jansson 18:31, 3. Okt 2005 (CEST)

Einen Artikel vom "Stern" über Sudoku gibt's hier.

Ich bin erst über ein Widget für Dashboard (Freeware) auf diese Seite gekommen. Vielleicht kann man diesen Link noch mit einfügen: http://www.apple.com/downloads/dashboard/games/sudokuwidget.html. Was meint ihr? --Stefan Uhlemann 12:40, 25. Dez 2005 (CET)

Schnellere Lösungsmethode?

Ich habe jetzt mehrer Websites mit Lösungsmethoden zu Sudokus angeschaut, nach dem ich mir selbst überlegt habe, wie man diese Rätsel lösen könnte. Warum kann ich das ganze nicht als Gleichungssystem auffassen (3 Systemmatrizen mit 9x9 Feldern - einmal für die Spalten, einmal für die Zeilen und einmal für die 3x3 Quadrate) und dann durch rückeinsetzen lösen? Ich könnte mir vorstellen, dass es keine eindeutige Lösung des Systems gibt, weil ja nicht berücksichtigt wird, dass in jeder Zeile/Spalte/Block jede Zahl von 1 bis 9 nur einmal vorkommen darf. Aber wäre es nicht sinnvoll das Gleichungssystem allgemein zu lösen und dann darauf Backtacking anzuwenden, bis eine richtige Lösung herauskommt? Würde das den Rechenaufwand nicht im Gegensatz zu reinem Backtracking vermindern? Vielleicht weiß ja jemand einen Link zu einer solchen Lösungsmethode/Widerlegung der Methode oder kann direkt den Fehler in meinen Überlgungen feststellen/die Überlegung bestätigen? --chsch 17:53, 15. Okt 2005 (CEST)

Die englische Seite sagt folgendes: "... A highly efficient way of solving such constraint problems is the Dancing Links Algorithm, by Donald Knuth." Knuth hat für alles schon einen optimalen Algorithmus. Ich würde mich freuen, wenn mir jemand dazu einen Artikel schreiben könnte. Ich habe Knuths Buch leider nicht zur Hand. Ich hätte es sonst schon in Perl realisiert. --Matze12 16:43, 28. Okt 2005 (CEST)

Der Haken am Vorschlag ist: Gleichungssysteme sind relativ einfach zu loesen, wenn die Variablen reell sind. Hier gibt es allerdings die zusaetzliche Einschraenkung, dass die Variablen (Eintraege im Loesungsvektor) natuerliche Zahlen sein muessen, denn man will ja nicht 0.37 im Sudoku-Feld stehen haben... Kenne den Dancing-Links-Algorithmus leider noch nicht. Ob Algorithmen "optimal" sind, kann man nicht beweisen, nur vermuten -- Die Algorithmen in TAOCP sind aber sehr effektiv. --ln, 22:11, 13. Nov 2005 (GMT)

Der c3le veranstaltet einen Coding-Contest zu dem Thema. Ergebnisse werde ich hier bekannt geben.

Sperrung

Da der Artikel in den letzten Wochen staendig mit irgendwelchen Links fuer Sudoku-Generatoren o.ae. zugemuellt wurde, und die entsprechenden Reverts die History unnoetig aufblaehen, habe ich den Artikel gesperrt. Ein Quelltext-Kommentar mit der Bitte keine weiteren Links mehr einzustellen war wenig bis contra-produktiv. Wenn inhaltliche Aenderungen gewuenscht werden:

1. Um Entsperrung bitten, gerne auch bei mir (Diskussionsseite)
2. Textpassagen hier einstellen und einen entsprechenden Vermerk machen.

--chris 論 11:32, 18. Okt 2005 (CEST)

Der Hofstaat sperrt sich einen

Ja ne is klar, null Ahnung von Sudoku und was es bedeutet, einen guten Generator zu haben, aber einfach mal so handstreichartig gute Links runterzunehmen. Und das offensichtlich ohne weitere Prüfung.

Mich kotzt die Art und Weise langsam an, dass manche Admins und Mods hier aus ihrer pseudoerhöhten Position ihre Profilneurose pflegen. Typisch deutsch übrigens. (vorstehender nicht signierter Beitrag stammt von 81.173.150.66•Diskussion•Beiträge ----Schwalbe ^Disku 13:57, 6. Dez 2005 (CET))

Siehe Wikipedia:Weblinks. Wenn dir dein Link so wichtig ist, dann schreib doch bitte, welchen du dafür rausnehmen willst. Ein paar Textvorschläge sind natürlich ebenfalls höchst willkommen. --Schwalbe ^Disku 13:57, 6. Dez 2005 (CET)

Literatur

Warum ist nichts bei der Rubrik Literatur zu finden, obwohl ich eine Rätselheft habe? Für alle Literaturwühlmäuse hier die ISBN-Nummer und der Verlag: ISBN 3-625-11268-X im NGV erschienen

Unter hier zu erwähnender Literatur würde ich mir eher etwas zur Theorie, Lösungsstrategie usw. vorstellen. Rätselhefte gibt es zahlreich, die müssen wir nicht im Artikel erwähnen. --Schwalbe ^Disku 20:11, 17. Dez 2005 (CET)

Link zu Sudoku-Rätseln

Hallo, der Artikel wurde ja gesperrt, damit keine Links zu Sudoku-Rätsel-Generatoren mehr erstellt werden. Folgender Link führt nicht zu einem Generator, sondern zu Rätseln der Wochenzeitung "Die Zeit": http://sudoku.zeit.de/sudoku/kunden/die_zeit/ Ich denke, dass es sinnvoll ist, hier einen Verweis auf eine vernünftige Seite mit vielen Sudokus zu machen, damit die Leser gleich eine Vorstellung davon bekommen, wie viel Spaß Sudoku macht. Also, checkt die Seite kurz, ob sie für euch in Ordnung ist, dann könnt ihr ja entscheiden, ob der Link euch auch sinnvoll erscheint.--Krambambuli 17:18, 30. Okt 2005 (CET)

Und noch ein Vorschlag für einen Sudoku-Link

Sudoku realtime Generator Rätsel zum Ausdrucken und online spielen

-> Schaut und entscheidet selber!

SUPER! Auf einen Klick bekommt man 4 Sudokus zum Ausdruck auf ein DIN a4 Blatt. Ideal für Bus- und Zugfahrt.

Doch noch ein Vorschlag für einen Sudoku-Link

Sudokumania.de hat - neben dem Üblichen - auch ein Weblog mit aktuellen News zu Sudoku und Lösungstipps auf Deutsch (bisher Mangelware). Wäre vielleicht eine Aufnahme in die Link-Liste zum Thema Sudoku wert? --Fneumeier 10:50, 2. Nov 2005 (CET)

Sudoku spielen Täglich ein neues Sudokupuzzle : zum ausdrucken und online spielen

[1] hat die japanischen Schriftzeichen erklärt.--LivingShadow 17:30, 7. Nov 2005 (CET)

Einen Artikel vom "Stern" zum Thema Sudoku gibt's hier.

Sudoku verlängert bis 30.11.

Sūdoku (jap. 数独, wörtlich Zahlen-Einzel) ist ein Zahlenpuzzle. Das Puzzlefeld besteht aus einem Quadrat, das in 3 × 3 Unterquadrate bzw. Blöcke eingeteilt ist.

Obwohl es wiederholt Probleme mit Weblinks gab/gibt, beschreibt der Artikel ansich das Thema recht umfassend.  Pro --Schwalbe ^Disku 08:35, 23. Nov 2005 (CET)

noch  Kontra: Der Artikel ist schon ziemlich gut. Folgendes stört mich aber, gerade auch im Hinblick auf Lesefreude:

• Unter "Lösungshilfen" ist nur eine einzige Hilfe eingetragen, die zudem noch in die Lösungswege integriert werden könnte. So wirkt das etwas wirr.
• Um die Lösungswege nachvollziehen zu können, muss man permanent im Artikel hoch- und runterscrollen. Einfacher wäre es doch, kleine Ausschnitte mit farblich markierten Lösungsschritten einzubauen.
• Wer sind diese Mathematiker, die die astronomischen Zahlen ausgerechnet haben? Muss man die kennen? Wenn ja, verlinken. Wenn nein, Namen nicht nennen.

Mit geringem Aufwand bekommt man den Artikel bestimmt lesenswert. Dann ändere ich auch gerne in pro um.--Bordeaux 13:53, 23. Nov 2005 (CET)

 Kontra: Die Abschnitte Lösungsmethoden und insbesondere Erstellen neuer Sudokus sehen mir nicht so aus, als ob sie objektiv den Stand der "Forschung" wiedergäben, sondern eher als ob verschiedene Autoren hier ihre persönlichen Theorien zusammengestellt hätten. Das widerspricht dem Grundsatz WP:WWNI Absatz2 (Theoriefinding vs. -darstellung). Diese Dinge gehören, wenn überhaupt, in die Diskussionsseite. Ich denke da hauptsächlich an das "Auswürfeln" neuer Sudokus. Ich kann mir nicht vorstellen, dass die verschiedenen Websites und Rätselhefte auf diese Weise ihre Sudokus erstellen, anschließend lösen und so beurteilen, ob es schwer oder leicht war. --Rat 20:50, 23. Nov 2005 (CET)

---

Schade. Na denn, wo sind die Mathematiker, die "den Stand der Forschung" kennen? Mir hätte ja das bisherige gereicht, aber wenn es noch mehr gibt - um so besser. ;-) --Schwalbe ^Disku 08:58, 30. Nov 2005 (CET)

Erneute Sperrung

Wikipedia ist keine Linksammlung (7.4): Da der Artikel schon wieder mit irgendwelchen Links fuer Sudoku-Generatoren o.ä. zugemüllt wurde, und die entsprechenden Reverts die History weiter aufblähen, habe ich den Artikel erneut gesperrt. Wenn inhaltliche Änderungen (siehe Kommentare zur Lesenswert-Kandidatur) gewünscht werden:

1. Textpassagen hier einstellen und einen entsprechenden Vermerk machen.
2. Um Entsperrung bitten, gerne auch auf meiner Diskussionsseite. --Schwalbe ^Disku 08:58, 6. Dez 2005 (CET)

Sudoku mit uninformierter Tiefensuche lösen???

"Auf dem Computer kann man ein Sudoku mit der Backtracking-Methode lösen. Beginnend mit dem ersten freien Feld, probiert man systematisch, mit der Eins beginnend, ob man zu einer Lösung kommt. Beim ersten Widerspruch geht man zurück (engl. backtrack). Dieser Lösungsweg lässt sich sehr elegant rekursiv formulieren, und man ist sicher, dass alle Kombinationsmöglichkeiten abgesucht werden."

--> Zweifellos wäre es deutlich erfolgversprechender, zu versuchen den Atlantik im Handstand zu überqueren, als ein Sudoku mit einer uninformierten Tiefensuche lösen zu wollen. Wer sich auch nur ein wenig mit KI auskennt, wird bei derart gelagerten Problemfällen immer eine Constraint-Suche mit vorheriger Constraint-Propagierung wählen. Allenfalls lokale Suchstrategien wären sonst noch denkbar.

"Da es sich um tausende Wege handeln kann, ist dieser Algorithmus nur für Computerprogramme geeignet."

--> ROFL! Diese Aussage ist gleichwertig mit der Aussage: "Das Universum besteht aus mehreren tausend Atomen."

"Der Lösungsalgorithmus ist sicher nur suboptimal, da er keinerlei analytische Vorinformationen verwendet und nur durch Ausprobieren vorgeht. Es stellt also den schnellen Weg zu einer Lösung, aber nicht unbedingt einen schnellen Lösungsweg dar."

--> Zuerst einmal sollte "suboptimal" durch "völlig unbrauchbar" ersetzt werden. So gesehen stellt der Algorithmus auch garantiert keinen "schnellen [im Sinne von einfachen] Weg zu einer Lösung" dar, da er eine Lösung mit größter Wahrscheinlichkeit nicht vor dem Ableben des Implementierers findet.

Fazit: Der ganze Abschnitt ist unrettbar und sollte gelöscht oder neu geschrieben werden.

--Novil Ariandis 01:29, 22. Dez 2005 (CET)

Ich muss dir wiedersprechen. Die Backtracking-Methode ist eine anerkannte Methode, solche Probleme zu lösen. Häufig reichen wegen der rekursiven Programmierung 3 bis 10 Programmzeilen. Dieses muss ja nicht bei dem Sudoku beschrieben werden. Leider ist der Backtracking-Artikel vor einem Monat gelöscht worden, da einer eine Urheberrechtsverletzung begangen hatte. Huch, er ist seit einigen Tagen wieder da! Deshalb bitte ich dich, meine obige behalten-Aussage, dort zu überprüfen. Oder frage mal Informatik-Studenten nach dem ersten Algorithmenkursus.

Du bist aufgefordert deine KI-Constraint-Suche genauer zu beschreiben. Wenn ich tausende Sudokus zu lösen hätte, würde ich das ja auch so machen. Im englischen Wikipedia ist auch der Dancing Links Algorithmus von Donald Knuth beschrieben, der mich auch sehr interessieren würde. Es gibt immer mehrere Wege nach Rom! Sei etwas toleranter! --Matze12 02:48, 22. Dez 2005 (CET)

Natürlich ist der Backtracking-Algorithmus schön kurz, aber aufgrund des wahnwitzigen Verzweigungsfaktors völlig unbrauchbar. Das hat nichts mit fehlender Toleranz gegenüber einfachen Algorithmen zu tun. Einfache Ansätze, die trotzdem schnell sind, sind klasse! Wenn der Verzweigungsfaktor nicht zu groß wird, ist Backtracking-Suche immer eine gute Alternative, in diesem Fall aber garantiert nicht. Was ich geschrieben habe war allgemeiner Konsens in unserem Kurs "Einführung in die KI", wo dieser Abschnitt des Artikels besprochen wurde. Und ich gehe doch mal schwer davon aus, dass sich 30 Informatikstudenten im Hauptstudium plus ein Dozent sich nicht alle derart gewaltig irren. --Novil Ariandis 10:29, 22. Dez 2005 (CET)

Meines Erachtens ist das hier Backtracking. Probier's mal aus... --Eike 22:59, 22. Dez 2005 (CET)

Was für ein "wahnwitziger Verzweigungsfaktor"? Jede Zelle hat neun Möglichkeiten der Verzweigung. D.h. dein Faktor ist im Durchschnitt 4,5. Nun lass mal die Kirche im Dorf! Außerdem haben wir nur 81 Felder zu berechnen, wovon meist schon 28 bekannt sind. Deine Forderung nach einem einfach zu programmierenden Algorithmus, der zusätzlich auch noch schnell ist, ist depressiv. So funktioniert die Welt selten. Du wirst dich also sehr häufig ärgern müssen. Wie du es gerade hier machst. Ich habe kein Problem damit, wenn der Computer arbeitet und ich eine Lösung in vertretbarer Zeit bekomme. Ich bleibe dabei: Backtracking ist eine geeignete Methode zum Lösen von Sudokus! (Ich darf mich ja auch mal wiederholen.) Und bitte nenne nicht etwas, was ich täglich benutze, "völlig unbrauchbar"! --Matze12 01:54, 23. Dez 2005 (CET)

...und die "vertretbare Zeit" liegt bei meinem Beispiel unter einer Sekunde. --Eike 11:36, 23. Dez 2005 (CET)

Ich schlage zu dem Absatz zwei Änderungen vor: Aus "tausende" könnte man "sehr viele" oder etwas vergleichbar Allgemeines machen. Den letzten Satz, "Es stellt also den schnellen Weg zu einer Lösung, aber nicht unbedingt einen schnellen Lösungsweg dar.", würde ich ersetzen wollen durch "Dennoch ist er auf gewöhnlichen PCs sehr schnell." --Eike 13:02, 24. Dez 2005 (CET)

Eike, ich bin nicht einverstanden. Es sind tausende. Ich zähle das immer nach. Warum dann ungenauer formulieren? Ich gebe zu, dass die Formulierung "schnelle Lösung ..." auf alle Backtracking-Lösungen zutrifft und nicht Sudoku-spezifisch ist, sie ist aber richtig und einprägsam. Deine "Dennoch ..."-Formulierung finde ich zu passiv formuliert. Besser wäre der zusätzliche Satz: "Auf gewöhnlichen PCs hat man eine Lösung in unter einer Sekunde." Das ist ja auch noch ein wenig von der gewählten Programmiersprache und der Compileroptimierung abhängig. --Matze12 19:53, 25. Dez 2005 (CET)

Mir war unklar, was mit "tausende Wege" gemeint sein könnte. Die durchprobierten kompletten Feld-Belegungen sind wohl meistens genau eins. Die durchprobierten einzelnen Zahlen hatte ich bis eben nicht zählen lassen - bei den zwei Rätseln, die ich probiert habe, ist die Anzahl aber tatsächlich vierstellig. Damit ist die Zahl wohl richtig, aber die Formulierung der "Wege" finde ich unverständlich. (Dabei bin ich Informatiker, und es sollte ja auch für Nicht-Informatiker verständlich formuliert sein...)

Den Satz "Es stellt also den schnellen Weg zu einer Lösung, aber nicht unbedingt einen schnellen Lösungsweg dar." finde ich zum einen entschieden unelegant - und zum anderen falsch. Unter einer Sekunde ist einfach mal schnell. (Hätte vor dem Ausprobieren nicht gedacht, dass es so schnell gehen könnte.)

Dein Vorschlag "Auf gewöhnlichen PCs hat man eine Lösung in unter einer Sekunde." passt so nicht so richtig zum Satz davor: "Der Lösungsalgorithmus ist sicher nur suboptimal, da er keinerlei analytische Vorinformationen verwendet und nur durch Ausprobieren vorgeht." Klingt nach "Es ist langsam (ja, ich weiß, dass das so nicht da steht, es klingt aber so). Es geht sehr schnell." Es sollte schon ein "aber", "dennoch" oder Ähnliches rein. "Unter einer Sekunde" einzubringen find ich ok. Also vielleicht "Dennoch erhält man die Lösung auf gewöhnlichen PCs innerhalb einer Sekunde."?

--Eike 20:10, 25. Dez 2005 (CET)

Kleiner Tipp an den Studenten und seine 30 Kumpels: Backtracking IST ok, denn es beinhaltet bereits mehrere Constraints. Immerhin werden nicht erst 81 Ziffern eingetragen, um dann zu prüfen, ob die Lösung valide ist, SONDERN es wird der Reihe nach probiert und sofort nach dem ersten Konflikt (Zeile, Spalte, Zelle) abgebrochen. Die Zahl der abzulaufenden Pfade reduziert sich dadurch dramatisch! Und nochwas: Sag Deinem KI-Dozenten, dass das hier ein NP-Problem ist und daher nicht einfach deterministisch gelöst werden kann, d.h. es gibt keinen Algorithmus, der nicht probiert (immer vorausgesetzt, es sind nur wenige Konstanten gegeben).

Mit Ersterem hast du natürlich recht. Leider zeigt Novil Ariandis nicht die Größe einzugestehen, dass er sich da viel zu weit aus dem Fenster gelehnt hat.

Letzteres halte ich für falsch. Ich hab noch kein Sudoku-Rätsel gesehen, bei dem man hätte probieren müssen. Warum ein Sudoku nicht NP-vollständig sein sollte, erschließt sich mir nicht. Welchen Aufwand setzt du denn an?

--Eike 19:27, 3. Jan 2006 (CET)

Größe hin, Größe her. Du widersprichst Dir. Du sagst, Sodokus wären NP-vollständig. Das ist korrekt. Aber dann sagst Du, du müsstest nicht probieren. Das stimmt nicht. Glaubst Du nicht? Gut, dann sage mir, wie viele Lösungen das folgende Sodoku besitzt (und wehe Du probierst :-):

123456789
.........
.........
.........
.........
.........
.........
.........
.........

"Ich hab noch kein Sudoku-Rätsel gesehen, bei dem man hätte probieren müssen." Jedenfalls kein ernst gemeintes. Zeig mir ein in einer Zeitung abgedrucktes Sudoku-Rätsel, das absichtlich nicht eindeutig, sondern nur durch Raten lösbar ist. Meines Erachtens ist die Eindeutigkeit eine Eigenschaft dieser Rätsel. --Eike 18:49, 4. Jan 2006 (CET)

Eindeutigkeit ist eben keine Eigenschaft. In der Beschreibung steht richtig "typischerweise" werden Konstanten vorgegeben - aber nicht zwingend. Es gibt also Fälle, in denen es für eine Vorgabe an Konstanten 2, 3 oder n viele Lösungen geben kann. Natürlich sind solch komplexe Rätsel manuell kaum noch lösbar - was aber nicht heißt, dass sie ungültig sind. Du solltest Sodokus nicht auf Zeitschriften-Rätsel reduzieren.

Beispiel: Das folgende Sodoku besitzt 192 gültige Lösungen.

123456789
456789123
789123456
561278934
932564871
874391265
.........
.........
.........

Wenn keine Konstanten vorgegeben werden, ist es kein Rätsel mehr. Zeig mir etwas, was als Sudoku-Rätsel veröffentlich wurde (Webseiten zählen dabei nicht, Druckwerk bitte), das nicht eindeutig lösbar ist. Im übrigen steht da nicht, dass typischerweise Konstanten vorgegeben werden, sondern dass typischerweise 22 bis 36 Konstanten vorgegeben sind. --Eike 11:40, 5. Jan 2006 (CET)

Ist mir zu doof. Dann sind es eben keine Sodokus, sondern Sadomasos! Tschüß -- 193.174.102.33 11:47. 5. Jan 2006 (CET)

Mir ist das auch zu doof. Auch Tschüß für diesen Diskussionspunkt. Macht doch was ihr wollt. Eike ich bin sauer. --Matze12 17:56, 5. Jan 2006 (CET)

Andere Namen

Es sollte vielleicht auch erwähnt werden, dass Sudoku auch unter den Namen "Number Place", "Zahlenplatzierung" und "Neunerkniffel" angeboten wird. Vielleicht gibt es sogar noch mehr Namen. -- ChrisM 11:20, 22. Dez 2005 (CET)

B166ER

Mein Name ist Daniil Mojerman und ich bin 15 Jahre alt. Ich habe ein Algorithmus entwickelt mit dem man durch logische Prozesse auf das Ergebniss kommen kann. Sollte sich jemand dafür interessieren, auf meiner Benutzerseite findet ihr alle nötigen Daten um mit mir Kontakt aufzunehmen (Leider kann ich noch immer keine Links einfügen). Dabei habe ich 2 Gedankenschritte angewandt. Zuerst erstelle ich eine Tabelle, in der zu jeder Variable alle möglichen Belegungen zu finden sind. Danach suche ich mit meinem Programm nach Stellen, die nur noch eine mögliche Belegung haben können. Der zweite Gedankenschritt ist, dass ich aus meiner erstellten Tabelle die möglichen Belegungen von Stellen aus einer Zeile bzw. Spalte bzw. 3x3 Sektor nehmen, und nach Stellen suche, die als einzige in der Reihe einen bestimmten Wert annehmen können. Nunja, ich hab an dem Algorithmus ca. 2 Wochen geschrieben und konnte auch 20 von 19 SUDOKU-Spiele damit lösen. Eines von den 20 hatte für meinen Algorithmus zu wenig bekannte Faktoren. Trotzdem finde ich es als ein relativ sicheres Verfahren. Der Link zu meinem Programm ist www.bereg-menestrel.de/sudoku_regenerator/index.html . Für Fragen stehe ich gerne bereit. Ahhhhh ... jetzt habe ichs raus!

B166ER