Sudoku < Sonstiges < Schule < Mathe < Vorhilfe
|
SUDOKU
Seinerzeit habe ich mich ein Stück weit von den Geheimnissen des Rubik-Würfels infizieren lassen - so weit, bis ich ganze Drehfolgen beherrschte, ohne zwischendurch hinschauen zu müssen. An die entsprechenden Künste einiger meiner Schüler kam ich allerdings nie heran.
Seit ein paar Jahren habe ich jeweils auf dem Nachttisch ein Sudoku-Heftchen der eher schwierigen (aber nicht gerade diabolischen) Klasse. Der Erfolg, so ein Rätsel gelöst zu haben, gibt das gute Gefühl, irgendwie über den Dingen zu stehen und ruhig einschlafen zu dürfen...
Die Sorte Sudokus, bei welchen man nicht umhin kommt, irgendwann probeweise eine Zahl einzusetzen, um dann eventuell nach 29 weiteren Schritten festzustellen, dass diese Wahl falsch war, anschliessend die 29 letzten Eintragungen wieder auszuradieren und mit der anderen Variante zu starten, finde ich etwas doof. Die sind nicht für Menschen geschaffen, sondern für den Computer, welcher das "backtracking" klaglos erledigt. Er teilt uns allerdings auch nicht mit, ob er das gerne tut.
Über eine Eigenschaft von Sudokus der Klasse, die man gerade noch durch Überlegungen und ohne "Probieren und Radieren" lösen kann, bin ich allerdings immer wieder erstaunt: Sie geben ihre Geheimnisse wirklich nur jeweils in "homöopathischen" Dosen frei. Es geschieht - vor allem in den mittleren bis späteren Phasen des Ausfüllens - kaum einmal, dass eine richtig erkannte Einsetzung zu einer ganzen Kaskade von weiteren "leichten" Zügen führt. Vielleicht führt der gute Gedanke dazu, dass man noch zwei oder drei weitere Felder ohne grosses Nachdenken besetzen kann, aber dann ist schon das nächste Stück Gehirnakrobatik fällig. Ich habe mich schon öfters gefragt, woran diese merkwürdige Eigenschaft liegen mag, die den Reiz des Spiels sicher auch erhöht.
Wer hat sich auch schon Gedanken über dieses Phänomen gemacht ?
LG Al-Chwarizmi
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:25 Fr 24.10.2008 | | Autor: | rabilein1 |
> Er (der Computer) teilt uns allerdings auch nicht mit,
> ob er das gerne tut.
Er (der Computer) wird bestimmt genau so oft über uns blöde Menschen fluchen, wie wir über widerspenstige Computer fluchen.
Ansonsten bin / war ich allerdings weder den Rubik-Würfeln noch den Sudokus verfallen. Das liegt wohl daran, dass ich in dieser Hinsicht nicht so ein Geduldsmensch bin, der mühseliger Kleinarbeit irgendwelche Felder ausfüllt.
Im Gegensatz (??? - siehe oben) zum Computer sind wir Menschen nun mal so gestrickt, dass wir manche Aufgaben gerne lösen, andere dagegen als reine Zeitverschwendung ansehen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:25 Fr 24.10.2008 | | Autor: | Bastiane |
Hallo Al-Chwarizmi!
> Wer hat sich auch schon Gedanken über dieses Phänomen
> gemacht ?
Ich mache selten Sudokus, aber immer, wenn ich eins mache, stelle ich fest, dass ich entweder zu doof bin oder dieses Sudoku recht schwierig ist. Warum sich nach einem Eintrag nicht gleich viele weitere einfache ergeben, habe ich mich eher selten gefragt, vielmehr frage ich mich, wer überhaupt solch ein Sudoku entwirft und woher derjenige weiß, dass es sich überhaupt lösen lässt (also ohne Ausprobieren und Backtracking) und wie man den Schwierigkeitsgrad bestimmt. Weißt du das zufällig?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:32 Fr 24.10.2008 | | Autor: | Teufel |
Hi!
Es wäre doch sicher einfach, ein Sudoku zu machen, wenn man einfach alle Felder ausfüllt und dann bestimmte rauslöscht, oder? Je mehr man dann rauslöscht (oder je nach Muster) wird das dann leichter oder schwieriger.
Habe es allerdings noch nicht probiert.
Ansonsten erstellen ja Computer solche Teile.
(Alle Angaben ohne Gewähr, sind nur meine Gedanken ;))
![[anon]](/images/smileys/anon.png "[anon]") Teufel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:49 Fr 24.10.2008 | | Autor: | leduart |
Hallo @ Teufel
Nein, so einfach ists nicht Sudokus garantieren eine eindeutige loesung und eine auffindbare.
Ich fand den "sudokususser" (frei im Netz, mit guter Anleitung fuer kids) mit seinen 4 verschiedenen Kategorien am besten, die "Tricks", bzw. Loesungsstrategien zu finden. Meistens findet sich uebrigens gegenueber der Wenn- dann Methode noch ne echte, logische Strategie.
Gruss leduart
|
|
|
| |
|
> ..... vielmehr frage ich mich, wer überhaupt
> solch ein Sudoku entwirft und woher derjenige weiß, dass es
> sich überhaupt lösen lässt (also ohne Ausprobieren und
> Backtracking) und wie man den Schwierigkeitsgrad bestimmt.
> Weißt du das zufällig?
>
> Viele Grüße
> Bastiane
>
Hallo zusammen !
Sudokus werden massenweise produziert, natürlich mittels
darauf zugeschnittener Computerprogramme. Wie diese genau
funktionieren, weiss ich nicht genau. Selber habe ich einmal
ein Programm erstellt, das vorgegebene (nicht allzu schwierige)
Sudokus löst.
Auch ein fertiges, komplett ausgefülltes Sudoku zu erstellen
ist kein Kinderspiel, da so viele Bedingungen zu erfüllen sind.
Dazu existieren aber wohl ausgetüftelte Strategien, um nicht
Millionen Jahre, sondern nur Sekundenbruchteile Rechenzeit
zu brauchen, um ein solches "Voll-Sudoku" zu erzeugen. Wie
viele und welche Felder gelöscht werden können, um immer
noch ein eindeutig lösbares Sudoku übrig zu lassen, ist die
nächste Frage, die wohl geklärt wird, indem man Lösungs-
programme verschiedener Spielstärke auf die teilweise redu-
zierten Sudokus ansetzt. Dabei können die Sudokus auch nach
Schwierigkeitsgraden klassifiziert werden.
Natürlich gibt es einfache Sudokus, bei denen in jedem
Stadium mehrere nächste Einsetzungen offensichtlich sind.
Das sind aber auch die Spiele, die einem wirklich sehr rasch
verleiden, weil keine Herausforderung drin steckt. Interessant
sind die Spiele jener Stufe, bei der man gefordert ist und in
mehreren Situationen Gedankengänge anwenden muss,
die einem selber neu sind.
Die Eigenschaft, dass Sudokus der mittleren bis schwierigeren
Sorte aber ihre Geheimnisse wirklich nur in minimalen
Häppchen preisgeben (bis auf die Schlussphase, wo man
die letzten freien Felder leicht ergänzen kann), scheint aber
irgendwie in der Logik des Spiels selber begründet zu sein.
Ich denke nicht, dass da eine entsprechende Absicht der
Sudoku-Programmierer dahinter steckt.
 Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:17 Do 06.11.2008 | | Autor: | maxi85 |
hmm das sich schnell weitere antworten aus einem richtig ausgefüllten feld ergeben lässt sich dadurch bewerkstelligen, das du einfach in jedes feld alle zahlen (klein) reinschreibst, die dort möglich sind. irgendwann kommst du auf ein feld in dem nur eine zahl möglich ist, streichst diese zahl aus allen feldern des gleichen 9ers, waagerechten und senkrechten, daraus ergibt sich dann eig. sofort die nächste zahl usw.
das verfahren wende ich allerdings erst an wenn ich sonst gar nicht mehr weiterkomme und es klappt auch nur bei nich "fast unlösbaren" Sudokus.
|
|
|
| |
|
Mir ging es hier eigentlich gar nicht um Lösungsverfahren im Einzelnen, sondern um die etwas enigmatische Eigenschaft vieler Sudokus der eher schwierigen Klasse, dass man oft, wenn man glaubt, einen entscheidenden Schritt vorwärts gemacht zu haben, feststellen muss, dass alle die "Türchen", die man glaubt, nun öffnen zu können, sich in verzwickter Weise miteinander verbünden, so dass man das eine nur öffnen kann, wenn man erst wenigstens eines der anderen geöffnet hat ...
Vielleicht ist der Vergleich etwas verwegen und sehr weit her geholt, aber ich kann mir nicht verkneifen zu sagen, dass ich da gewisse Ähnlichkeiten zu den paradoxen Phänomenen der Quantenphysik sehe. Dort haben wir es allerdings mit noch viel komplexeren interagierenden Systemen zu tun.
Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:27 So 09.11.2008 | | Autor: | rabilein1 |
> ... dass ich da gewisse Ähnlichkeiten zu den paradoxen
> Phänomenen der Quantenphysik sehe.
Ich kenne zwar weder deine Sudokus noch die Phänomene der Quantentheorie, aber mir fällt ein Vergleich zu einem Phänomen ein, das auch ein Schüler der 10. Klasse kennt:
Man lernt, wie man ein Gleichungssystem "Zwei Gleichungen mit zwei Unbekannten" löst.
Man lernt auch, wie man ein System "Drei Gleichungen mit drei Unbekannten" in ein System "Zwei Gleichungen mit zwei Unbekannten" überführen kann.
Aus diesem Wissen heraus sollte es dann auch ohne weitere Hilfsmittel möglich sein, zehn Gleichungen mit zehn Unbekannten zu lösen, indem man Schritt für Schritt eine nach der anderen Unbekannten "eliminiert".
Da sind wir dann wieder bei den sogenannten Arschleder-Aufgaben, und in meinen Augen stellen Sudokus eine ebensolche Art von Aufgabe dar (vom Prinzip her lösbar, aber nur mit viel Geduld)
|
|
|
| |
|
> vom Prinzip her lösbar, aber nur mit viel Geduld
Was Geduld wirklich bedeutet, hat ![[]](/images/popup.gif) Johann Gustav Hermes gezeigt,
indem er neben seiner Arbeit als Oberlehrer in über zehnjähriger
Arbeit eine 200-seitige Anleitung zur Konstruktion einer Figur
anfertigte, welche man von einem Kreis nicht unterscheiden kann:
das regelmässige 65537-Eck.
Die Anleitung zur Konstruktion des regelmässigen 65536-Ecks
ist dagegen kinderleicht und würde auf einen Bierdeckel passen.
Man kann nur rätseln, wie Hermes auf die herkulische Bieridee
kommen konnte, das 65537-Eck tatsächlich zu konstruieren.
Ein Indiz: er bestand seine Reifeprüfung am Kneiphöfischen
Gymnasium in Königsberg ... 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:07 Mo 10.11.2008 | | Autor: | rabilein1 |
Ich weiß nicht, was die Motivation des Herrn Hermes zu dieser zehnjährigen Arbeit war.
Dennoch habe ich eine Vermutung: Herr Hermes war sich ziemlich sicher, dass er der Erste (und Einzige) ist, der so eine Konstruktionsanleitung erarbeitet.
Vermutlich hätte er aber nicht einmal die Geduld gehabt, sich auch nur eine Woche mit dem Thema selbständig zu beschäftigen, wenn ihm bekannt gewesen wäre, dass bereits eine 200-seitige Anleitung existiert.
Jedenfalls geht es mir so: Ich habe wenig Lust, Dinge zu tun, die jeder andere genau so gut kann, bzw., die viele andere schon bereits getan habe (Stichwort: "Beweise" = so was finde ich schrecklich und langweilig, es sei denn, man würde etwas "beweisen", was vorher noch niemand gezeigt hat; dann wären 10 Jahre Arbeit eventuell lohnenswert)
Um auf Sudoku zurück zu kommen: Das ist der Grund, warum ich dazu keine Geduld habe: weil die Lösung ja irgendwie bekannt ist und keine nützlichen Effekte hat. (Wenn ich dagegen ein Lego-Haus baue, kann ich ziemlich sicher sein, dass es genau dieses Haus kein zweites Mal auf der Welt gibt)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:19 Mi 17.12.2008 | | Autor: | chrisno |
Ich frage, ob der Effekt wirklich gegeben ist. Nach meiner Erfahrung geht es nach einer Hürde meistens doch mit ein paar Feldern, deren Einträge als nächste folgen weiter.
Ich fürchte, da muss erst einmal eine Statistik her. Vielleicht sind die Sudokus, die ich mache, auch zu leicht. Mein Eindruck ist, dass der Schweregrad einfach aus der Anzahl der offenen Felder bestimmt wird.
|
|
|
| |
|
> Ich frage, ob der Effekt wirklich gegeben ist. Nach meiner
> Erfahrung geht es nach einer Hürde meistens doch mit ein
> paar Feldern, deren Einträge als nächste folgen weiter.
Es hängt schon vom Schwierigkeitsgrad ab. Bei den leichten
und mittleren Sudokus ist der Effekt nicht oder kaum
vorhanden. Doch gerade bei denen, welche gerade noch
ohne "backtracking" (wo man eine Zahl versuchsweise
einsetzt und nachher notfalls eine ganze Reihe von Einträgen
ausradiert, nachdem ein Widerspruch aufgetreten ist) lösbar
sind, habe ich schon oft festgestellt, dass ein nach langem
Überlegen "geknacktes" Feld vielleicht nur zwei Schritte
weiterführt und dass man dann schon wieder steckenbleibt.
Und dies ein paar mal hintereinander, bis dann am Schluss
vielleicht die letzten paar Felder leicht zu ergänzen sind.
> Ich fürchte, da muss erst einmal eine Statistik her.
> Vielleicht sind die Sudokus, die ich mache, auch zu leicht.
Mit Löseprogrammen verschiedener "Spielstärke", losge-
lassen auf ganze Serien von Sudokus eines gewissen
Schwierigkeitsgrades könnte man sowas vielleicht machen.
Allerdings ist zu dieser Methode folgender Einwand möglich:
die für die massenweise vertriebenen Heftchen produzierten
Sudokus werden ja nach Schwierigkeitsgraden vorsortiert,
natürlich ebenfalls durch Einsatz von Löseprogrammen.
Möglicherweise ist also der besagte "Hürdenlauf-Effekt"
sogar bewusst eingebaut, indem bei der Auswahl für eine
bestimmte Schwierigkeitsklasse solche Sudokus den
anderen, leichter lösbaren, vorgezogen werden.
Tatsächlich habe ich einmal selber ein Löseprogramm
gemacht, das gerade etwa soviel konnte wie ich aus eigener
Kraft zustande brachte. Es blieb oft exakt an den Stellen
stecken, wo ich selber scheiterte - eigentlich nicht sooo
verwunderlich, aber für mich war es immerhin die Bestä-
tigung, offenbar doch meine eigenen Strategien richtig ins
Programm abgebildet zu haben. Über meine eigenen Erfah-
rungen mit den "Betthupferl-Sudokus" führe ich allerdings
nicht Buch und habe auch nicht vor, damit anzufangen ...
> Mein Eindruck ist, dass der Schweregrad einfach aus der
> Anzahl der offenen Felder bestimmt wird.
Dies ist allerdings keinesfalls so. Es gibt welche mit
wenig vorgegebenen Eintragungen, die erstaunlich leicht
zu bewältigen sind, aber auch solche, bei denen schon
vieles ausgefüllt ist, die sich dann aber als sehr schwierig
entpuppen.
Gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:00 Sa 20.12.2008 | | Autor: | rabilein1 |
> Tatsächlich habe ich einmal selber ein Löseprogramm
> gemacht, das gerade etwa soviel konnte wie ich aus eigener
> Kraft zustande brachte.
Über diesen Satz musste ich etwas schmunzeln, da er doch ein altbekanntes Phänomen widerspiegelt: Man programmiert seinen Computer so, dass er (der Computer) genau so denkt wie man selbst - nur um einiges schneller.
Mal angenommen, es gäbe einen genialen Lösungsweg, dein Sodoku auf genial-einfache Art und Weise zu lösen. Du hast diesen Weg aber noch nicht gefunden.
Wie aber soll dein Computer diesen Weg finden, wenn du es bist, der ihn programmiert hast?
|
|
|
| |
|
> > Tatsächlich habe ich einmal selber ein Löseprogramm
> > gemacht, das gerade etwa soviel konnte wie ich aus
> > eigener Kraft zustande brachte.
> Über diesen Satz musste ich etwas schmunzeln, da er doch
> ein altbekanntes Phänomen widerspiegelt: Man programmiert
> seinen Computer so, dass er (der Computer) genau so denkt
> wie man selbst - nur um einiges schneller.
> Mal angenommen, es gäbe einen genialen Lösungsweg,
> Sudokus auf genial-einfache Art und Weise zu lösen.
> Du hast diesen Weg aber noch nicht gefunden.
> Wie aber soll dein Computer diesen Weg finden, wenn
> du es bist, der ihn programmiert hast?
Es gibt durchaus sehr prominente Fälle, in welchen die
Hardware wesentlich "intelligenter" wird als das Programm,
auf welchem sie beruht, und auch intelligenter als der
Programmierer. Unter Umständen erübrigt sich sogar ein
eigentlicher "Programmierer". Das allerbeste Beispiel dazu
sind unsere eigenen Gehirne.
Hallo rabilein,
darüber, dass ich so ein Programm zustande brachte, war
ich damals trotzdem - und ich glaube berechtigterweise -
ein Stück weit stolz: hatte ich es doch immerhin fertigge-
bracht, meine eigenen Lösungsstrategien so weit zu durch-
schauen, dass es mir gelang, sie auf den Computer zu
übertragen.
In manchen Zusammenhängen ist es durchaus möglich,
dass ein Programm, das auf recht schlichten Grundlagen
beruht, viel stärkere Leistungen erbringen kann, als es
seinem Programmierer aus eigenen Kräften je möglich
wäre. Dabei werden (im Dialog über die vielleicht nur
durch "brute computer force" erreichten Ergebnisse)
nicht nur quantitative, sondern auch qualitative Grenzen
überschritten.
Würde es gelingen, nicht nur Lösungsstrategien für ein
einfaches Spiel, sondern intellektuelle Fähigkeiten, viel-
fältige Kenntnisse über reale Zusammenhänge und einige
grundlegende und demokratisch erarbeitete Zielvorgaben
über eine wünschenswerte Zukunft getreu in ein Compu-
terprogramm zu übertragen, könnten daraus Experten-
systeme von immensem Wert entspringen.
Lieben Gruß Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:30 So 21.12.2008 | | Autor: | rabilein1 |
> Würde es gelingen, nicht nur Lösungsstrategien für ein
> einfaches Spiel, sondern intellektuelle Fähigkeiten,
> vielfältige Kenntnisse über reale Zusammenhänge und einige
> grundlegende und demokratisch erarbeitete Zielvorgaben
> über eine wünschenswerte Zukunft getreu in ein Compu-
> terprogramm zu übertragen, könnten daraus Experten-
> systeme von immensem Wert entspringen.
Ob so etwas aber jemals gelingt?
Selbst bei Sodoku oder Schach - wo es zwar sehr viele, aber dennoch nur endlich viele Möglichkeiten gibt - stoßen Computerprogramme schnell an ihre Grenzen.
Wie ist es aber, wenn es unendlich viele Möglichkeiten gibt (wie es bei "realen Zusammenhängen" der Fall ist)?
Bedenke nur, dass jeder einzelne Mensch in jeder Sekunde eine Vielzahl von Möglichkeiten hat, in welche Richtung er jede einzelne seiner Gliedmaßen bewegt. Wie soll ein von außen gelenkes System so etwas koordinieren können?
|
|
|
| |
|
Hallo rabilein,
Ob so etwas gelingen wird, bevor unsere Zivilisation
vor den grossen Problemen, deren wahre Dimensionen
wir heute erst erahnen können, ins Wanken kommt,
ist wenigstens fraglich.
Bei dem Begriff "von aussen gelenktes System" kommt
mir die Arbeit meines seinerzeitigen Studienkollegen und
AI-Forschers Rolf Pfeifer in den Sinn. Eine seiner haupt-
sächlichen Thesen ist, dass Computerchips allein kein
geeignetes Substrat bilden, auf welchem so etwas wie
Intelligenz gedeihen kann. Vielmehr entsteht Intelligenz
erst im intensiven Austausch mit einer Umwelt, in der
Entwicklungsmöglichkeiten warten, aber auch harte
Vorgaben gelten und manche Gefahren lauern.
Hier die url eines Interviews mit ihm:
http://www.peshawar.ch/tech/rolf-pfeifer-interview.htm
viele Grüße Al
|
|
|
| |
|
Hallo!
Zunächst muß ich sagen, daß mich selbst das Sudoku-Fieber noch nicht gepackt hat. Ich finde das Prinzip zwar interessant, hab auch schon aus Zeitvertreib hier und da angefangen, aber weil die Zeit dann vertrieben war, hab ich aufgehört. Interessant finde ich dagegen den Einsatz von Computern, um Sudokus zu erstellen oder zu lösen.
Beispielsweise hab ich vor Jahren auf dem Rechner eines Schulfreundes Minesweeper entdeckt. Zugegeben, ein sehr einfaches Spiel, das auch nicht besonders lange reizt, aber es war bei Win95 dabei, während ich es für meinen Atari nicht hatte (ich bekam meinen Atari geschenkt, als dieser schon ausgestorben war. Was mir blieb, war eine kleine Softwaresammlung und GFA-Basic, ein Basic, teils mächtiger als C++ heute).
Ich hatte nun großen Spaß daran, Minesweeper nachzuprogrammieren. Als es dann lief - und auf meinen rekursiven Aufdeckalgorithmus war ich besonders stolz - war das Spiel langweilig.
Bei Sudoku geht es mir da ähnlich, denke schon drüber nach, wie man so ein Programm zum Lösen schreiben würde.
Prinzipiell sollte die brute-force-Methode von oben für den Programmierer das einfachste sein. Der Recher checkt also für jedes freie Feld, welche Zahlen NICHT rein dürfen, und sucht anschließend nach den Feldern, wo nur noch eine Zahl erlaubt ist.
Wurde nach einem Durchgang keine neue Zahl eingetragen, ist das Spiel nicht sahen wir mal deterministisch lösbar. Ebenso kann man einfach Widersprüche entdecken. Für einen PC sollte das kein Problem sein.
Interessant wird es, wenn man anfangen muß zu raten, denn dann müßte der PC immer, wenn es stockt, meist mehrere Sudokus mit eingesetzten, möglichen Zahlen zu lösen versuchen. Auch das ist sicherlich einfach programmierbar, wird aber einiges an Rechenzeit fordern.
Generell denke ich aber, das auch das noch gut zu schaffen ist, denn einerseits sind Rechner heute sehr schnell, andererseits möchte ich mir kein Sudoku vorstellen, bei dem wirklich viele Felder geraten werden müssen.
Dennoch ist das bisher eine recht stumpfsinnige Methode. Interessant wird es, wenn man wie hier auch geschrieben, eine gewisse Intelligenz in Form von Regeln, die auch der Mensch benutzt, einsetzt. Damit könnte das Spiel vor allem am Anfang, wenn das Feld noch leer ist, evtl stark beschleunigt werden (wenngleich ich mich frage, ob die Anwendung von Regeln evtl mehr Rechenzeit als das sture Suchen nach möglichen zahlen benötigt).
Ich kann mir vorstellen, daß man weiterhin die Brute-Force-Methode weg läßt (oder als letztes Mittel vorsieht), und den Rechner nur mit den Regeln arbeiten läßt. Die Anzahl und Art der benutzten Regeln sollte dann erlauben, Aussagen über die Schwierigkeit des Sudokus zu machen.
Ich denke, es gibt auch einen gewaltigen Unterschied zwischen Sudoku und Schach.
Bei Sudoku gibt es eine einzige feste Lösung, die durch letztendlich recht einfache Regeln erreicht werden kann. Sudoku ist weitgehend deterministisch und damit durchschaubar, sodaß man die meiste Zeit einfach durchlaufen kann (oder auch vollständig, wenn es ohne Raten lösbar ist).
Schach dagegen hat ein komplizierteres Regelwerk, da jede Figur ganz andere Bewegungsmuster ausüben kann, und auch das ganze Spiel über beweglich bleibt (sofern sie nicht festgesetzt wurde). Weiterhin gibt es keine feste Lösung, bei der man ständig prüfen kann, wie weit man ihr näher gekommen ist, sondern es gibt nur ein Ziel, nämlich den Gegner zu besiegen. Dummerweise - und das kommt erschwerend hinzu - bewegt sich der Gegner, und versucht zu entkommen bzw einem selbst zu schaden.
Das alles macht Schach auch für den Computer sehr schwer. Es ist nicht möglich, mehr als ne Hand voll Schritte vorauszusimulieren, und daraus den günstigsten zu benutzen.
Mir kommt da grade die perfide Idee zu einem "Schadoku": Zwei Personen, ein komplett leeres Sudoku-Feld. Jeder trägt abwechselnd eine Zahl ein. Wer ne nicht passende Zahl einträgt, verliert.
Hierbei gibts auch keine feste Lösung, und man hat immer die Aktion des Gegners als unbekannte mit drin.
|
|
|
| |
|
> Ich hatte nun großen Spaß daran, Minesweeper
> nachzuprogrammieren. Als es dann lief - und auf meinen
> rekursiven Aufdeckalgorithmus war ich besonders stolz - war
> das Spiel langweilig.
Das ging mir auch bei meinen Programmen für
verschiedene Spiele so. Beim Programmieren
gilt noch mehr als in anderen Bereichen das
Motto "Der Weg ist das Ziel".
> Bei Sudoku geht es mir da ähnlich, denke schon drüber nach,
> wie man so ein Programm zum Lösen schreiben würde.
>
> Prinzipiell sollte die brute-force-Methode von oben für den
> Programmierer das einfachste sein. Der Recher checkt also
> für jedes freie Feld, welche Zahlen NICHT rein dürfen, und
> sucht anschließend nach den Feldern, wo nur noch eine Zahl
> erlaubt ist.
Das ist nicht einmal "brute force". Damit kommt man aber
auch nur bei sehr einfachen Sudokus zum Ziel. Schon bei
mittelschweren Sudokus ist es mit der einfachen Anwendung
der Regeln nämlich oft keineswegs leicht, herauszufinden,
welche Zahlen in einem Feld nicht passen. Man muss dann
schon die Kombination von zwei oder drei Regeln und
mehrere Felder berücksichtigen, um eine weitere Eintragung
sicher zu begründen.
Unter "brute force" würde ich eher den intensiven Einsatz
des "backtracking" bezeichnen.
> Wurde nach einem Durchgang keine neue Zahl eingetragen, ist
> das Spiel nicht sagen wir mal deterministisch lösbar.
Jedes Sudoku ist deterministisch lösbar, bzw. kann man
deterministisch zeigen, dass es unlösbar (also gar kein
regelgemässes Sudoku) ist.
> Ebenso kann man einfach Widersprüche entdecken. Für einen
> PC sollte das kein Problem sein.
>
> Interessant wird es, wenn man anfangen muß zu raten, denn
> dann müßte der PC immer, wenn es stockt, meist mehrere
> Sudokus mit eingesetzten, möglichen Zahlen zu lösen
> versuchen. Auch das ist sicherlich einfach programmierbar,
> wird aber einiges an Rechenzeit fordern.
genau das wäre backtracking !
> Generell denke ich aber, das auch das noch gut zu schaffen
> ist, denn einerseits sind Rechner heute sehr schnell,
> andererseits möchte ich mir kein Sudoku vorstellen, bei dem
> wirklich viele Felder geraten werden müssen.
>
> Dennoch ist das bisher eine recht stumpfsinnige Methode.
> Interessant wird es, wenn man wie hier auch geschrieben,
> eine gewisse Intelligenz in Form von Regeln, die auch der
> Mensch benutzt, einsetzt. Damit könnte das Spiel vor allem
> am Anfang, wenn das Feld noch leer ist, evtl stark
> beschleunigt werden (wenngleich ich mich frage, ob die
> Anwendung von Regeln evtl mehr Rechenzeit als das sture
> Suchen nach möglichen zahlen benötigt).
>
> Ich kann mir vorstellen, daß man weiterhin die
> Brute-Force-Methode weg läßt (oder als letztes Mittel
> vorsieht), und den Rechner nur mit den Regeln arbeiten
> läßt. Die Anzahl und Art der benutzten Regeln sollte dann
> erlauben, Aussagen über die Schwierigkeit des Sudokus zu
> machen.
>
>
> Ich denke, es gibt auch einen gewaltigen Unterschied
> zwischen Sudoku und Schach.
> Bei Sudoku gibt es eine einzige feste Lösung, die durch
> letztendlich recht einfache Regeln erreicht werden kann.
> Sudoku ist weitgehend deterministisch und damit
> durchschaubar, sodaß man die meiste Zeit einfach
> durchlaufen kann (oder auch vollständig, wenn es ohne Raten
> lösbar ist).
> Schach dagegen hat ein komplizierteres Regelwerk, da jede
> Figur ganz andere Bewegungsmuster ausüben kann, und auch
> das ganze Spiel über beweglich bleibt (sofern sie nicht
> festgesetzt wurde). Weiterhin gibt es keine feste Lösung,
> bei der man ständig prüfen kann, wie weit man ihr näher
> gekommen ist, sondern es gibt nur ein Ziel, nämlich den
> Gegner zu besiegen. Dummerweise - und das kommt erschwerend
> hinzu - bewegt sich der Gegner, und versucht zu entkommen
> bzw einem selbst zu schaden.
> Das alles macht Schach auch für den Computer sehr schwer.
> Es ist nicht möglich, mehr als ne Hand voll Schritte
> vorauszusimulieren, und daraus den günstigsten zu
> benutzen.
Trotz des komplizierten Regelwerks ist Schach ein
deterministisches Spiel. Im Prinzip sollte es durch
endlich viele Rechenschritte abklärbar sein, ob es
z.B. für Weiss (mit dem ersten Zug) eine sichere
Siegstrategie gibt oder nicht. Allerdings übersteigt
diese komplette Analyse des Schachspiels die
Möglichkeiten aller heute existierenden Rechner.
> Mir kommt da grade die perfide Idee zu einem "Schadoku":
> Zwei Personen, ein komplett leeres Sudoku-Feld. Jeder trägt
> abwechselnd eine Zahl ein. Wer ne nicht passende Zahl
> einträgt, verliert.
> Hierbei gibts auch keine feste Lösung, und man hat immer
> die Aktion des Gegners als unbekannte mit drin.
Für dieses Spiel müsstest du genau definieren, was
du unter einer "nicht passenden Zahl" verstehst.
Wahrscheinlich meinst du, dass die eingetragene
Zahl keine der drei Grundregeln (betr. Zeile, Spalte,
Block) verletzen darf.
Man könnte den Begriff "nicht passende Zahl" aber
auch so verstehen: Wenn das teilweise ausgefüllte
Zahlenschema zusammen mit der neu eingetragenen
Ziffer sich nicht mehr zu einem vollständigen Sudoku
ergänzen lässt, ist die Ziffer nicht passend. Allerdings
könnte kein Mensch dieses Spiel wirklich spielen.
Schiedsrichter müsste immer ein Computer sein.
Aus der einfacheren Spielregel könnte aber durchaus
ein zwar anfangs immer langweiliges, dann aber span-
nender werdendes Spiel werden. Jedoch befürchte ich,
dass aus den allermeisten Spielen (ich würde mal
behaupten in mehr als 999 Promille der Fälle) kein
fertiges Sudoku resultieren würde. Ob es für den
interessanten Teil des Spiels - wo die noch möglichen
Eintragungen rar werden, Strategien gibt, um das
Spielglück auf die eigene Seite zu zwingen, wäre eine
interessante Frage.
LG Al-Chw.
|
|
|
| |
|
Hallo!
Das Wort "deterministisch" hab ich hier zugegebenerweise nicht im Sinne seiner normalen Bedeutung benutzt, ich hätte das beschreiben sollen. Ich wollte damit sagen, daß das Spiel vollkommen ohne Raten und ausprobieren auskommt, sondern daß sich immer für irgendein freies Feld zwingend die richtige Zahl aus den bekannten Zahlen auf anderen Feldern ergibt.
Solche Sudokus sollten sich immer dadurch lösen lassen, daß man wiederholt für jedes freie Feld prüft, welche Zahlen nicht eingesetzt werden können. Nach jeder Überprüfung des gesamten Sudokus muß sich dann auch mindestens ein Feld finden lassen, in das sich wegen Ausschluß aller anderen Zahlen die richtige Zahl einsetzen läßt.
Auch hier hast du mich erwischt, denn das ist nur Anwendung stupider Logik, während BruteForce tatschlich einfach das Ausprobieren meint.
Das ist nicht einmal "brute force". Damit kommt man aber
auch nur bei sehr einfachen Sudokus zum Ziel. Schon bei
mittelschweren Sudokus ist es mit der einfachen Anwendung
der Regeln nämlich oft keineswegs leicht, herauszufinden,
welche Zahlen in einem Feld nicht passen. Man muss dann
schon die Kombination von zwei oder drei Regeln und
mehrere Felder berücksichtigen, um eine weitere Eintragung
sicher zu begründen.
Hier muß ich sagen, daß ich nicht genau verstehe, was du meinst. Aber vermutlich habe ich mich dazu einfach nicht genug mit Sudokus beschäftigt. Vermutlich müßte ich einfach mal ein Programm schreiben und auf ein paar schwerere Sudokus loslassen...
Trotz des komplizierten Regelwerks ist Schach ein
deterministisches Spiel. Im Prinzip sollte es durch
endlich viele Rechenschritte abklärbar sein, ob es
z.B. für Weiss (mit dem ersten Zug) eine sichere
Siegstrategie gibt oder nicht. Allerdings übersteigt
diese komplette Analyse des Schachspiels die
Möglichkeiten aller heute existierenden Rechner.
Das ist richtig, es übersteigt unsere Möglichkeiten. Aber ob es wirklich sowas wie einen "goldenen Weg" gibt, mit dem Weiß immer gewinnt, wage ich sehr zu bezweifeln. Es gibt sicherlich viel oder wenig versprechende Züge (also Wahrscheinlichkeiten für Sieg), aber der Sieg hängt doch zu sehr von dem ab, was der Gegner macht. Naja, vielleicht wissen wir das in 30 Jahren ja...
Was mein Schadoku angeht: Natürlich muß das Spiel zu jedem Zeitpunkt zu einem korrekt lösbaren Sudoku führen können, demnach definiere ich eine falsche Zahl so, daß durch sie das Erstellen eines korrekten Sudokus unmöglich wird. Wahrlich muß darüber ein Computer unter exzessivem Einsatz von BruteForce wachen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:47 So 21.12.2008 | | Autor: | rabilein1 |
> > Mir kommt da grade die perfide Idee zu einem "Schadoku":
> > Zwei Personen, ein komplett leeres Sudoku-Feld. Jeder trägt
> > abwechselnd eine Zahl ein. Wer ne nicht passende Zahl
> > einträgt, verliert.
> > Hierbei gibts auch keine feste Lösung, und man hat immer
> > die Aktion des Gegners als unbekannte mit drin.
Das wäre doch mal was Interessant-Neues. Denn irgendwann müssen doch mal alle möglichen Sodokus und nahezu alle möglichen Schachpartien "ausgelutscht" sein.
> Für dieses Spiel müsstest du genau definieren, was
> du unter einer "nicht passenden Zahl" verstehst.
> Wahrscheinlich meinst du, dass die eingetragene
> Zahl keine der drei Grundregeln (betr. Zeile, Spalte,
> Block) verletzen darf.
> Man könnte den Begriff "nicht passende Zahl" aber
> auch so verstehen: Wenn das teilweise ausgefüllte
> Zahlenschema zusammen mit der neu eingetragenen
> Ziffer sich nicht mehr zu einem vollständigen Sudoku
> ergänzen lässt, ist die Ziffer nicht passend. Allerdings
> könnte kein Mensch dieses Spiel wirklich spielen.
> Schiedsrichter müsste immer ein Computer sein.
Ob sich später noch ein vollständiges Sodoku ergibt, ist meines Erachtens unerheblich. Das Spiel ist ja beendet, sobald sich keine Zahl mehr einsetzen lässt.
Vielleicht wird Schadoku aber auch deshalb langweilig, weil...
... immer derjenige gewinnt, der einen ungeraden Zug macht (der also anfängt)
... es gar keine "Strategie" gibt, sondern nahezu Zufall ist, wer gewinnt
... es am Ende eher darauf ankommt, wer noch ein mögliches Feld entdeckt (Zufall) - ähnlich wie beim Käsekästchen
|
|
|
| |
|
Hallo!
Beim Schadoku müßte man sich darauf einigen, wann das Spiel endet. So, wie du es beschreibst, gehst du davon aus, daß beide Spieler das Feld bis zum Schluß auffüllen, dann gewinnt immer der, der anfängt. Ich glaube aber, daß es in der Realität nicht so häufig dazu kommen wird, daß das Spiel bis zum "bitteren Ende" gespielt wird.
Ich glaube, daß schon lange vorher einer einen Fehler machen wird, und die Entscheidung zu dem Zeitpunkt stattfindet, wenn das lustige Einsetzen weitgehend zufälliger Ziffern auf dem noch leeren Sudoku aufhört, und man langsam anfängt, sich mit Logik irgendwelche Felder zu erarbeiten. Später, wenn das Sudoku größtenteils gefüllt ist, wird es ja wieder einfacher.
Achso, kennt einer Hexadoku? Mit den Zahlen 1-F und 4x4-Feldern. Das gibt es immer im Elektor, einem Elektronik-Magazin. Man kann sich das auch kostenlos auf der Homepage runterladen, allerdings muß man sich registrieren.
Dann haben die wohl auch ein "alphadoku", wo sie gleich 5x5-Felder benutzen...
|
|
|
| |
|
> Das wäre doch mal was Interessant-Neues. Denn irgendwann
> müssen doch mal alle möglichen Sodokus und nahezu alle
> möglichen Schachpartien "ausgelutscht" sein.
Meiner Meinung nach sind beispielsweise auch alle
Fussballsituationen schon längst ausgelutscht. Aber
es gibt viele - und immer wieder neue - Menschen,
denen das Lutschen an ausgelutschten Objekten
offenbar immer wieder Spass macht, oft zum Ärger
ihrer Partnerinnen oder Partner, die eher Lust auf
neue Spiele und Erfahrungen hätten .....
> Ob sich später noch ein vollständiges Sodoku ergibt, ist
> meines Erachtens unerheblich. Das Spiel ist ja beendet,
> sobald sich keine Zahl mehr einsetzen lässt.
> Vielleicht wird Schadoku aber auch deshalb langweilig,
> weil...
> ... immer derjenige gewinnt, der einen ungeraden Zug macht
> (der also anfängt)
> ... es gar keine "Strategie" gibt, sondern nahezu Zufall
> ist, wer gewinnt
Bei "Schadoku" (um es zu propagieren, müsste man
erst noch einen besseren Namen finden, um nicht
zuallererst die Assoziation zu "Schaden" zu wecken)
nach der einfachen Regel (an einer Position ist eine
Ziffer erlaubt, wenn die gleiche Ziffer weder in der
gleichen Zeile, der gleichen Spalte noch dem gleichen
Block schon vorkommt) ist wohl von vornherein kei-
neswegs absehbar, ob es nach einer geraden oder
nach einer ungeraden Anzahl Züge endet, da das Feld
im Normalfall überhaupt nicht vollständig ausgefüllt
werden kann. Ich vermute deshalb, dass es durchaus
gewisse Strategien für ein geschicktes Endspiel geben
könnte. Im Vorteil wäre der Spieler, der als erster er-
kennt, dass es sich nur noch um eine überschaubare
Endspielsituation handelt und seine folgenden Züge so
planen kann, dass nicht er selber, sondern der Gegner
in der notwendigen Sackgasse endet. Ich schliesse also
die Möglichkeit keineswegs aus, dass da ein durchaus
attraktives Endspiel resultieren könnte. Vielleicht gibt
es in den Internet-Zeitungen von 2014 neben dem
Schach-Rätsel "Matt in 2 Zügen" die Rubrik "Schadoku-
Matt in 3 Zügen".
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:25 Mo 22.12.2008 | | Autor: | froopkind |
> Meiner Meinung nach sind beispielsweise auch alle
> Fussballsituationen schon längst ausgelutscht. Aber
> es gibt viele - und immer wieder neue - Menschen,
> denen das Lutschen an ausgelutschten Objekten
> offenbar immer wieder Spass macht, oft zum Ärger
> ihrer Partnerinnen oder Partner, die eher Lust auf
> neue Spiele und Erfahrungen hätten .....
Sehr gut!!!!
Darf ich dich da an geeigneter stelle im Leben mal Zitieren, ja?
Vielen dank für den Spruch!
|
|
|
| |
|
> > Meiner Meinung nach sind beispielsweise auch alle
> > Fussballsituationen schon längst ausgelutscht. Aber
> > es gibt viele - und immer wieder neue - Menschen,
> > denen das Lutschen an ausgelutschten Objekten
> > offenbar immer wieder Spass macht, oft zum Ärger
> > ihrer Partnerinnen oder Partner, die eher Lust auf
> > neue Spiele und Erfahrungen hätten .....
>
> Sehr gut!!!!
>
> Darf ich dich da an geeigneter Stelle im Leben mal
> zitieren, ja?
Ohne weiteres, gerne !
Es gibt allerdings Wahrheiten, mit denen man sich
kaum Freunde schafft
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:03 Mo 22.12.2008 | | Autor: | rabilein1 |
> Meiner Meinung nach sind beispielsweise auch alle
> Fussballsituationen schon längst ausgelutscht.
Mal angenommen, ein Schachspiel endet nach maximal 200 Zügen. Jeder Zug lässt durchschnittlich 20 (sinnvolle) Möglichkeiten zu.
Dann gäbe es also etwa [mm] 20^{200} [/mm] mögliche Verläufe einer Schachpartie. Das ist zwar eine ganze Menge, aber es ist eine endliche Zahl.
Aber wie sieht es bei einem Fußballspiel aus?
Man könnte die 90 Minuten in 54.000 Zehntelsekunden zerlegen, oder in 540.000 Hunderstelsekunden.
Jeder der 22 Spieler hat eine Position, die man auf den Zentimeter genau bestimmen kann. Dazu kommt noch seine Blickrichtung und Körperhaltung.
Und dann ist noch der Ball - der sich sogar dreidimensional über das Spielfeld bewegt.
Auf wie viele Möglichkeiten kommt man da? Mehr als beim Schach? Gibt es nicht sogar unendlich viele Möglichkeiten, wie so ein Spiel verlaufen kann?
Sollte das am Ende sogar der Grund sein, warum sich mehr Leute für Fußball als für Schach interessieren ???
|
|
|
| |
|
hallo rabilein,
du magst ja Recht haben
darin sehe ich aber keinen Grund, in meiner zweiten
Lebenshälfte plötzlich noch zum Fussballfan zu mutieren
|
|
|
| |
|
Hallo rabilein und andere Spiele-Fans,
Vielleicht können wir hier im MatheRaum aus deiner
Idee tatsächlich ein neues Spiel entwickeln, das
durchaus mit den vertrauten Brettspielen mithalten
kann und auch keine "langweilige Phase" hat.
mit ein paar Ideen dazu eröffne ich einen neuen Thread
Gruß Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:46 Mo 22.12.2008 | | Autor: | reverend |
Hallo,
ich verfolge diese Diskussion schon seit einiger Zeit und möchte auch noch meinen Senf dazugeben. Manches ist davon schon gesagt; wenn ich es wiederhole, dann nur, weil mir die Zusammenstellung neu erscheint.
Die Zeit meiner Sudoku-Manie ist vorbei. Noch vor zwei Jahren habe ich jeden Tag einige gelöst und war immer auf der Suche nach höheren Schwierigkeitsgraden. Rätsel, die "backtracking" erforderten, habe ich dabei immer gehasst. Meistens aber lag es daran, dass mir ein möglicher logischer Schluss noch nicht ersichtlich war.
In der mittlerweile erheblich angewachsenen Sudoku-Sekundärliteratur - meist allerdings nur Einleitungen zu den "schwierigeren" Sammlungen - finden sich insbesondere im Umgang mit "Kandidatenlisten" einige absonderliche Beschreibungen. Selbst beim Lösen der sog. "diabolischen" Sudokus (oder wie auch immer die höchste Schwierigkeitsstufe heißen mag) haben mir bisher die auf brainbashers.com beschriebenen [url:http://www.brainbashers.com/sudokuhelp.asp] Lösungstechniken [/url] fast immer genügt. Sudokus, die mit diesen Mitteln zu lösen sind, löse ich mit Anzeigeassistent innerhalb von typischerweise weniger als 10 Minuten, auf Papier kann es dann doch eine gute halbe Stunde dauern.
Allerdings gibt es immer wieder einmal Sudokus, die sich dieser Zugangsweise entziehen. Im glücklichsten Fall gibt es z.B. irgendwo ein Feld mit nur noch zwei oder drei Kandidaten, die man der Reihe nach durchgehen kann, so dass sich für den untersuchten Fall ein Widerspruch ergibt - oder nicht. So kann die Liste verkleinert werden, und man kommt zum Ergebnis, ohne vorläufige Zahlen wieder ausradieren zu müssen.
Im Kontakt mit einem Sudokuproduzenten habe ich in der Tat das erfahren, was hier schon vermutet wurde: ausgehend von einem vollständig ausgefüllten Sudoku werden rückwärts gehend einzelne Zahlen entfernt. Jedesmal wird zugleich überprüft, mit welcher Argumentation die Zahl wiederzugewinnen ist. Hieraus ist der Schwierigkeitsgrad gut zu bestimmen. Löschungsfolgen, die mit einfachsten Mitteln zu rekonstruieren sind, werden dabei bei den höchsten Schwierigkeitsgraden weitestgehend vermieden oder doch so kurz gehalten wie möglich. Der Rechenaufwand für die Erstellung des eigentlichen Rätsels ist deutlich höher als der für die Erstellung der vollständigen Lösung, die mit recht einfachen Algorithmen erzeugt werden kann. Letztlich genügt m.W. ein Sudoku, um alle anderen daraus zu rekonstruieren, durch Zeilen- und Spaltentausch (sehr mühsam wegen der Nebenbedingungen), Drehung, Spiegelung und/oder durch Permutation der Ziffern (alle jederzeit beliebig anwendbar).
Die Zahl der vorgegebenen Ziffern ist übrigens im wesentlichen Augenwischerei. Es gibt Verlage, die Rätsel mit nur 21-22 Vorgaben als superschwer verkaufen, aber sobald man die erste Zahl gefunden hat, rattern gleich 12 bis 15 weitere hinterher, und danach sinkt der Schwierigkeitsgrad enorm. Andere haben dafür manchmal 32,34 Vorgaben und man bekommt kaum ein Bein auf die Erde bzw. eine Zahl aufs Papier - und selbst wenn, ist die nächste in schier unerreichbarer Ferne.
Dass der Ansatz dieser Rätselform gerade bei der Beschränkung auf bestimmte Lösungsmethoden (will heißen: logische Argumentation aufgrund bestimmter Muster) irgendwann an Reiz verliert, versteht sich von selbst. Immerhin ist es eine gute Möglichkeit, Zeit mit logischem Denken totzuschlagen, und dabei ja auch eine Tätigkeit, die sich jederzeit unterbrechen lässt.
Das vorgeschlagene "Schadoku" gibt es m.W. schon in verschiedenen Varianten - auch die Spieleerfinder sind ja längst auf die Sudoku-Welle eingestiegen, und ich meine, eine solche Spielbeschreibung schon mehrmals gelesen zu haben.
Übrigens gibt es ja inzwischen eine ganze Flut von "japanischen" Zahlenspielen - Bahnhofskioske sind voll davon. Für die, die gern rechnen, bietet sich "Kakuro" an, und mir gefallen gerade die Rätsel unter dem Namen "Futoshiki", auch wenn da ein Ende schnell absehbar ist. Hat man erstmal hundert (schwierigere) gelöst, sind weitere nicht mehr sehr spannend.
Liebe Grüße,
reverend
|
|
|
| |
|
> Letztlich genügt m.W. ein Sudoku, um alle anderen daraus zu
> rekonstruieren, durch Zeilen- und Spaltentausch (sehr
> mühsam wegen der Nebenbedingungen), Drehung, Spiegelung
> und/oder durch Permutation der Ziffern (alle jederzeit
> beliebig anwendbar).
Hallo reverend,
ich denke, dass diese Vermutung doch ziemlich
viel zu kurz (oder im Gegenteil viiiel zu weit)
greift. Nach Russell und Jarvis gibt es
immerhin noch einige Milliarden, nämlich
$\ 5'472'730'538$ unterscheidbare Sudokus, auch wenn
man alle möglichen Symmetrien in Betracht
zieht und eliminiert. Für allfällige Fragen
nach den Details hinter dieser Zahl müsste
ich Dich aber an die Autoren verweisen !
Lieben Gruß ! Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:16 So 21.12.2008 | | Autor: | froopkind |
Soweit ich weiß (hab das jetzt nicht mehr genauer nachgeschaut) kommen die Sudokus nicht wie viele denken aus einer fernöstlichen Kultur und aus einer längst vergangenen Zeit, sondern von einem älteren Herren aus England aus den achtzigern des letzten Jahrhunderts.
Dieser Herr hat einen Algorithmus entworfen, welcher Sudokus beliebigen Schwierigkeitsgrades generiert. Basieren tut das ganze auf den Lateinischen Quadraten von Herrn Euler.
Diese Software hat er dann günstig an diverse Zeitungsverlage verkauft. Das hat den Wahn ausgelöst.
Einfach mal "sudoku geschichte" googlen (2. Eintrag)
mfg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:18 Mo 22.12.2008 | | Autor: | Dath |
Ja, solche Sudokus kenne ich, die sind schrecklich. Einmal musste ich bei der letzten Zahl feststellen, dass es nicht aufging. Ach ja, wie schnell kannst du eigentlich den "Zauberwürfel" lösen? Würde mich 'mal interessieren.
|
|
|
| |
|
> wie schnell kannst du eigentlich den "Zauberwürfel" lösen?
das müsste ich erst wieder fast von Grund auf lernen ...
spüre aber im Moment keinerlei Bedürfnis dazu
Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:14 Mo 22.12.2008 | | Autor: | Dath |
Verstehe ich :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:21 Mo 22.12.2008 | | Autor: | froopkind |
Die Eve aus Wall-E schlägst du eh nicht
Bin nur froh, dass die dinger sich nach diesem Film nicht wieder neu verbreiten... Wir hatten sie schon fast ausgerottet...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:03 So 28.12.2008 | | Autor: | Dath |
Ich habe gehört, dass in den USA ein gewisser Chris Dzoan leben soll, der den 3er Würfel in 16s mit verb. Augen lösen kann.
Ob das wahr ist, frage ich micht schon.
|
|
|
| |
|
> Ich habe gehört, dass in den USA ein gewisser Chris Dzoan
> leben soll, der den 3er Würfel in 16s mit verb. Augen lösen
> kann.
> Ob das wahr ist, frage ich mich schon.
Es finden öffentliche Wettbewerbe statt, wo die
Bedingungen sehr wohl kontrolliert werden.
Ob dieses Beispiel zutrifft, weiss ich aber nicht.
Vielleicht war das doch nicht mit verbundenen
Augen. Für diesen Fall kursieren aber sogar
noch kürzere Zeiten.
Es gibt noch andere Disziplinen: Würfel einhändig lösen,
auch zwei gleichzeitig, Würfel untergetaucht lösen,
Würfel anstatt mit den Händen mit den Füssen drehen.
Phantasie und Ehrgeiz scheinen unbegrenzt zu sein ...
Sollte jemand Appetit auf eine mathematische Arbeit
zu Rubik's Cube haben, bitte: ![[a]](/images/paperclip.gif "Dateianhänge") Datei-Anhang
Dies scheint aber auch schon wieder kein Rekord mehr
zu sein. Tomas Rokicki behauptet, die Zahl der not-
wendigen Seitendrehungen schrittweise auf 25, 24, 23
und zuletzt auf 22 reduziert zu haben. Dafür war
aber ein immenser Einsatz von Computerleistung
und -Zeit vonnöten. So quasi als Nebenprodukt wurde
dabei gezeigt, dass es Würfelkonstellationen gibt, bei
welchen mindestens 20 Drehungen notwendig sind.
Noch ein Link: "God's Number"
Gruß
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:03 So 28.12.2008 | | Autor: | ChopSuey |
Hallo Al-Chwarizmi,
nun hab ich Appetit bekommen
Würde mich über den Dateianhang freuen, der scheint zu fehlen.
Vielen Dank.
Grüße,
ChopSuey
******Entschuldigt bitte, der Link Funktioniert nun wieder********
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:08 Mo 22.12.2008 | | Autor: | Parkan |
Sudoku besteht aus mehreren Problemen, diese Bilden zusammen "das Problem". Kein normaler Mensch kann ein Sudoku auf anhieb Lösen, das heisst keiner kann diese Probleme gleich alle aufeinmal Lösen. Deswegen teil der Mensch das große Problem auf kleine und Löst sie dann Schritt für Schritt.
Wir nehmen an es gibt
Problem 1
Problem 2
Problem 3
Hat man alle gelöst, so ist das Sudoku geschaft.
---> Problem 1 beinhaltet mehrere Unbekannte. Am Anfang ist es deswegen schwierig den richtigen Weg zu gehen. hast du es aber gelöst so sind die anderen unbekannten des Problems 1 schneller zufinden. Das ist so als ob du eine LGS mit 4 Variablen löst und dannach eints mit 3 mit 2 mit 1. Ist Problem 1 gelöst gehst du zu 2. Wieder ein LGS mit 4 Variablen.... deswegen verspürt man immer ein starkes schwanken des Schwierigkeitsgrades.
Gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:37 Do 25.12.2008 | | Autor: | kilchi |
Ich "spiele" seit einiger Zeit Sudoku. Zu beginn konnte ich mich überhaupt nicht anfreunden mit dieser Art von Gehirnakrobatik. Ich fand das eher langweilig und idiotisch.
Doch je mehr Sudoku man löst umso grösser wird das Verlangen nach dem nächsten. Ja es entwickelte sich regelrecht eine Sucht bei mir.
Man entwickelt seine eigene Strategie um noch zuerst überhaupt ein Sudoku zu lösen und dann einfach um schneller zu werden. Den Ehrgeiz lässt es wohl bei mir nicht zu, mich einfach "nur" mit dem lösen des Sudokus zufrieden zu geben, nein, es muss in einerzufriedenstellenden Zeit geschehen sein!
Irgendwie auch faszinierend, wie man mit den verschiedensten Techniken zum Ziel kommt.
Ich frage mich einfach immer wieder: Gibt es eigentlich nur den einen Lösungsweg? und kann es IMMER nur eine Lösung geben?
|
|
|
| |
|
> Ich frage mich einfach immer wieder: Gibt es eigentlich nur
> den einen Lösungsweg? und kann es IMMER nur eine Lösung
> geben?
Lösungswege für Sudokus gibt es verschiedene.
Dass es immer nur eine Lösung gibt, gehört zur
Definition des Sudokus: Ein Sudoku ist nur dann
ein richtiges Sudoku, wenn es eine und nur
eine bestimmte Lösung hat.
Würde man einfach so um die 20 Ziffern rein zufällig
(und natürlich ohne offensichtliche grobe Verstösse
gegen die Sudoku-Regeln) auf dem Feld verteilen,
so kämen in den allermeisten Fällen unlösbare
"Pseudo-Sudokus" heraus oder aber solche, bei
welchen es verschiedene Lösungen gäbe. All dies
sind keine regelgemässen Sudokus.
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:50 Do 01.01.2009 | | Autor: | rabilein1 |
> Dass es immer nur eine Lösung gibt, gehört zur
> Definition des Sudokus: Ein Sudoku ist nur dann
> ein richtiges Sudoku, wenn es eine und nur
> eine bestimmte Lösung hat.
>
> Würde man einfach so um die 20 Ziffern rein zufällig
> (und natürlich ohne offensichtliche grobe Verstösse
> gegen die Sudoku-Regeln) auf dem Feld verteilen,
> so kämen in den allermeisten Fällen unlösbare
> "Pseudo-Sudokus" heraus oder aber solche, bei
> welchen es verschiedene Lösungen gäbe. All dies
> sind keine regelgemässen Sudokus.
In einem Heft habe ich sowohl ein Sudoku mit bereits 25 ausgefüllten Zahlen als auch eines mit 38 bereits ausgefüllten Zahlen gefunden.
Angeblich handelt es sich bei beiden um "richtige" Sudokus.
Meine Fragen:
a) Gibt es eine Mindest-Anzahl von Feldern, die ausgefüllt sein müssen? Und wie müssen die dann verteilt sein?
b) Wenn man bei dem 38er Feld irgend welche (sagen wir 5) Zahlen willkürlich unkenntlich machen würde, würde es dann immer noch ein "richtiges" Sudoku ergeben?
Mit anderen Worten: Sind die meisten bereits vorgegebenen Zahlen redundant (zu deutsch: überflüssig) und sollen lediglich das Lösen erleichtern?
|
|
|
| |
|
Hallo Ralph,
zuerst mal alles Gute zum neuen Jahr !
> In einem Heft habe ich sowohl ein Sudoku mit bereits 25
> ausgefüllten Zahlen als auch eines mit 38 bereits
> ausgefüllten Zahlen gefunden.
>
> Angeblich handelt es sich bei beiden um "richtige"
> Sudokus.
>
>
> Meine Fragen:
> a) Gibt es eine Mindest-Anzahl von Feldern, die ausgefüllt
> sein müssen? Und wie müssen die dann verteilt sein?
So viel ich weiss, gelten Sudokus mit 17 aus-
gefüllten Feldern als "Minimal-Sudokus".
Siehe z.B. da.
Meines Wissens ist aber bisher nicht bewiesen,
dass die Mindestzahl der ausgefüllten Felder
wirklich gleich 17 ist. Möglicherweise könnte
sie noch kleiner sein.
Die geometrische Verteilung der ausgefüllten
Felder kann sicher auch bei Minimalsudokus
sehr unterschiedlich sein.
Was ich aber sicher weiss ist, dass solche
"Minimal-Sudokus" nicht unbedingt schwierig
sein müssen. Ich habe mehrere davon gelöst,
ohne irgendwelche Notizen zu machen, was
ich bei wirklich schwierigen Sudokus immer
muss.
Dass 17 ausgefüllte Felder genügen können,
bedeutet auch nicht, dass man bei einem
Sudoku mit z.B. 25 vorgegebenen Zahlen stets
noch welche weglassen könnte, ohne die ein-
deutige Lösbarkeit zu verlieren.
> b) Wenn man bei dem 38er Feld irgend welche (sagen wir 5)
> Zahlen willkürlich unkenntlich machen würde, würde es dann
> immer noch ein "richtiges" Sudoku ergeben?
Eine genaue Antwort auf diese Frage könnte
sich sehr schwierig gestalten. Ich würde eher
ein Nein vermuten, wenn irgendwelche 38-er
Sudokus zugelassen sind und beliebige 5 Felder
gelöscht werden dürfen.
> Mit anderen Worten: Sind die meisten bereits vorgegebenen
> Zahlen redundant (zu deutsch: überflüssig) und sollen
> lediglich das Lösen erleichtern?
Bei den Heftchen-Sudokus der leichtesten Levels
dürfte dies der Fall sein.
Gruß Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:53 Fr 02.01.2009 | | Autor: | rabilein1 |
Hallo Al-Chwarizmi, dir auch alles Gute zum Neuen Jahr.
Du sprachst ja mal von "richtigen" Sudokus, also solchen, die nur eine einzige Lösung zulassen.
Mal angenommen, man würde dir ein "unrichtiges" Sudoku vorlegen (mehrere mögliche Lösungen), ohne dir vorher zu sagen, dass es "unrichtig" ist.
Denkst du, dass du dadurch größere Schwierigkeiten beim Lösen hättest, da du ja nach der einzigen Lösung suchst, oder würde das Lösen eher schneller gehen, da es ja mehrere richtige Lösungen gibt?
|
|
|
| |
|
> Hallo Al-Chwarizmi, dir auch alles Gute zum Neuen Jahr.
>
> Du sprachst ja mal von "richtigen" Sudokus, also solchen,
> die nur eine einzige Lösung zulassen.
>
> Mal angenommen, man würde dir ein "unrichtiges" Sudoku
> vorlegen (mehrere mögliche Lösungen), ohne dir vorher zu
> sagen, dass es "unrichtig" ist.
> Denkst du, dass du dadurch größere Schwierigkeiten beim
> Lösen hättest, da du ja nach der einzigen Lösung suchst,
> oder würde das Lösen eher schneller gehen, da es ja mehrere
> richtige Lösungen gibt?
Beim Lösen geht man ja üblicherweise so vor,
dass man nur Einsetzungen macht, die durch
die aktuelle Konstellation "erzwungen" sind,
vielleicht über diverses "um-die-Ecke-denken".
Bei einem mehrdeutigen Spiel käme man
irgendwann an den Punkt, wo man damit
nicht mehr weiter käme. Dann würde man
versuchen, einzelne Felder zufällig zu besetzen
und zu schauen, was sich daraus ergibt. Wenn
aber dieses probeweise Ausfüllen immer wieder
in die Leere führen würde, hätte das früher
oder später einen erheblichen Anstieg des
Adrenalinspiegels, die Zerstörung des Heftchens
und möglicherweise andere Kollateralschäden
zur Folge.
lieben Gruß Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:07 Fr 02.01.2009 | | Autor: | rabilein1 |
Deine Antwort finde ich sehr interessant und aufschlussreich (ich meine damit nicht die Kollateralschäden).
Das erinnert mich an das Lösen von "Drei Gleichungen mit vier Unbekannten". Nur erkennt man dort die Nicht-Eindeutigkeit sofort, so dass Kollateralschäden auszuschließen sind.
Was ich an deiner Antwort verwunderlich finde, ist eigentlich nur:
Wie kommst du eigentlich darauf, dass jedes im Heftchen abgedruckte Sudoku "richtig" sein muss?
a) Weil das im Kleingedruckten steht?
b) Weil das schon immer so war?
c) .... ?
|
|
|
| |
|
> Deine Antwort finde ich sehr interessant und
> aufschlussreich (ich meine damit nicht die
> Kollateralschäden).
>
> Das erinnert mich an das Lösen von "Drei Gleichungen mit
> vier Unbekannten". Nur erkennt man dort die
> Nicht-Eindeutigkeit sofort, so dass Kollateralschäden
> auszuschließen sind.
>
> Was ich an deiner Antwort verwunderlich finde, ist
> eigentlich nur:
> Wie kommst du eigentlich darauf, dass jedes im Heftchen
> abgedruckte Sudoku "richtig" sein muss?
>
> a) Weil das im Kleingedruckten steht?
> b) Weil das schon immer so war?
> c) .... ?
Hallo rabilein,
a) 1. In einem sorgfältig konzipierten Sudoku-Heftchen
sollte dies eigentlich wenigstens im Kleingedruckten
stehen.
2. Es ist anzunehmen, dass die Verleger selber nicht
in der Lage sind, selber Sudokus zu entwerfen und
demzufolge Kunden von Firmen sind, deren Computer
nur "richtige" Sudokus liefern.
b) Glücklicherweise war das wenigstens bisher so.
Ich würde den Vertreibern von Sudoku-Heftchen
dringend davon abraten, ohne Vorwarnung mehr-
deutige Sudokus auf die ohnehin schon geplagte
Menschheit loszulassen.
Falls sie dies jemals planen sollten, würde ich
empfehlen, dies nur mit einer Warnung analog
zu jenen auf Zigarettenpackungen zu tun.
Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:17 Fr 02.01.2009 | | Autor: | rabilein1 |
> Ich würde den Vertreibern von Sudoku-Heftchen
> dringend davon abraten, ohne Vorwarnung mehr-
> deutige Sudokus auf die ohnehin schon geplagte
> Menschheit loszulassen.
So wie du das beschreibst...
Bestimmt liegen solche Heftchen schon massenweise in den Arsenalen der Militärs, um sie dann über feindlichem Gebiet abzuwerfen und den Gegner damit in den Wahnsinn zu treiben...
|
|
|
| |
|
> > Ich würde den Vertreibern von Sudoku-Heftchen
> > dringend davon abraten, ohne Vorwarnung mehr-
> > deutige Sudokus auf die ohnehin schon geplagte
> > Menschheit loszulassen.
>
> So wie du das beschreibst...
> Bestimmt liegen solche Heftchen schon massenweise in den
> Arsenalen der Militärs, um sie dann über feindlichem Gebiet
> abzuwerfen und den Gegner damit in den Wahnsinn zu
> treiben...
Zugegeben: ich bin noch am Üben prägnanter
Ausdrucksweisen - aber gerade so habe ich mir
das eigentlich nicht vorgestellt. Den kalten und
den weniger kalten Krieg lassen wir mal besser
hinter uns - vielleicht haben wir ja noch eine
Chance auf einen wohltemperierten Frieden vor
uns, wenn wir uns alle dafür Mühe geben ...
Liebe Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:07 Sa 28.02.2009 | | Autor: | hase-hh |
Moin,
ich habe hier einige Beiträge gelesen, und möchte dazu folgendes sagen.
Sudoku, denke ich, wird man - wie andere Spiele auch - totrechnen können. Wäre vielleicht mal interessant, die Anzahl der theoretisch denkbaren Alternativen auszurechnen. (Man glaubt ja auch, bei Kreuzworträtseln, immer wieder ein anderes zu machen, aber weiss man das?)
Der Schwierigkeitsgrad von Sudokus ist sicher abhängig von der Anzahl der vorgegebenen Zahlen und der Kombination der gegebenen Zahlen.
Ich kann es - aus eigener Erfahrung - gut nachvollziehen, dass es frustrierend ist, einen Versuch nach 29-Zügen scheitern zu sehen. Und es scheinbar zeitweise komplexer wird...
Schach, das auf Minimierung der Chancen des Gegners beruht, ist inzwischen hart an der Grenze, von Computern "tot gemacht" zu werden, wenn kein Mensch einen Computer mehr schlagen kann.
Und ich habe einen Programmierer kennen gelernt,der ein Schachprogramm entwickelt hat, das wesentlich besser spielte als er (vor ca. 20 Jahren bereits fast Großmeisterstärke hatte), obwohl dieser kaum etwas vom Schach verstand. Das ist nicht immer die absolute Begrenzung.
Wenn auch das Bewusstsein, selbstverständlich die Wichtigste Einflußgröße ist.
Wie sagte Einstein: Man sieht nur,was man weiß.
Denn die Kernfrage betrifft mehr das Spirituelle.
Kosmos ist eben mehr, als logisches Denken, mehr als Aristotelische Logik, mehr als ein bisschen Quantentheorie. Und wie sonst? Wir stehen doch noch ganz am Anfang. Und Kosmos wandelt sich ständig.
Und daher wirst du die Antwort auch nur in dir finden, im Geist.
lg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:01 Do 26.03.2009 | | Autor: | Dath |
Auf jeden Fal abhängig von der Anzahl, aber auch der Position der Zahlen, und um welche es sich handelt. Wenn man z.b. 36 Zahlen gegeben hat, baer nur Zahlen 1;2;3;4, dann ist das Sudok doch schon ein Stück kanckiger.
Ich hoffe ich verstoße gegen keine Forumsregel, wenn ich diesen Link reinstelle:
http://www.freeware.de/download/sudoku-sudogu_30384.html
Das ist ein recht schönes Programm
1. zum Lösen von Sudokus
2. zum Erstellen " ---"----
|
|
|
|
