Diskussion:Sudoku/Archiv/1

Dieses Diskussionsarchiv hat die empfohlene Seitengröße erreicht und gilt damit als abgeschlossen. Sein Inhalt sollte nicht mehr verändert werden (ausgenommen Kleinbearbeitungen wie Link- und Vorlagenfixe). Verwende für die Archivierung von Diskussionsbeiträgen bitte das aktuelle Archiv und benutze bitte für aktuelle Diskussionen die aktuelle Diskussionsseite. Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise [[Diskussion:Sudoku/Archiv/1#Abschnittsüberschrift]] oder als Weblink zur Verlinkung außerhalb der Wikipedia https://de.wikipedia.org/wiki/Diskussion:Sudoku/Archiv/1#Abschnittsüberschrift

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 Google "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!

Gute Idee, weil gerade die Chinesen für den Schutz von geistigem Eigentum ja sehr bekannt sind (autos, transrapid...) :-)) (nicht signierter Beitrag von 213.61.179.82 (Diskussion) )

Was willst du damit sagen? Diebe darf man beklauen? Beziehungsweise Landsmänner von Dieben? --Eike 20:31, 8. Mär 2006 (CET)

Eine Diskussion um die japanische Erfindung ist doch müßig, wenn die ersten Rätsel 1979 in Amerika veröffentlicht wurden. Wo sie ihren Durchbruch erlebt haben, spielt doch für den Herkunftsnachweis keine Rolle?

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

Reines Backtracking ist so ziemlich das naivste was man machen kann, zumal das bei größeren (16x16) Sudokus arg in die Hose gehen kann, je nach Programmiersprache. Der c3le hat einen CodingContest zu Sudoku veranstaltet, es wird bald dazu eine eigene Seite geben, deren Ergebnisse ich online stellen will; es kamen mehrere Beiträge (u.a. in Haskell, Sed, c++, Java und Lisp) zustande, deren Ansätze zwar nichts großartig neues aufzeigen, aber sicher performanter als Backtracking sind ;-) --Feuervogel 00:44, 28. Mär 2006 (CEST)

Also für 9*9 dauerts es weniger als 'ne Sekunde (C++). Gib mir ein 16*16-Rätsel, und ich kuck mal, wie lang das dauert. --Eike 08:35, 28. Mär 2006 (CEST)

Bitteschön: [1] mit dem titel: "16x16 wirklich schwer von blitz". für das "ein grosses 16x16" brauche ich seit heute abend mit php unter einer sekunde. allerdings war bei unserem coding-contest die c++-lösung auch die schnellste. --Feuervogel 02:02, 30. Mär 2006 (CEST)

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?

"Im Allgemeinen wird vorausgesetzt, dass ein Sudoku nur eine Lösung hat. Diese Eigenschaft wird zum Teil sogar benutzt um ein Rätsel zu lösen (In Zeile a stehen die Zahlen x und y an den Positionen m und n. Wenn jetzt x in Zeile b in m oder n steht, kann nicht y auch in diesen Feldern stehen, sonst wäre das Rätsel nicht mehr eindeutig lösbar. Die Schwierigkeit eines Sudoku lässt sich meines Wissens nur über tatsächliches Testlösen bestimmen. Ich habe schon Rätsel mit 17 Vorgaben gesehen, die verhältnismässig einfach zu lösen waren. Das Gegenteil bildet ein Rätsel von der letzten deutschen Meisterschaft, das 61 (!) Vorgaben hatte aber nach übereinstimmender Aussage "nur" durch Raten gelöst wurde..."

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)

Meiner Meinung nach ist das Grundlegende des Rätsels bzw. Spiels nicht ausreichend und auch nicht gut erklärt. Es fehlt mir als Leser des ersten Abschnitts das Aha-Erlebnis: "Worum geht es überhaupt?" "Was ist das Ziel des Spiels?" "Regeln im Überblick" stattdessen geht es gleich in die mathematische Ecke mit Lösungsstrategien etc. (nicht signierter Beitrag von 84.135.140.34 (Diskussion) 12:45, 26. Mär 2006)

Ich habe die Einleitung mal etwas verändert, so besser? -- Ολλίμίνατορέ ^Ω 16:42, 26. Mär 2006 (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)

Also ich fände es gut wenn möglichst wenig Links zu Sudoku Seiten in den Weblinks wären. Wikipedia ist keine Linkliste oder Webverzeichnis und Sudokuseiten, Solver, etc sind per Suchmaschine sehr einfach zu finden. Vielleicht sollten alle Links entfernt werden, da die meisten, nach meiner Meinung, wenig bis gar nichts zu dem Artikel beitragen und letztendlich meist nur Werbung für eine Seite sind.

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.

Hier findet man eine Implementierung des 'Dancing Links' Algorithmus zur Lösung von Sudokus in Java

Dancing Links ist eigentlich kein Algorithmus sondern nur eine Technik um Backtracking in der Praxis elegant umzusetzen. Zusätzlich kann man Backtracking auch noch durch Heuristiken wie foreward-checking oder constraint propagation beschleunigen. Sudoku ist übrigens NP-vollständig. Deshalb macht es eigentlich auch wenig Sinn sich über "Optimalität" Gedanken zu machen. -- Marc D. Migge 01:12, 5. Nov. 2006 (CET)

Es ist übrigens auch möglich Sudokus mit ganzzahlig linearer Optimierung zu lösen. Thorsten Koch hat dazu ein Paper (Rapid Mathematical Programming or How to Solve Sudoku Puzzles in a few Seconds) geschrieben, welches auch Codings für die Modellierungssprache ZIMPL enthält. Ach ja, wieso und in welcher Form ist Sudoku NP-vollständig? Gibt's dazu irgendeine Ausarbeitung?

Werd ich mal lesen. Warum Sudoku NP-vollständig ist kann man z.B. hier lesen: ( http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdf ) Außerdem ist Sudoku wohl äquivalent zu en:Exact Cover (s. Abschnitt 6.3 dort). -- Marc D. Migge 00:02, 18. Nov. 2006 (CET)

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)

Gibt es eigentlich in der Wiki-Software auch die Möglichkeit, nur Teile des Artikels zu sperren, also hier konkret den Abschnitt 'Weblinks'? --130.83.244.x 15:36, 18. Jan 2006 (CET)

Leider nicht, ich könnte ihn nur ganz für IP-Edits sperren, dann wärst du allerdings auch betroffen. ;-) --Schwalbe ^Disku 17:27, 18. Jan 2006 (CET)

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

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

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

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

Herzlichen Glückwunsch, du hast das NP Problem SUDOKU auf SAT reduziert. Das lernt man eigentlich im Informatikstudium, aber ist sicher recht bemerkenswert, wenn man da von selbst draufkommt. Wenn du mehr darüber wissen willst, was du gemacht hast, kannst du nach "Erfüllbarkeitsproblem der Aussagenlogik" googeln und dich SATlesen (haha Wortspiel ^^). MFG und bitte signiere deine Beiträge. --F GX 15:02, 23. Okt. 2009 (CEST)

6 jahre

> Sechs Jahre brauchte er, um eine Software zu entwickeln, die neue Sudokus per Knopfdruck entwickeln kann. kann da irgendjemand die quelle angeben? mir komt dasein gaaanz klein wenig zu lange vor. Elvis_untot [[Benutzer_Diskussion:Elvis_untot|42]] 12:32, 7. Jan 2006 (CET)

also in dem Sudoku Rätselbuch von Zeit und Handelsblatt steht auch 6 Jahre. --G-Man Diskussion 15:18, 7. Jan 2006 (CET)

Was natürlich eine sehr seriöse Quelle ist. Bitte rausnehmen, niemand benötigt 6 Jahre dafür, ich kenne dutzende Generatoren, welche das auch machen. Wenn er wirklich 6 Jahre gebraucht hat, war er SEHR inkompetent. ~~

Ich habe das mit den sechs jahren auch schon des öfteren gelesen. Ich fands zwar auch lustig findes es aber durchaus 1. glaubens 2. erwähnenswert ~~

admelyssis: Ich hab im Urlaub einen eigenen Lösungsalgorithmus und Generator ohne Internet/Literatur etc. in je etwa 4 Stunden im Hotelzimmer geschrieben. Die 6 Jahre kann ich mir nur mit sehr alten Computern mit sehr wenig Speicher erklären (schlechter als C64 z.B.) oder vielleicht damit das er die Software besonders teuer verkaufen wollte?

Offline Generator

Ich empfehle diesen Generator hier: "SuDoKu Generator" Der ist ebenfalls Offline, bietet aber viel mehr: Rätsel sind ausdruckbar oder als Bild speicherbar. Es lassen sich auch 4 Rätsel auf einer Seite ausdrucken. Zudem lassen sich Zahlen vormerken, was das Rätseln angenehmer macht und es lassen sich auch eigene Rätsel lösen. Es ist in Java geschrieben, so kommen auch Linux oder Mac User auf ihre Kosten...

Okay ich hab ihn jetzt mal mitreingenommen ! Für die anderen OS ist halt auch gut, benötgt aber JAVA .... (-)

Denke das die WebLinks jeztzt perfekt sind. D.h. es werden KEINE neuen mehr benötigt. Wenn jemand noch nen GEistesblitz hat, dann soll er ihn hier bitte posten, bevor er ihn reinhaut !!!

mfg nico

Aha jett isser wieder draussen, lol. Scheint wohl nicht so gemocht zu werden ^^

/mfg nico

Wurde rausgenommen wegen direktem Download. Hab das mal geändert.

Scheiß Zensur hier! Muss man echt mal sagen. Warum keine weiteren Links? Es gibt hier bisher nur dumme Exe-Dateien (wer will sowas schon runterladen -> Sicherheitsrisiko) und JAVA-Programme (haben manche ebenfalls aus Sicherheitsgründen aus) als Sudoku-Links. Wie wär's denn mal damit, den neulich gelöschten Link vom tollen JavaSCRIPT-Rätsel wieder einzustellen? Nein? Dann macht doch den ganzen Laden hier dicht, wenn man nix mehr einfügen darf. Das geht am Wikipedia-Konzept total vorbei und ist echt daneben.

Ersetzt diesen Offline-Generator("Offline Sudoku (Game + Generator + Helper + Solver)" - Für die Offliner unter uns). Der ist viel zu umständlich, hat zu wenige Features und sieht schlecht aus. Es gibt wirklich genügend bessere...

Mach doch einen Vorschlag für einen besseren... Am Besten einen wo es eine deutsche Version davon gibt. -- Stephan Heuscher 17:39, 17. Feb 2006 (CET)

Ich bin für den Java-Generator: "SuDoKu Generator" Benötigt zwar Java, dafür sind auch Linux/Mac User bedient. Hat zudem ziemlich viele Features die das Rätseln angenehm machen.

Der Java-Generator ist zusätzlich noch Deutsch. Habe den Link getauscht. -- Stephan Heuscher 13:06, 19. Feb 2006 (CET)

Ich verstehe dass Plusminus seinen eigenen Generator hier drin haben will, aber diese Begründung ist doch Schrott! Bei den meisten läuft Java und der .exe Generator hat kein einziges Feature mehr, ist nur schlechter zu bedienen und sieht schlechter aus. Jemand sollte die Programme mal testen und ein Machtwort sprechen ;-)

Ich stimme der obigen Aussage voll zu. Weder die Installation noch die Bedienung ist beim Englischen .exe besser als beim Deutschen Java Programm. Hab beide ausprobiert und finde das Java besser. Aus eigener Erfahrung kann ich auch sagen, dass ein Link auf der Wikipedia Sudoku Seite ca. 200 Visits/Tag bringt. Da versteht man die Motivation schon besser. Bitte meldet euch, falls Ihr einen besseren Offline-Generator (in Deutsch) kennt. Ich werde den Edit von Plusminus zurücksetzen. Stephan Heuscher 22:12, 19. Feb 2006 (CET)

- Meinung zu: http://mos-page.ch.vu/?section=SuDoKu

JAVA wird von beinahe niemandem genutzt, bzw rafft niemand es zu nutzen !!!111einself Ich weiß es nicht genau aber ~95% der besucher nutzen WINDOWS(tm). Wozu dann ein java-programm, das nur die hälfte benutzen kann ?!?!? Die mörder-werbung die den ganzen bildschirm verdeckt möcht ich mal dahingestellt lassen :D

- Meinung zu: http://www.heuscher.ch/Sudoku

Naja, du hast die features angesprochen ... Bei dem windows-dings sind irgendwie viel mehr features, die drucken-möglickeit is ganz nett. Außerdem sind beide JAVA-teile unübersichtlich bis zum geht nicht mehr ... Der braucht irgendwie sehr lang zum lösen ... zZzZzzZ (Web-Zeug halt) Ich finde seine begründung halt irgendwie besser...

oje, funzt netmal ganz richtig ^^ tztztz..

--> Rücksetzung

/shadow

Plusminus: Siehtste ... Außerdem, wie du merkst befindest du dich in der Kategorie OFFLINE-SOlver udn da sollte auch ein OFFLINE-Solver rein und kein SeiteSpeichern-Web-Solver !

Also eins möchte ich mal ganz einfach klarstellen: Die Nutzung von Java ist überhaupt nicht schwieriger als ein .exe! Durch das Web ist Java schon sehr verbreitet und auf den meisten Windows-PC installiert. Der Installer erstellt einen Link auf dem Desktop und im Startmenü. So einfach wie ein exe, man merkt gar nicht, das es Java ist. Jedes Applet braucht auch Java. In den Weblinks sind auch Applets verlinkt und die funktionieren ja bei allen, so wies aussieht, also ist euer Argument völlig nichtig. Die Bedinung des englischen Generators (wieso soll hier ein englischer rein?) finde ich nicht so gut. Für jede Zahl die man eingeben will geht ein Fenster auf, das ist der Horror. -- Kabumm 10:06, 20. Feb 2006 (CET)

Ich stimme Kabumm zu. Warum ein Englischer Solver? Wenn schon, dann auf der Eglischen Wikipedia. Schadow: Danke für dein Feedback. Du hast völlig recht, dass mein Javascript Solver (der in jedem Browser funktioniert) nicht so viele Features hat wie eine Windows oder Java Applikation, aber er kann jedes Sudoku lösen und hilft beim Ausfüllen von "primitiven" Regeln. Wenn du die Seite http://www.heuscher.ch/Sudoku speicherst, wirst du sehen, dass der Solver sehr wohl auch offline funktioniert (Javascript sei Dank). Unter http://www.onlinesudoku.ch/ kannst du kein eigenes Sudoku eingeben, es ist also kein Solver. Ich reverte wieder einmal. :-) -- Stephan Heuscher 11:03, 20. Feb 2006 (CET)

Finde die Änderung natürlich gut. Die Seite onlinesudoku.ch ist wirklich zu 100% von der Seite zeit.de abgedeckt. -- Kabumm 11:13, 20. Feb 2006 (CET)

Plusminus: Bitte stelle dich der Diskussion. Das sture Ändern der Weblinks bringt niemanden weiter. Stephan Heuscher 13:36, 20. Feb 2006 (CET)

Gib mir mal Argumente, für DEINEN (!) Solver, außer dass er (so wie ein weiterer) JAVA-basiert ist ?!?!?! Solange du hier nur Argumente gegen andere bringst, wird das immer zurückgesetzt werden.

Es WIRD ein JAVA-Solver rausgeschmissen, weil es momentan (gleich nicht mehr) 2 (ZWEI) gibt, welche sich nicht wirklich unterscheiden !!! Allein das ist schon ein Grund.

/mfg plusminus

Anmerkung: Erfahrungsgemäß haben mehr Surfer JAVASCRIPT DEAKTIVIERT, als dass sie kein Windows nutzen --> Vorteil dieses Windows-Tools !

shadow

Argumente für http://www.heuscher.ch/Sudoku :

1. Der Löser ist in Deutsch gehalten
2. Der Löser läuft auf jedem Javascriptfähigen Browser, d.h. praktisch jedem Betriebsystem (Java ist nicht gleich Javascript)
   • Dies bedeutet, dass ihn jeder Online-Wikipedia-Benutzer sofort benutzen kann (ohne Download, Viren- oder Phisching-Gefahr)
3. Der Löser unterstützt den Benutzer beim Lösen, indem er ihm die einfachen und fehlerträchtigen Aufgaben abnimmt
4. Der Löser löst jedes Sudoku (auch bei falschen Benutzer-Eingaben)
5. Der Löser ist auch offline einsetzbar
6. Der Löser übernimmt Sudokus von websudoku.com (mithilfe von Bookmarklets), die mühsame Eingabe entfällt
7. Einmal angefangene Sudokus können durch Speicherung des Permalinks-Bookmarks jederzeit weitergeführt werden (auch im Offline-Modus)
8. Der Löser kann auf jede Website integriert werden
9. Der Source-Code des Lösers ist für jedermann einsehbar
10. Ungültige Eingaben können rückgängig gemacht werden
11. Es gibt eine ausführliche Hilfe-Sektion
12. Alles auf einer Webseite
13. Im Link-Text auf Wikipedia steht ganz klar "Javascript"

Mir ist durchaus bewusst, dass es bessere Englische Javascript Sudoku-Programme gibt (z.B. http://www.stolaf.edu/people/hansonr/sudoku/). In Deutsch habe ich bis jetzt nirgends bessere gefunden

Plusminus: Dein Sudoku Programm ist nicht sooo schlecht, aber es ist in Englisch. Bitte übersetze es doch, dann sehen wir weiter. Nimm die Argumente als Ansporn, nicht als Angriff.

Ich bin gespannt auf die Argumente für dein Programm. Stephan Heuscher 14:27, 20. Feb 2006 (CET)

AAAaalllsoo ...

 Pro-Argumente für http://www.alekto-programming.com/modules.php?name=Downloads&d_op=viewdownload&cid=2 :

1. Voll funktionsfähiges Windows-Programm
2. vollkommen Browser-Unabhängig.
3. Sehr beliebt ~4500 Downloads (stark steigend) sprechen für sich!
4. Viele Funktionen
   • Generieren in 5 Schwierigkeits-Stufen (sehr einfach bis extrem schwer)
   • Lösen von jedem eindeutigen Sudoku (die restlichen schafft der 'Normalo'-User nicht)
   • Druck-Funktion (Single-Druck / 6-er-Druck)
   • Durchmisch-Funktion
   • Sehr einfaches Speichern / Laden / Zwischenspeichern
   • Nach dem DL KEINE I-Net Abhängigkeit (auch nicht zum Generieren, wie es bei den anderen Tolls der Fall ist)
   • Einfaches eingeben der Zahlen durch Maus (oder Maus-Tastatur-Kombi)
   • On-The-Fly Help
     • Höhere Übersichtlichkeit, als wenn alle möglichen Zahlen eingetragen sind (de)aktivierbar
5. Dateigröße 527 kB nicht 1,2MB (in Zeiten von Bretiband-Internet kein Thema mehr, nichtmal mit ISDN...)
6. Zeit-Counter + weitere Infos über den Spielstand
7. Klein und übersichtlich.

 Kontra-Argumente zu http://www.heuscher.ch/Sudoku 's-Argumenten:

  1. Der Löser ist in Deutsch gehalten

--> Die vorkommenden Begriffe, wie Play, Help, Mix Generate, Open, Save sind wohl auch Fast-Analphabeten bekannt

  2. Der Löser läuft auf jedem Javascriptfähigen Browser, d.h. praktisch jedem Betriebsystem (Java ist nicht gleich Javascript)
         * Dies bedeutet, dass ihn jeder Online-Wikipedia-Benutzer sofort benutzen kann (ohne Download, Viren- oder Phisching-Gefahr)

--> Stark abhängig vom Web (User-Internet / Hoster ). Inet-/ Traffic-Kosten --> Viren fängt man sich überall (!) im Web ein.

  3. Der Löser unterstützt den Benutzer beim Lösen, indem er ihm die einfachen und fehlerträchtigen Aufgaben abnimmt

--> Kann 'mein' Solver auch

  4. Der Löser ist auch offline einsetzbar

--> Der Löser vielleicht aber der Generator ?? (Nicht nachgeschaut)

  5. Der Löser übernimmt Sudokus von websudoku.com (mithilfe von Bookmarklets), die mühsame Eingabe entfällt

-->

  6. Einmal angefangene Sudokus können durch Speicherung des Permalinks-Bookmarks jederzeit weitergeführt werden (auch im Offline-Modus)

--> Aber KEINE Erstellung von Weiteren!

  7. Der Löser kann auf jede Website integriert werden

--> Der Windows-Solver kann frei verlinkt werden.

  8. Der Source-Code des Lösers ist für jedermann einsehbar

--> Wird wohl kaum jemand ein fertiges Programm weiterentwickeln. Aber egal.

 9. Ungültige Eingaben können rückgängig gemacht werden

--> Funktion in Entwicklung.

 10. Es gibt eine ausführliche Hilfe-Sektion

--> Tipps-Sektion ebenfalls in Konstruktion

 11. Alles auf einer Webseite

--> = Problem! :P

Außerdem: Sehr unübersichtlich ! (alles voller Zahlen) Sortier mal ein bissel / Übersichtlichkeit.

 Neutral Conclusion: Umstrukturierung der Weblinks (Aufteilung in WebLinks und Solver), wie in anderen Sprachen. Weblinks sind nach der Definition (glaube ich) Links, die sich auf den Artikel an sich beziehen.

Änderungen bitte hier Ankünidgen !

/mfg plusminus

Da es Betriebssytem-unabhängige Lösungen gibt, verlinken wir keine Betriebssystem-abhängige Lösung. Windows kostet Geld, Browser und Java gibt's (für die sehr wenigen, die noch nicht beides haben) umsonst. Punkt. --Eike 19:29, 20. Feb 2006 (CET)

Anzahl der Möglichkeiten und minimale Zahl der Vorgaben

Vom Artikel hierher verschoben --Eike 21:26, 27. Jan 2006 (CET)

Einer, dessen Schulzeit allerdings lange(1958) zurückliegt, hat gewisse Zweifel an der Zahl möglicher 9x9-Sudokus: Ich vermute: 9!2!3!3!-Wieso man zu der goßen Primzahl kommt, müßte oder sollte ein Eingeweihter erklären. Zur Mindestzahl von Vorgaben: Reichen nicht 15, z.B. so

o23 456 78o
ooo 1oo ooo
ooo ooo 1oo
o1o ooo ooo
ooo o1o ooo
ooo ooo o1o
oo1 ooo ooo
ooo oo1 ooo
ooo ooo oo1

(nicht signierter Beitrag von 89.51.81.201 (Diskussion) )

Ich sehe nicht, dass die 15 Zahlen reichen würden. Außer der ersten Zeile sehe ich gar kein Feld, das eindeutig bestimmt wäre... --Eike 21:47, 27. Jan 2006 (CET)

Du hast - auf der Artikelseite statt der Diskussionsseite, das bitte nicht noch einmal - die "einzige Lösung" vorgeschlagen. Eine davon deutlich verschiedene ist die hier:

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

Dein "Rätsel" hat vermutlich Milliarden Lösungen. Ich hab den Computer bei 100 Millionen Lösungen gestopt, nach dem Verlauf ist anzunehmen, dass das nur ein kleiner Bruchteil ist.

--Eike 13:38, 29. Jan 2006 (CET)

Da ist wohl etwas schiefgegangen: Zeilen und Spalten sind gegenüber oben genannter Vorgabe vertauscht und eine Zeile bzw. Spalte fehlt. --Hardy42 17:08, 29. Jan 2006 (CET)

Du hast natürlich völlig Recht, ich hab's jetzt korrigiert. Die 100 Millionen Lösungen bleiben unberührt, es war nur ein Ausgabeproblem --Eike 18:42, 29. Jan 2006 (CET)

Es ist nicht möglich, die Zahl möglicher 9x9-Sudokus zu berechnen, indem man die jeweilige Zahl der Möglichkeiten, das nächste Symbol zu plazieren, multipliziert. Die Zahl der möglichen Plätze für ein weiteres Symbol in einer Zeile hängt nicht nur davon ab, wieviele Symbole schon in der Zeile stehen, sondern auch davon, in welchen Blöcken sie stehen. Zur Berechnung sind also einige Fallunterscheidungen notwendig.

Beispiel: Wenn man ein Sudoku zeilenweise füllt, gibt es für die erste Zeile 9! Möglichkeiten. Zur weiteren Betrachtung seien den einzelnen Feldern der ersten Zeile die Variablen a, b, c, d, e, f, g, h, i zugeordnet. Für a, b, c gibt es nun in der 2. Zeile 6·5·4 Möglichkeiten; für d gibt es folgende Fälle:

• a, b, c stehen in der 2. Zeile alle im selben Block wie d in der 1. Zeile => 6 Möglichkeiten für d

Bsp.: 1. a b c  d e f  g h i
      2.        a b c           (oder jede andere Reihenfolge für a, b, c) 
                                  d kann hier unter a, b, c, g, h, i plaziert werden

• von a, b, c stehen genau 2 Symbole in der 2. Zeile im selben Block wie d in der 1. Zeile => 5 Möglichkeiten für d

Bsp.: 1. a b c  d e f  g h i
      2.        a b    c        

• von a, b, c steht genau 1 Symbol in der 2. Zeile im selben Block wie d in der 1. Zeile => 4 Möglichkeiten für d

Bsp.: 1. a b c  d e f  g h i
      2.        a      b c      

• a, b, c stehen in der 2. Zeile alle in einem anderen Block als d in der 1. Zeile => 3 Möglichkeiten für d

Bsp.: 1. a b c  d e f  g h i
      2.               a b c    (oder jede andere Reihenfolge für a, b, c) 
                                  d kann hier unter a, b, c plaziert werden

Für e bis i und die restlichen Zeilen sind weitere - oft noch aufwendigere - Fallunterscheidungen notwendig. Dass man durch Addition dieser Fälle zu einer Zahl mit einem großen Primfaktor kommt, ist plausibel.

Gemäß dem englischen WP-Artikel wurde ein Teil des Ergebnisses durch numerische Berechnung nach der "Brute-Force-Methode" - also gezieltes Probieren per Computerprogramm - ermittelt. Daraus schließe ich, dass keine analytische Berechnungsmethode bekannt (oder möglich?) ist. Auch das spricht m. E. eher gegen eine glatte Zahl wie n!·m!·... --Hardy42 17:05, 28. Jan 2006 (CET)

Zur Frage der Zahl möglicher Sudokus. Und dort, ob die oben nur 15 vorgegebenen Feldern meines Beispiels eindeutig zu einer Lösung führen. Hardy42 schreibt für die 1. Zeile gibt es 9! Möglichkeiten.(9!=1x2x3x4x5x6x7x8x9=362 880) Das sehe ich auch so. Wenn wir nun für die allgemeine Betrachtung die Buchstaben a bis i in die 1. Zeile setzen, behauptet er: Für a,b,c gibt es nun in der 2. Zeile 6x5x4 Möglichkeiten. Für a seh ich auch 6 Möglichkeiten, nämlich die freien Plätze in der mittleren und der rechten (3x3)-Box. Aber schon bei b zweifele ich und vermute nur noch jeweils eine einzige Möglichkeit, nämlich direkt rechts neben a. Alle anderen Plätze scheinen mir - freilich etwas intuitiv - zu inneren Widersprüchen zu führen. Irren ist menschlich. Ein Beispiel, dass b auch einen anderen Platz haben könnte, würde mich so menschlich machen. Danke im voraus! K.-C.W.

Wenn b in der 2. Zeile immer rechts neben a stehen müsste, müsste aus Symmetriegründen auch h immer links neben i stehen; ähnliches würde auch für die erste und zweite Spalte sowie für die letzte und vorletzte Zeile bzw. Spalte gelten. Da die Drittel (3 über- oder nebeneinanderliegende Blöcke) beliebig vertauscht werden können, müsste entsprechendes auch d und e usw. gelten; derartige Überlegungen führen zu Widersprüchen oder es bleiben nur wenige, sehr einfache Sudokus übrig.

Hier ist ein Gegenbeispiel:

a b c  d e f  g h i
d e h  b g i  f a c
i f g  c a h  d e b

h g a  i d b  e c f
b d f  e c a  h i g  
e c i  h f g  b d a

g i e  a b d  c f h
f h d  g i c  a b e
c a b  f h e  i g d

Gruß --Hardy42 12:56, 29. Jan 2006 (CET)

Karl-Christian Weise dankt Hardy42 und Eike für ihre klugen Sudoku-Löungen und -Erklärungen. Ich weiß jetzt, dass ich fast nichts weiß und dass das wohl auch so bleibt. Ich will mich nun von der Sudoku-Spielsucht zu befreien versuchen und verabschiede mich - wenn es in diesem Forum überhaupt als zugelassene Sache gelten kann - mit einem besonders schweren Sudoku, das ich aus einem anderen entwickelt habe.-Wenn Ihr wollt, ärgert Euch man schön! Oder besser ignoriert es brav! (Aber vielleicht schau ich doch später hier noch mal nach, ob mich weitere Reaktionen überraschen.

                         6oo ooo o1o
                         oo4 871 260
                         o1o 6o2 oo8

                         ooo 16o 834
                         46o ooo 197
                         3o1 7o4 ooo

                         8oo 2o7 o41
                         o49 o16 o8o
                         1oo ooo ooo

Gut gemacht, nicht zu leicht, aber zum Ärgern reicht's nicht. Gruß --Hardy42 00:14, 1. Feb 2006 (CET)

Mit 37 gegebenen Zahlen kann es nicht so schwer sein (meistens :-P). Es ist schon etwas verwunderlich was alles unter „schweren“ oder „sehr schweren“ Sudokus auf manchen (Tageszeitungen) Seiten angeboten wird. Wenn man dafür nur die einfachste Technik das „Hidden-Single“ (Versteckter Einer) benötigt. Dann kommt das „Nacked Pair“ und gleich danach das „Locked-“ oder „Hidden-Pair“ (Verstecktes Paar). Diese auch (sehr) einfache Technik wird für das letztere („schwere“) Rätsel benötigt und das auch nur 2mal (demnach ist genau Mitte die 2, 1.Zeile 7.Spalte die 7) und das war's. Das ist auch ein Grund, warum der Artikel nicht Lesenwert (wie im Englischen) sein kann, da diese (und weitere) Techniken hier überhaupt nicht erwähnt, geschweige denn erläutert werden. --Ολλίμίνατορέ ^Ω 01:50, 10. Feb 2006 (CET)

Soo verwunderlich find' ich das nicht: Ein "schweres" Rätsel gelöst zu haben gibt dem Leser ein gutes Gefühl. Und das ist halt wichtig, wenn man ein Produkt verkaufen will...

Die Lösungstechniken sollten tatsächlich beschrieben werden - machst du das? :o)

--Eike 13:04, 11. Feb 2006 (CET)

Mit Vergnügen :-)! Die Engländer sind so verückt, die haben eine ganze Kategorie:Sudoku, wie auch eine Extraseite für alle Begriffe mit Erklärung. Was dann später vielleicht hier auch ausgelagert werden kann (muss). --Ολλίμίνατορέ ^Ω 08:28, 15. Feb 2006 (CET)

Entfernung von online-Solvern und Sudoku-Generatoren

Ich habe die Weblinks um diese Einträge gekürzt. Eine ausführlichere Begründung findet sich hier. Wer so was sucht, möchte bitte selbst bei Google suchen. --Schwalbe ^Disku 13:56, 19. Jan 2006 (CET)

Ich stimme dem zu. --Eike 20:58, 19. Jan 2006 (CET)

Naja, das Problem, dass da immer wieder beliebige Seiten verlinkt werden, wird damit wohl kaum beseitigt. Ich bin der Meinung, eine deutsche Seite, die übersichtlich ist, keine oder wenig Werbung enthält und gratis Sudoku Rätsel, Lösungen und eine Linksammlung anbietet, bringt den Leser weiter. Es ist nicht ganz einfach, in Google qualitativ hochwertige Webseiten zu diesem Thema zu finden. Das zeigt sich z.B. bei der jetztigen Linksammlung: Da ist doch tatsächlich eine englische Lösungsanleitung dabei. Bei den zwei Millionen deutschen Sudoku-Seiten bei Google wäre doch bestimmt auch eine geeignete dabei - nur hat sie noch niemand gefunden... --Heilandsack 19:36, 20. Jan 2006 (CET)

Und du meinst, wenn da eine Seite drinsteht, hält das andere davon ab, ihre einzufügen? Im Gegenteil, die werden sich benachteiligt fühlen... --Eike 19:46, 20. Jan 2006 (CET)

Benachteiligung: Hat denn jemand von kommerziellen Seiten gesprochen? Oder wer soll denn einen Nachteil haben? Deshalb kommt sudoku.nanosim.net wieder rein. Ganz im Sinne von "das Feinste vom Feinsten". Das ist ein Wunsch vieler Benutzer. Kannst ja zur Beruhigung deines Gemütes den Webmaster fragen, ob er im Sinne einer guten Sache den kleinen Google-Ad und den Top-50 Sudoku Button rausnimmt. So wie die Seite aussieht würder er dies warscheinlich sogar machen. Und eine gute deutsche Lösungsanleitung könntest du noch suchen und anstelle der englischen verlinken. Damit es bei max. 5 Links bleibt, habe ich den nutzlosen Zeitungsartikel gelöscht. --Heilandsack 23:09, 21. Jan 2006 (CET)

Ich finde es ja interessant, diese Diskussion weiter zu verfolgen und hatte dazu an dieser Stelle einen zugegebenermaßen kritischen Kommentar zum Thema Löschung der Solverseite nansim verfasst. Zum allgemeinen Verständnis der Meinungsfreiheit Einzelner scheint es zu gehören, solche Kommentare dann auch gleich mit zu löschen. Nur weil man nicht Redakteur ist, oder warum ? Wenn sich schon jemand den Orden für die Letztentscheidung eigenständig umhängen kann, dann sollte er wenigstens akzeptieren, dass es auch andere Meinungen gibt und diese nicht einfach auch noch wegzensieren. Finde ich eine Unverschämtheit. Aber leider gibt es diese Art von Besserwisserei auch in anderen Institutionen; im DMOZ kann man unter den Editoren ähnliche Tendenzen ausmachen. Sollte das etwa menschlich sein ? Dennoch: ich finde es unpassend. ChristianK 6.2.2006

Wenn du eine Antwort haben willst, bräuchte es noch einen Link auf die fragliche Änderung, in der ein Kommentar gelöscht wurde. Den findet du in der Rubrik "Versionen/Autoren". Da ich keine Ahnung habe(n kann), wann welcher Kommentar wo entfernt worden sein soll, find ich den nicht selbst. --Eike 14:17, 6. Feb 2006 (CET)

Falls jemand an einem Online-Solver interessiert ist, der auch Sudokus der Größe 16*16 und 25*25 löst, findet man den unter http://www.ulds.de/sudoku.html. --Uwe 00:04, 18. Apr 2006 (CET)

Weblinks-Aufräumaktion

• "Die Einsamkeit der Zahlen" - Artikel von Detlef Kuhlbrodt in der taz vom 24.12.2005

- Löschung, da der Text inhtlasmäßig beinahe exakt dem Wikipedia Text entspricht

• Sudoku Lösungen, Rätsel und Links

- Löchung, da * "Sudoku-Spiele in "Die Zeit"" die Online-Solver sehr zu genüge abdeckt.

• cw. funpic. de/modules.php?name=News&file=categories&op=newindex&catid=2 "Offline Sudoku (Game + Generator + Helper + Solver)" - Für die Offliner unter uns. Direkt Download

- Einfügung, da es sich um einen OFFLINE-Solver handelt, und dieser die Weblinks und damit den ganzen Artikel bereichert. Vor allem natürlich, für die Leute, die keine Flatrate haben und trotzdem KOSTENLOSEN Sudoku-Spaß genießen wollen !!!

Nun wird die empfohlene WebLink-Anzahl von 5 eingehalten ! Außerdem decken diese Links das Thema vollständig ab.

Bitte Änderungsvorschläge bitte zuerst hier posten !!!

Änderungsvorschlag: http://heuscher.ch/Sudoku aufnehmen (Unterstützer/Solver mit reinem Javascript und Zwischenspeicher). Kann auch im Offline-Modus des Web-Browsers verwendet werden.

Thema Backtracking

Na es gibt nicht nur stupide Backtrackingmethoden, denn z.B. der Dancing-Links-Algorithmus nutzt mit entsprechender Kodierung schon "analytische Vorinformationen".

Mehr hier: http://www.technixblog.de/archives/entwicklung/java/abzahlen-von-sudoku-gittern-mit-dem-dancing-links-algorithmus

Gruß, Marco

Hallo Marco! Das hat ja auch niemand gesagt. Es wäre schön, wenn du den Dancing-Links-Algorithmus - Artikel für uns (Wikipedia) beschreiben könntest. Das habe ich schon im vorigen Jahr (siehe weiter oben) gesucht. Im Artikel Sudoko könnte man diesen Algorithmus dann zusätzlich aufnehmen und verlinken. Gruß --Matze12 19:18, 6. Sep 2006 (CEST)

Dancing Links gibt es in der deutschen Wikipedia als Tanz_der_Kanten (bei dem Titel denk ich aber eher an Schlägertypen in der Disco). Dancing Links ist aber nur die Technik die Knuth verwendet hat um seinen Algorithmus X zu implementieren (s. Abschnitt "Implementations" dort). Da steckt aber "null" Theorie drin. Das ist eine reine Programmiertechnik und ändert an der Backtrackingmethode gar nichts. Was in einem anderen Abschnitt der Diskussion als Constraint Propagation genannt wurde ist auch nur eine Verfeinerung von Backtracking - eine Heuristik die dafür sorgt das nicht mehr blind alle Möglichkeiten in Betracht gezogen werden, sondern nur noch die die "Sinn machen". Im englischen Artikel zu Exact Cover (dieses Problem löst der Algorithmus X) steht übrigens auch wie man Sudoku-Rätsel in Instanzen des Excat Cover Problems umwandelt. Dieser Ansatz ist wohl auch das, was die beiden mir bekannten "Dancing Sudoku"-Programme implementieren. Vielleicht finde ich bald mal die Zeit den Rattenschwanz der da folgt (Backtracking, Dancing Links, Algorithmus X, Exact Cover) in der deutschen Wikipedia zu ergänzen. Dann sollte einer sinnvollen Neugestaltung dieses Abschnitts nichts mehr im Wege stehen. -- Marc D. Migge 02:13, 5. Nov. 2006 (CET)

Ja das wäre gut, wenn du das ergänzen könntest. Ich komme da im Moment leider nicht zu. Habe auch schon eine Anmerkung in der Diskussion zu Tanz der Kanten geschrieben. Gruß Marco

Hallo, ich hab ein Algorithmus geschrieben der sich Rekursiv selbst aufruft und ich denk es entspricht der Methode.

Wenn ihr möchtest, könnt ihr ihn gern verwenden, ich denk das würe einigen Programmieren die Arbeit erleichtern (Programmiersprache ist Turbo Pascal)

{X und Y ist das Feld, welches er ausprobiert, wenn man es durchlaufen lassen will, bei 1|1 anfangen}

    const groesse = 3;
    type TFeld = record
    Feld:Array[1..groesse*groesse, 1..groesse*groesse] of integer;
    end;

    function LoesSoduku(X,Y:integer; var ASoduku:TFeld):integer;
    var BesetzteZahl:array[0..groesse*groesse] of boolean;
   Position:integer;
   Zahl:integer;
   DivX,DivY:integer;
    begin
    if ((X = groesse*groesse) AND (Y = groesse*groesse)) then
    begin
         LoesSoduku := 10;
         exit;
    end
    else if (X = groesse*groesse) then
    begin
         Y := Y+1;
         X := 1;
    end
    else X := X+1;
     
    if (ASoduku.Feld[X,Y] <> 0) then
    begin
         LoesSoduku := LoesSoduku(X,Y,ASoduku);
         exit;
    end;
    for Position := 1 to groesse*groesse do
    begin
         BesetzteZahl[Position] := false;
    end;   
    for Position := 1 to groesse*groesse do
    begin
         Zahl := ASoduku.Feld[X,Position];
         BesetzteZahl[Zahl] := true;
         Zahl := ASoduku.Feld[Position,Y];
         BesetzteZahl[Zahl] := true;
         DivX := (((X-1) div groesse))*groesse + ((Position-1) div groesse)+1;
         DivY := (((Y-1) div groesse))*groesse + ((Position-1) mod groesse)+1;
         Zahl := ASoduku.Feld[DivX,DivY];
         BesetzteZahl[Zahl] := true;
    end;
    for Position :=1 to groesse*groesse do
    begin
        if (BesetzteZahl[Position] = false) then
        begin
             ASoduku.Feld[X,Y] := Position;
             
             if (LoesSoduku(X,Y,ASoduku) = 10) then
             begin
                  LoesSoduku := 10;
                  exit;
             end;
        end;
    end;
    ASoduku.Feld[X,Y] := 0;
    LoesSoduku := 0;
    exit;
    end;

Portal:Denksport

Ich habe vor ein Portal:Denksport zu erstellen. Darin würde eben nicht nur Schach, sondern auch andere Strategiespiele, die sportlich ausgeübt werden, und Randsportarten wie beispielsweise Gedächtnissport oder Kopfrechnen aufgelistet werden und anschaulich vorgestellt werden. Wer hätte Lust, sich daran zu beteiligen?--Gruß,MH ?! Bewertung Let There Be Brights! 16:22, 24. Sep 2006 (CEST)

4er Sudokus

Bei 4er Sudokus befinden sich 4 Zahlen horizontal und vertikal, insgesamt also 16 Zahlen, die den Sudoku-Regeln genügen müssen. Die Menge der 4er-Sudokus ist mit normalen Rechnern leichter handhabbar, deshalb wurden diese Untersuchungen gemacht. Unter [http://zahlen.theateaufcd.de] werden deshalb alle 288 möglichen 4er Sudoku-Felder zu Forschungs- und Lehrzwecken aufgelistet. Diese Zahl wurde empirisch mit einem Perl-Skript ermittelt und kann leicht nachvollzogen werden. Symetrien wurden nicht berücksichtigt. Dabei gibt es 48 Super-Sudoku-Felder, dort kommen auch in den Diagonalen die Zahlen 1..4 vor. Dazu wird beschrieben, wie man algorithmisch auf die Sudoku-Felder kommt. Interessant ist dabei u.A. folgender Aspekt: Wie beim 9er Sudoku ist die Gesamtzahl der Sudoku-Felder ein Teiler der Fakultät der Feldlänge. <Anzahl 9er Sudokus> : 9! geht auf genauso wie 288:24. Das deutet darauf hin, dass eine erste beliebige Reihe, Quadrant, oder Linie mit allen Permutationen (in dem Fall von (1,2,3,4)) aufgefüllt werden und alle anderen leeren Felder davon abhängig sind. Im Fall der 4er Sudokus bedeutet das, dass es nach Setzen der ersten 4er Permutation in beispielsweise die oberste Reihe daraus nur noch 12 weitere Sudoku-Felder generiert werden können, da 288:24=12 ist.

5er Sudokus

IM Sudoku-Heft vom PM-Magazin sind 5*5-er Unterquadrate, also 625 Einzelfelder. Solche Sudokus sind also existent und lösbar, nicht bloß denkbar oder möglich, wie im Text

ZDF-Show

Sollte man irgendwo erwähnen, dass es seit Neuestem im ZDF die Show Sudoku - Das Quiz gibt? --jeanyfan 15:05, 18. Okt. 2006 (CEST)

Roxdoku

Als ich unter Varianten Roxdoku vorgestellt habe, habe ich das getan, um den Lesern die möglichkeit zu geben diese, meiner Meinung nach sehr geniale, Variante selber ausprobieren zu können. Desshalb habe ich auch den Link zum einzigen mir bekannten Spiel das Roxdoku beinhaltet mit angegeben. Leider wurde dieser von Benutzer:Clemfix gelöscht, was ich desshalb entschieden ablehne, weil es für den Leser wertlos ist, von Roxdoku gehört zu haben, ohne es ausprobieren zu können!

Hier der Satz um den es geht: "Ein Computerspiel das neben Sudoku auch noch Roxdoku beinhaltet ist zum Beispiel ksudoku, ein Linuxspiel für KDE. Hier kann man ksudoku herunterladen. [3]"

see335

4.1 Intuitiv

Fehlt da ein Bild an der rechten Seite? Zumindest wird im Text auf ein Bild Bezug genommen. Oder ist das große Sudoku am Anfang des Textes gemeint? Dann sollte das exakter formuliert werden. Mich hat der Text so zumindest irritiert. --KpK (℆) 16:15, 29. Okt. 2006 (CET)

Hab mich ebenfalls darüber gewundert, dass das Bild direkt rechts von dem Text nicht zum Text passt, obwohl der Text sagt "am rechts abgebildeten Beispiel". Bin dafür den Text so zu ändern, dass er sich auf das Bild bezieht welches wirklich rechts daneben ist. Vielleicht dann das Bild noch bis unter die Überschrift hochziehen. --AndiR

Varianten

Sudoku: Man könnte noch erwähnen das X-Sudokus leichter zu lösen sind durch die zusätzliche Einschränkung.

Samurai: Dazu habe ich hier was gefunden Was ist Samurai-Sudoku?

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)

Sudoku

Sūdoku (jap. 数独, wörtlich Zahlen-Einzel) ist ein Zahlenpuzzle.

kann den lesenswert baustein nicht einfügen, vielleicht holt das ein höheres wesen nach...--Carroy 00:18, 3. Jan 2006 (CET)

•  Pro zugegeben die einführung ist etwas kurz und das ganze wird in ein paar monaten wohl vergessen sein.--Carroy 00:18, 3. Jan 2006 (CET)
•  Kontra - Ist gerade erst Ende November durchgefallen. Seitdem keine wesentlichen Änderungen. --Griensteidl 00:54, 3. Jan 2006 (CET)

das habe ich wohl übersehen, hätte aber wohl schon damals für pro gestimmt. soll/kann ich die kanditatur zurückziehen?--Carroy 01:04, 3. Jan 2006 (CET)

Als Vorschlagender steht dir das jederzeit frei. -- Achim Raschka 08:26, 3. Jan 2006 (CET)

•  Kontra Ich denke, der Artikel sollte sich noch ein paar Scheiben von en:sudoku abschneiden. Was die Bilder betrifft, ist der allerdings auch mau, Bilder wären bei den Methoden sicher hilfreich. „Hilfen beim Lösen“ hat nicht mal mittleres How-to-Niveau. Und die Einleitung ist mal wieder nicht existent... sigh. -- Dr. Shaggeman ^{Der beißt nicht!!!} 01:30, 3. Jan 2006 (CET)
•  Neutral Leider fehlt eine Einleitung, ansonsten finde ich, dass der Artikel gut zu lesen ist und recht informativ ist. --Flothi 01:36, 3. Jan 2006 (CET)
•  Pro Find ich voll gut die Seite 84.133.169.191 00:03, 4. Jan 2006 (CET) (Signatur nachgetragen. norro 18:11, 5. Jan 2006 (CET))
•  Pro - ist doch praktisch, wenn man nicht weiß, wie man Sudokus löst. -- Blumenbach 17:16, 7. Jan 2006 (CET)

Erstellung neuer Sudokus

Nach anfänglichen Problemen mit dem Wikipedia Umgang... ;-)

Ich hätte einige Anmerkungen / Fragen zum "Erstellung neuer Sudokus":

"1. Weg: Ein leeres Puzzlefeld wird Zelle für Zelle durch "Auswürfeln" (Zufallsgenerator) mit Ziffern befüllt. Sobald es zu einem Regelverstoß kommt, muss per Backtracking-Methode eine andere Belegung probiert werden. Dies ist weniger trivial als beim Lösen des Puzzles: Da eine möglichst "zufällige" Belegung des Puzzlefeldes benötigt wird, kann man nicht einfach alle Ziffern der Reihe nach durchprobieren. Es hindert aber nicht, alle Ziffern, sobald sie einmal "ausgewürfelt" wurden, als künftig - für die jeweilige Zelle - gesperrt "abzuhaken" (in einer Tabelle zu markieren"

Nehmen wir an, wir erstellen unser Sudoku mit dieser "Brute force" Methode. Jedes der 81 Felder kann mit Ziffern zwischen 1 und 9 bestückt werden. Es gibt also 9^81 Möglichkeiten. Natürlich erfüllen nicht so gewonnenen Sudokus die 3 Kriterien ( 1 x jede Zahl pro 3x3; 1x jede Zahl pro Zeile, einmal jede Zahl pro Spalte ). Es gibt nach Felgenhauer 6.670.903.752.021.072.936.960 mögliche Sudokus. Unter allen 9x9 Feldern die mit Ziffern von 1 bis 9 aufgefüllt werden ( sind in etwa 1,96 * 10^77 ) erfüllen NUR 6,6 * 10^21 Feldern die "Sudoku-Kriterien". So etwas lässt sich unmöglich auf diese Art und Weise lösen! Dh, wenn ich anfange Kästchen um Kästchen zufällig auszufüllen und dabei nur immer gültige Zahlen eintrage werde ich ziemlich wahrscheinlich scheitern. Mit einer Wahrscheinlichkeit von 3,36 *10^ -56 wird mein Sudoku aufgehen... Also überhaupt nicht! In allen anderen Fällen kann ich es gar nicht fertigstellen, weil ich eine Zahl eintragen müsste, die ich gar nicht mehr eintragen darf... In der Theorie mag das schön logisch erscheinen in der Praxis ist das allerdings völlig unmöglich!

"3. Weg: Man füllt eine Zeile oder eine Spalte in beliebiger Reihenfolge mit den erlaubten Ziffern, verschiebt dann mit jeder weiteren Zeile/Spalte die Ziffernfolge, bis man am Schluss alle möglichen Varianten untereinander/nebeneinander in einer n x n Matrix vorliegen hat. "

Vielleicht verstehe ich die Anleitung nicht korrekt, aber ich habe mich mal daran versucht: Zufällige Ziffernfolge:

329 516 784

Verschieben der Ziffernfolge nach jeder weiteren Zeile:

1. 329 516 784
2. 432 951 678
3. 843 295 167
4. 784 329 516
5. 678 432 951
6. 167 843 295
7. 516 784 329
8. 951 678 432
9. 295 167 843

Zwar erfüllt dieses "Sudoku" die Bedingung in jeder Zeile und Spalte jede Zahl nur einmal auftreten zu lassen, für die 3x3 Unterquadrate gilt das jedoch nicht:

1. 329
2. 432
3. 843

Vielleicht kann mir jemand erklären wo mein Denkfehler liegt.

Viele Grüße Lui

Nur kurz, weiß nicht, ob es stimmt, aber es sagt ja keiner, dass du nur um eins verschieben sollst. Stimmt die untere Version? Nur durch verschieben erstellt.

1. 329 516 784
2. 784 329 516
3. 516 784 329
4. 295 167 843
5. 843 295 167
6. 167 843 295
7. 951 678 432
8. 432 951 678
9. 678 432 951

Gruß, -- Hey Teacher 21:31, 14. Jan 2006 (CET)

Hallo, danke für deine schnelle Antwort. Das Problem bleibt aber bestehen! Das "dumme" ist, wir haben 9 Zeilen:

1. 123 456 789
2. 789 123 456
3. 456 789 123
4. 123 456 789
5. 789 123 456
6. 456 789 123
7. 123 456 789
8. 789 123 456
9. 456 789 123

Dh entweder es wiederholen sich bei dieser Methode die Zahlen innerhalb der 3x3 Quadrate oder innerhalb der Zeile / Spalte. Ich finde die Anleitung Nr. 3 ist entweder irreführend oder falsch - oder ich kapiers ned so ganz. Und Lösungsansatz Nr.1 ist mit normalen PCs praktisch nicht machbar. Grüße

Lui

Du verschiebst immer drei Zahlen, das musst du aber nicht. Schau noch einmal her:

1. 123 456 789
2. 789 123 456
3. 456 789 123
4. 912 345 678
5. 345 678 912
6. 678 912 345
7. 891 234 567
8. 234 567 891
9. 567 891 234

So kann's doch gehen, oder? Gruß, -- Hey Teacher 22:47, 14. Jan 2006 (CET)

Hallo, habs zu spät gesehen... Hast natürlich vollkommen Recht! Ist ja auch schon spät :-) Vielen vielen Dank!

Grüße Lui

zu "Schwieriger als das Lösen der Puzzle dürfte das Herstellen derselben sein." Ist diese Behauptung nicht völlig aus der Luft gegriffen? Interessant ist stattdessen vielleicht ein Ansatz zur systematischen Beurteilung der Schwierigkeit eines gegebenen Puzzles. Denn einen solchen zu entwerfen kann meiner subjektiven Meinung nach durchaus ein Grund gewesen sein, warum Wayne Gould ganze sechs Jahre gebraucht hat um seine Software zu entwickeln. -- Marc D. Migge 02:42, 5. Nov. 2006 (CET)

Nachdem alle in dieser Diskussion nach mathematischen Hintergründen schreien: Betrachtet man alleine die Zeilen- und Spaltebbedingungen reicht es, wenn die Zahl teilerfremd zu 9 ist (3 ist also ein denkbar ungünstig gewähltes Beispiel...). Nimmt man noch die Unterquadrate hinzu muss man zusätzlich beachten, dass ein "Sprung" mindestens drei Felder weit reichen muss. Mit einer Sprungweite von 4 z.B. bekommst du eine wunderschöne Lösung hin... (Das sollten eigentlich alle Informatiker auch gelernt haben, soweit ich weiss hören die auch LA I...)

Sudoku-Würfel

Im Handel sind sog. "Sudoku-Würfel" zu finden. Es handelt sich dabei um Rubik's Cube (3x3, "Zauberwürfel") mit den Ziffern 1 bis 9 auf jeder Fläche. Laut Kurzanleitung soll man den Würfel so verdrehen, dass ein Sudoku daraus wird. Es gelingt mir nicht, diesen Würfel sinnvoll als Sudoku zu interpretieren, bzw. die naheliegende Interpretation (Zeile bzw. Spalte auf die angrenzenden Flächen weiterdenken) ist ganz offensichtlich unlösbar, weil vier gleiche Ziffern auf drei Zeilen bzw. Spalten verteilt werden müssten. Auch mit 4x4-Würfeln gibt es meinen Überlegungen nach keine Lösung. Für 5x5 ist mir die persönliche Prüfung, ob es eine Lösung gibt, zu aufwändig und damit fehleranfällig; ich werde es demnächst mal den Rechner durchprüfen lassen. Kennt jemand eine sinnvolle Deutung des 3x3-Würfels als Sudoku? --130.83.244.x

Meiner Erachtens ist das Verarsche. Sie wollen wohl, dass man den Ursprungszustand wiederherstellt, von den Sudoku-Regeln bliebe dann nur, dass ein 3*3-Feld jede Zahl genau einmal enthalten muss. Alle Angaben ohne Gewähr. --Eike 20:03, 18. Jan 2006 (CET)

Ich kann da Eike nur zustimmen. Die Beweglichkeiten des Würfels mit den Abhängikeiten innerhalb eines Sudokus zu verbinden ist absoluter Nonsens. adaso 11:52, 23. Mai 2006 (CEST)

Erneute Sperrung

Es tut mir leid, ich habe alles versucht. Für IPs ist jetzt erst einmal Pause verordnet. --Schwalbe ^Disku 17:23, 30. Jan 2006 (CET)

 Pro, aber nicht in der Dis. oder? --Ολλίμίνατορέ ^Ω 18:36, 30. Jan 2006 (CET)

Natürlich nicht auf der Diskussionsseite, sondern nur im Artikel selbst. ;-) --Schwalbe ^Disku 21:02, 30. Jan 2006 (CET)

Weltmeisterschaft

Hallo, ist vielleicht ganz interessant: 10.-11. März findet in Lucca in Italien die erste Sudoku Weltmeisterschaft statt: [4] --FlyingFinger 11:44, 1. Feb 2006 (CET)

Erlaubte Transformationen beim Erstellen eines Sudoku und Zahlenentfernung

In der Beschreibung wie man Sudokus erstellt steht unter „3. Weg“, dass verschiedene Transformationen erlaubt sind, um das triviale Sudoku zu verändern. Wie sehen diese Transformationen genau aus? Und gibt es noch mehr Transformationen, die erlaubt sind, die (noch) nicht erwähnt sind?

Danach müssen ja Zahlen entfernt werden. Wie geht man hier vor, damit ein eindeutig lösbares Sudoku entsteht?

Lösungsmethoden-Algorithmisch

Ich verstehe den Absatz nicht, was vielleicht daran liegt, dass ich nicht weiß was eine schnittmenge ist. Vielleicht sollte das in einem Satz erklärt werden, da den artikel durchzulesen immer aufwändiger ist als wenn das gleich in einem Satz erklärt ist. Das ist deshalb so, weil in dem seperaten Artikel viel für mich Irrelevantes steht (ursprung, verschiedene arten,...) --<johannnes' Unterschrift> 19:29, 14. Mai 2006 (CEST)

Habe das jetzt besser verlinkt. Hoffe das hilft! -- H005 21:35, 14. Mai 2006 (CEST)

Deutsche Zeitungen

Ist es sinnvoll, alle deutschen Zeitungen und Zeitschriften aufzuzählen, in denen Sudokus zu finden sind? Sind das nicht ziemlich viele...? --Eike 11:13, 15. Jun 2006 (CEST)

weniger trivial = schwerer?!

Hi, warum steht unter "Erstellung neuer Sudokus", "Algorithmus", "1. Weg" dieser Satz: "Dies ist weniger trivial als..." warum schreibt man nicht "komplizierter" oder "komplexer" das ist nicht so kompliziert, klingt besser und verwirrt nicht. Oder habe ich das falsch verstanden? --Florian3

Erstellen neuer Sudokus

Ist nicht die letzte der drei beschriebenen Methoden die einzig vernünftige? Bei der Beschreibung wie man nach England kommt, würde ich auch nicht die Methoden Schwimmen und Ruderboot erwähnen, sondern mich auf Fähre, Kanaltunnel und Flugzeug beschränken. Wenn kein Widerspruch kommt, werde ich die ersten beiden Wege nächsten Sonntag löschen, die nerven mich schon lange ;-) --Rat 19:31, 9. Jul 2006 (CEST)

Was is denn an der 1. Methode so schlimm? Ich kann nichts über die Qualität der Sudokus aussagen die über die verschiedenen Wege generiert werden, aber aus dem Bauch heraus würde ich sagen das die nach der 1. Methode "besser" sind weil sie zufälliger sind. --Florian3

Urgh, grausam! Bitte schnappt euch einen Informatiker und überarbeitet diesen Abschnitt!

• "Schwieriger als das Lösen der Puzzle dürfte das Herstellen derselben sein." Entweder isses das oder nicht, ein "dürfte" ist hier überhaupt nicht angebracht. Was bedeutet "schwierig"? "Kombinatorische Komplexität", "exponentielle Laufzeit" oder einfach nur "dauert ewig, das Zeuch von Hand zu machen"?
• "3. Weg: [...] Von den hier vorgestellten Erstellungsmethoden ist diese die am wenigsten aufwendige aber rechenintensivste." Hä? "Aufwändig" = "rechenintensiv"!
• "Ohne weitere Kontrolle kann es hierbei passieren, dass das Puzzle trivial (langweilig) oder nicht mehr eindeutig lösbar wird." Und wie sieht diese weitere Kontrolle aus? Dynamische Programmierung, um alle Lösungsmöglichkeiten abzuklappern? Algorithmus, der menschliches Lösungsverhalten imitiert? Wenn das nach jeder Entfernung ausgeführt werden muss, ist es dann nicht gerade dieser Teil, der die Laufzeit explodieren lässt? --Θ~ 13:40, 20. Jul 2006 (CEST)

• Jetzt muss ich mich doch mal einmischen. Auf dieser Seite wird am laufenden Band über möglichst mächtige Lösungs- oder Erstellungsalgotrithmen diskutiert. Wenn man sich aber die Rätsel z.B. der letzten Weltmeisterschaft anschaut, sind die alle handgemacht (auch wenn es im Vergleich zu dem oft zitierten Millisekundenbereich lange dauert). So kann der Autor direkt beim erstellen den Schwierigkeitsgrad festlegen. Dieser Weg des Erstellens sollte m.E. auch in den Artikel aufgenommen werden. Bei den Sudoku-Cracks wird zudem zwischen "schönen" und "anderen" Lösungswegen unterschieden. Handgemachte Rätsel bieten hier den Vorteil dass der Lösungsweg vorher bekannt ist und nicht ausprobiert werden muss (der "unschönste" Lösungsweg wäre wohl der, bei dem man raten muss. Wobei mir ein solcher noch nie untergekommen ist, meistens mangelt es doch an der eigenen Hirnleistung. Aber das geht schon wieder zu weit in die NP-Diskussion...). Zudem gibt es wie oben schon erwähnt noch unzählige Lösungswege, die ich noch nie in einem Programm gesehen habe (zugegebenermassen als Programmier-Rookie). Zum testen neuer Algorithmen emphehle ich das Buch "Sudoku-Hardcore" von Stefan heine, erhältlich auf Amazon.

Als Fazit wollte ich noch feststellen, dass ich den Sinn dieser Seite nicht darin sehe, irgendwie einen möglichst guten Algorithmus anzugeben, sondern neugierigen, unbefleckten Menschen Sudoku näher zu bringen. Ich finde diesen Sinn erfüllt die Seite meiner Meinung nach schon recht gut, mit zu viel Informatik würde man nur Menschen abschrecken...

Was hat Leonhard Euler wirklich verfasst?

Hallo. Ich habe in einem Sudoku-Rätselbuch gelesen, dass Herr Eulers Rätsel nicht Carré latin (Lateinisches Quadrat) waren, sondern, im Gegensatz zum Artikel, Carrés Magiques (Magische Quadrate) waren. Kann mir das jemand bestätigen?

Tippfehler

Kanditatenmengen -> Kandidatenmengen -WortUmBruch 12:37, 21. Mär 2006 (CET)

Weblinks

Unter den Weblinks und auch im OpenDirectory ist leider kein einziger Link zu einem Sudokulöser zu finden, der nicht nur von diesem generierte, sondern beliebige Sudokus löst. Gerade das wird aber sicherlich recht häufig benötigt (Menschen wollen in ihrer Tageszeitung ein Sudoku lösen, schaffen es nicht und brauchen Hilfe). Ich bin kein Wikipediaprofi, deshalb würde ich den Link nicht selbst einfügen, mein Vorschlag allerings: Ein Link zu Sudoku-Löser an der TU Chemnitz - ein simpler, aber leicht zu bedienender Sudoku-Löser.

Das stimmt so nicht. Im OpenDirectory sind (allerdings in der Unterkategorie "Software") diverse Sudokulöser aufgeführt. Insofern bin ich dagegen, hier doch wieder diverse Links auf Sudoku-Programme einzuführen. Clemfix 12:21, 5. Apr 2006 (CEST)

Intuitiv Lösen ?

Kann man da nicht verständlicher sagen: "Versuch-Irrtum-Lösen"? Das wäre deutsch und intuitiv kann ja alles sein.

Dell Magazine

Das "Dell Magazine" scheint nach der eigenen Internet-Präsenz nichts mit der Computer-Firma Dell zu tun zu haben, wie es im Artikel steht.

Australische Mathematiker

Haben die im Artikel erwähnten australischen Mathematiker auch Namen? Haben sie den Beweis schon irgendwo veröffentlicht (Referenz?) ? Wüßte dies doch zu gern... JKn sprich! 16:25, 17. Apr 2006 (CEST)

Insbesondere ist das etwas komisch wenn man die Aussage mit den japanischen Sudokuenthusiasten aus "Regeln und Begriffe" paart. Ohne Quelle sollte man den Abschnitt zu den Australiern wohl loeschen. --DaTroll 16:09, 26. Apr 2006 (CEST)

Oh, das ist wohl wirklich eine spannende Frage. Auf der Suche nach Primärquellen stieß ich auf Gordon Royle (University of Western Australia), der tausende 17er-Puzzle aber kein 16er gefunden hat. Das mag der Hintergrund des Eintrags gewesen sein, ist aber kein Beweis, wie auch en:Sudoku, [5] (Stand 27.3.06) und [6] (Stand 1.2.06) betonen. Interessant fand ich noch einen Kommentar von David Bryant vom 29.7.05, der die 17 für plausibel hält: „The idea that at least 17 clues are required to give a unique solution is plausible -- imagine a 9x9 grid with the 17 clues aligned along the top row, and in the first column. The idea that the values in the remaining 64 cells can be fixed by these "boundary values," but that a lesser number of "boundary values" won't work, is intuitively appealing.“ [7] --Schwalbe D | C | V 17:32, 26. Apr 2006 (CEST)

Ich habe die australischen Mathematiker ersatzlos entfernt. --DaTroll 11:25, 27. Apr 2006 (CEST)

Bloß gibt es leider kein solches Gitter. Soweit ich es überblick, lassen sich alle mit reinem Außenwinkel in diese 5 Grundtypen transformieren (ebenso die in T- oder "+"-Form u.Ä.):

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

Und die haben alle äußerst viele Lösungen. --84.150.168.102 06:21, 8. Mai 2006 (CEST)

Sudoku

Sudoku (jap. 数独 Sūdoku, kurz für 数字は独身に限る Sūji wa dokushin ni kagiru, wörtlich: Zahlen als Einzel beschränken) ist ein Logikrätsel und ähnelt Magischen Quadraten.

• pro - ich würde diesen Artikel gern kritischen Blicken überlassen. Ich denke, die Autoren haben sehr gute Arbeit geleistet und sollten entsprechend gewürdigt werden - ich danke -- トロール 21:03, 19. Jul 2006 (CEST)

•  Pro die Lösungsmethoden sind zwar schwierig zu verstehen, aber trotzdem ein sehr guter artikel -david2212 22:07, 19. Jul 2006 (CEST)

•  Pro ist jetzt der dritte Anlauf für den Artikel, von mir aus ist der schon lange lesenswert. --Schwalbe D | C | V 22:36, 19. Jul 2006 (CEST)
•  Pro ein interessanter, lesenswerter Artikel--Stephan 04:58, 20. Jul 2006 (CEST)
•  Kontra geht mir an vielen Stellen zu sehr in How-to („Hilfen beim Lösen“, „Erstellung neuer Sudokus“). -- ShaggeDoc You’ll Never Walk Alone 09:27, 20. Jul 2006 (CEST)
• contra über weite Strecken Theoriefindung oder zumindest sehr schlecht belegt --Gunther 10:06, 20. Jul 2006 (CEST)
•  Pro ein lesenswerter Artikel - dass man das mit einer Formel lösen kann, hab ich nicht gewusst --> toll gemacht! --Hufi ^Rating 11:07, 21. Jul 2006 (CEST)
•  Pro lesenswert. CSchrader 15:36, 21. Jul 2006 (CEST)
• Warum ist das Bild aus dem Abschnitt Scanning des englischen Artikels nicht eingebaut? Laut en-Wikipedia ist es gemeinfrei, bestehen dagegen irhgendwelche Bedenken? --h-stt !? 20:05, 21. Jul 2006 (CEST)
•  Pro sehr interessant und gut zu lesender Artikel, kann auch Leute ohne Ahnung in das Thema gut einführen. --J-PG evaluate! 16:22, 24. Jul 2006 (CEST)
•  Pro Als Sudoku-Fan einerseits, als Wissenschaftler andererseits. Hätte nicht gedacht, dass es dazu soviel zu sagen gibt. -- Stefan M. aus P. 20:53, 24. Jul 2006 (CEST)
•  Kontra Nein. 1) Vergleich zum engl. Artikel. 2) Geschichte, Entstehung 85.179.90.152 23:04, 24. Jul 2006 (CEST)

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)

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)

In welcher Sprache ist der Algorithmus denn implementiert? --Feuervogel 04:10, 2. Apr 2006 (CEST)

In Java 1.5, wie oben erwähnt. Ich hab's gerade nochmal gemessen (glaub's selbst kaum): Die heutigen Rätsel von Sudokumeister je 3333 mal, also insgesamt fast 10000 Durchläufe, benötigen insgesamt 2,0 sec auf dem 2,4 GHz PC, d.h. 0,2 Millisekunden pro Durchlauf. Hier ist der Quelltext --Rat 18:28, 2. Apr 2006 (CEST)

Dann nimm doch mal bitte das 16x16 wirklich schwere von blitz und teste damit, würde mich wirklich mal interessieren --Feuervogel 11:59, 3. Apr 2006 (CEST)

Ich schieb mich hier mal dazwischen Das 16x16 gross von der gleichen Seite war kein Problem (7ms). Das wirklich schwere bestätigt allerdings, dass "stumpfes" Backtracking schnell an Grenzen stößt. Nach inzwischen 38 Stunden Laufzeit ist noch keine Lösung gefunden. Ich werde das Experiment wohl abbrechen.

Wenn man als nächsten Probierkandidaten immer den nähme, der die wenigsten Möglichkeiten lässt ... Aber dann ist es eben kein "stumpfes" Backtracking mehr. Dann also doch "richtige" Lösungsstrategien. --Rat 13:44, 9. Apr 2006 (CEST)

Naja, so wirklich gut ist meine Lösung auch nicht. Man muss irgendwann anfangen mit Backtracken so wie es aussieht, und wenn man das nicht ausgesprochen intelligent macht, ists halt blöd. Ein Freund von mir merkt sich z.b. die Sackgassen und läuft diese dann nicht mehr ab, was einiges verkürzt. Dies konnte ich jedoch noch nicht erfolgreich implementieren. --Feuervogel 19:22, 9. Apr 2006 (CEST)

Ich habe mir in Prog. in rexx gestrickt, welches gleich in der Eingabe interaktiv alle logischen Schlüsse vollzieht. Ich habe mal das obige Beispiel eingegeben und komme zum entsetzlichen Resultat, daß zum Ende aller Vorgaben kein (!) Schluß zur Bildung eines neuen Positiveintrags führte. Die logischen Ausschlüsse führen nur in einem einzigen Feld (=Zelle) zu zwei Optionen, nämlich in Zeile 2 Spalte 9 für 1 und 6. Aber beide Varianten führen danach weder zu einer vollständigen (dramatischen) Lösung, noch zu einem Ausschluß, noch zu weiteren 2-Optionen-Feldern. Dies bedeutet, daß dieses Sudoku praktisch mit dem Kopf nicht lösbar ist. Die Eingabe von drei Zahlen gleich zu Anfang (Zeile-Spalte-Wert: 112, 994, 126) führte hingegen zu der demonstrierten Lösung. Jede der drei Zahlen für sich allein aber nicht. Beim Konstruieren solcher Aufgaben sollte man schon den Lösenden nicht vergessen, der ja nur über beschränkte Möglichkeiten verfügt. Das Durch-und-durch-Probieren ist so nicht zumutbar und macht auch keinen Spaß.--Wikipit 19:18, 6. Mär. 2008 (CET)

Nachtrag: Ich wollte damit sagen, daß "Aufgabe-Programmieren" und "Lösungsweg" ziemlich nahe beieinander liegen. Eine unvollständig formulierte Aufgabe, die also mehr als logisch zwingende Schlüsse erfordert, sollte dann auch nicht mehr als 2 Varianten zulassen, von denen eine zum Widerspruch führen muß, sonst wäre die Eindeutigkeit der Lösung ja nicht gegeben.--Wikipit

Meines Erachtens ist das klassische Backtracking zwar eine sehr elegante (und wie oben beschrieben häufig auch eine sehr schnelle Art) Sudokus zu lösen, wenn es aber darum geht, festzustellen, ob ein Sudoku überhaupt ein gültiges Sudoku ist (also lösbar und nur eine Lösung) kommt man mit reinem Backtracking nicht sehr weit (oder besser: man braucht u. U. seeeeehr lange). Versucht doch mal, dieses (zugegebenermaßen ziemlich pathologische) Problem

- - - - - - - - -
- - - - - - - - -
- - - - - - - - 1
- - - - - - - - -
- - - - - - - - -
- - - - - - 1 - -
- - 1 - - - - - -
- - - - - - - 2 -
- - - - - 1 - - -
mit Backtracking zu lösen. Als Mensch sieht man sofort, dass das nicht lösbar ist, aber so ein dummer Rechner... Und es gibt beliebig viele (auch nicht ganz so offensichtlich unlösbare) Probleme, an denen sich klassisches Backtracking die Zähne ausbeißt.
Just my two cent Clemfix 09:54, 9. Apr 2006 (CEST)

Toter Link

(Zum Buch von Claudia Bach) Aktualisierungen zum Buch erfolgen auf der Internetseite der Autorin.

Geschichte? Magische Quadrate (Albrecht Dürers, 16Jhd.) oder lateinischen Quadrate (Euler, 18Jhd)

Ich finde die Wikipedia widerspricht sich hier selbst, entstammt sudoku nun den lateinischen quadraten vom herrn euler oder den magischen quadraten die Durers schon kannte?

Dem stimme ich zu! das berühmteste aller Magischen Quadraten, wo es neben Zeilen-, Spalten- und Diagonalensummen (immer 34) noch weitere 34er Summen (z.B. im zentralen kleinen 2*2 Quadrat)gibt, ist in Albrecht Dürers Bild Melencolia (o.ä.) zusammen mit der Jahreszahl 1514 festgehalten. Gesichert ist, dass schon in der Zeit davor bei Mathematikern und Alchimisten mag. Quadrate in Mode gekommen waren. vermutlich ist das chinesische 3*3 Quadrat am ältesten. Euler hat das nicht erfunden, sondern einige hilfreiche math. Sätze und Anleitungen verfasst sowie eigene magische Quadrate veröffentlicht. (geophil, 7.8.07)

Wann ist ein Sudoku unlösbar?

Gibt es irgendwo Kriterien, die beschreiben, wann ein Sudoku unslösbar ist? Natürlich dann, wenn die Regeln offentsichtlich verletzt werden. Aber vielleicht etwas vorrausschauender? --Feuervogel 13:24, 24. Apr 2006 (CEST)

Wohl kaum, denn mit einem solchen Kriterien wäre jedes Sudoku leicht lösbar. Wird nämlich in ein Sudoku eine Ziffer eingetragen, ist es immer unlösbar, sofern nicht die richtige Zahl eingetragen wird. Könnte man leicht erkennen, welche Rätsel unlösbar sind, könnte die richtige Zahl mit maximal 8 Versuchen leicht gefunden werden. --88.68.122.212 15:19, 15. Jul. 2008 (CEST)

Weblink

Ich schlage vor, den Link "Windows-OFFLINE-Sudoku (Spiel + Generator + Helfer + Löser + Drucker) - Für die Offliner unter uns (Englisch)" gegen .net basiertes Sudoku-Programm (deutsch & englisch auszutauschen (ebenso auf Windows beschränkt). M. E. ist dieser Löser/Generator/Drucker viel übersichtlicher, hat mehr Funktionalitäten (unter anderem ist die "Uhrzeigerstrichmethode" implementiert :-) ). --Clemfix 14:55, 5. Mär 2006 (CET)

Dagegen. Das läuft ja auf noch viel weniger Systemen als eine normale Windows-Exe - geschweige denn ein Java-Programm. --Eike 21:24, 5. Mär 2006 (CET)

Dafür, wenn das Programm auch als ein normales Windows-Exe zur Verfügung gestellt wird, sonst dagegen. Das Programm selbst ist IMHO besser als das momentan gelinkte Windows-Exe (v.a. Deutsch). Läuft das .net auch auf Mono? -- Stephan Heuscher 10:30, 6. Mär 2006 (CET)

Ein "normales" Windows-Exe (also ohne .net Framework) wird man so ohne weiteres daraus nicht machen können. Und ich bezweifele (ohne dass ich es ausprobiert habe), dass das Ganze unter Mono läuft. Es war eine Spielerei, die ich mit dem kostenlosen Visual Studio gemacht habe, und ich habe hier das ziemlich neue .net Framework 2.0 genutzt. Meines Wissens nach unterstützt Mono das (noch) nicht (lasse mich aber auch gerne eines Besseren belehren). --Clemfix 13:55, 6. Mär 2006 (CET)

Vorschlag: Ersetzten des Links "Windows-OFFLINE-Sudoku (Spiel + Generator + Helfer + Löser + Drucker) - Für die Offliner unter uns (Englisch)" durch http://angusj.com/sudoku/ . Grund: Deutsche Menu-Führung vorhanden. -- Stephan Heuscher 08:01, 9. Mär 2006 (CET)

Da sich zwei Tage niemand gemeldet hat, setzte ich meinen Vorschlag um Stephan Heuscher 11:17, 11. Mär 2006 (CET)

Auch wenn 2 Tage etwas kurz sind, stimme ich dem zu. Das Programm gibt es schon eine ganze Weile mit einer beachtlichen Qualität. Leider wird es auch – seit über einem Jahr – nicht mehr weiter entwickelt. Ich wundere mich, dass bis jetzt kein OpenSource Solver vorgeschlagen wurde, desweiteren gibt es einen (oder mehr) unter GNU-Lizens (in einer Linux-Distribution).

Hier meine Vorschläge

• (en) sudoku.sourceforge.net (International Freie Software, Java)

Des Weitern denke ich wäre der DMoz-Link hier sehr hilfreich/ angebracht (vorbeugend und darf nicht fehlen).

• Linkkatalog zum Thema Sudoku bei curlie.org (ehemals DMOZ) – Eine aktive Auflistung von Sudoku-Links.

--Ολλίμίνατορέ ^Ω 13:38, 11. Mär 2006 (CET)

Hat auch jemand evtl. einen Link für PocketPC-Sudokus ?? --Stell98

http://www.spiralmile.com/ zufällig gerad gesehn.

Da der DMoz-Link (dem Wiki-nahe, empfohlene) die (in mehreren Sprachen) Software-Frage hinreichend löst. Werden entsprechende (schon wieder private, mit Werbung verbundene) Links entfernt werden müssen. Was auch einer in Zukunft unsachlichen (nie enden) Streits entgegen tritt (vorbeugt). So denke ich auch wieder („teil-“) entsperrt werden kann. -- Ολλίμίνατορέ ^Ω 13:34, 14. Mär 2006 (CET)

Das mit dem DMOZ scheint mir ein guter Kompromiss zu sein. Wer wirklich so was sucht, ist dort eindeutig an der besseren Adresse. Ansonsten habe ich wenig Verständnis für Leute, die sich nur in der Wikipedia anmelden, um Links einzusetzen. Etwas konstruktiver könnte die Mitarbeit schon noch werden. Die Sperre erscheint mir weiterhin berechtigt - mit Benutzern kann man wenigstens diskutieren, mit IPs kaum. --Schwalbe ^Disku 11:48, 15. Mär 2006 (CET)

Auch wenn ich nur eine IP bin, empfehle ich folgendes Programm: http://www.volleyballschlaeger.de/download/sudokumaster-1.0.tar.gz , vorallem wenn man sich auch mal den quellcode ansehen will, er ist sehr einfach in c/c++ gehalten.

Mein Lieblings Sudoku Programm ist Dr. Kawashimas Gehirn-Jogging für den Nintendo DS. Es enthält eine Anzahl leichter, mittlerer und schwerer Probleme. Sehr schön ist die Handschrifterkennung, man malt mit dem Stift auf dem Touchscreen die Zahlen bzw. Hilfszahlen. Dabei ist der Sudokuteil nur ein Bonus der europäischen Version. Das Hauptspiel ist auch nett. --Marc van Woerkom 01:36, 13. Feb. 2007 (CET)

Lesenswert und QS

Der Artikel wird seit Monaten zugleich durch ein Lesenswert-Zeichen wie auch durch einen QS-Baustein ausgezeichnet. Eine sicherlich sonderbare Kombination. Der damalige Verfasser dieser außergewöhnlichen Prämierung, Benutzer:Gunther, hat seine Mitarbeit bei Wikipedia aus mir unbekannten Gründen eingestellt. Er kann deshalb nicht weiterhelfen. Ich plädiere deshalb dafür, den QS-Baustein zu entfernen. Sollte jemand anderer Meinung sein, bitte ich das hier anzumerken.--Genossegerd 21:35, 3. Jan. 2007 (CET)

wie viele lösungen gibt es?

im artikel steht was von 6 trilliarden sudokus. wie viele lösungen gibt es jedoch? ich habe in den letzten tagen ein recht schnelles verfahren implementiert zur erstellung von lösungen, allerdings hätte ich gerne mal wenigstens eine obere und eine untere schranke für die lösungen (wie viel min/max es gibt). --Feuervogel 00:23, 12. Jan. 2007 (CET)

Es gibt sicher weniger als 9!⁹ = 109.110.688.415.571.316.480.344.899.355.894.085.582.848.000.000.000 Lösungen. So viele Lösungen gäbe es, wenn lediglich berücksichtigt wird, dass in jedem Quadrat eine Permutation der neun Ziffern auftreten kann. Eine realistische Schätzung wäre (9!)³ = 47.784.725.839.872.000, also 48 Billiarden. (9!)³, so viele Kombinationen gibt es die 27 Ziffern in den drei Quadraten in der Diagonalen einzutragen. Da jedoch einige Vorgaben mit nur 17 statt 27 Ziffern bereits eindeutig lösbar sind, gibt es wahrscheinlich deutlich weniger Lösungen. Der Artikel behauptet es seien etwa 6 Trilliarden. Uups, da habe ich ja etwas verschätzt. Das sind viel mehr Lösungen. Ich kann das aber auch nicht glauben. Ok, von den 27 Ziffern brauchen nur 24 angegeben werden, aber eindeuig lösbare Sudokus mit 24 vorgegebenen Ziffern sind doch nichts ungewöhnliches. --88.68.124.85 17:26, 19. Nov. 2007 (CET)

Die Zahl ist wohl offensichtlich zu groß abgeschätzt. Es gibt sicher deutlich weniger als (9!)⁴, ungefähr 17 Trilliarden, Möglichkeiten, um 4 Quadrate mit 36 Ziffern auszufüllen, da beim Ausfüllen des vierten Quadrats, die in den Zeilen oder Spalten bereits eingetragenen Ziffern zu berücksichtigen sind. Für die erste Ziffer gibt nur noch 6 statt 9 Möglichkeiten. Mit 36 zufällig ausgefüllten Feldern gibt es aber wahrscheinlich selten eine Lösung. Denn wer ein Sudoku einfach auf gut Glück ausfüllt, wird selten die Lösung finden. Die 6 Trilliarden sind einfach Quatsch. 18:10, 19. Nov. 2007 (CET)

Stimmt, die Zahl der möglichen Lösungen ist sicherlich unbekannt und liegt wahrscheinlich unter 48 Billiarden. Einfach und exakt berechbar ist die Zahl der Möglichkeiten in die 3 Quadrate auf einer Diagonalen 27 Ziffern einzutragen ohne eine Ziffer innerhalb der Quadrate mehr als einmal zu verwenden. Werden die Ziffern nacheinander zunächst in das erste Quadrat eingetragen gibt es zunächst 9 Möglichkeiten, dann 8, 7, ... und zum Schluß noch eine. Dies ergibt 9*8*7* ... *1 = 9! Möglichkeiten. Die gleiche Überlegung kann für jede der drei Quadrate angestellt werden. Jede dieser Möglichkeiten kann mit jeder anderen frei kombiniert werden. Es ergeben sich damit (9!)³ Möglichkeiten. Für welche dieser (9!)³ Vorgaben Lösungen für alle 81 Felder existieren und wie viele verschiedene, kann nur schwer geschätzt werden. Da jedoch einige Sudokus mit nur 17 vorgegebenen Feldern bereits eindeutig lösbar sind, erscheint es bereits ziemlich unwahrscheinlich, dass es für jede der (9!)³ Möglichkeiten jeweils tausende Lösungen gibt. Wenn die 27 Felder in der Diagonalen ausgefüllt sind, sind für alle übrigen Felder bereits in einer Zeile und einer Spalte drei Ziffern eingetragen. Es gibt daher noch maximal 6 Möglichkeiten, falls die Zeile und die Spalte genau die gleichen drei Ziffern enthält. Es kann jedoch auch nur 3, 4 oder 5 Möglichkeiten geben. Die Berechnung artet daher in eine heillose Fallunterscheidung aus. Eigentlich könnte dies nur mit einem Computer abgezählt werden. Doch selbst für einen Computer sind es einfach zu viele Möglichkeiten. --88.68.116.72 10:58, 20. Nov. 2007 (CET)

Ein typisches Sudokurätsel mit eindeutiger Lösung hat deutlich weniger als 36 vorgegebene Ziffern. Dies gilt selbst für leichtere Sudokurätsel, obwohl meist nicht alle vorgegeben Ziffern erforderlich sind die eindeutige Lösung zu finden. Für das im Artikel angegebene Rätsel ist etwa die 6 im linken oberen Unterquadrat und die 5 im rechten unteren Unterquadrat nicht erforderlich. Damit ist es wenig plausibel, dass 6 Trilliarden Lösungen existieren. Es sind zweifellos deutlich weniger. 84.59.63.237 14:23, 22. Nov. 2007 (CET)

Nach meinem Verständnis von Sudoku gibt es jeweils nur eine Lösung - aber ich glaube mein Verständnis der Frage ist vielleicht falsch.--Genossegerd 22:21, 12. Jan. 2007 (CET)

ja, scheint wohl so. es gibt natürlich für jedes sudoku genau eine lösung (zumindest sollte es so sein), aber es ist wohl so, dass es mehrere sudokus gibt, die die gleiche lösung haben...ich generiere zur zeit lösungen und wollte gerne wissen, wann ich aufhören muss :-) --Feuervogel 23:32, 12. Jan. 2007 (CET)

Ich fürchte, dass es darauf keine Antwort gibt.--Genossegerd 22:06, 17. Jan. 2007 (CET)

Wer schon einmal das eine oder andere Sudoku gespielt hat weiss, dass es in aller Regel nur eine Lösung gibt. Wer die Ziffern einfach auf gut Glück einträgt, wird mit ziemlicher Sicherheit nicht zum Erfolg kommen. Damit ist klar, es kann nicht mehr Lösungen geben, als Möglichkeiten etwa 30 vorgegebene Felder auszufüllen. Dies sind maximal (9!) * (9!) * (9!) * (6 * 5 * 4) knapp 6 Trillionen oder 0,006 Trilliarden. Tatsächlich dürfte es für die Mehrzahl dieser Vorgaben gar keine Lösung geben. In einigen Fällen kann es auch mehrere Lösungen geben, aber wohl selten mehr als 1000. Ich bin mir ziemlich sicher, dass es nicht mehr als 6 Trillionen Lösungen gibt. Wahrscheinlich sind es noch deutlich weniger. --88.68.115.192 10:15, 23. Nov. 2007 (CET)

Abschnitt Lösungsmethode

Je häufiger ich diesen sicherlich sehr wesentlichen Abschnitt durchlese, desto mehr meine ich, dass er eine tiefergehende Überarbeitung benötigt. Allein schon die Gliederung zeigt kein klares Konzept mit sauber voneinander getrennte Themen bzw Unterthemen: 4.1 Intuitiv 4.2 Analytisch-systematisch 4.2.1 Scannen 4.2.2 Analyse 4.3 Algorithmisch 4.4 Nach der Backtracking-Methode. So häufen sich dann auch im Text zu den einzelnen Punkten Wiederholungen. So wird der Weg, um die 5 auf dem grünen Feld im Beispielbild zu finden, viermal beschrieben (intuitiv, Scannen→Kreuzschraffur, Bildunterschrift und Analyse→Durch Kombination). Weiterhin heißt es im Unterabschnitt Analyse, dass es zwei Hauptverfahren gäbe, die Eliminierung (oder Kandidatenbeseitigung) und die Hypothese (oder „was-wenn“). Zum zweiten Verfahren kommen dann aber nachfolgend keine Erläuterungen. Auch wäre eine einheitliche Begriffswahl für das Verständnis hilfreich. Wenn ich in den nächsten Tagen mal Zeit finde, werde ich eine Überarbeitung versuchen.--Genossegerd 22:06, 17. Jan. 2007 (CET)

Für den Abschnitt Nach der Backtracking-Methode möchte ich ein Update vorschlagen. Es ist zwar eine eigenständige Methode, die zum Ziel führt, aber sie ist wie beschrieben nicht effizient und wird wohl eher selten in dieser simplen Form zum Einsatz kommen. Backtracking stellt doch eher einen Lösungs-Ansatz dar, den man mit einfachen Mitteln optimieren kann / sollte. Bevor man alle Zahlen von 1 bis 9 in einem freien Feld durchprobiert, wird kontrolliert, welche Zahlen man davon von vornherein ausschließen kann. Kommt z.B. die 3 bereits in der Zeile, Spalte oder dem 3 x 3 Block vor, hat es keinen Sinn diese mit zu überprüfen, zumal wegen der rekursiven Funktionsweise bei jeder weiteren Variante unzählige andere Stellungen zusätzlich abgearbeitet werden müssen. Wichtig ist auch, dass nur sehr wenige Felder überhaupt Backtracking erfordern. Selbst bei schweren Sudoku gibt es oft Situationen bei denen man zumindest einem Feld eine Zahl eindeutig zuweisen kann. Und jede hinzugekommene Zahl ändert die Anzahl der Varianten vieler anderer Felder, so dass nach jedem Eintrag erneut nach trivialen Feldern gesucht werden sollte. Erst wenn für das leichteste Feld immer noch 2 Varianten übrig bleiben, sollte Backtracking eingesetzt werden. Einen Vorteil kann es auch bringen, nicht immer oben links mit dem Auffüllen der leeren Felder zu beginnen, sondern stets mit dem leichtesten Feld (indem man für jedes freie Feld die Anzahl der Varianten bestimmt und entsprechend sortiert).--Ralf Rehberg

Es wäre sicherlich gut, den Abschnitt „nach der Backtracking-Methode“ weiter zu ergänzen. Neben der dargestellten simplen Methode gibt es zahlreiche elegantere Lösungsansätze, bei denen Vorinformationen genutzt werden. (p.s. Wenn Du am Ende Deines Bearbeiten-Texts auf das obere vorletzte Button klickst, kommt eine volle Signatur. Vorausgesetzt man hat sich vorher bei Wikipedia angemeldet.)--Genossegerd 18:01, 10. Feb. 2007 (CET)

Ups, den hatte ich noch nicht entdeckt... praktisch, Danke! --Ralf Rehberg 18:57, 10. Feb. 2007 (CET)

Weltmeisterschaft

Die genannten Termine für die Deutsche Meisterschaft liegen in der Vergangenheit. Entsprechend sollte dieser Abschnitt aktualisiert werden, z.B. mit den Wettkampfergebnissen. Der Link auf den Stern sollte dabei entfernt werden, da dort nur steht, wann der Wettbewerb stattfinden soll und ab wann die Aufgaben verschickt werden. --Emil Bild 16:10, 18. Jan. 2007 (CET)

Link auf www.x-sudoku.de

Kann mir jemand erklären, warum man bei der Variante X-Sudoku auf http://www.x-sudoku.de/limit/ linken muss? (Wikipedia ist keine Linksammlung (7.4)) 85.2.161.103 00:12, 11. Feb. 2007 (CET)

Das ist kein normaler Link, sondern eine Quellenangabe. Meiner Meinung nach ist es interessant, dass bei X-Sudoku aufgrund der zusätzlichen Bedingungen Aufgaben mit weniger Vorgaben noch zu einer eindeutigen Lösung führen. Anstatt einfach zu behaupten, dass dies noch bei 16 vorgegebenen Zahlen möglich ist, halte ich eine Quellenangabe für sinnvoll. Insbesondere da es der einzige Beleg dafür zu sein scheint. Mir ist jedenfalls kein weiters Beispiel bekannt. --Ralf Rehberg 09:31, 11. Feb. 2007 (CET)

Eine Website gilt nicht als Quelle, siehe Wikipedia:Quellenangaben. 85.2.200.149 23:45, 11. Feb. 2007 (CET)

Neben Literaturangaben sind Weblinks ausdrücklich als Hauptquellen genannt (wie bei es bei Wolfram MathWorld ja auch umgesetzt wurde), daher kann ich Deinen Einwand nicht nachvollziehen. Schon Deine Fragestellung finde ich schade: Wenn man den Artikel auf das reduzieren würde, was darin stehen MUSS - was bliebe dann ausser den Regeln noch übrig? Es geht doch um interessante, lesenswerte Inhalte und da zähle ich Superlative eindeutig dazu. Anscheinend findest Du das auch, sonst hättest Du einen vergleichbaren Abschnitt im Bereich Mathematik über die Mindestzahl an Vorgaben bei normalen Sudoku konsequenterweise auch löschen müssen!?--Ralf Rehberg 14:21, 12. Feb. 2007 (CET)

Beispiele für Sudokus mit nur 17 Startzahlen

Hier gibts Beispiele für Sudokus mit nur 17 vorgegebenen Zahlen: http://people.csse.uwa.edu.au/gordon/sudokumin.php Evtl. könnte jemand den entsprechenden Abschnitt verbessern, ich weiß nicht wie das geht.(Der vorstehende, nicht signierte Beitrag stammt von 85.178.24.77 (Diskussion • Beiträge) 11:24, 3. Mar 2007) -- Ολλίμίνατορέ 21:34, 6. Mär. 2007 (CET)

Mein Solver (http://home.arcor.de/clemens-pichl) kommt nur auf eine Lösung. Kannst Du die Lösungen mal posten? (Der vorstehende, nicht signierte Beitrag stammt von Clemfix (Diskussion • Beiträge) 20:42, 6. Mar 2007) -- Ολλίμίνατορέ 21:34, 6. Mär. 2007 (CET)

Bitte das Signieren nicht vergessen. Nicht nur dein Solver, wie es scheint muss sich Herr Stoeckel geirrt haben. Welchen Abschnitt meinst du denn? So besonders ist der Link auch nicht. (im ODP ist der Link ja schon) -- Ολλίμίνατορέ 21:34, 6. Mär. 2007 (CET)

Eigenen Beitrag wieder raus genommen. War Blödsinn ;-) Habe mich beim übernehmen vertan und zwei Vorgaben falsch eingetragen. Volker Stöckel

Beispiel-Sudoku

Ist eigentlich noch niemand aufgefallen, dass das Beispiel-Sudoku Bild:Sudoku-by-L2G-20050714.svg nicht eindeutig lösbar ist? Neben der im Bild dokumentierten Lösung ist auch noch diese möglich:

 5 3 4 | 6 7 8 | 9 1 2 
 6 7 2 | 1 9 5 | 4 3 8 
 1 9 8 | 3 4 2 | 6 5 7
-------+-------+------ 
 8 1 9 | 7 6 4 | 5 2 3 
 4 2 6 | 8 5 3 | 7 9 1 
 7 5 3 | 9 2 1 | 8 4 6 
-------+-------+------ 
 9 6 1 | 5 3 7 | 2 8 4 
 2 8 7 | 4 1 9 | 3 6 5 
 3 4 5 | 2 8 6 | 1 7 9

Wäre eine kleine Überraschung, ist aber nicht so. In der 3. Zeile und 8. Spalte steht eine 6 und keine 5.--Genossegerd 21:08, 26. Mär. 2007 (CEST)

Ups. Ich nehme alles zurück und behaupte das Gegenteil...

--91.89.114.235 22:38, 26. Mär. 2007 (CEST)

Auszählen?

der Abschnitt der Lösungsmethode ist völlig unverständlich. Was muß man zählen?? Wie ergeben sich Lösungen?? So hilft das nicht!

Ich habe den Text ergänzt; ist es jetzt verständlich?--Genossegerd 23:42, 11. Jul. 2007 (CEST)

Weitere Twin-Methode

Ich habe noch eine weitere, ähnliche Twin-Methode, könnte man ja ergänzen: Wenn in einer Einheit zwei Zellen jeweils zwei Kandidatenziffern haben, die sich gleichen und man ausschließen kann, dass diese beiden Ziffern in anderen Zellen der Einheit möglich sind, dann kann man in den beiden Zellen mögliche andere Kandidatenziffern gefahrlos streichen. --Pohli 13:58, 25. Sep. 2007 (CEST)

besten Dank, ich habe es ergänzt.--Genossegerd 23:07, 26. Sep. 2007 (CEST)

X-Wing-Methode unverständlich?

Ich habe sie nicht verstanden. Liegt's an mir oder an der Formulierung? Dort wird mal der Begriff Reihe und mal Zeile verwendet; ist damit das selbe gemeint? --Pohli 13:58, 25. Sep. 2007 (CEST)

Hoffentlich ist es jetzt besser zu verstehen.--Genossegerd 23:08, 26. Sep. 2007 (CEST)

Schritt-für-Schritt Lösung

Für Leute wie mich, die gerne wissen möchten, wo es den jetzt hakt bei der eigenen Logik beim Lösen, gibt es eine nett gemachte Schritt-für-Schritt Web-Lösung in englisch. --Katpatuka 08:49, 2. Okt. 2007 (CEST)

Sudoku = Puzzle

Also ich finde es falsch ein Sudoku als Puzzle zu bezeichnen. Ich kann nur vermuten das dies evtl. aus dem englischen Artikel stammt allerdings würde ich jederzeit sudoku puzzle mit Sudoku Rätsel übersetzen.

Du hast Recht. Ändere es bitte.--Genossegerd 09:45, 28. Okt. 2007 (CET)

Geändert.

Evtl. das Erzeugen und Lösen von Sudokus in eigenen Artikel auslagern?

Ich fände es besser wenn die Absätze zum Thema Erzeugen von Sudokus und dem Lösen per Backtracking etc einen eigenen Artikel hätten. Ich schlage dies vor weil ich der Meinung bin das diese Punkte hier im Artikel nur halbherzig behandelt werden können. Für den Leser der Infos zu Sudokus generell sucht werden diese Themen nicht unbedingt interessant sein und es bläht den Artikel nur unnötig auf. Wer sich allerdings wirklich mit der Erzeugung oder ähnlichen beschäftigen will wird evtl. mehr Informationen brauchen.

Für mich ist das eine Frage des Textumfangs. So wie es derzeit ist, würde sich ein Auslagern von Unterpunkten eher nachteilig auf die Übersichtlichkeit des Artikels auswirken. Wenn Du die beiden Abschnitte („Erstellung eines neuen Sudokus“ sowie „Lösung eines Sudokus nach der Backtracking-Methode“) jedoch ausbauen möchtest, könnte ein Auslagern igendwann sinnvoll werden.--Genossegerd 10:11, 11. Nov. 2007 (CET) p.s. Durch Druck auf die zweite Taste von rechts oben über dem Schreibfeld kann (und sollte) man seinen Beitrag signieren.

Intuitives Raten ist keine Lösungsmethode

Eine Lösungsmethode ist eine Methode die zur Lösung führt. Raten zählt nun mal nicht dazu. Die Überschrift dieses Absatzes sollte geändert werden, da es eher ein einleitender Text ist und nicht wirklich eine Lösungsmethode behandelt die auf intuitiven Raten beruht.

Stimmt! Das ist so unreflektiert aus anderen Quellen übernommen worden. Ich habe es geändert.--Genossegerd 09:57, 11. Nov. 2007 (CET)

Hyper Sudoku

Ich habe eine neue Sudoku Variante hinzugefügt. Für den kurzen Text diente mir http://www.sudoku-space.de/hyper-sudoku als Quelle. Aber ich bin mir etwas unsicher in welcher Form ich Quellen angeben soll/muss.

--84.171.73.194 12:32, 5. Dez. 2007 (CET) Michael

Algorythmus

Weiß jemand einen guten Algorythmus oder Programmcode zum Erstellen eines Sudokus? Ich bin auf der Suche nach einem, programmiere auch gerne, bin aber nicht unbedingt ein Genie im programmieren, da ich erst in der 5. Klasse bin. Also, der Code sollte möglichst in Visual Basic .NET sein. --Umweltschutz 11:57, 23. Feb. 2008 (CET)

Schau mal bei Backtracking, dort hab ich einen Quellcode veröffentlicht (Turbo Pascal, aber geht in jeder anderen Sprache auch, man muss lediglich den Syntax anpassen), allerdings musst du dann einige Zahlen vorgeben bzw ich empfehl dir, schreib in die Erste Reihe die zahlen von 1-9, rein zufällig (aber regeln beachten, keine zahl doppelt!). Wenn du das getan hast, einfach die funktion durchlaufen lassen. --23:06, 12. Mai 2008 (CEST)

Varianten: Kakuro

Hier steht: "Kakuro wird häufig als Variante oder gar Nachfolger von Sudoku bezeichnet, ist jedoch faktisch ein eigenständiges Zahlenrätsel, das mit Sudoku nur den japanischen Ursprung gemein hat."
Aber diese Formulierung widerspricht dem zuvor geschriebenen, dass Sudoku seinen Ursprucng nicht in Japan hat. Wer könnte dies korrekter formulieren?--Wikipit 17:49, 6. Mär. 2008 (CET)

Hypothese

Hier steht: "Meist liegen diese Zellen mehr im Zentrum des Sudokus bzw. in Räumen, die bereits vergleichsweise weit gelöst sind."
Wer hat diese These aufgestellt? Alle bei mir "unlösbaren" Sudokus wiesen solche Felder mit nur zwei möglichen Lösungsziffern nicht (!) im Zentrum des Rätsels auf. Nun kann das Zufall sein, nur der obige Satz muß doch eine rationale Grundlage haben, sonst ist er entbehrlich.--Wikipit 18:05, 6. Mär. 2008 (CET)

Eliminierung

Kann jemand diesen Teil präziser fassen? Bereits am Anfang geht es nicht um Eliminierung, sondern einen positiven Schluß. Daß eine neue Zahl dann zur Eliminierung führt, ist dann klar.
Die Nackter-Einer-Methode ist falsch erläutert, da beispielsweise in der zitierten 5. Spalte in der 3. Zeile zunächst sogar eine 3, 4 und 5(!) stehen kann. Erst wenn dann laut Erklärung die 5 in der 5. Zeile Platz findet, bleiben 3 und 4 übrig und der restlich Schluß stimmt dann wieder. Schmerz bereiten mir auch folgende Formulierung unter der Twin-Methode: "Wenn nun eine dieser beiden Kandidatenziffern auch bei einer weiteren Zelle dieser selben Einheit als Kandidat auftaucht, kann man sie dort von der Kandidatenliste streichen." Welcher der Zellen hat denn Priorität? Oder meint der Verfasser eine andere Einheit?
Weiter stört die folgende Formulierung: "Die gleiche Regel gilt, wenn drei oder vier Kandidatenziffern auf drei bzw. vier Zellen eines Elements vorkommen. In diesem Fall reicht es sogar, wenn ein „Drilling“ (bzw. Vierling) unvollständig ist und nur zwei (bzw. drei) Ziffern enthält." Was darf man jetzt streichen/löschen/eliminieren ? --Wikipit

Ich habe es selbst umgemodelt. Hoffentlich billigt die Mehrzahl der Leser meine Formulierung.--Wikipit

Präziser fassen - ja, bitte - das möchte ich unterstützen - einfach zielgruppengerecht formulieren - für Leute, denen Sudoku noch neu ist und die mehr über Lösungsmöglichkeiten wissen möchten. Beispielsweise ist für mich diese Formulierung nicht mehr nachvollziehbar: "Weitere Kandidaten kann man in denselben Zellen eliminieren (= versteckte Twin-Methode)." Im Satz davor war von Twin-Zellen die Rede - wieso gibt es auf einmal weitere eliminierbare Kandidaten? Was meint bloß der Autor?fmeyer

Sicher kann man vieles anders ausdrücken. Aber Schritt-für-Schritt: Wo steht Twin-Zellen?--Wikipit 00:08, 27. Jul. 2008 (CEST)

Wenn Doppelpaare (Doppel-Zwilling, zwei Paare) in bespielsweise in nur zwei Zellen einer Zeile, was übrigens eine Art von Einheit darstellt, wie zuvor erklärt wurde, stehen, dann können keine weiteren Kandidaten in diesen betroffenen zwei Zellen gültig sein. Nach der indirekten Twin-Methode darf man die "weiteren", bisher noch nicht getilgten Kandidaten löschen, tilgen, vernichten, ausschließen. --Wikipit 00:07, 27. Jul. 2008 (CEST)

Oder der nächste Satz: "Ferner sind diese beiden Felder stets zugleich auch Element weiterer Einheiten. Sind die beiden Felder in derselben anderen Einheit gelegen, so sind diese Kandidatenzahlen in anderen Feldern dieser Einheit zu streichen (= direkte Twinmethode)." Ist dem Autor bewusst, was "dasselbe" semantisch bedeutet wenn er schreibt "derselben anderen"? Diese beiden Wörter gehören einfach nicht zusammen sonst kommt Quatsch heraus. fmeyer

Daß jedes Feld in drei "Einheiten" steht, steht irgendwo vorher., nämlich in einer Zeile, in einer Spalte und in einem Quadranten (=Block). Nein, der Schreiber der Zeilen ist nicht in Semantik geschult und hat sich Sudoku wie so vieles im Leben autodidaktisch angeeignet. Aber er weiß, was da inhaltlich stehen sollte und kann es nochmal erläutern: Ein isoliertes (= alleine) nur in zwei Feldern stehendes Doppelpaar (Zwillingsdoppel, gedoppeltes Paar von Kandidaten) einer Eiheit (z.B. Zeile) wird diesen beiden Feldern schließlich als Lösung dienen müssen. Sind diese beiden Felder zugleich gemeinsam (!) in einer anderen Einheit (z.B Quadrant) gelegen, dann sind diese Kandidaten in jener anderen Einheit außerhalb der beiden Felder zu löschen, tilgen oder ähnlich. Umgekehrt (vice versa) (Quadrant -> Zeile) gehts auch, gleichfalls Quadant -> Spalte oder Spalte -> Quadrant, nur Zeile zu Spalte und umgekehrt dürfte nicht gehen ;-))--Wikipit 00:07, 27. Jul. 2008 (CEST)

Verwirrung

• Dieser Untertitel verwirrt mich. Läuft die detailliert und gut bebilderte Beschreibung einer Lösungsmethode (ohne Computer) nicht ebenfalls auf einen "negativen" Schluß, also einen "Ausschluß von Kandidaten" hinaus?
• Ansonsten ist der Beitrag gut, besonders die "Logikregel 4", mit welcher der Artikel um die bis hierher noch nicht beschriebene (atypische) X-Konstellation mit Endpunkten im jeweils gleichen Quadranten (=Block) ergänzt wurde.--Wikipit
• ein "Auschluss von Kandidaten" und ein "negativer Schluß" ist richtig. Ich habe es trotzdem nicht so genannt, da bei diesem Verfahren eine zusätzliche Metaebene drinsteckt: es wird nur mit bestimmten Kandidaten (nämlich Paaren) gearbeitet, und nicht (wie bei "Auschluss von Kandidaten" und "negativer Schluß") ursprünglich gemeint) mit allen Kandidaten. Durch die Beschränkung auf Paare ist alles sehr übersichtlich, da sie die eigentlichen "wertvollen" Kandidaten sind. Diese Art von Selektion habe ich bisher nirgends gefunden. --Friedrich Graf 7.5.08

  Doch, doch. Irgendwie ist "Eliminierung" immer konkret, kann auch analysiert und gegliedert werden. Bisher steht theoretisch inhaltlich alles unter dem Punkt "Eliminierung" im Artikel. Da hatte ich mal rumgefuhrwerkt.
  Nur leider kam mir Deine "Logikregel 4" nicht in den Sinn und so habe ich Sie auch nicht formuliert. Entweder muß ich das noch in "X-Wing" reinquetschen oder davon noch einen Unterpunkt schaffen. Ist ja irgendwie mit X-Wing bezogen auf Spalte und Zeile verwandt, nur auf Quadrant bezogen, wobei Dein Beispiel ein gemischtes ist, denn zwei Enden folgen der Zeile, zwei andere ausschließlich einem Quadranten. Man könnte da aber auch noch den reinen Typ mit je zwei Enden in je einem gleichen Quadranten ohne zusätzlich Übereinstimmung in Zeile und (!) Spalte reinstopfen. Nur was kann man dann sicher eliminieren ;-)
  Was die sprachliche Begriffsbildung angeht, war ich nicht schöpferisch und habe die Termini den hier verlinkten Quellen entnommen. Ich mag eigentlich auch lieber deutsch als denglish.--Wikipit

• Es freut mich, das auch andere Freude an der deutschen Sprache haben :- ))) --Friedrich Graf 7.5.08
• Dieser Teil sieht einfach schon rein optisch eher schlecht aus. Zu viele Farben, mäßiges Beispiel und langweilige Erklärung. Nach meiner Meinung sollte er nochmal gründlich überarbeitet werden (welches ich Bewusst nicht selbst tue, da ich mit den neusten Anwandlung von Wikipedia nicht einverstanden bin) --84.171.105.55
• Beispiel, Erklärung, ... stimmt. Da ich selbst unsicher war, habe ich es vorher bei verschiedenen Nutzergruppen (Anfänger, Fortgeschrittene, Profis, Männer, Frauen, Kinder,...) getestet. Das Ergebnis war eindeutig. Die gewählte Art der Darstellung war die einzigste, die von ALLEN verstanden wurde. Natürlich hatte jeder seine Kritikpunkte: dem einen zu lang, dem anderen ... ... aber letztendlich ist Wikipedia für die "Masse" - und das war für mich das Entscheidungskriterium.

Was die Farben betrifft: ich verdiene meine "Brötchen" mit Farben; und hier gilt: weniger Farbe gleich weniger Verständnis. ... Für den größten Teil der Menschheit ist Logik eine schwierige Sache. Wenn man also Logik erklärt, sollte man dies nicht komplizierter machen, als nötig.--Friedrich Graf 16:43, 15. Mai 2008 (CEST)

• Mangelnde Qualität der Texte durch mehr Farben ausgleichen. So sollte man das Angehen. Die Farben im Text (Schritt 1 ist gelb Hinterlegt, etc) sind vollkommen überflüssig. In den einzelnen Grafiken sollte sich die Farben eher wiederhohlen (gleiche oder ähnliche Sachverhalte gleich darstellen...) anstatt zu versuchen jede mit anderen Farben zu machen. Der Text ist auf schlechten Niveau und passt nicht zum Rest des Artikels (ich sage nur "du siehst ...", "du ermittelst ..." usw.
• Danke für die konstruktive Kritik.--Friedrich Graf 15:01, 16. Mai 2008 (CEST)

Globale Paarsuche (GPS) überscheidet sich mit Eliminierung

GPS ist erstmal eine unglücklich gewählte Abkürzung. Globale Paarsuche spiegelt in großen Teilen den Abschnitt Eliminierung (vergleiche mit Twin-Methode, etc) wieder. Generell sollte "die Sprache" von Globale Paarsuche dem Rest des Artikels angeglichen werden. Ich finde 1-3 Beispiele reichen völlig aus um den Sachverhalt zu erklären.

--84.171.103.11

• Warum unglücklich? Die Methode stellt eine spezielle Selektion kombiniert mit verschiedenen Methoden dar. Durch die Methode der Selektion und die Beschränkung auf bestimmte Logikmethoden stellt sie etwas besonderes dar.

Daher benötigt die Methode einen besonderen Namen - und zur Abwechslung keinen Englischen. Was die Länge der Beispiele betrifft, kann ich es gerne kürzen, würde aber gerne erst mehr Meinungen hören. Schließlich habe ich bei verschiedenen Gelegenheiten die Menge der Erklärungen getestet und bin eher für zu wenig kritisiert worden. Schließlich dient die Erklärung nur denen, die es noch nicht verstanden haben...--Friedrich Graf 19:29, 22. Mai 2008 (CEST)

Grafik: Logikmuster C

"Beispiel 3 (Logikmuster C - Rosa): - du siehst 3 Lösungszahlen - du ermittelst in 2 Einheiten „34“-Doppelpaare, die paarweise angeordnet sind (Spaltenweise) - die Konsequenz aus den Doppelpaaren ist in „Logikregel 5“ beschrieben - damit entsteht im oberen rosa Block ein neues Doppelpaar: die „3“ und die „4“ kann nur in den mit den schwarzen Punkten markierten Feldern stehen"

Das neue Doppelpaar 34 entsteht nur dann, wenn du die Vorgabe 4 links oben im rosa Kästchen durch eine andere Ziffer ersetzt!

Ich danke herzlich für den Hinweis: wird schnellstmöglich ausgebessert.--Friedrich Graf 20:10, 3. Jul. 2008 (CEST)

Wir haben fertig. --Friedrich Graf 21:31, 3. Jul. 2008 (CEST)

Logikregel 3 (siehe Logikmuster A - Orange)

Ist soweit klar. Meine Kritik: Hier werden zwei verschiedene "Logikregeln" vermischt, denn wenn in einer Zeile 7 von 9 Zahlen belegt sind, verbleiben sowieso nur zwei Zahlen für die verbliebenen Felder. Also folgen keine weiteren Einschränkungen in der Zeile als bekannt und dieses Beispiel unterscheidet sich also nicht von "Logikregel 2 : Logikmuster grün". Einziger Unterschied besteht darin, daß beispielhaft erklärt wird, wie es zu einem Doppelzwilling kommen kann, was bei 2 (bewußt abstrahierend) unterblieb. Mein Wunsch wäre, diese "Logikregeln", die ja zur Erkennung von Mustern beitragen können, (sorgfältiger zu trennen oder) zu verschmelzen.--Wikipit

Lass mir ein wenig Zeit, über deine Gedanken nachzudenken ...--Friedrich Graf 19:44, 4. Jul. 2008 (CEST)

Kritik zur Darstellung der GPS-Methode

Danke Wikipit, für deine Mühe. Mir ist eine handfeste Kritik lieber als 3 höfliche Bemerkungen. Wenn ich jetzt einiges Bekannte wiederhole, bedenke bitte, das ich versuche nur "laut" zu denken (und nicht, dich zu belehren). Vielleicht erkennst du an irgendeiner Stelle meinen Irrtum oder einen Gedankenfehler bei mir.
A) Sudoku-Freunde, die sich an schwierigere Rätsel wagen, geraten oft in einen Teufelskreislauf: sie versuchen nach ihrer bekannten Methode zu lösen (durch das Erstellen von Kandidatenlisten) und erhalten schnell eine unübersichtliche Menge von Kandidaten.
B) Bei diesen vielen Kandidaten gibt es ähnlich wie bei Schach, wertvolle und weniger wertvolle Kandidaten. Bei dem größten Teil aller Sudokus werden diese weniger wertvollen Kandidaten nicht benötigt, um zu einer Lösung zu kommen.
C) Die GPS-Methode zwingt einen Rätselfreund, nur wertvolle Kandidaten aufzuschreiben.
Du schreibst "in irgendeiner Weise müssen die Paare zwingenderweise alleine sein...". Wenn sie nicht alleine wäre, würden sie nicht in der Kandidatenliste auftauchen (wie gesagt, durch die GPS-Methode ist es keine gewöhnliche Kandidatenliste).
D) Ein wichtiges Element, das in fast allen anderen Methoden fehlt, ist das der Sperre. Wer also Sperren findet, reduziert die ohnehin schon reduzierte Kandidatenmenge. Dabei soll das rätseln als Kreislauf verstanden werden:
- erst (besondere) Kandidaten suchen
- dann aus den relativ wenigen Kandidaten Schlussfolgerungen ziehen (Sperren ermitteln)
- und anschliessend auf erneute Kandidatensuche gehen (denn ähnlich wie beim Schach durch den Zug des Gegners, entsteht hier durch gefundene Sperren eine neue Spielsituation)
E) das Verständis dafür (das ganze als Kreislauf mit besonderen Kandidaten) darzustellen, war mir wichtig. Wenn du also deine Kritik übst, vermute ich, das mir das nicht komplett gelungen ist. Hast du eine Idee wie?
F) zur Kritik "Logikregel3":
- Du hast recht. Es wird ein und die selbe Medaillie von beiden Seiten erklärt. Für uns beide, die wir in Logik geübt sind, ist das "doppelt gemoppelt".
- Ich hielt es für wichtig, beide Seiten der Medailie jeweils extra zu erklären, da für Logikanfänger auch einfachste Zusammenhänge dargestellt werden müssen (OMA-Prinzip von Wikipedia).
G) Zur Kritik "Logikregel 4":
- wenn ein normales Sudoku mit normalen Kandidatenlisten gelöst wird, entstehen zwingende Logikregeln. Diese zwingenden Logikregeln basieren (meist) auf vollständigen Kandiadtenlisten
- die GPS-Methode und deren Logikregeln gehen (meist) NICHT von vollständigen Kandidatenlisten aus, sondern von sortierten Kandidatenlisten.
- durch diese (Vor-)sortierung der Kandidaten funktioniert Logikregel 4 in jedem Fall. ABER auch nur, weil vorsortiert wurde.
- wird also Logikregel 4 bei einer normalen Kandidatenliste angewendet, ist deine Kritik berechtigt.
Daher wäre es vermutlich das Beste, die Wichtigkeit dieser besonderen Kandidatenliste noch mehr herauszustreichen. Hast du eine Idee?
H) Zur Kritik "Beispiel1":
Du hast recht. Wahrscheinlich ist es mir zu schlecht gelungen, den Grundgedanken des "Kreislaufs" zu transportieren. Ich wollte eigentlich illustrieren, das die Kandidatensuche immer von neuem beginnt, da sich die Spielsituation ständig ändert. Daher hatte ich zur Illustration "Schritt1-4" gewählt. Wie kann ich das deutlicher machen?--Friedrich Graf 22:23, 5. Jul. 2008 (CEST)

Ich würde beides unbedingt trennen! Die sich wiederholende Vorgehensweise einerseits (ist natürlich notwendig und zweckmäßig) und die Listung der Methoden andererseits. Bei den Methoden würde ich alle listen und präzis beschreiben, was ihre Voraussetzungen sind und welche Schlüsse man dann (und nur dann) ziehen kann (in der Regel führen die von Dir geschilderten zu Kandidatenlöschung). Nichts ist nämlich frustierender, als wenn man Neulinge zu falschen Schlüssen durch bekannte Muster verleitet. Zwar trifft es zu, wie Du schilderst, dass man nicht sofort und jederzeit alle Kandidaten braucht. Jedoch bevor man einen falschen Schluß zieht, sollte man immer die Voraussetzungen schon prüfen. Beispiel: ein zwingendes Paar in einer Zeile führt zu gar nichts, zwei in korrespondierend gleichen Spalten hingegen kann zur Löschung in den beiden betroffenen Spalten führen. Wären aber dieselben Felder in der Spalte zwingendes Paar, so kann man in der Zeile putzen usw. Ohne eine zwingende Voraussetzung in einer der beiden Richtungen ist diese Konstellation nicht nützlich.--Wikipit

Ich werde mich mal an einer Umformulierung versuchen - vielleicht kannst du helfen? BG--Friedrich Graf 10:20, 6. Jul. 2008 (CEST)

Der Start ist geschafft...--Friedrich Graf 13:17, 6. Jul. 200

NP-Vollständigkeit hat keine korrekte Quelle und ist unter Umständen FALSCH

Im Artikel heißt es, dass das Finden einer Sudoku-Lösung ein NP-vollständiges Problem ist. Diese Aussage verstehe ich nicht, obwohl mir die Komplexitätstheorie einigermaßen gut bekannt ist. Die angegebene Quelle hilft hier nicht weiter und erwähnt Sudokus nicht einmal.

NP-Probleme oder NP-vollständige Probleme sind Entscheidungsprobleme, die mit Ja oder Nein beantwortet werden müssen. Welches soll bei der obigen Behauptung die Fragestellung sein?

1. Ob ein vorgegebenes Sudoku eine Lösung hat? Dann ist die Antwort doch schon definitionsgemäß ein Ja, und somit nicht NP-vollständig sondern trivial.
2. Ob eine vorgegebene Zahlenzuweisung eine Lösung für ein vorgegebenes Sudoku darstellt? Das ist auf triviale Art in polynomialer Zeit zu ermitteln und somit niemals NP-vollständig.
3. Ob eine vorgegebene Zahl in ein vorgegebenes Feld gehört? Ob eine vorgegebene Zahl nicht in ein vorgegebenes Feld gehört? Das scheinen mir durchaus interessante und nichttriviale Fragestellungen zu sein, aber es sind nicht einmal die einzigen, und welche von allen ist nun gemeint??? Solange das nicht geklärt ist, sollte die Aussage gestrichen werden und gehört nicht in einen lesenswerten Artikel.

Ich konnte bisher sämtliche angegangene Sodokus mit Hilfe der Linearen Optimierung lösen, und falls so etwas immer möglich sein sollte, dan wären die Fragestellungen unter 3 ebenfalls nicht NP-vollständig, ja sogar gänzlich irreführend.
--Heinrich Puschmann 12:46, 21. Mai 2008 (CEST)

NP-Vollständigkeit ist zutreffend. Obwohl Standard Sudokus mit 9x9 Felder schnell per Computer lösbar sind, tritt wie auch im Artikel erklärt dieser Effekt erst auf wenn du es mit größere Sudoku handelt(z.B 100x100). --84.171.103.11

Richtig, ich muss wohl übermüdet gewesen sein. Eine einzelne nxn-Sudoku-Klasse kann für sich genommen ja garnicht NP-vollständig sein, da die Anzahl der möglichen Zahlenbesetzungen endlich ist. In der Literatur über die NP-Vollständigkeit lautet die entscheidende Fragestellung bei größeren Sudokus freilich anders als üblich, nämlich: "Existiert eine gültige Zahlenbesetzung oder nicht?" Wenn schon vorausgesetzt wird, dass genau eine Lösung existiert, dann ist die Aufgabenstellung aufgrund der angegebenen Quellen nicht zwingend NP-vollständig.
--Heinrich Puschmann 11:12, 26. Mai 2008 (CEST)

Neu gefundenes Zitat:
It is unknown whether the general Sudoku problem restricted to puzzles with unique solutions remains NP-complete or becomes polynomial, in Alberto Moraglio & Julian Togelius, Geometric Particle swarm Optimization for the Sudoku Puzzle, ACM 978-1-59593-697-4/07/0007, GECCO'07. Dieses Zitat erscheint mir glaubwürdig, der Artikel ist öffentlich einsehbar und kann heruntergeladen werden (http://julian.togelius.com/Moraglio2007Geometric.pdf).

Die starke Bedingung hier ist die Einzigartigkeit der Lösung. Falls wir beim Standard-Sudoku lediglich wüssten, dass eine oder mehrere Lösungen existierten, dann bräuchte die Suche nach einer Lösung ebenfalls exponentiell viele Schritte (leicht zu beweisen).

Ich bin dafür, die NP-Vollständigkeits-Aussage aus dem Artikel zu entfernen, solange keine Beweise für die allgemein beabsichtigte Fragestellung vorhanden sind. Die Schlussfolgerung, dass ein Sudoku von beliebiger Größe nur in exponentieller Zeit lösbar wäre, ist aus dem vorhandenen jedenfalls nicht zulässig.
--Heinrich Puschmann 11:59, 26. Mai 2008 (CEST)

In (http://w3studi.informatik.uni-stuttgart.de/~thomds/SudokuinNPC.pdf) liegt der Beweis vor, dass die allgemeine Lösung von n^2 x n^2 Sudokus beliebiger Größe ein NP-vollständiges Problem ist. Diese Quelle ist eigentlich schon seit geraumer Zeit im Artikel enthalten und es ist mir ein Rätsel warum sie kürzlich daraus entfernt wurde. Solange hier niemand nachweisen kann, dass die Argumentation fehlerhaft ist, sollte sie zumindest als Weblink vorhanden bleiben.

Zahl der Lösungsmöglichkeiten

Fakt ist, dass es 9! = 9*8*7*6*5*4*3*2*1 = 362.880 Möglichkeiten gibt eine Unterquadrat mit den Ziffern 1 bis 9 auszufüllen ohne eine Ziffer mehrfach einzutragen. Für die drei diagonalen Unterquadrate, die keine gemeinsamen Spalten oder Zeilen haben, gibt es 362.880 * 362.880 * 362.880 = 47.784.725.839.872.000 Möglichkeiten 27 Ziffern einzutragen ohne die Regeln unmittelbar zu verletzen. Im Allgemeinen gibt es bereits für drei Blöcke weniger Möglichkeiten, weil gemeinsame Spalten oder Zeilen beachtet werden müssen. Die Zahl der möglichen Lösungen dürfte kaum wesentlich höher als 47.784.725.839.872.000 liegen (wahrscheinlich liegt sie eher darunter), zumal es sogar schon Vorgaben mit nur 17 Ziffern gibt, die eine eindeutige Lösung besitzen. Viele schwierige Sudoku-Rätsel haben nur 27 vorgegebene Ziffern. Viele der 47.784.725.839.872.000 Vorgaben besitzen keine Lösung und einige dafür mehrere. Unter dem Strich sind es sicherlich nicht wesentlich mehr als 47.784.725.839.872.000 eindeutige Lösungen. Die genaue Zahl dürfte niemand kennen, da es keine wirklich universal anwendbaren Lösungsmethoden gibt. Es gibt offenbar keine Weltformel oder allgemeine Sudokutheorie, um zu berechnen wie viele Lösungen es zu einer Vorgabe gibt. Dies wird erst am Schluss erkennbar. Die gesamte Zahl der Lösungen ist somit erst recht nicht berechenbar. Die angegebene Zahl 6.670.903.752.021.072.936.960 - offenbar eine Fantasiezahl - ist sicherlich zu groß abgeschätzt. --84.59.130.161 23:32, 8. Jun. 2008 (CEST)

Die im Artikel genannte Zahl 6.670.903.752.021.072.936.960 ist etwa 140.000-fach größer als 47.784.725.839.872.000. Dies ist vollkommen unrealistisch. Denn wird nach den drei Blöcken in der Diagonalen noch ein vierter Block ausgefüllt, gibt es bereits weit weniger als 362.880 Möglichkeiten diese 9 zusätzlichen Felder auszufüllen. Für das erste Feld im vierten Block gibt es maximal noch sechs eventuell sogar nur noch drei Möglichkeiten. Wird beispielsweise die unterste Reihe ausgefüllt, gibt dafür keinesfalls mehr als 6*5*4 = 120 Möglichkeiten, weil drei Zahlen in dieser Reihe bereits vergeben sind. Diese obere Grenze ergibt sich, falls nur einer der schon ausgefüllten diagonalen Blöcke berücksichtigt wird. Für die restlichen sechs Zahlen bleiben maximal 6! = 720 Möglichkeiten, womit sich als obere Grenze von 86.400, weit weniger als 140.000, ergibt. Für vier Blöcke oder 36 Felder ergeben sich folglich weniger als 6.670.903.752.021.072.936.960 Möglichkeiten für erlaubte Vorgaben. Für die meisten dieser Vorgaben (sofern eindeutig lösbar, ein recht einfaches Sudoku) gibt es aber sicherlich keine Lösung und die Gesamtzahl der Lösungen liegt mit höchster Wahrscheinlichkeit niedriger. --88.68.117.109 11:26, 10. Jun. 2008 (CEST)

Wer mal ein paar Sudoku-Rätsel gelöst hat, weiß dass das Einfüllen von Ziffern auf gut Glück selten zum Ziel führt. Leichte Sudoku-Rätsel haben etwa 32 Vorgaben. Falls vier weitere Ziffern auf gut Glück eingetragen werden (ohne die Regeln unmittelbar zu verletzen natürlich), wird es in den meisten Fällen am Ende nicht aufgehen. Sudoku-Rätsel mit 36 Vorgaben, entsprechend vier Blöcken, gibt es praktisch nicht (viel zu einfach!). Von diesen 36 Vorgaben werden sicherlich etliche nicht wirklich erforderlich sein, so dass das Rätsel offensichtlich auch bereits mit weniger Vorgaben lösbar wäre. --84.59.240.223 12:54, 15. Jun. 2008 (CEST)

Das Beispiel mit nur 22 Vorgaben (schwarze Ziffern) besitzt tatsächlich nur eine einzige Lösung, die durch die roten Ziffern angeben ist. Dies lässt sich etwa wie folgt zeigen: Im Block rechts unten ist die Position der 1 eindeutig festgelegt. Die Ziffern 4 und 9 in diesem Block können zunächst nur bis auf die Reihenfolge in der rechten Spalte festgelegt werden. Damit verbleiben für die Ziffern 6 und 3 nur noch die beiden Felder links in der Mitte. Die Position der 6 ist wegen der 6 im Block oben rechts eindeutig und damit auch die 3. Die 1 im Block oben rechts kann als nächstes eindeutig festgelegt werden, wobei die 1 im Block unten links verwendet wird. Mit diesem Wissen folgt auch die Position der 1 im Block oben links. Auch die 9 im Block oben rechts kann festgelegt werden. Dabei ist dabei zu beachten, dass die 4 und die 9 im Block unten rechts in der rechten Spalte liegen müssen. Die 1 im Block links unten kann ebenfalls leicht gefolgert werden. Mit der 1 im Block links unten wird klar, dass die 4 dort nicht in der oberen Zeile liegen kann. Damit ist auch klar wo im Block unten rechts 4 und 9 liegen müssen. Die 3 ist im oberen mittleren Block in der unteren Zeile und die 8 in der oberen Zeile. In den Blöcken unten links und in der Mitte können die Ziffern zunächst eindeutig auf die Zeilen oben, unten und in der Mitte verteilt werden, wobei die Verteilung auf die Spalten zunächst noch offen bleibt. Im mittleren Block liegen unten 2,8 und 6. Dabei ist klar, dass 2 und 6 links oder rechts liegen müssen. Für die 8 verbleibt daher nur noch die Mitte. Analog liegen 3,5 und 7 oben. (3,5) liegen links und in der Mitte und die 7 daher rechts ... Nach einer Reihe weiterer Schlussfolgerungen dieser Art folgt schließlich, dass die Lösung tatsächlich eindeutig ist. Die Zahl der Möglichkeiten unterschiedliche Ziffern an den 22 Positionen vorzugeben ist kleiner (9*8*7*6) * (8*7*6) * (7) * (8*7) * (8*8*7) * (7 ) * (7) * (8*6*7) * (8*7*6*6) = 5.922.581.291.546.443.776. Diese Abschätzung ergibt sich, wenn die Blöcke zeilenweise von oben nach unten und von links nach rechts durchgegegangen werden. Die angegebne Schätzung für die Zahl der Lösungsmöglichkeiten dürfte mindestens um einen Faktor tausend zu groß abgeschätzt sein.

Uups, das geänderte Bild passt jetzt nicht mehr zum Text. Die 6 im Block links oben fehlt, dafür ist die 7 im Block darunter (links in der Mitte) nachgetragen, schließlich wurde 3 und 6 rechts in der Mitte hinzugefügt. --88.68.110.32 10:31, 5. Jul. 2008 (CEST)

Naja, Dein Bild stammt von der Artikelseite. Hier in der Diskussion weiter unten wurde über das "ideale" Sudoku diskutiert und von mir postuliert, dass unnötige Vorgaben entfallen sollten. Darauf wurde mir die die überflüsssige 6 im Quadrant oben links mitgeteilt, was stimmt und deshalb von mir entfernt wurde (wodurch aber die Schönheit etwas litt) und das Lösungsdiagramm ergänzt. Weitere Änderungen wie eine 7 und 3 bzw. eine 6 unten in der Mitte wurden nicht (!) verändert, warum auch.--Wikipit

Es zeigt sich, dass die Bestimmung der Zahl der Lösungsmöglichkeiten, hier eins für ein eindeutig lösbares Sudoku-Rätsel, alles andere als einfach ist. Inbesondere gibt es keine effiziente Methode, die sich für alle möglichen Vorgaben anwenden lässt. Je weniger Vorgaben es gibt, um so schwieriger wird die Aufgabe. Um die Zahl aller Lösungen zu bestimmen, könnten neun Ziffern in einem Block, einer Zeile oder einer Spalte vorgegeben werden. Die Zahl der gefundenen Lösungen wäre dann am Ende noch mit 9! zu multiplizieren, da die Ziffern in der Vorgabe vertauscht werden könnten. Bei der riesigen Zahl an Lösungen ist dies jedoch selbst mit einem Supercomputer undenkbar. --88.68.121.115 11:08, 23. Jun. 2008 (CEST)

Die angegebene Zahl ist nicht nur viel zu groß sondern auch aus einem anderen Grund eindeutig falsch: Aus einer Lösung ergeben sich zunächst 9! Lösungen indem die Ziffern vertauscht werden. Dann können auch noch jeweils die ersten drei Zeilen, die Zeilen 3,4 und 6 oder die Zeilen 7,8,9 vertauscht werden. Ebenso können die Spalten (1,2,3), (4,5,6) oder (7,8,9) vertaucht werden. Für jede dieser Vertauschungen von Spalten und Zeilen gibt es 6 Möglichkeiten. Es ist zu beachten, dass die Vertauschung zweier Ziffern immer zu einem anderen Ergebnis führt als die Vertauschung zweier Zeilen oder Spalten. Die Zahl der Lösungen muss daher ein ganzzahliges Vielfaches von (9!)*(6⁶) sein. Dies ist bei der angegebenen Zahl nicht zutreffend. --84.59.61.97 23:14, 27. Jun. 2008 (CEST)

Die letze Überlegung ist falsch. Die Zeilen im Block 1 links oben seinen (z1,z2,z3), dann könnten die Zeilen in Block 2 rechts daneben wie folgt vertauscht sein (z2,z3,z1) und im dritten Block (z3,z1,z2). In den Blöcken B4, B5, B6 darunter könnten die Ziffern in gleicher Weise auf die Zeilen verteilt werden, wobei nur die Spalten vertauscht werden. Schließlich kann dies auch für die Blöcke B7,B8,B9 in der unteren Zeile gelten. In einem solchen Fall wäre eine Vertauschung der Zeilen im gesamten Sudoku gleichbedeutend mit einer Vertauschung der Ziffern. Daher kann in diesem Fall keine neue Lösung erzeugt werden, indem diese Zeilen vertauscht werden. Dies ändert allerdings nichts daran, dass die Zahl der Lösungsmöglichkeiten sicher kleiner 6.670.903.752.021.072.936.960 ist. --88.68.100.217 09:42, 9. Jul. 2008 (CEST)

Die ideale Aufgabe

Im Artikel steht nichts über Eigenschaften von Aufgabenstellungen (mit Ausnahme der Eindeutigkeit). Deshalb postuliere ich mal (und erbitte konstruktiven Widerspruch!):

1. eine eindeutige Lösung
2. keine unnötigen Zahlen = nur zwingend notwendige Zahlen. Alles andere verwässert, wie die Vorgabe eines Steines beim Schachspiel.
3. ist zur Lösung eine alternative, letzte Zahl erforderlich, so sollte dies zuvor bekannt sein (mindestens als schwere Aufgabe gekennzeichnet, selbst wenn sie nicht "schwer" ist)--Wikipit 17:18, 14. Jun. 2008 (CEST)

• ich würde mal vermuten, das mit den unnötigen Zahlen - funktioniert nicht:

1. a) es gibt unterschiedliche Lösungsmethoden, die sich auf unterschiedlichen Weg dem Ziel nähern. Für die eine Methode ist das erreichen des Zieles unkompliziert, für die nächste Methode mühselig. Welche Methode man wählt, hängt von zu vielen Faktoren ab.
2. b) eine "ideale" Aufgabe, ohne "unnötige" Zahlenvorgaben, würde nur einen Typ Rätselfreund zulassen: den "idealen". Aber nicht den zerstreuten, halbintelligenten, hastigen, strategischen usw. Ich vermute aber, das das gerade den Reiz ausmacht: jeder findet seinen persönlichen Weg. Die Voraussetzung: unterschiedliche Mengen (und Qualitäten) von Vorgaben.

... was "die letzte Zahl" betrifft, so geht es mir damit ähnlich (wie mit der "idealen Aufgabe"). Wer kann festlegen, wann ich diese letzte Zahl brauche? Egal ob Mensch oder Computerprogramm: jeder streikt an einer anderen Stelle. Was ist also die EINE Zahl? (ich hoffe, das war nicht zu philosopisch :-).--Friedrich Graf 22:14, 14. Jun. 2008 (CEST)

Ich teile Deine Meinung, daß die zusätzliche letzte Zahl, wie ich sie nannte, von den verwendeten Methoden abhängig ist. So man "alle" Methoden verwendet, die ohne Computer der Mensch verwenden könnte, könnte es also sein, daß keine letzte Zahl erforderlich ist, richtig. Aber dann sollten wenigstens "alle" diese Methoden in diesem Artikel genannt und beschrieben werden. Ansonsten ist Sudoku ein "Spiel" ohne feste Regeln!?--Wikipit

• Da muss ich jetzt mal "laut" denken:

1. - an der "GPS"-Methode sieht man, das es für 75% aller Sudokus zuviele Methoden gibt ... denn für diese 75 % (die die Mehrheit der Meschheit löst - die ganz schweren Fälle sind ein anderes Thema) braucht man nur die GPS-Methode. Und in dieser GPS-Methode sind NICHT alle jemals beschriebenen Lösungsmethoden enthalten. Sind diese anderen Methoden dann unnötig?
2. - die restlichen 25 % der Sudokus sind wiederum nicht KOMPLETT mit den bekannten Regel lösbar (Beispiel: schwere Sudokus, die nur mittels Fallunterscheidung zu lösen sind - was ich persönlich aber nicht als logische Lösung, sondern mehr als systematisches Raten bezeichnen würde - aber die Geschmäcker sind halt verschieden). Siehe hierzu auch: http://www.mathematische-basteleien.de/sudoku.htm ziemlich weit unten, Kapitel "Versuch und Irrtum"
3. - an einer Methode zum logischen lösen (ohne Computer und Raten) von den im Beispiel genannten Sudokus arbeite ich zur Zeit, habe auch schon einen "roten Faden" - aber Erfahrenungsgemäß ziehen sich solche Freizeitbeschäftigungen sehr lange hin ...
4. - solange also nicht alle Lösungsmethoden bekannt sind, müssen die Alten reichen.
5. >>>>> ist das dadurch ein Spiel ohne feste Regeln?
6. - ich denke es ist ein Spiel mit festen Regeln, nur die Lösungwege sind individuell (so individuell wie Menschen halt sind).
7. - Gemäß dem Motto "viele Wege führen nach Rom" ist bei Sudoku (=Rom) das Ziel eindeutig definiert. Jetzt aber festzulegen, das nur der Weg über die Alpen der beste Weg nach Rom ist, geht glaube ich nicht (und wäre sicherlich auch ein verkehrter Ansatz bei diesem Spiel).--Friedrich Graf 12:42, 15. Jun. 2008 (CEST)

• Hallo Friedrich, um uns in einem Dialog nicht zu zerfleischen, versuche ich mal Deinen letzten Beitrag (ab "laut denken") mit meiner Terminologie in Einklang zu bringen und dann zu analysieren:
  • Die berichtete %-Verteilung (75:25) steht schon im Artikel und sagt mir nichts Neues.
  • "Systematisches Raten" gehört nach meiner vorherigen Terminologie zum Begriff "alternative letzte Zahl". Aber im Unterschied hierzu, sprach ich nur von EINER Alternative (also zwei alternative Kandidaten) und auch nur für die "letzte Zahl", also in dem letzten Lösungsschritt. Mehrere Schritte sind wegen der Vielzahl der Möglichkeiten kaum akzeptabel und kommen m.W. einer nicht zu Ende gedachten Sudoku-Aufgabe gleich. Beim Schach gibts zwar Matt in 1...5 Zügen aber niemals Matt in 40 Zügen und auch wird stets bei einer Aufgabenstellung die Zahl der Züge angegeben, damit der Anfänger nicht durch zu hohe Schwierigkeit frustriert wird. Warum dann nicht Sudoku mit "offener Variante" im Namen?
  • Lösung ohne Computer sollte doch die Regel sein, wenn man eine Aufgabe für Menschen stellt. Vergleichsweise kann man ja auch mal Schachaufgaben mit Computer lösen, das hätte auch keinen Sinn, es sei denn, man will dessen Leistungsfähigkeit testen.
  • Du unterscheidest nicht zwischen Lösungs"wegen" und Lösungs"methoden". Ich denke, daß schon alle Methoden bekannt sind nach mehr als 10 Jahren Existenz eines so einfachen "Spiels". Aber natürlich gibts immer verschiedene Wege und man kann nach Erfordernis dabei auch verschiedne Methoden einsetzen, um in Deinem Beispiel Rom zu bleiben, mit oder ohne Bergsteigerausrüstung, also über die Alpen oder um sie herum.
  • Zu den Methoden (ohne Computer): Immer handelt es sich doch um "Figuren", die es zu erkennen gilt und die dann nach feststehenden Regeln zu Schlußfolgerungen führen, wie Kandidatenelimination in bestimmten betroffenen Einheiten oder zur Festlegung einer Lösungszahl. Nur wenn es keine solche erkennbare Figur mehr gibt, kann überhaupt eine Probiermethode zwingend sein. Nur über die Zulässigkeit einer solchen am Ende aller Logik hatte ich dikutiert.
  • Nach wie vor: Zusätzliche unnötige Zahlen sollten unterbleiben. Das bezieht sich auch bei Ausschöpfung der üblichen Methoden.--Wikipit

• Ich will dich nicht agitieren, aber du hast um konstruktiven Widerspruch gebeten. Um es kurz zu sagen: es geht (meiner Ansicht nach) nicht. Das was du willst, funktioniert nicht.
• Ich zitiere mal deinen Einstiegstext: "keine unnötigen Zahlen = nur zwingend notwendige Zahlen. Alles andere verwässert, wie die Vorgabe eines Steines beim Schachspiel."

Also, wenn ich das richtig verstanden habe, entsteht bei mir eine neue Frage: was sind die zwingend notwendigen Figuren im Schach? Wenn es also eine Methode "abc" gibt: "Schach in 3 Zügen", werden ja nicht alle Steine gebraucht. Sind sie dann unnötig? Nein, denn bei anderen Methoden werden sie gebraucht.--Friedrich Graf 22:34, 16. Jun. 2008 (CEST)

Zu Beginn des Schachspiels erhalten beide Spieler alle 16 Figuren, es sind alle nötig. "Vorgabe" ist beim Schach ein feststehender Terminus; man verzichtet als stärkerer Spieler freiwillig auf eine Kampffigur, die sogenannte Vorgabe. Solch eine Konstellation geht aber von taktischen oder strategischen Fehlern (nicht Regelfehlern) des schlechteren Spielers aus und man will den Verlauf des Spiels für beide gleich stark machen. Somit kann aber eine solche Konstellation niemals in einer Aufgabenstellung vorgegeben werden.--Wikipit

• Deinen Vergleich "Immer handelt es sich doch um "Figuren", die es zu erkennen gilt und die dann nach feststehenden Regeln zu Schlußfolgerungen führen" finde ich sehr gut (ich würde allerdings den Begriff der "Muster" passender finden)... und zugleich einen Trugschluß:

- es geht immer darum Muster zu finden - Ja.--Friedrich Graf 22:34, 16. Jun. 2008 (CEST)

Muster ist der zutreffendere Begriff.--Wikipit

- jedes Muster, das eine Lösung hervorruft, erzeugt ein neues Muster.--Friedrich Graf 22:34, 16. Jun. 2008 (CEST)

Aber dies steht nicht zur Diskussion, sondern Muster werden schrittweise, sofern erkannt, mit einer bestimmten bekannten Methode gelöst.--Wikipit

- damit hängt von der Reihenfolge der Mustererkennung das finden einer Lösung ab.--Friedrich Graf 22:34, 16. Jun. 2008 (CEST)

Nein. Entweder erkennt man das Muster oder nicht. Wenn man "nicht weiter kommt", weil man ein Muster nicht erkannt hat, so braucht der Aufgabensteller dies nicht zu beachten oder unterstützen, es sei denn, er will "Anfänger"n eine Aufgabe bereiten. Aber dann sollte er dies kennzeichnen.--Wikipit 10:45, 17. Jun. 2008 (CEST)

- wie soll es dabei feststehende Regeln geben?:

- welches Muster ist es wert, immer zuerst betrachtet zu werden?--Friedrich Graf 22:34, 16. Jun. 2008 (CEST)

Das ist unwichtig, sofern es überhaupt einen Schritt weiter geht. Willst Du etwa behauptem, dass die Notwendigkeit von einzelnen Aufgabenzahlen nur entsteht, weil der Lösende unterschiedliche Wege gegangen ist? Das wäre für Sudoku m.E. ein Todesstoß.--Wikipit 10:45, 17. Jun. 2008 (CEST)

- wie soll ich allen Menschen vermitteln, das nur dieses eine Muster das "alles selig machende" ist, wenn ich (logischerweise) auch schwierige Muster verwenden muss (was aber den Intellekt mancher Leute übersteigen dürfte.--Friedrich Graf 22:34, 16. Jun. 2008 (CEST)

Sofern schwierige Muster nur solche sind, die der Computer "überschaut", sind sie nach meiner obigen Forderung, auch in einer Aufgabe für Fortgeschrittene auszuschließen. Wenn das Erkennen dieser "schwierigen" Muster aber für normale Menschen erlernbar ist, darf m.E. dies bei der Aufgabe berücksichtigt werden, d.h. Aufgabenzahlen darüberhinaus sind unnötig.--Wikipit 10:45, 17. Jun. 2008 (CEST)

auch das gibt es beim Schach nicht! Es gibt immer wieder ungewöhnliche Lösungen (für bekannte Probleme). Ist Schach damit verwässert?

>>> Entweder missverstehe ich dich, oder ich brauche mal ein anderes Beispiel als Schach :-) --Friedrich Graf 22:34, 16. Jun. 2008 (CEST)

Bezgl. Schach: Natürlich gibt es immer wieder ungewöhnliche (schnellere, elegantere) Löäsungen, aber die gestellte Aufgabe hat in aller Regel keine unnötigen Voraussetzungen. Sonst ist sie keine interessante Aufgabe.--Wikipit 10:45, 17. Jun. 2008 (CEST)

Jetzt haben wir doch den Sprung ins Philosophische geschafft :-) Darum direkt heraus: mir scheint, als ob dir irgendetwas Konketes vorschwebt. Sprich!--Friedrich Graf 08:19, 18. Jun. 2008 (CEST)

Unnötige Vorgaben

Ich schätze mindenstens 90 Prozent, allemal die leichten Sudokurätsel, enthalten unötige Zahlenvorgaben, so dass die eindeutige Lösung auch ohne einige Vorgaben zu finden wäre. Im Beispiel

ist etwa die 6 im Block oben links nicht erforderlich. Die 6 im Block unten rechts kann zunächst ermittelt werden, anschließend im Block darüber rechts in der Mitte, dannach auch im Block links in der Mitte und schließlich zeigt sich, dass die 6 im Block oben links nur links in der Mitte liegen kann. Dabei ist noch zu beachten, dass im Block oben in der Mitte die 6 in der oberen Zeile liegen muss. Dieses bereits relativ schwere Sodoku benötigt daher maximal 21 Vorgaben, um die eindeutige Lösung finden zu können. --88.68.101.150 13:41, 27. Jun. 2008 (CEST)

Stimmt, leider geht die Symmetrie damit dann völlig flöten. Aber ich werde die Zahl 6 tilgen, gut so? --Wikipit

Häh, ich kann da weder mit noch ohne die Zahl 6 irgendeine Symmetrie erkennen. Kannst du das mal etwas genauer erklären? --12:13, 5. Jul. 2008 (CEST)

(z=Zeile , s=Spalte, Q= Quadrant [= Block ; von mir zeilenweise und fortlaufend durchnumeriert] ) Mit der 6 in z2s1 ist Quadrant 1 der Form nach gespiegelt zum 9. Quadranten, so wie gegenwärtig der 3.Q mit dem 7.Q noch ist. Der Mittelquadrant hatte in der ursprünglichen Fassung noch eine Ziffer in z5,s4 , so daß er in sich selbst symmetrisch war. Der 6.Q hatte noch im Ursprung in z6s9 noch eine Zahl, womit er ebenfalls formsymmetrisch zu 4.Q war. Insofern stellt eine zahlen"sparende" Version immer eine Gefahr für die ursprüngliche Aufgabenschönheit dar. Daher ist ja die Konstruktion von "schönen" Aufgaben, die zugleich korrekt und ideal (also ohne unnötige Zahlenvorgaben) sind, eine Herausforderung dar.--Wikipit

Ich denke die 9 in Q1 z3s2 ist auch unnötig. Kann dies mal jemand überprüfen? --84.59.230.27 21:46, 6. Jul. 2008 (CEST)

Das dürfte falsch sein. Falls die 9 in z3s2 durch eine 4 ersetzt wird, gibt eine andere Lösung. Diese Lösung ist vermutlich auch eindeutig. Ich bin da aber nicht so sicher. Ich bin mir aber nicht ganz sicher, ob da nicht vielleicht eine 1 stehen könnte. Vielleicht kann dies mal jemand überprüfen. --84.59.44.137 10:29, 7. Jul. 2008 (CEST)

Nein, mit der 4 in z3s2 gibt es keine Lösung und ich denke die Zahlenangabe in z3s2 kann tatsächlich entfallen. Vielleicht kann dies ja noch mal jemand prüfen.

Ich habe das noch einmal genauer geprüft. Das Sudoku-Rätsel kann auch ohne in 9 in z3s2 eindeutig gelöst werden. Dabei kann weitgehend genauso vorgegangen werden. Zunächst kann die 1 in Q9 bestimmt werden, dann 6 und 3 in Q9, dann 6 in Q6,Q4 und Q1, dann die 1 in Q3, (die 1 in Q7 kann jetzt nicht so rasch bestimmt werden). Das Paar (7,2) und (5,9) in Q3 und das Paar (4,9) in Q9 und das Paar (4,1) in Q5 kann festgelegt werden. Die Ziffern in Q8 können zunächst auch die Zeilen verteilt werden und dann die Position von 7 und 8 in Q8 bestimmt werden ... Wenn das Sudoku fast gelöst ist, scheint es noch möglich zu sein eine Lösung mit (9,1) in Q7 und Q1 vertauscht zu finden. Dies geht aber dann doch nicht auf. Die Lösung kann also auch ohne die Vorgabe der 9 gelöst werden. --88.68.122.81 13:54, 8. Jul. 2008 (CEST)

Wenn ich richtig verstehe, probierst Du an einer Stelle zwei Möglichkeiten, was aber meinen o.g. Bedingungen einer idealen Aufgabe widerspricht (in Satz 3 nur mit Deklaration erlaubt). Mit der umstrittenen 9 in z3s2 ist die Aufgabe ohne Probieren lösbar! --Wikipit

Das kann man so sehen. Ich wollte an dem Beispiel mit der 6 und der 9 eigentlich auch nur erläutern, dass Sudoku-Rätsel in der Regel unnötige Vorgaben enthalten. Erstens ist es sehr schwer nachzuweisen, ob eine bestimmte Ziffer wirklich benötigt wird und zweitens sind minimale Rätsel ohne unnötige Ziffern nicht unbedingt ideale Rätsel. Vor allem sind sie so schwer, dass sie nur durch durch Raten oder mit Helfestellung und kaum ohne Computer gelöst werden können. Solche minimalen Sudoku-Rätsel enthalten aber wohl selten mehr als 22 Vorgaben. Damit ist die vermeintlich von Russell (oder Felgenhauer?) berechnete Zahl mit an Sicherheit grenzender Wahrscheinlichkeit falsch, weil viel zu groß. --88.68.108.7 10:01, 9. Jul. 2008 (CEST)

Dein letzter Satz paßt nicht in dieses topic (unnötige Vorgaben oder idelale Aufgabe) und darüber will ich noch nicht mitdiskutieren. Dafür müßte ich mich mehr mit Mathematik beschäftigen als bis hierher erforderlich war.--Wikipit

Korrektur: Die 9 in z3s2 ist doch notwendig, um eine eindeutige Lösung zu erhalten. Ohne die 9 gibt es noch eine Lösung mit (9,1) vertauscht in Q1, Q4, Q7, (4,1) und (9,8,7) in Q5, (4,8,7) in Q6. Ausgehend von dieser zweiten Lösung gibr es noch eine Dritte mit (5,9) in Q1 und Q3 vertauscht. --84.59.226.59 18:35, 11. Jul. 2008 (CEST)

Worum geht es ?

Die Zahl der Möglichkeiten die 21 Vorgaben mit unterschiedlichen Ziffern auszufüllen kann wie folgt abgeschätzt werden: Für z1s2 in Q1 gibt es 9 Möglichkeiten. Für z3s2 und z3s3 in Q1 gibt es dann noch 8*7 Möglichkeiten. Für z2s4 in Q2 gibt es dann wieder 9 Möglichkeiten für z2s5 und z2s6 sind es dann 8 und 7 Möglichkeiten. Für z3s8 in Q3 sind es 7 Möglichkeiten (die Ziffern in z3s2, z3s3 entfallen). Dies liefert schließlich die obere Grenze (9*8*7)*(9*8*7)*(7) * (9*8) * (8*7*7) * (7) * (7) * (8*6*7) * (8*7*6*6) = 1.665.725.988.247.437.312, die ist erheblich kleiner als die vermeintliche Zahl möglicher Sudoku-Lösungen von 6.670.903.752.021.072.936.960. --88.68.114.214 13:40, 6. Jul. 2008 (CEST)

Gäbe es für jede der Vorgaben in den 21 Felder eine Lösung, wäre die Zahl der Lösungen mit Sicherheit kleiner als 1.665.725.988.247.437.312. Werden ausgehend von dem gegebenen Rätsel die Ziffer in den 21 Feldern vertauscht (etwa 1->2, 2->3, ... 9->1) gibt es natürlich weiterhin genau eine Lösung. Somit ergaben sich schon 9! Vorgaben mit genau einer Lösung. Im Allgemeinen ist schwer vorherzusagen, ob es mehrere oder gar keine Lösung mehr geben wird, falls andere Zahlen in die 21 Felder eingetragen werden. Wird etwa die 9 in Q1 (Z3s2) durch eine 7 ersetzt gibt es keine Lösung mehr. Dies ergibt sich aber erst, nach dem man beginnt eine Lösung zu suchen und irgendwann nicht mehr weiter kommt. --84.59.236.42 16:35, 6. Jul. 2008 (CEST)

Dieser Ed Russel schreibt sich wohl eher Ed Russell. Der Mann scheint ohnehin ziemlich unbekannt zu sein und die Behauptung über die vermeintliche Zahl der Lösungen ist unglaubhaft und auch nicht durch Quellen belegt. --88.68.117.41 14:27, 7. Jul. 2008 (CEST)

Die zweifelhafte Zahlenangabe des unbekannten Herrn Russell ist mittlerweile aus der englischsprachigen Wikipedia ganz verschwunden. Ich behaupte mal, die korrekte Zahl kennt niemand und liegt deutlich niedriger. Die umfangreiche Diskussion hier hat ja deutlich gemacht, dass es keine Weltformel gibt, um jedes Sudoku zu lösen. Es gibt auch keine allgemeine Formel, die es erlaubt zu entscheiden, ob ein Sudoku-Rätsel eindeutig lösbar ist, mehrere Lösungen besitzt oder unlösbar ist. Damit ist es natürlich auch nicht möglich zu bestimmen wieviele Lösungen es gibt. Die Zahl dürfte im Bereich von 1.665.725.988.247.437.312 liegen und kann allenfalls mit einem Supercomputer bestimmt werden. --84.59.224.69 18:15, 7. Jul. 2008 (CEST)

Uups, da habe ich doch etwas übersehen: en:Mathematics_of_Sudoku. --88.68.111.193 22:17, 8. Jul. 2008 (CEST)

Einfach nur zum Köpf schütteln was da alles steht ! Einfach berechenbar, ohne eine Unzahl an Fallunterscheidungen, ist nur die Zahl der Möglichkeiten, wenn alle Bedingungen (Spalten, Zeilen und Blöcke) weggelassen werden (9⁸¹) oder wenn nur Zeilen, nur Blöcke oder nur Spalten berücksichtigt werden ((9!) ⁹). Auch wenn nur Zeilen und Spalten berücksichtigt werden (lateinische Quadrate), ist die Sache praktisch nur noch für winzige Quadrate berechnenbar, jedenfalls ohne Computer. Die Zahlenangeben ab 49 Feldern sind praktisch nicht nachvollziehbar. Angeblich hat da irgend jemand in stundenlangen Berechnungen auf einem Supercomputer eine Zahl berechnet und der stauende Leser soll dies glauben. Nicht einmal der Algorithmus mit dem dies berechnet sein soll ist veröffentlicht. Aber angeblich gibt es da irgendwo einen Zweiten der genau die gleiche Zahl ausgerechnet haben will. Ich bin mir trotzdem sicher: Die Zahl der Möglichkeiten für das Standard-Sudoku ist viel kleiner als Felgenhauer behauptet, denn meine Schätzmethoden erweisen sich für die winzigen Quadrate, die auch mein Computer genau berechnen kann, als durchaus zutreffend. Es gibt offenbar eine Vielzahl von Rätseln mit 21 oder weniger Vorgaben, die eindeutig lösbar sind. Die Zahl aller Lösungen sollte daher kleiner 9²¹ etwa 10²⁰ sein. Sie ist wahrscheinlich noch wesentlich kleiner, in keinem Fall jedoch größer. --88.68.100.29 12:35, 10. Jul. 2008 (CEST)

Obere Grenze

Eine obere Grenze für die Anzahl der Lösungen kann abgeschätzt werden, wenn zunächst die Frage beantwortet wird, wieviele Möglichkeiten es gibt Q2 auszufüllen, falls Q1 bereits mit 9 Ziffern gefüllt ist. Dazu kann wiederum zuerst die Frage beantwortet werden wieviele Möglichkeiten es gibt, die Ziffern auf die drei Zeilen (z1,z2,z3) zu verteilen. Es gibt für je drei Ziffern jeweils zwei Möglichkeiten, insgesamt 8. Um die Ziffern in einer Zeile auf die Spalten zu verteilen gibt es je 6 Möglichkeiten. Es gibt daher (6*6*6 = 216)*8 Möglichkeiten. Analog überlegt man sich, dass es 8*8 Möglichkeiten gibt Q5 auszufüllen, wenn Q4 und Q2 bereits ausgefüllt sind. Sind Q1 und Q2 bereits gefüllt sind die Ziffern in Q3 bereits eindeutig auf die Zeilen verteilt. Es gibt daher noch 216 Möglichkeiten innerhalb der Zeilen zu tauschen. Es gibt 216*8 Möglichkeiten Q4 zu füllen, falls Q1 vorgegeben ist. Schließlich gibt es noch 8 Möglichkeiten für Q6, wenn Q3, Q4 und Q5 gefüllt sind. Diese Überlegungen führen schließlich zu folgender oberen Grenze (Q1 = 9!)*(Q2=216*8)*(Q3=216)*(Q4=216*8)*(Q5=64)*(Q6=8)*(Q7=216)*(Q8=8)*(Q9=1) = (9!)*216⁴*8⁶ = 2,07 * 10²⁰. --84.59.51.210 13:06, 14. Jul. 2008 (CEST)

Ich habe nochmal nachgedacht: Es handelt sich eigentlich nicht nur um eine obere Grenze sondern die Zahl der Möglichkeiten beträgt exakt 207.070.369.962.440.785.920 --88.68.107.179 22:51, 14. Jul. 2008 (CEST)

Wenn Q1, und Q2 vorgegeben sind, ist sofort klar wie sich die Ziffern in Q3 auf die Zeilen (z1,z2,z3) verteilen, denn es verbleiben ja nur jeweils diese drei Ziffern in der jeweiligen Zeile. Es scheint zunächst fraglich, ob die Ziffern auf Q1,Q2 so verteilt werden können, dass es gar nicht mehr möglich ist Q3 den Regeln entsprechend zu füllen. Dies ist jedoch nicht der Fall. Dazu betrachten wie einmal die Ziffern 1,2,3. Es gibt 6 Möglichkeiten diese in Q1 auf die Zeilen zu verteilen. Wie sie auf die Spalten verteilt werden braucht zunächst nicht zu interessieren. Egal wie die Ziffern auf die Zeilen verbleiben noch zwei Möglichkeiten diese Ziffern in Q2 und Q3 zu verteilen. Wird in Q2 eine dieser Möglichkeiten ausgewählt verbleibt noch eine Möglichkeit für Q3. Damit wird klar, es gibt genau 207.070.369.962.440.785.920 Möglichkeiten ein Sudoku (Standardvariante) mit Ziffern den Regeln entsprechend zu füllen. --84.59.227.6 12:06, 15. Jul. 2008 (CEST)

Wenn jedoch Q2,Q4 gefüllt sind kann es weniger 64 Möglichkeiten geben Q5 zu füllen. Dies wird am einfachsten klar, wenn man (2x2)- statt (3x3)-Blöcke betrachtet. Es handelt sich aber um eine obere Grenze. --84.59.142.81 09:21, 16. Jul. 2008 (CEST)

8 (CEST)

Ob obere Grenze oder exakte Zahl ist jedoch eher irrelevant. Bemerkenswert an der Sache ist ja vor allem, dass diese absurde Zahl von Felgenhauer sich über Jahre über Presse und Medien verbreitet hat ohne je ernsthaft angezweifelt zu werden, obgleich die Zahl offenbar weitgehend aus der Luft gegriffen ist. In dem Werk von Felgenhauer findet sich etwa die lapidare Feststellung.

It is known that the number of 9 × 9 Latin squares is 5524751496156892842531225600 5.525 × 10²⁷.

Zur Erklärung: Ein 9 × 9 Latin square ist nichts weiter als Sudoku ohne Berücksichtigung der (3x3)-Blöcke.

Auf dieser in keiner Weise belegten Aussage, die höchstwahrscheinlich auch falsch ist, soll die weitere Berechnung beruhen. Es wird dabei aber auch nicht wirklich klar, wie der Reduktionsfaktor durch die (3x3)-Blöcke berechnet wird. Diese Art der Argumentation erinnert mich stark an die Urknalltheorie. Da wird einfach vorausgesetzt, das Universum sei vor einigen Milliarden Jahren aus einem Punkt hervorgegangen, ohne das es dafür wirklich Beweise gäbe. Angeblich ließen sich mit dieser Theorie allerlei Dinge wie die Hintergrundstrahlung erklären, die weder eindeutig belegt sind noch plausibel aus der Urknalltheorie erklärt werden können. --84.59.235.3 11:08, 16. Jul. 2008 (CEST)

Pseudo-Mathematik

Was Felgenhauer, Jarvis als vermeintliche Mathematik verkaufen ist doch in Wahrheit nur Pseudo-Mathematik, zum Großteil schlicht falsch und natürlich völlig nutzlos. Die Zahl von 6,7 Trilliarden Lösungen ist nicht nachvollziehbar und höchst unplausibel, wie hier ja schon ausführlich dargelegt. Mit bedeutsam klingenden Begriffen, insbesonderer die Symmetrie betreffend, wird der Anschein einer wissenschaftlich begründeten Arbeit erweckt. Aus dem ganzen pseudowissenschaftlichen Ausführungen ergeben sich jedoch keine wirklich neuen Erkenntnisse. In der Presse wird dies Zeugs dennoch gerne unkritisch verbreitet.

Es gibt einige einfache Überlegungen, die jeder leicht nachvollziehen kann: Offensichtlich sind die 81 Felder beim Sudoku symmetrisch als Quadrat angeordnet. Die beiden Seitenhalbierenden und die Diagonalen sind Symmetrieachsen. Ferner ist das Quadrat symmetrisch unter Drehungen von 90, 180 oder 270 Grad. Es ist ferner ersichtlich, dass eine Lösung in eine weitere Lösung überführt wird, falls diese an den Achsen gespiegelt wird oder eine Drehung um 90, 180 oder 270 Grad durchgeführt wird. Neben diesen "Symmetrieoperation" können die Zeilen (1,2,3), (4,5,6) oder (7,8,9) beliebig vertauscht werden, um neue Lösungen zu erhalten. Gleiches gilt auch für die Spalten und die Vertauschung mehrerer Blöcke. Schließlich können auch die Ziffern für alle 81 Felder vertauscht werden. Es ist jedoch nicht möglich zu sagen, wie vielen unterschiedliche Lösungen aus einer Lösung hervorgehen, da verschiedene "Symmetrieoperation" zum gleichen Ergebnis führen können.

Darüber hinaus gibt es aber kaum wirkliche Erkenntnisse allgemeiner Art. Es ist unklar wie viele Lösungen es gibt, wieviele Vorgaben erforderlich sind, damit eine Sudoku eindeutig lösbar ist. Es gibt auch keine allgemeinen Regeln ein Rätsel zu lösen oder zu entscheiden, ob und wie viele Lösungen es gibt. Offensichtlich ist die ganze Theorie ziemlich nutzlos, weil damit nichts wirklich berechnet werden kann. Dies erinnert mich alles stark an die Allgemeine Relativitätstheorie. --84.59.233.36 13:32, 31. Jul. 2008 (CEST)

Warum Felgenhauers Zahl unglaubwürdig ist

Die Ergebnisse von Felgenhauer sind vollkommen unglaubhaft, weil die Zahlenangaben nicht zusammenpassen. Es gibt 9⁸¹ etwa 2*10⁷⁷ Möglichkeiten die Ziffern ohne Beachtung der Sudokuregeln in die 81 Felder einzutragen. Werden nur die Zeilen berücksichtigt sind es noch (9!)⁹ etwa 10⁵⁰ Möglichkeiten. Nach Felgenhauer wird diese Zahl noch einmal um mehr als 22 Größenordnungen reduziert, falls auch noch die Spalten betrachtet werden. Durch die Berücksichtigung der Blöcke wird jedoch nur noch eine Reduktion um nicht einmal 6 Größenordnungen erreicht. Dies erscheint absurd. Weiterhin spricht die Tatsache, dass es eindeutig lösbare Rätsel mit nur 17 Vorgaben gibt dafür, dass die Zahl in Wahrheit deutlich kleiner ist. --88.68.123.125 12:27, 21. Jul. 2008 (CEST)

In der Tat kann die Frage nach der Zahl der Lösungen nicht mit einer gigantischen Fallunterscheidung mittels eines Computers ermittelt werden. Im Prinzip könnten alle lateinischen Quadrate aufgelistet werden (auch wenn nicht ganz klar ist wie) und jeweils geprüft werden, ob diese auch die Bedingungen für die Blöcke erfüllen. Selbst wenn etliche Milliarden solcher Prüfungen in einer Sekunde durchgeführt werden könnten, selbst wenn je einige tausend Fälle auf "symmetrische" Fälle zurückgeführt werden könnten, wäre selbst ein Supercomputer dazu nicht in der Lage. --88.68.125.124 09:50, 24. Jul. 2008 (CEST)

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)

Eine Sekunde Laufzeit ist fuer einen Algorithmus, der auf einem aktuellen Computer (sagen wir mal 3 GHz, also 3 Milliarden Rechenoperationen pro Sekunde) ein Sudoku loest schon ziemlich langsam. Also liegt es an der unvorstellbaren Geschwindigkeit heutiger Computer, dass "1 Sekunde" und "langsam" sich auf den gleichen Algorithmus beziehen. :) 89.56.251.180 21:23, 25. Jun 2006 (CEST)

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)

Mir sind in den Druckwerken „Kronenzeitung“ und „Kurier“ schon mehrmals Sudokus verschiedener Schwierigkeitsgrade untergekommen, die eben nicht eindeutig lösbar sind, sondern zwei richtige Lösungen haben. Ein leichtes Beispiel aus der Krone, Vorwoche:

3..146...

..2...1.6

6178...34

.3....96.

1.6..3845

29.654...

..136..89

5.4.7.6..

9.34.12.7

Meine Lösung ohne die mehrdeutigen Teile:

359146728

842537196

6178..534

435718962

176..3845

298654371

721365489

584.7.613

963481257

Und jetzt versucht einmal, weiter zu behaupten, es könne nur eine einzige Lösung geben. --Franz Fuchs 11:35, 19. Okt. 2006 (CEST)

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)

Ähm - wieso sauer? --Eike 00:26, 9. Jan 2006 (CET)

Kein Grund sich hier gleich mit Diskussions-unfähigkeit zu disqualifizieren. Laut en:Sudoku hat Herr Eike recht. Somit stimme ich seiner anderen Behauptung auch zu. Lasst uns einfach auf eine mögliche Lösung einigen und die Diskussion vernünftig weiter führen. Wobei ich noch nicht den (linearen) Algorithmus gesehen habe der dies vollführt. (außer Dancing Links Algorithm von Donald Knuth) Kennt jemand einen? --Olliminatore 00:29, 6. Jan 2006 (CET)

Ich kann mir keinen vorstellen. --Eike 00:26, 9. Jan 2006 (CET)

Schaut euch doch mal den Anlgorithmus von B166ER an. (weiter unten). 15 Jahre alt, aber wesentlich schlauer als ihr alle zusammen.

Der Algorithmus ist - wenn ich die nicht sehr aufschlussreichen Erklärung richtig verstehe - nicht linear. Vielleicht hilft es ja doch was, Informatik zu studieren... --Eike 18:40, 9. Mai 2006 (CEST)

Ich finde, wie Novil Ariandis, die Beschreibung "suboptimal" falsch. Da Sudoku ein NP-vollständiges Problem ist (zu zeigen z.B. durch Reduktion auf Exact Cover), gibt es sehr wahrscheinlich keinen Algorithmus der asymptotisch besser ist als Backtracking. Die ganzen "Alternativen" die hier vorgeschlagen wurden (Dancing Links, Constraint Propagation) sind nur minimale Verfeinerungen von Backtracking und haben die gleiche exponentielle Worst-Case-Laufzeit wie Backtracking. Diese Verfahren sollten dann auch im Artikel Backtracking beschrieben sein. Wer hier aber behauptet Backtracking sei suboptimal, der hat das P/NP-Problem gelöst und sollte seinen Beweis veröffentlichen um die darauf ausgeschriebenen 1 Millionen Dollar zu kassieren. Falls also niemand Argumente dagegen einbringt werde ich die Aussage entfernen. -- Marc D. Migge 12:48, 12. Nov. 2006 (CET)

Ich wiederspreche. Backtracking ist sicher kein optimaler Lösungsweg, denn er sucht nur systematisch. Ein Sudoku-Algorithmus, der analytische Voruntersuchungen integriert ist sicher optimaler, aber sicher auch aufwendiger zu programmieren, als der Backtracking-Dreizeiler. Und deshalb ist die Formulierung "suboptimal" nicht falsch. Hier sollen Sudokus mit 9 x 9 Feldern gelöst werden und keine "asymptotischen" Probleme und schon gar keine "Problemklassen"! Dieses ist eine Artikel in einfacher Sprache über Sudokus. Ich halte den Artikel NP-Vollständigkeit für vollkommen unverständlich und selbstreferenziell. Schreibt den erst mal besser! --Matze12 02:09, 13. Nov. 2006 (CET)

Was den Artikel NP-Vollständigkeit angeht hast Du sicher recht. Das ändert aber nichts daran, dass die von Dir falsch als "optimaler" bezeichneten Verfahren mit "analytischer Vorinformation" sich letztendlich genauso verhalten wie Backtracking. Wie ich schon oben geschrieben habe sind das nämlich nur Varianten von Backtracking die bei einigen wenigen Sudokus schneller sein mögen, sich bei "schweren" Sudokus aber 100% genauso wie stinknormales Backtracking verhalten. Es ist und bleibt also letztendlich Backtracking und Backtracking ist damit nach aktuellem Stand der Forschung optimal. Also gehört das "suboptimal" raus und die Varianten mit "analytischer Vorinformation" in den Artikel Backtracking (wo sie leider noch nicht stehen bzw. nur mit dem recht Abstrakten Begriff Heuristiken erwähnt werden). Die Varianten sind nämlich keineswegs Sudoku-spezifisch. Wenn Du anderer Meinung bist skizziere hier doch mal umgangssprachlich einen Algorithmus mit "analytischer Vorinformation" der besser sein soll als Backtracking. -- Marc D. Migge 23:24, 17. Nov. 2006 (CET)

Dein letztes Beispiel ist zwar uneindeutig aber dafür ganz "eindeutig" zweideutig lösbar und somit überschaubar. Die Endlösung wird durch Wahl aus zwei alternativen (Zahl 2 oder 9) und dann in jedem Fall erreicht.--Wikipit 15:32, 1. Aug. 2008 (CEST)

andere Meinung zur Möglichkeiten-Anzahl

Meiner Meinung nach gibt es für die 1. Zeile oder Spalte, Kästen kann man ignorieren 9 Möglichkeiten, so viele wie es überhaupt nur gibt. Für die Zweite fällt diese nun weg, bleiben also 8, dann 7, dann 6. also 9*8*7*6*5*4*3*2*1 = 362880 oder ich verstehe nicht woher die anderen Variablen kommen, geben die Zeilen nicht schon alles vor, den gewisse Spielraum rechne ich ja mit!?

Ja klar,gibt es 9*8*7*6*5*4*3*2*1 = 9! Möglichkeiten eine Zeile, eine Spalte oder einen Block zu füllen, ohne eine Ziffer mehrfach zu benutzen. Danach sind aber noch 8 Zeilen leer. Es gäbe daher insgesamt (9!)⁹ Möglichkeiten alle Zeilen zu füllen, wenn es nicht die zusätzlichen Bedingungen gäbe, dass die Ziffern auch in jeder Spalte und in jedem Block nur einmal vorkommen dürfen. Durch die Bedingung für jede Zeille, dass jede Ziffer einmal vorkommt, reduzieren sich die Zahl der Möglichkeiten von 9⁹ auf 9! etwa um einen Faktor tausend. Wäre es für jede Einheit (Zeile, Spalte und Block) je ein Faktor tausend, ergäbe sich insgesamt einen Faktor 10⁸¹ und es würden gar keine Lösungen mehr übrig bleiben. Da jedoch ausgehend von einer Lösung insgesamt 9! Lösungen, die durch Vertauschung der Ziffern entstehen und etwa eine Million Vertauschungen von Zeilen, Spalten und Blöcken sind möglich, die neue Lösungen aus einer vorgegebenen erzeugen, gibt es sicherlich mehr Lösungen. Aber höchst wahrscheinlich auch weit weniger als Felgenhauer berechnet hat. --84.59.236.116 15:07, 22. Aug. 2008 (CEST)

Lesenswert-Diskussion: 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: Der Abschnitt "Anleitung" unter "Globale Paarsuche" wirkt wie ein Fremdkörper. Vorallem wegen des "Du". --Hfst 14:49, 26. Aug. 2008 (CEST)

 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)

Wikipedia und Wikibooks

Wenn ich mir den Wikipediaartikel und das Sudoku-Wikibook anschaue, dann passt das nicht zusammen. Der Wikipediaartikel ist umfangreicher und besser als das Buch. Für eine bessere Aufteilung würde ich

• Die Abschnitte 1-4 beibehalten
• Den Abschnitt 5 in Wikipedia straffen und die Langfassung (besser gegliedert ins Wikibook)
• Abschnitt 6 kann m.E. im Wikipedia komplett entfallen und ins Buch
• Abschnitt 7 gestrafft ins Wikipedia und ausführlich ins Buch
• Abschnitt 8-11 bleiben

--Hfst 17:09, 27. Aug. 2008 (CEST)

Dem kann ich mir nur anschließen. Vor allem das Kapitel 5.2 (Globale Paarsuche) hat m. E. im Wikipediaartikel nichts verloren. -- Clemfix 18:37, 27. Aug. 2008 (CEST)

---

An sich ein richtiger Gedanke - ich denke aber das eigentliche Problem ist ein Wikipedia-typisches:

• Die Wahrnehmung von Wikibook und all den anderen Projekten ist stark unterentwickelt. So unterentwickelt, das es in 99% aller Artikel noch nicht einmal einen Hinweis, Link o.ä. zu diesen anderen Projekten gibt (obwohl es sehr oft passt). D.h. die Wahrnehmung ist noch nicht einmal bei den Schreibern, geschweige denn bei den Lesern da.
• Globale Paarsuche (GPS) u.a. in Wikibook zu verschieben würde diesen Teil des Artikel völlig aus der Wahrnehmung entfernen - ein Todesstoß! Dann kann man auch gleich über die Löschung abstimmen.
• Wer sich den Wikibook-Artikel ansieht (HIER), erkennt man, das auf den, der den Artikel übertragen will, sehr viel Arbeit wartet. GPS hat ein anderes Erklärungskonzept, Beispieldesign und Zielgruppenansprache als Wikibook.
• Wer sich Wikibook in der History ansieht, merkt, das vor über einem Jahr die letzte Änderung erfolgte; während hier in Wikipedia sozusagen "der Bär steppt". Wer will eine Arbeit tun, die keinen interessiert?

---

Mein Gegenvorschlag:
Wie wäre es mit 2 Lemma?:

• Sudoku
• Sudoku - Lösungsmethoden

Eine Realisierung ist sehr unkompliziert. Nur im Einleitungstext müßte jeweils auf den anderen Artikel verwiesen werden. Vielleicht noch ein paar Wikilinks und fertig. -- Friedrich Graf 19:28, 27. Aug. 2008 (CEST)

Sudoku gleich mathematisches Rätsel ?

Ich habe ein paar Artikel, in denen es um Sudokus geht gelesen. Leider ist mir dabei folgendes aufgefallen:

In diesem Artikel: http://de.wikipedia.org/wiki/Mathematisches_R%C3%A4tsel heißt es Sudoku sei ein mathematisches Rätsel..

Und in diesem: http://de.wikipedia.org/wiki/Negativraster heißt es Sudoku sei kein mathematisches Rätsel..

Klar wurden beide Artikel von verschiedenen Autoren geschrieben, klar ist auch, dass es bestimmt Ansichtssache ist, ob es sich um ein solches handelt oder nicht. Trotzdem denke ich, sollten 2 Artikel nicht gegensätzliches enthalten.

MfG Marc

Was denkst Du selber? Hat das Ganze nichts mit Gleichungen zu tun? (Das hier Zahlen=Ziffern verwendet werden, ist hingegen keine Begründung, weil man auch andere Zeichen nehmen könnte)--Wikipit

Laut Definition (Wikipedia): "Für Mathematik gibt es keine allgemein anerkannte Definition; heute wird sie üblicherweise als eine Wissenschaft, die selbst geschaffene abstrakte Strukturen auf ihre Eigenschaften und Muster untersucht, beschrieben."
Nach dieser Definition ist Sudoku ein mathematisches Rätsel.

... wichtiger aber als die Festlegung wäre mir die Vereinheitlichung in den Wikipedia-Definitionen. -- Friedrich Graf 23:14, 28. Aug. 2008 (CEST)

Ob mathematisch oder nicht: ist Sudoku ein Rätsel? --Hfst 12:46, 29. Aug. 2008 (CEST)

Für alle Witzbolde:
Laut Wikipedia: "Unter Rätsel versteht man eine Aufgabe, die durch Denken gelöst werden muss." Wird Sudoku nicht durch denken ermittelt? ;-)
-- Friedrich Graf 09:09, 30. Aug. 2008 (CEST)

Pittiplatsch:"...dann ist Regieren ja auch ein Rätsel?"--Wikipit

Schnatterinchen: "...aber Pitti, regieren ist doch keine Aufgabe, nak, nak!" -- Friedrich Graf 09:43, 30. Aug. 2008 (CEST)

Bitte um Archivablage

Ich habe alle Diskussionsthemen, die ausschließlich 2005 und 2006 geschrieben wurden sortiert. Könnte jemand mit Ahnung daraus bitte eine 2. Seite, eine Ablage, oder ein Archiv machen? Sonst ist man bei der Diskussion mehr mit suchen als mit Diskutieren beschäftigt. Danke. -- Friedrich Graf 20:25, 27. Aug. 2008 (CEST)

Dank Hilfe ist es erledigt. -- Friedrich Graf 09:42, 30. Aug. 2008 (CEST)

Ich hab das gerade repariert. Bitte verschieb nie wieder eine Diskussionsseite in den Artikelnamensraum. Die gehören nur in den Diskussionsnamensraum. Ich hab eine Autoarchivierung aktiviert, die das ab jetzt erledigt und auch an den richtigen Ort verschiebt. Details zum richtigen Archivieren findest du unter Hilfe:Archivieren. Falls du Probleme hast, frag beim nächsten Mal bitte. -- Cecil 04:14, 31. Aug. 2008 (CEST)

Ich hatte gefragt: Hier, aber vermutlich irgend etwas falsch verstanden. Am liebsten wäre es mir, das ich beim nächsten Mal nach getaner Arbeit jemand raufsehen lassen könnte. Wen fragt man da? -- Friedrich Graf 10:32, 31. Aug. 2008 (CEST)

6.670.903.752.021.072.936.960

Dieser Unsinn ist wohl nicht aus der Welt zu schaffen. Bereits mit 17 ausgefüllten Feldern gibt es eindeutig lösbare Rätsel. Es auch nicht ausgeschlossen, dass es solche mit nur 16 oder 15 gibt. Es gibt jedenfalls solche Rätsel mit 16 Vorgaben, die nur 2 Lösungen haben. Gäbe es bei 17 ausgefüllten Feldern im Mittel 1000 Lösungen, gäbe es deutlich weniger als 1000 mal 9¹⁷ = 16.677.181.699.666.569.000 Lösungen. Denn es gibt genau 9¹⁷ Möglichkeiten in 17 Felder die Ziffern 1 bis 9 einzutragen, ohne dabei die Sudokuregeln zu beachten. Die meisten davon verletzen aber die Regeln, da in einer Zeile, einer Spalte oder einem Block eine Ziffer mehrfach auftaucht. Auch die Vorgaben, die nicht unmittelbar die Regeln verletzen, müssen keine Lösung mit 81 ausgefüllten Feldern besitzen. Es lässt sich auch zeigen, dass es genau (56*216²)²*(9*8*7*6*5*4*3*2*1) = 2.477.160.187.538.964.480 Möglichkeiten gibt in die fünf Blöcke mit 45 Feldern ohne die 4 Blöcke in den Ecken, die Ziffern unter Beachtung der Regeln einzutragen. Dabei gibt es aber in der Regel keine Möglichkeit mehr die übrigen 36 Felder auch noch auszufüllen. Selbst sehr leichte Sudoku-Rätsel haben meist deutlich weniger als 45 Vorgaben. Mit an Sicherheit grenzender Wahrscheinlichkeit gibt es weniger als 6.670.903.752.021.072.936.960 Möglichkeiten die 81 Felder den Regeln entsprechend auszufüllen. --84.59.238.202 19:27, 14. Okt. 2008 (CEST)

Da wundert es nicht, dass auch die CKM-Matrix nicht aus der Welt zu schaffen ist. Da gibt sogar haufenweise Nobelpreise dafür. --84.59.238.202 19:39, 14. Okt. 2008 (CEST)

-- Zitat:

Es gibt 6.670.903.752.021.072.936.960 verschiedene (vollständig ausgefüllte) Standard-Sudokus.

-- Zitat Ende

Wenn jeder Mensch eine Milliarde Sudokus ausfüllt – das reicht nicht! --84.59.43.25 22:50, 14. Okt. 2008 (CEST)

Erfinder

Liebe Autoren,

in der Einleitung steht Das Rätsel wurde vom Schweizer Leonhard Euler (1707−1783) erfunden. Ich kann das aber nicht glauben, zumal im englischsprachigen Artikel Leonhard Euler is sometimes incorrectly cited as the source of the puzzle, based on his related work with Latin squares.[1] steht, dort sogar - zumindest formal - mit Quelle (in der nicht explizit steht, dass es nicht von ihm erfunden wurde). Ohne Quelle sollte das hier so nicht stehen bleiben, meine ich. Oder sollte ich einfach mal heimlich in Carl Friedrich Gauß hinschreiben? Herzliche Grüße --Peu 14:33, 28. Nov. 2008 (CET)

Hab's dann mal geändert. --Peu 09:11, 2. Dez. 2008 (CET)

Hauptbeispiel entspricht nicht ganz der Lösung

Einige Felder im Beispiel-Sudoku sind in der Lösung schon vorgegeben, während sie in der unausgefüllten Variante leer sind.

Kann jemand die .svg-Grafiken entsprächend anpassen? --Loilo92 14:53, 10. Feb. 2009 (CET)

1. Es ist keine svg-Grafik.
2. Es sollte nur die Logikregel erklärt werden, indem alles (für die Erklärung) Unnötige weggelassen wurde. Würde das Muster den Anspruch auf komplette Vollständigkeit haben, würde es unübersichtlich werden.

BG -- Friedrich Graf 15:29, 10. Feb. 2009 (CET)

->Friedrich, Loilo92 meint das Beispiel oben auf der Seite, nicht Deine Bilder zu GPS und hat Recht. Ich habe bei meiner letzten überarbeitung ältere Fehler wieder reingabaut. Nun habe ich es korrigiert.
->Loilo92: Danke für Deine Aufmerksamkeit.--Wikipit 16:28, 10. Feb. 2009 (CET)

6.670.903.752.021.072.936.960

Die Zahl ist doch vollkommen aus der Luft gegriffen. Die wahre Zahl ist zweifellos kleiner. Es gibt schließlich Rätsel mit 17 Vorgaben, die eindeutig lösbar sind. Tatsächlich gibt es sehr viele solcher Rätsel und zwar nicht nur solche, die durch "Spiegeln" aus einander hervorgehen. Es gibt sogar Rätsel mit nur 16 Vorgaben, die lediglich zwei Lösungen besitzen. Werden an 17 vorgegebenen Position die Ziffern 1 bis 9 ohne Beachtung der Sudoku-Regeln eingetragen, gibt es dafür 9¹⁷ oder 16.677.181.699.666.569 Möglichkeiten. Die meisten davon verletzen offensichtlich die Regeln, weil in einer Zeile, Spalte oder einem Block Ziffern mehrfach auftreten. Für andere gibt es keine Lösungen, obgleich die Regeln nicht unmittelbar verletzt sind. Für einige gibt es genau eine Lösung, für andere mehrere, eventuell bis zu tausend Lösungen. Selbst wenn es im Mittel 100.000 Lösungen wären, ergäben sich noch weniger als 6.670.903.752.021.072.936.960 Lösungen. --88.68.110.183 15:05, 10. Feb. 2009 (CET)

Es gibt 9! = 9*8*7*6*5*4*3*2*1 = 362.880 Möglichkeiten in einer Zeile, Spalte oder einem 3x3-Block verschiedene Ziffern einzutragen. Es gibt etwa tausend mal so viele Möglichkeiten die Ziffern einzutragen, wenn sie nicht paarweise verschieden sein müssen. In alle 81 Felder könnten ohne Beachtung der Regeln 9^81 etwa 2*10^77 Möglichkeiten eine der neun Ziffern einzutragen. Wenn die Ziffern in jeder Zeile verschieden sein müssen reduziert sich die Zahl auf (9!)^9, etwa 10^50. Müssen auch die Ziffern in jeder Spalte verschieden sein, kann die Zahl der Möglichkeiten nicht mehr einfach berechnet werden. Die Zahl der Möglichkeiten reduziert sich zwar ebenfalls etwa um einen Faktor tausend, im Vergleich zum Fall ohne Randbedingungen, es ist aber zu berücksichtigen, dass durch die Bedingung für die Zeilen etlich Fälle bereists ausgeschlossen wurden, die nicht noch einmal berücksichtigt werden dürfen. Laut en:latin square gibt es für 9x9 Felder (9!)(8!)* 377.597.570.964.258.816 etwa 5,5*10^27 Möglichkeiten für unterschiedlichen Ziffern in jeder Spalte und Zeile. Die durchschnittliche Reduktion pro Spalte ist somit deutlich kleiner als tausend aber immer noch deutlich größer als hundert. Läge der durchschnittliche Faktor bei Hinzunahme der neun 3x3-Blöcke je Block noch bei 10 ergeben sich nur noch 5,5*10^18. Selbst wenn dieser Faktor nur bei 5 läge ergeben sich noch weniger als 6,7*10^21 Möglichkeiten. Die Zahl ist daher zweifellos zu hoch gegriffen. --84.59.225.179 13:48, 1. Mär. 2009 (CET)

Meine Vermutung

Ein Mini-Sudoku mit vier 2x2-Blöcken hat nur 288 Lösungen, was weniger, genau die Hälfte nämlich, als (4!)^2 = 576 ist. Dies lässt führt zu der Vermutung, dass analog beim 9x9-Sudoku es weniger als (9!)^3 Lösungen gibt. Ich behaupte mal:

Es gibt genau (9!)^3/3 =  15.928.241.946.624.000 Lösungen. 

So, jetzt beweisst mir mal das Gegenteil! --88.153.114.161 10:54, 6. Mär. 2009 (CET)

Lösbarkeit

gibt es eine möglichkeit fest zu stellen ob ein sudoku eindeutig lösbar ist? (nicht signierter Beitrag von 88.74.17.115 (Diskussion) )

Datei:MinimalSudoku.jpg

Eindeutig lösbar

Es gibt offenbar keine einfache Methode, eine einfache Regel, nach der dies zu entscheiden wäre. Die Frage nach einer eindeutigen Lösung kann nur beantwortet werden, wenn die Lösung nach den diversen Verfahren, die im Artikel teilweise beschrieben sind, bestimmt wird. Sonst wäre die Lösung eines Sudokus auch einfach. Setze Feld für Feld in jedes der freien Felder die testweise Ziffern 1-9 ein. Für jedes Feld solange bis sich durch Einsetzen eine eindeutige Lösung ergibt. Aber so geht das nicht, sonder nur etwas mühsamer. In dem Beispiel folgt, dass (5,9) im Block unten in der Mitte nur oben rechts stehen kann. Die 5 ganz oben rechts und darunter die 9. Die 1 kann im Block in der Mitte am rechten Rand nur rechts in der Mitte stehen. Nach dem Einsetzen dieser 1 verbleibt im Block in der Mitte nur das Feld oben rechts für die 1. Nach dem Einsetzen bleibt für die 8 im gleichen Block nur noch das Feld unten rechts. Jetzt hat die 8 im Block rechts in der Mitte nur noch oben in der Mitte Platz, dann die 9 darunter, … Schließlich zeigt sich, die Lösung ist tatsächlich eindeutig. Aber das sieht man erst zum Schluss, wesentlich abkürzen geht nicht. --84.59.249.209 20:00, 1. Mär. 2009 (CET)

Eine interessante Frage.
Erstmal vorneweg: Sudokus müssen, um S. heißen zu dürfen, eine eindeutige Lösung haben. Aber ich habe die Frage so verstanden, ob man im Nachhinein so eine Art "Quersumme" suchen kann, um zu sehen "ja, alles eindeutig".
Tja: es gibt Computerprogramme, die Sudokus erstellen. Aber alle sind letztlich nur schnelle Rechenknechte (d.h. je Variante wird durchprobiert, bis die gewünschte Lösung gefunden wurde). D.h.: keine "Quersumme".
Da ich die Frage auch nicht beantworten kann, frage ich mich: "Wie kann man die Zahl der Lösungsmöglichkeiten errechnen?" - vielleicht steckt hier der Ansatz für eine Lösung drin.
Wie gesagt: interessante Frage. -- Friedrich Graf 22:10, 1. Mär. 2009 (CET)

na die anzahl der möglichkeiten zu berechen ist ja wohl schwieriger als fest zu stellen ob es nur eine lösung gibt

Jedensfalls dann, wenn es Millionen oder noch viel mehr mögliche Lösungen gibt. --88.68.106.234 09:23, 2. Mär. 2009 (CET)

hm heißt das es gibt keine Möglichkeit ein nicht eindeutiges sudoku zu lösen außer duch backtracken? und gibt es eine weg festzustellen ob ein sudoku überhaubt lösbar ist?

Es gibt jedenfalls nirgends eine nachvollziehbare Erklärung wie ein beliebiges Sudoku zu lösen ist und entsprechend auch keine allgemeine Theorie des Sudoku, um zu entscheiden wie viele Lösungen es gibt 0, 1, 2, 3, … Die Behauptung es gäbe genau 6.7xx. … Lösungen für ein leeres Sudoku ist daher unglaubhaft und tatsächlich völlig aus der Luft gegriffen. --88.68.106.234 09:23, 2. Mär. 2009 (CET)

na ja wenn einen das genauer interresirt kann man schon bestimmen wie viele lösungen ein bestimtes (auch ein lehres) sudoku hat. man muss einfach alle finden indem mal die bekannten algorithmen anwendet um alle lösungen zu suchen. Außerdem kann ich weder beweisen, noch wiederlegen, dass es eine möglichkeit gibt dies schneller zu tun. allerdings gehe ich davon aus.

Bei 6.670.903.752.021.072.936.960 Lösungen können diese in tausend Jahren nicht bestimmt werden, wenn pro Sekunde eine Milliarde berechnet werden könnten. --88.153.114.161 23:44, 2. Mär. 2009 (CET)

Eine interessante Frage. Erstmal vorneweg: Sudokus müssen, um S. heißen zu dürfen, eine eindeutige Lösung haben. Aber ich habe die Frage so verstanden, ob man im Nachhinein so eine Art "Quersumme" suchen kann, um zu sehen "ja, alles eindeutig".

Nein ein sudoku kann auch 2 lösungen haben --88.74.17.115 2. Mär. 2009 (CET)

Sicher? -- Friedrich Graf 19:15, 2. Mär. 2009 (CET)

Das ist doch ein Streit um des Kaisers Bart. Für jeden "Endnutzer" muß eine Sudoku-Aufgabe (eine?) zwingend eindeutige Lösung haben. Gut, zwei "spiegelbild"liche Lösungen wären für die Spezis ebenfalls unproblematisch denkbar. Aber mehr als diese, da wäre die Aufgabenstellung nicht vollendet, sondern noch in der Konstruktionsfrage stehengeblieben. Wenn man an die Frage der "möglichen" Lösungen auf einem leeren Feld rangeht, dann ist diese theoretische Aufgabe der maximalen Zahl der Möglichkeiten zwar für Mathematiker eine interessante Fragestellung, aber keineswegs für "Endnutzer". Analog geht es doch bei andern Spielen auch so zu, bei Mühle, bei Dame oder Schach (Backgammon kenne ich nicht mal in Anfängen, leider). Auch hier gibt es abertausend Varianten. Eine "ideale" Schach"aufgabe" sieht "zwingende" Lösungen vor, gut, nicht immer bezüglich des Wegs, dann aber bezüglich der Zugzahl. Beim Schach kann man ebenfalls eine "Mittel- oder Endspielstellung" "analysieren", nur in der konkreten "Schachaufgabe" geht es dann um eine Lösung und nicht um Bewertungen usw.--Wikipit 22:13, 2. Mär. 2009 (CET)

A) ... richtig, Wikipit. Die Frage nach der Menge der Lösungsmöglichkeiten ist für Statistiker sicherlich interessant. Aber für die Frage "kann man feststellen, ob ein Sudoku eindeutig lösbar ist" sicherlich zweitrangig.
B) ... nach meinem "Gefühl" geantwortet: "JA" (es gibt eine Möglichkeit). Denn: ein Sudoku hat ein inneres Muster, eine innere Struktur. Diese Struktur für uns Normalsterbliche nur schwer zu sehen. Daher "raten" und "rätseln" bzw. "probieren" wir die Lösung zu finden. Aber: schau dir die GPS-Methode an: sie vereinfacht die Mustererkennung. Wer diese Methode "verinnerlicht" findet leichter die innere Struktur des Sudokus. Hier setzt mein "Gefühl" an: vermutlich gibt es eine Methode, die innere Struktur eines Sudokus schneller zu "knacken". -- Friedrich Graf 07:25, 3. Mär. 2009 (CET)

Also, nach meinem Gefühl kann jeder normal intelligente Mensch mit etwas Übung praktisch jedes eindeutig lösbare Sudoku mit der Zeit lösen und auch feststellen, ob die Lösung tatsächlich eindeutig ist. Ich habe bisher noch fast jedes Sudoku lösen können. Wer beim Sudoku auf gut Glück Ziffern einsetzt, obgleich auch andere Ziffern nicht auszuschließen sind, wird selten Erfolg haben. Nur wenn es nicht anders geht, wird ein erfahrener Spieler spekulieren und zuvor nach eindeutigen Ziffern suchen. Neue Sudokus zu konstruieren ist übrigens auch ohne Computer nicht wirklich schwer. Als Ausgangspunkt kann ein fertig ausgefülltes oder ein leichtes Sudoku mit vielen Vorgaben dienen. Von diesem Sudoku können schrittweise einzelne Vorgaben entfernt werden, wenn diese aus den übrigen eindeutig erschlossen werden können. Von einem Sudoku können viele Millionen weitere durch Spiegeln, Drehen oder Vertauschen von Ziffern gewonnen werden. Aus einem schweren Sudoku kann natürlich ein leichteres gemacht werden, indem einige Ziffern der Lösung zusätzlich vorgegeben werden. --88.153.114.161 11:45, 3. Mär. 2009 (CET)

Dem widerspreche ich aus vielerlei Gründen:
1. Was ist ein normal intelligenter Mensch? Wo liegt da die Norm?
2. Auch wenn sich das Sudoku zwingend lösen läßt, bedeutet dies nicht, daß auf einem anderem Weg nicht auch eine Lösung herausgekommen wäre. Hier besteht eine echt theoretische Fragestellung, woran man die Eindeutigkeit beweisen kann.

Bei vielen leichten Sudokus lässt sich immer ein leeres Feld finden, das eindeutig mit einer Ziffer belegt werden kann. Ist das Rätsel mit dieser Methode vollständig gelöst, ist damit auch gezeigt, dass die Lösung eindeutig ist. Manchmal ist es auch nötig Ziffern auf gut Glück einzusetzen. In diesem Fall wird der Rätselfreund am Ende nicht prüfen, ob er das Rätsel auch mit einer anderen Spekulation hätte lösen können. Er weiß schließlich, dass er nur eine Lösung gibt, die er schon gefunden hat. Im Prinzip könnte er aber auch nachprüfen, dass es mit der anderen Wahl nicht aufgeht. --88.153.114.161 18:37, 3. Mär. 2009 (CET)

3. Mit ich habe... kann man gar nicht beweisen.
4. Ziffern auf "Gut Glück" eintragen und überprüfen, ob es geht, sonst zurück (sogenanntes backtracking) ist theoretisch unanfechtbar eine korrekte Methode, auch wenn sie nicht die Herzen der Sudokufans höher schlagen läßt und fast nichts mit Intelligenz zut tun hat. Ist wie der Ariadnefaden im Labyrinth.

Genau, um die Eindeutigkeit auch bei schweren Sudokus zu lösen, muss der Rätselfreund sich merken, wenn er eine nicht unmittelbar eindeutige Ziffer einsetzt. Falls es am Ende nicht aufgeht, muss er quasi entlang des Ariadnefaden, seinen Notizen, wieder zurück und die nächste Ziffer testen.

5. Jeder Spieler spekuliert. Jeder Denker spekuliert (wrtl. korrekt), daran ist gar nichts auszusetzen. Fraglich ist nur, ob man eine Regel oder Gesetzmäßigkeit erkennen kann oder müßte oder gar erkannte.
6. Da jedes Sudoku von einer einheitlichen Grundfläche mit vorgegebenen Regeln ausgeht, sind Verwandtschaften nicht ausgeschlossen. Irgendwie ist ja auch jedes Regelschachspiel untereinander verwandt, nämlich Schach. Aber es gibt Klassifikationen. Das kann ich mir beim Sudoku auch vorstellen.
7. Aus Rückentwicklung von einem leichten ein schweres durch Ziffernrücknahme zu erzeugen, scheitert an der Tatsache, daß irgendwann dann keine eindeutige und zwingende Lösung mehr resultiert, was aber eine Hauptregel einer Aufgabe sein sollte. Sonst könnte man ja mit weniger als 17 Zahlen auskommen...--Wikipit 17:11, 3. Mär. 2009 (CET)

Klar, irgendwann ist das Rätsel minimal, das heißt, die Lösung ist nicht mehr eindeutig, wenn eine vorgegebene Ziffer entfernt wird. Ich vermute das Beispiel mit 17 Vorgaben ist in diesem Sinne minimal. Dies ist aber nicht wirklich leicht zu überprüfen. Ich vermute minmale Rätsel haben selten mehr als 21 Vorgaben. Wenn die Zahl 6.7xx.… stimmt, dann muss es aber auch welche mit 23 Vorgaben geben. Ich kenne aber keine solchen. --88.153.114.161 18:37, 3. Mär. 2009 (CET)

Minimale Rätsel mit mehr als 23 Vorgaben herzustellen, ist so schwer nicht. Das folgende Rätsel hat z. B. 24 Vorbelegungen:

7 0 0  0 0 0  1 0 0

0 0 5  0 7 0  0 8 0

0 2 0  0 0 5  0 0 0

0 0 2  5 0 0  0 0 0

0 4 0  0 2 0  8 7 3

0 0 3  1 0 0  0 6 0

0 0 0  8 0 0  3 2 1

0 1 0  6 0 0  0 0 4

0 0 0  0 0 0  0 0 0

BTW: Das Programm pi-c-it Sudoku (http://sudoku.pi-c-it.de) kann minimale Probleme erzeugen. Und wenn man das lange genug rechnen läßt, findet das sicher auch noch Probleme mit mehr Vorbelegungen. Clemfix 20:55, 3. Mär. 2009 (CET)

Wird mir zu schwierig

7 3 9   2 X X   1 4 5

4 8 5   3 7 1   2 8 6

1 2 6   4 8 5   9 3 7

0 0 2   5 0 0   4 1 9

5 4 1   9 2 6   8 7 3

0 0 3   1 0 0   5 6 2

0 0 7   8 0 0   3 2 1

0 1 8   6 0 0   7 0 4

0 0 4   7 1 0   6 0 8

Zunächst die 5 in der mittleren Zeile. Die kann nur ganz links stehen. Dann hat die 1 in der gleichen Zeile nur rechts im Block links in der Mitte Platz. Jetzt ist klar wo die 6 und dann auch wo die 9 in der mittleren Zeile liegen. Für die eins im Block rechts in der Mitte gibt es auch nur ein Platz in der Mitte über der 7. In der Spalte ganz rechts liegt die 8 ganz unten. 7 und 6 haben dann im unteren Block nur links unten Platz. Die 4 im Block rechts in der Mitte liegt in der linken Spalte (oben oder unten). Damit liegen (3,4) im Block oben rechts in der mittleren Spalte. die 5 liegt im Block unten rechts in der mittleren Spalte und daher im Block oben rechts ganz rechts oben … Das Rätsel kann damit erst einmal soweit hier eingetragen ohne viel zu spekulieren gefüllt werden. Dann habe ich mal angenommen in Zeile 1 und Spalte 8 wäre die 4. Dann geht es nicht auf. Bei XX im Block oben in der Mitte kann keine 9 eingetragen werden.

Ist das minimale Rätsel mit 24 wirklich eindeutig lösbar? Ehrlich gesagt, ohne Computer ist mir das auf die Schnelle zu schwer. Wenn aber tatsächlich minimale Rätsel meist 24 (vielleicht mit wenigen Ausnahmen auch 25 oder 26) Vorgaben haben spricht dies sehr dafür, dass die Zahl der Lösungen kleiner 6.7xx. … ist. Es gibt viel weniger nämlich (9!)^3 etwa 4,8*10^16 Möglichkeiten drei in einer Diagonale liegende 3x3-Blöcke zu füllen. Lässt man je eine Vorgabe pro Block weg, die sich ja eindeutig ergibt, sind dies 24 Vorgaben. --88.153.114.161 14:14, 5. Mär. 2009 (CET)

Lieber junger Freund, die WP soll eine Enzyklopädie sein und keine Rätselzeitschrift mit Leserbrief. Um aber Deine Anfrage abzukürzen:
1. Hast Du schon mit Zeile 1 Spalte 8 Zahl 3 versucht?
2. Deine Aufgabenstellung beinhaltet eine Reihe unnötiger Vorgabezahlen, die sich bereits in einem früheren Zeitpunk als entbehrlich erweisen. Wenn Du den Text dieser Diskussion und des Artikels studiert hast, kannst Du erkennen, daß man von mindestens 17 Zahlen ausgeht, nicht von 24, so daß Deine Überlegung zur Anzahl von Lösungen von einer falschen Prämisse ausgeht.--Wikipit 10:40, 6. Mär. 2009 (CET)

Du schon mit Zeile 1 Spalte 8 Zahl 3 versucht?

7 0 4   2 0 0   1 3 5

0 0 5   4 7 0   2 8 6

0 2 0   3 0 5   9 4 7

0 0 2   5 0 0   4 1 9

5 4 1   9 2 6   8 7 3

0 0 3   1 0 0   5 6 2

0 0 7   8 0 0   3 2 1

0 1 0   6 0 0   7 0 4

0 0 0   7 0 0   6 0 8

Ok, soweit ist die Sache ziemlich klar. Jetzt muss wieder spekuliert werden. Ich nehme mal an Spalte 1, Zeile 2 ist 3.

7 0 4   2 9 8   1 3 5

3 0 5   4 7 1   2 8 6

1 2 8   3 6 5   9 4 7

0 0 2   5 3 0   4 1 9

5 4 1   9 2 6   8 7 3

0 0 3   1 0 0   5 6 2

0 5 7   8 4 9   3 2 1

8 1 X   6 5 3   7 9 4

0 3 0   7 1 2   6 5 8

Das geht scheinbar nicht auf, die 2 kann in das Feld X nicht eingetragen werden. --88.153.114.161 12:08, 6. Mär. 2009 (CET)

Nein, die 183 (Zeile-Spalte-Zahl) ist die (!) Lösung (aus nur zwei Möglichkeiten), dann braucht nichts mehr spekuliert zu werden. Wenn Du natürlich falsche weitere Schlüsse ziehst, kommst Du nicht zur Lösung.--Wikipit 12:13, 6. Mär. 2009 (CET)

Ok, ich setze die 3 mal in die Mitte des Blocks oben links:

7 6 4   2 9 8   1 3 5

8 3 5   4 7 1   2 8 6

1 2 9   3 6 5   9 4 7

0 0 2   5 0 0   4 1 9

5 4 1   9 2 6   8 7 3

0 9 3   1 0 0   5 6 2

4 6 7   8 5 9   3 2 1

9 1 8   6 0 0   7 5 4

2 5 X   7 0 0   6 9 8

An der Stelle X kann die 3 nicht eingetragen werden. So, geht es also auch nicht auf. --88.153.114.161 16:35, 6. Mär. 2009 (CET)

Ja, und damit ist das Rätsel kein eindeutig lösbares minimales Sudoku, sondern es gibt keine Lösung. Die Frage, ob es minimale Sudoku-Aufgaben mit 24 Vorgaben gibt, bleibt somit offen. --88.153.114.161 20:38, 6. Mär. 2009 (CET)

Was ist mit dieser Lösung:

7 8 4  2 6 9  1 3 5

3 9 5  4 7 1  2 8 6

1 2 6  3 8 5  9 4 7

8 6 2  5 3 7  4 1 9

5 4 1  9 2 6  8 7 3

9 7 3  1 4 8  5 6 2

6 5 7  8 9 4  3 2 1

2 1 8  6 5 3  7 9 4

4 3 9  7 1 2  6 5 8

Ich habe das o. g. Programm mal eine Weile rechnen lassen. Und neben einer Menge von minimalen Problemen mit 19 - 24 Vorbelegungen, hat es auch welchen mit 25 oder 26 Vorbelegungen erzeugt. Und eins hatte 27 Vorbelegungen… -- Clemfix 20:46, 6. Mär. 2009 (CET)

Scheint, ich habe da tatsächlich eine Lösung übersehen. Gibt es vielleicht noch welche? Ich würde es nicht ausschließen. Menschen machen halt manchmal kleinere Fehler. Das Ergebnis des Programms erscheint somit plausibel. Was aber keineswegs für die 6,7*10^21 spricht. Es gibt tatsächlich weit weniger als 9^N, an N Positionen Ziffern einzutragen ohne die Regeln zu verletzen. Bei drei Blöcken in der Diagonale mit 27 Vorgaben sind es etwa nur (9!)^3, etwa 3*10^16, weit weniger als 9^27. --88.153.114.161 22:08, 6. Mär. 2009 (CET)

Verstehe ich Dich richtig, Du willst durch Probieren ohne komplette Permutation/Kombination oder ähnlich die Gesamtzahl der möglichen Lösungen bestimmen?

Natürlich gibt es weniger sinnvolle Aufgabenstellungen als die Gesamtzahl theoretischer Möglichkeiten, nur dürfte die Bestimmung so einfach nicht sein. Die großen Zahlen, die bisher hier berichtet wurden, waren keine sinnvollen Aufgabenstellungen, die überflüssige Zahlen bis zur Zwangslösung fortließen, sondern die Summe aller Möglichektien, die die einfachen Regeln einhielten. Man mußte sich erst terminologisch einigen, was Lösungen sein sollen.--Wikipit 23:25, 6. Mär. 2009 (CET)

NP-Link

Abgesehen von den wieder überbordenden Links zum Thema Sudoku verweist ein Link auf den Beweis zur NP-Vollständigkeit. Was ist das im "Sudoku-Deutsch"? Im Text wird es nirgend erklärt. BG -- Friedrich Graf 14:16, 19. Mai 2009 (CEST)

Könnten Sie kurz erklären was Sie mit "Sudoku-Deutsch" meinen? --84.57.197.171 19:49, 24. Mai 2009 (CEST)

Wer weiß? Vermutlich Deutsch der Sudokuliebhaber oder -spezialisten. Aber tatsächlich wird unter dem Link NP-Vollständigkeit der Begriff reflexiv erklärt, d.h. gar nicht erklärt. Was ist NP, was ist NP-Vollständigkeit, warum ist NP-Vollständigkeit oder das Fehlen beim Sudoku so wichtig, daß ständig darauf verlinkt wird?--Wikipit 22:56, 24. Mai 2009 (CEST)

Also Wikipits Frage trifft den Kern ... und was das "Deutsch" betrifft ein Beispiel:

• im Artikel "NP-Vollständigkeit" steht u.a.: "Der Begriff NP-Vollständigkeit ... zeichnet spezielle formale Sprachen der Komplexitätsklasse NP aus."
  • ... jetzt lese ich also im Sudoku-Artikel den Begriff "NP" und folge dem Link
  • ... jetzt lese ich im NP-Artikel einen Satz, der für Nicht-Fachleute nichtssagend ist und folge dem Link
  • ... usw. Ist das Absicht?
• Der im Artikel "NP" zitierte Satz ist also eine Aneinanderreihung deutscher Worte, die für den normalen deutsch lesenden Benutzer keinen Sinn ergeben.
  • nun können wir auf Grund der seltsamen Definition im "NP"-Artikel nicht die ganze Wikipedia umschreiben - aber den Artikel "Sudoku" verbessern.
• Das meine ich mit "Sudoku-Deutsch" (also nicht nur deutsche Worte, sondern einen Sinn im Zusammenhang mit Sudoku)

BG -- Friedrich Graf 09:48, 25. Mai 2009 (CEST)

Zahl der Lösungsmöglichkeiten

wie genau kommt man auf die 6,7*10^21 lösungen?

--84.113.196.14 10:22, 1. Sep. 2009 (CEST)

Ist doch verlinkt unter Quellen: Mathematics of Sudoku. Die exakte Rechnung beinhaltet leider einen Enumerationsteil, der von einem Programm auszuführen ist. Es wird aber auch eine elegante Heuristik beschrieben, mit der man auch auf 6,7*10^21 kommt - wenn auch nur als Näherungswert. --Mixia 15:56, 1. Sep. 2009 (CEST)

Gebietssoduko

Diese Variante, in der nicht 3x3 Felder die neun Zahlen enthalten sondern beliebig geformte neuner Felder.

-- Red-Viper (nicht signierter Beitrag von 217.85.62.130 (Diskussion | Beiträge) 14:15, 31. Okt. 2009 (CET))

X-Sudoku

Unabhängig vom im Artikel beschriebenen X-Sudoku kann man alternativ oder zusätzlich die Bedingung einführen, daß in allen Nebendiagonalen zwar nicht jedes Element einmal auftaucht (dafür beinhalten die nicht genug Elemente), so doch aber, daß jedes Element, das in jeder Nebendiagonale auftaucht, in jeder dieser nur einmal auftaucht. (nicht signierter Beitrag von 89.244.71.80 (Diskussion | Beiträge) 17:54, 17. Nov. 2009 (CET))

..."alternativ" - zu was? --Friedrich Graf 08:39, 18. Nov. 2009 (CET) Werde Kommissar

Drückte ich mich so unverständlich aus? Alternativ bedeutet oder. Also, man kann das (große) "X" in den Sudokus als zusätzlich Bedingung einfügen und/oder die von mir weiter unten genannte (daß in jeder Nebendiagonale jedes AUFTRETENDE Element eben nur einmal auftritt, aber nicht zwangsweise, daß das auch für die Hauptdiagonale gilt). (nicht signierter Beitrag von 94.134.3.95 (Diskussion | Beiträge) 19:04, 22. Nov. 2009 (CET))

...Ja, du hast dich missverständlich ausgedrückt. Denn nach deiner jetzigen "Übersetzung" heißt dein Satz "... kann man oder oder zusätzlich ...". BG --Friedrich Graf 22:28, 22. Nov. 2009 (CET) Werde Kommissar