Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Permutationen und Freiheitsgrade bei Sudoku
397 views
Skip to first unread message
Marcus Glöder
Aug 23, 2013, 12:37:53 AM8/23/13
to
Hallo alle zusammen,
in meiner Freizeit spiele ich gerne Sudoku und mir ist ein kleines
Problem eingefallen, mit dem ich mich gerade beschäftige. Eigentlich
geht es dabei um zwei verschiedene Fragestellungen:
1.
Wieviele verschiedene gelöste Sudokus sind bei einer gegebenen
Sudoku-Größe (Anzahl der Zeilen, Spalten und Quadranten) möglich (Anzahl
der Permutationen,[1] die der Regel entsprechen, dass jede Ziffer pro
Zeile, Spalte und Quadrant genau einmal vorkommen muss)?
2.
Wieviele Zellen müssen bei einem Sudoku gegebener Größe mindestens
vorgegeben werden, damit alle anderen Zellen determiniert und das Sudoku
damit eindeutig lösbar ist (Anzahl der Freiheitsgrade[2])?
Zusatzfrage: wie müssen die vorgegebenen Zellen verteilt sein, damit
möglichst wenig davon benötigt werden? Oder spielt das keine Rolle?
Das kleinste mögliche Sudoku hat 4x4=16 Felder. Die vier Quadranten
benenne ich jetzt mal so:
ab
cd
und die Felder so:
a1 a2 b1 b2
a3 a4 b3 b4
c1 c2 d1 d2
c3 c4 d3 d4
Die Felder habe ich also nach den Quadranten benannt, in denen sie
liegen. Bei anderen Sudoku-Größen, beispielsweise mit 6x6, 9x9
(Standard) oder 16x16 Feldern, erfolgt die Benennung dann entsprechend.[3]
Im kleinsten Fall, einem 4x4-Sudoku, sind beide Fragen ohne viel
Mathematik noch recht einfach zu bestimmen. Was die Freiheitsgrade
betrifft, so sind das 4, nämlich 1 Freiheitsgrad in jedem Quadrant. Die
Anzahl der Permutationen lässt sich sukzessive bestimmen, sozusagen
Quadrant für Quadrant. Wenn ich bei Quadrant a anfange, dann hat dieser
Quadrant für sich genommen 1*2*3*4=4!=24 Permutationen. In Quadrant b
gibt es jetzt in der oberen Zeile (Zellen b1 und b2) zwei Permutationen,
weil durch die Zellen a1 und a2 schon zwei Ziffern vergeben sind, und in
der unteren Zeile (Zellen b3 und b4) aus demselben Grund (durch die
Zellen a3 und a4 sind schon zwei Ziffern, nämlich die beiden, die in den
Zellen a1 und a2 nicht stehen, vergeben) ebenfalls zwei, macht zusammen
also vier Permutationen in Quadrant b. Ganz entsprechend ist das bei
Quadrant c. Auch hier habe ich, aus demselben Grund, wie bei Quadrant b,
vier Permutationen. Wenn die Quadranten b und c festgelegt sind, ist
Quadrant d determiniert. Es gibt also (wenn ich das richtig sehe) in
einem 4x4-Sudoku
4!*(2*2!)*(2*2!)=24*4*4=384
Permutationen. Soweit ist das alles ganz einfach. Wie sieht es aber bei
größeren Sudokus (wie 6x6, 9x9 oder 16x16) aus? Kann die demonstrierte
Vorgehensweise im Prinzip übertragen werden und was wäre ggf. zu beachten?
Viele Grüße
Marcus
–––>
Eine Randbemerkung sei mir gestattet. Mir ist aufgefallen, dass es in
dieser NG offenbar seit Jahren gut gepflegte Feindschaften, mit
ellenlangen Flamewars und einem etwas ruppigen Ton (um das mal so zu
sagen) gibt. Deshalb möchte ich vorsichtshalber sagen, dass Diskussionen
über »binäre Bäume« oder »Matheologie« hier wirklich /off topic/ sind
und bitte in andere Threads verlagert werden sollten.
<–––
Anmerkungen
[1]
Vgl. http://de.wikipedia.org/wiki/Permutation#Permutation_ohne_Wiederholung
[2]
Das Wort »Freiheitsgrade« habe ich aus einem anderen Zusammenhang
geklaut, nämlich dem Chi-Quadrat-Test. Dabei geht es um die Anzahl von
Zellen in einer Kreuztabelle, die bei gegebenen Randverteilungen relativ
(in den Grenzen, die die Randverteilungen vorgeben) frei festgelegt
werden können, bevor alle anderen Zellen determiniert sind.
Vierfeldertafeln haben 1 Freiheitsgrad, 3x3-Tabellen 4 Freiheitsgrade
usw. Allgemein ist in diesem Zusammenhang (Chi-Quadrat-Test) die Anzahl
der Freiheitsgrade df = (r-1)*(c-1), wenn r die Anzahl der Zeilen und c
die Anzahl der Spalten ist. Vgl. dazu beispielsweise Borz 2005:173,
Claus/Ebner 1968:239–240 oder Sahner 1982:135
[3]
6x6 ist eine Art Zwischengröße, die ich auf der Kinderseite der
Rheinischen Post gesehen habe. Dabei sind die Quadranten nicht
quadratisch, sondern haben zwei Zeilen und drei Spalten. Es liegen zwei
Quadranten nebeneinander und drei Quadranten untereinander. Das Ganze
sieht also so aus:
a1 a2 a3 b1 b2 b3
a4 a5 a6 b4 b5 b6
c1 c2 c3 d1 d2 d3
c4 c5 c6 d4 d5 d6
e1 e2 e3 f1 f2 f3
e4 e5 e6 f4 f5 f6
Literatur
Bortz, Jürgen, (6)2005: Statistik für Human- und Sozialwissenschaftler.
Heidelberg: Springer
Claus, Günter und Heinz Ebner, 1968: Grundlagen der Statistik für
Psychologen, Pädagogen und Soziologen. Berlin: Volk und Wissen
Sahner, Heinz, (2)1982; Statistik für Soziologen 2. Schließende
Statistik. (= Teubner Studienskripten 23) Stuttgart: Teubner
--
PMs an: m.gl...@gmx.de
in meiner Freizeit spiele ich gerne Sudoku und mir ist ein kleines
Problem eingefallen, mit dem ich mich gerade beschäftige. Eigentlich
geht es dabei um zwei verschiedene Fragestellungen:
1.
Wieviele verschiedene gelöste Sudokus sind bei einer gegebenen
Sudoku-Größe (Anzahl der Zeilen, Spalten und Quadranten) möglich (Anzahl
der Permutationen,[1] die der Regel entsprechen, dass jede Ziffer pro
Zeile, Spalte und Quadrant genau einmal vorkommen muss)?
2.
Wieviele Zellen müssen bei einem Sudoku gegebener Größe mindestens
vorgegeben werden, damit alle anderen Zellen determiniert und das Sudoku
damit eindeutig lösbar ist (Anzahl der Freiheitsgrade[2])?
Zusatzfrage: wie müssen die vorgegebenen Zellen verteilt sein, damit
möglichst wenig davon benötigt werden? Oder spielt das keine Rolle?
Das kleinste mögliche Sudoku hat 4x4=16 Felder. Die vier Quadranten
benenne ich jetzt mal so:
ab
cd
und die Felder so:
a1 a2 b1 b2
a3 a4 b3 b4
c1 c2 d1 d2
c3 c4 d3 d4
Die Felder habe ich also nach den Quadranten benannt, in denen sie
liegen. Bei anderen Sudoku-Größen, beispielsweise mit 6x6, 9x9
(Standard) oder 16x16 Feldern, erfolgt die Benennung dann entsprechend.[3]
Im kleinsten Fall, einem 4x4-Sudoku, sind beide Fragen ohne viel
Mathematik noch recht einfach zu bestimmen. Was die Freiheitsgrade
betrifft, so sind das 4, nämlich 1 Freiheitsgrad in jedem Quadrant. Die
Anzahl der Permutationen lässt sich sukzessive bestimmen, sozusagen
Quadrant für Quadrant. Wenn ich bei Quadrant a anfange, dann hat dieser
Quadrant für sich genommen 1*2*3*4=4!=24 Permutationen. In Quadrant b
gibt es jetzt in der oberen Zeile (Zellen b1 und b2) zwei Permutationen,
weil durch die Zellen a1 und a2 schon zwei Ziffern vergeben sind, und in
der unteren Zeile (Zellen b3 und b4) aus demselben Grund (durch die
Zellen a3 und a4 sind schon zwei Ziffern, nämlich die beiden, die in den
Zellen a1 und a2 nicht stehen, vergeben) ebenfalls zwei, macht zusammen
also vier Permutationen in Quadrant b. Ganz entsprechend ist das bei
Quadrant c. Auch hier habe ich, aus demselben Grund, wie bei Quadrant b,
vier Permutationen. Wenn die Quadranten b und c festgelegt sind, ist
Quadrant d determiniert. Es gibt also (wenn ich das richtig sehe) in
einem 4x4-Sudoku
4!*(2*2!)*(2*2!)=24*4*4=384
Permutationen. Soweit ist das alles ganz einfach. Wie sieht es aber bei
größeren Sudokus (wie 6x6, 9x9 oder 16x16) aus? Kann die demonstrierte
Vorgehensweise im Prinzip übertragen werden und was wäre ggf. zu beachten?
Viele Grüße
Marcus
–––>
Eine Randbemerkung sei mir gestattet. Mir ist aufgefallen, dass es in
dieser NG offenbar seit Jahren gut gepflegte Feindschaften, mit
ellenlangen Flamewars und einem etwas ruppigen Ton (um das mal so zu
sagen) gibt. Deshalb möchte ich vorsichtshalber sagen, dass Diskussionen
über »binäre Bäume« oder »Matheologie« hier wirklich /off topic/ sind
und bitte in andere Threads verlagert werden sollten.
<–––
Anmerkungen
[1]
Vgl. http://de.wikipedia.org/wiki/Permutation#Permutation_ohne_Wiederholung
[2]
Das Wort »Freiheitsgrade« habe ich aus einem anderen Zusammenhang
geklaut, nämlich dem Chi-Quadrat-Test. Dabei geht es um die Anzahl von
Zellen in einer Kreuztabelle, die bei gegebenen Randverteilungen relativ
(in den Grenzen, die die Randverteilungen vorgeben) frei festgelegt
werden können, bevor alle anderen Zellen determiniert sind.
Vierfeldertafeln haben 1 Freiheitsgrad, 3x3-Tabellen 4 Freiheitsgrade
usw. Allgemein ist in diesem Zusammenhang (Chi-Quadrat-Test) die Anzahl
der Freiheitsgrade df = (r-1)*(c-1), wenn r die Anzahl der Zeilen und c
die Anzahl der Spalten ist. Vgl. dazu beispielsweise Borz 2005:173,
Claus/Ebner 1968:239–240 oder Sahner 1982:135
[3]
6x6 ist eine Art Zwischengröße, die ich auf der Kinderseite der
Rheinischen Post gesehen habe. Dabei sind die Quadranten nicht
quadratisch, sondern haben zwei Zeilen und drei Spalten. Es liegen zwei
Quadranten nebeneinander und drei Quadranten untereinander. Das Ganze
sieht also so aus:
a1 a2 a3 b1 b2 b3
a4 a5 a6 b4 b5 b6
c1 c2 c3 d1 d2 d3
c4 c5 c6 d4 d5 d6
e1 e2 e3 f1 f2 f3
e4 e5 e6 f4 f5 f6
Literatur
Bortz, Jürgen, (6)2005: Statistik für Human- und Sozialwissenschaftler.
Heidelberg: Springer
Claus, Günter und Heinz Ebner, 1968: Grundlagen der Statistik für
Psychologen, Pädagogen und Soziologen. Berlin: Volk und Wissen
Sahner, Heinz, (2)1982; Statistik für Soziologen 2. Schließende
Statistik. (= Teubner Studienskripten 23) Stuttgart: Teubner
--
PMs an: m.gl...@gmx.de
Bergholt Stuttley Johnson
Aug 23, 2013, 5:27:46 AM8/23/13
to
Ein paar Antworten findest du in:
http://www.amazon.de/dp/0199756562
--
fix$(<$>)<$>(:)<*>((<$>((:[])<$>))(=<<)<$>(*)<$>(>>=)(+)($))$1
http://www.amazon.de/dp/0199756562
--
fix$(<$>)<$>(:)<*>((<$>((:[])<$>))(=<<)<$>(*)<$>(>>=)(+)($))$1
Marcus Glöder
Aug 23, 2013, 5:58:37 AM8/23/13
to
Am 23.08.2013 11:27, schrieb Bergholt Stuttley Johnson:
> Ein paar Antworten findest du in:
> http://www.amazon.de/dp/0199756562
Hallo Bergolt,
> Ein paar Antworten findest du in:
> http://www.amazon.de/dp/0199756562
vielen Dank f�r den Link. Jetzt stellt sich mir nur noch die Frage: Gibt
es das Buch vielleicht auch auf Deutsch? Mein Englisch ist n�mlich
inzwischen ziemlich eingerostet. Aber auch wenn nicht: zulegen werde ich
mir das. :-)
Nochmal Danke und Viele Gr��e
Marcus
--
PMs an: m.gl...@gmx.de
Hans-Peter Diettrich
Aug 23, 2013, 7:01:45 AM8/23/13
to
Marcus Glöder schrieb:
> Wenn die Quadranten b und c festgelegt sind, ist
> Quadrant d determiniert.
In einem 9*9 Sudoku kann es passieren, daß man erst mit den letzten zwei
Ziffern Probleme bekommt. Alles übrige paßt, nur diese beiden nicht
mehr. Es dürfte also weniger gültige Lösungen als Permutationen geben.
Literaturhinhweise hast Du ja schon bekommen, Sudoku wurde bereits recht
intensiv wissenschaftlich beackert. Es ist schon faszinierend, wieviele
Disziplinen (außer Statistik/Kombinatorik) bei solchen Spielen von
Belang sind.
Was Deine lückenhaften Englischkenntnisse betrifft, wäre so ein Buch
eine gute Gelegenheit, diese Kenntnisse zu vertiefen, quasi zwei Fliegen
mit einer Klappe geschlagen. Ich habe Englisch eigentlich erst aus
Computer-Handbüchern gelernt, weil die deutschen Übersetzungen vor
lauter Übersetzungsfehlern oft völlig unbrauchbar waren. Wobei ich nicht
beurteilen kann, ob mathematisches Englisch ähnlich einfach ist wie
(Computer-)technisches Englisch. Zumindest hatte ich mehr von dieser
Lektüre als von meinem ganzen Englisch-Unterricht, bei dem wir zuletzt
zwar Shakespeare lesen konnten, aber keine vernünftige Unterhaltung über
ganz alltägliche Themen führen konnten.
2b|!2b? ;-)
DoDi
> Wenn die Quadranten b und c festgelegt sind, ist
> Quadrant d determiniert.
Ziffern Probleme bekommt. Alles übrige paßt, nur diese beiden nicht
mehr. Es dürfte also weniger gültige Lösungen als Permutationen geben.
Literaturhinhweise hast Du ja schon bekommen, Sudoku wurde bereits recht
intensiv wissenschaftlich beackert. Es ist schon faszinierend, wieviele
Disziplinen (außer Statistik/Kombinatorik) bei solchen Spielen von
Belang sind.
Was Deine lückenhaften Englischkenntnisse betrifft, wäre so ein Buch
eine gute Gelegenheit, diese Kenntnisse zu vertiefen, quasi zwei Fliegen
mit einer Klappe geschlagen. Ich habe Englisch eigentlich erst aus
Computer-Handbüchern gelernt, weil die deutschen Übersetzungen vor
lauter Übersetzungsfehlern oft völlig unbrauchbar waren. Wobei ich nicht
beurteilen kann, ob mathematisches Englisch ähnlich einfach ist wie
(Computer-)technisches Englisch. Zumindest hatte ich mehr von dieser
Lektüre als von meinem ganzen Englisch-Unterricht, bei dem wir zuletzt
zwar Shakespeare lesen konnten, aber keine vernünftige Unterhaltung über
ganz alltägliche Themen führen konnten.
2b|!2b? ;-)
DoDi
Detlef Müller
Aug 23, 2013, 9:13:55 AM8/23/13
to
On 23.08.2013 06:37, Marcus Glöder wrote:
> Hallo alle zusammen,
>
> in meiner Freizeit spiele ich gerne Sudoku und mir ist ein kleines
> Problem eingefallen, mit dem ich mich gerade beschäftige. Eigentlich
> geht es dabei um zwei verschiedene Fragestellungen:
>
> 1.
> Wieviele verschiedene gelöste Sudokus sind bei einer gegebenen
> Sudoku-Größe (Anzahl der Zeilen, Spalten und Quadranten) möglich (Anzahl
> der Permutationen,[1] die der Regel entsprechen, dass jede Ziffer pro
> Zeile, Spalte und Quadrant genau einmal vorkommen muss)?
>
...
> Hallo alle zusammen,
>
> in meiner Freizeit spiele ich gerne Sudoku und mir ist ein kleines
> Problem eingefallen, mit dem ich mich gerade beschäftige. Eigentlich
> geht es dabei um zwei verschiedene Fragestellungen:
>
> 1.
> Wieviele verschiedene gelöste Sudokus sind bei einer gegebenen
> Sudoku-Größe (Anzahl der Zeilen, Spalten und Quadranten) möglich (Anzahl
> der Permutationen,[1] die der Regel entsprechen, dass jede Ziffer pro
> Zeile, Spalte und Quadrant genau einmal vorkommen muss)?
>
> Das kleinste mögliche Sudoku hat 4x4=16 Felder. Die vier Quadranten
> benenne ich jetzt mal so:
>
> ab
> cd
>
> und die Felder so:
>
> a1 a2 b1 b2
> a3 a4 b3 b4
>
> c1 c2 d1 d2
> c3 c4 d3 d4
>
> Die Felder habe ich also nach den Quadranten benannt, in denen sie
> liegen. Bei anderen Sudoku-Größen, beispielsweise mit 6x6, 9x9
> (Standard) oder 16x16 Feldern, erfolgt die Benennung dann entsprechend.[3]
>
> Im kleinsten Fall, einem 4x4-Sudoku, sind beide Fragen ohne viel
> Mathematik noch recht einfach zu bestimmen. Was die Freiheitsgrade
> betrifft, so sind das 4, nämlich 1 Freiheitsgrad in jedem Quadrant.
Freiheitsgrad sein soll.
Wegen 4^4=256 < 384 kann, wenn Du die Anzahl richtig berechnet
hast, durch 4 Einträge nicht alles fest gelegt sein.
> Die
> Anzahl der Permutationen lässt sich sukzessive bestimmen, sozusagen
> Quadrant für Quadrant. Wenn ich bei Quadrant a anfange, dann hat dieser
> Quadrant für sich genommen 1*2*3*4=4!=24 Permutationen. In Quadrant b
> gibt es jetzt in der oberen Zeile (Zellen b1 und b2) zwei Permutationen,
> weil durch die Zellen a1 und a2 schon zwei Ziffern vergeben sind, und in
> der unteren Zeile (Zellen b3 und b4) aus demselben Grund (durch die
> Zellen a3 und a4 sind schon zwei Ziffern, nämlich die beiden, die in den
> Zellen a1 und a2 nicht stehen, vergeben) ebenfalls zwei,
im Größeren Feld bleiben mehr Zahlen übrig, als in die Zeile
passen (hier genau die zwei anderen).
Für die k-te Zeile im zweite (n)x(n)-Sudoku-Teilkasten von oben links
sind n aus n^2-(k-1)*n verbleibenden zur nehmen, die zudem nicht in der
entsprechenden Zeile von a stehen ... das wird haarig (und das schon
beim zweiten von n^2 Kästen).
> macht zusammen
> also vier Permutationen in Quadrant b. Ganz entsprechend ist das bei
> Quadrant c. Auch hier habe ich, aus demselben Grund, wie bei Quadrant b,
> vier Permutationen. Wenn die Quadranten b und c festgelegt sind, ist
> Quadrant d determiniert. Es gibt also (wenn ich das richtig sehe) in
> einem 4x4-Sudoku
>
> 4!*(2*2!)*(2*2!)=24*4*4=384
>
"Number of (completed) sudokus (or Sudokus) of size n^2 X n^2"
unter
http://oeis.org/A107739
taucht 288 auf - nach einem Nachmittag Rechnen habe ich
auch den Fehler gefunden: man kann die Quadrate a,b,c
nicht so unabhängig von einander behandeln:
12 34
34 21
23 *#
41 **
lässt sich zum Beispiel bei # nicht ergänzen, die Wahl von
a,b schränkt die Möglichkeiten für c offenbar ein.
Gruß,
Detlef
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Detlef Müller
Aug 23, 2013, 9:38:00 AM8/23/13
to
On 23.08.2013 13:01, Hans-Peter Diettrich wrote:
> Marcus Glöder schrieb:
>
>> Wenn die Quadranten b und c festgelegt sind, ist Quadrant d determiniert.
>
> In einem 9*9 Sudoku kann es passieren, daß man erst mit den letzten zwei
> Ziffern Probleme bekommt. Alles übrige paßt, nur diese beiden nicht
> mehr. Es dürfte also weniger gültige Lösungen als Permutationen geben.
> ...
> Marcus Glöder schrieb:
>
>> Wenn die Quadranten b und c festgelegt sind, ist Quadrant d determiniert.
>
> In einem 9*9 Sudoku kann es passieren, daß man erst mit den letzten zwei
> Ziffern Probleme bekommt. Alles übrige paßt, nur diese beiden nicht
> mehr. Es dürfte also weniger gültige Lösungen als Permutationen geben.
Wobei ich mich erst von meinem Rechner (im 4x4-Fall) auf ein
Gegenbeispiel stoßen lassen musste ... das laxe
" ... ist Quadrant d determiniert" kam mir
zwar komisch vor, aber daß er auch nicht "überdeterminiert" sein
kann habe ich nach ein, zwei Proben einfach mal (fälschlicher
Weise) geglaubt.
Marcus Glöder
Aug 23, 2013, 12:00:51 PM8/23/13
to
Hallo Hans-Peter,
vielen Dank für Deine Antwort.
> Was Deine lückenhaften Englischkenntnisse betrifft, wäre so ein Buch
> eine gute Gelegenheit, diese Kenntnisse zu vertiefen, quasi zwei Fliegen
> mit einer Klappe geschlagen.
Ack. :-)
> 2b|!2b? ;-)
:-D
Es hat was gedauert, bis der Groschen gefallen ist. Wobei sich das (in
LaTeX) auch so schreiben lässt:
\[
\left(2b\right)\vee\neg\left(2b\right)
\]
> DoDi
Viele Grüße
vielen Dank für Deine Antwort.
> Was Deine lückenhaften Englischkenntnisse betrifft, wäre so ein Buch
> eine gute Gelegenheit, diese Kenntnisse zu vertiefen, quasi zwei Fliegen
> mit einer Klappe geschlagen.
> 2b|!2b? ;-)
:-D
Es hat was gedauert, bis der Groschen gefallen ist. Wobei sich das (in
LaTeX) auch so schreiben lässt:
\[
\left(2b\right)\vee\neg\left(2b\right)
\]
> DoDi
Viele Grüße
Marcus Glöder
Aug 23, 2013, 2:37:13 PM8/23/13
to
Hallo Detlef,
Dein Gegenbeispiel:
> 12 34
> 34 21
>
> 23 *#
> 41 **
ist schlagend. Vielen Dank dafür (und auch dafür, dass Du Dir die Mühe
gemacht hast, Dich einen ganzen Nachmittag lang damit zu beschäftigen).
Das zeigt, dass die Dinge auch in einem so kleinen Sudoku lange nicht so
einfach liegen, wie ich ursprünglich angenommen hatte.
> Da ist mir auch mit der Erklärung unten nicht klar, was so ein
> Freiheitsgrad sein soll.
> Wegen 4^4=256 < 384 kann, wenn Du die Anzahl richtig berechnet
> hast, durch 4 Einträge nicht alles fest gelegt sein.
Ich habe gar nicht gerechnet, sondern einfach ausprobiert, das heißt,
mit einem Kuli so ein 4x4-Sudoku auf ein Blatt Papier gezeichnet und
festgestellt, dass ich zu einem eindeutig lösbaren Sudoku komme, wenn
ich in jeden der vier Quadranten eine der vier Ziffern schreibe, und
zwar so, dass in jeder Zeile und in jeder Spalte auch nur eine Ziffer
steht. Zum Beispiel führt:
1* **
** 2*
*4 **
** *3
zu
12 34
43 21
34 12
21 43
Das nutzt jetzt sehr wahrscheinlich Besonderheiten des 4x4-Sudokus aus
(nehme ich jedenfalls an). Dass ich /nicht/ richtig gerechnet hatte,
hast Du ja schon festgestellt. Aber auch die 288 von der von Dir
verlinkten Webseite (wie immer dieser Wert zustande kommt) sind immer
noch größer als 256. Dennoch dürfte mit der von mir beschriebenen
Methode (jede Ziffer einmal, in jeder Spalte, jeder Zeile und jedem
Quadranten genau eine Ziffer) jedes 4x4-Sudoku mit 4 Ziffern vollständig
und widerspruchsfrei determiniert sein. Dass das in mindestens einem
Fall geht, habe ich gerade gezeigt. Dass es in jedem Fall geht, ist eine
(falsifizierbare) Hypothese.
Inzwischen glaube ich, dass die Frage, wieviele gelöste Sudokus
einer gegebenen Größe es gibt, allenfalls näherungsweise lösbar ist.
Sudokus der Größe n x n können als lateinische Quadrate mit n Zeilen
und n Spalten unter der zusätzlichen Bedingung, dass es auch n
Quadranten gibt, die alle n Ziffern enthalten, betrachtet werden. Bei
einem 4x4-Sudoku könnte es sein, dass die zusätzliche Bedingung bei
allen lateinischen Quadraten dieser Größe automatisch erfüllt ist. Bei
größeren Sudokus schränkt die zusätzliche Bedingung (Quadranten) die
Anzahl gültiger Permutationen ein. Nun steht aber hier:
http://de.wikipedia.org/wiki/Lateinisches_Quadrat#Anzahl_der_lateinischen_Quadrate
dass die Anzahl gültiger lateinischer Quadrate einer bestimmten
Größenordnung nur näherungsweise bestimmbar ist (was mich wirklich
überrascht; – ich hatte mit einer einfachen Formel oder einem Rechenweg
gerechnet, die das eindeutig bestimmbar machen).
Das von Bergholt empfohlene Buch werde ich mir jedenfalls zulegen.
Das interessiert mich jetzt.
> Gruß,
> Detlef
Dein Gegenbeispiel:
> 12 34
> 34 21
>
> 23 *#
> 41 **
gemacht hast, Dich einen ganzen Nachmittag lang damit zu beschäftigen).
Das zeigt, dass die Dinge auch in einem so kleinen Sudoku lange nicht so
einfach liegen, wie ich ursprünglich angenommen hatte.
> Da ist mir auch mit der Erklärung unten nicht klar, was so ein
> Freiheitsgrad sein soll.
> Wegen 4^4=256 < 384 kann, wenn Du die Anzahl richtig berechnet
> hast, durch 4 Einträge nicht alles fest gelegt sein.
mit einem Kuli so ein 4x4-Sudoku auf ein Blatt Papier gezeichnet und
festgestellt, dass ich zu einem eindeutig lösbaren Sudoku komme, wenn
ich in jeden der vier Quadranten eine der vier Ziffern schreibe, und
zwar so, dass in jeder Zeile und in jeder Spalte auch nur eine Ziffer
steht. Zum Beispiel führt:
1* **
** 2*
*4 **
** *3
zu
12 34
43 21
34 12
21 43
Das nutzt jetzt sehr wahrscheinlich Besonderheiten des 4x4-Sudokus aus
(nehme ich jedenfalls an). Dass ich /nicht/ richtig gerechnet hatte,
hast Du ja schon festgestellt. Aber auch die 288 von der von Dir
verlinkten Webseite (wie immer dieser Wert zustande kommt) sind immer
noch größer als 256. Dennoch dürfte mit der von mir beschriebenen
Methode (jede Ziffer einmal, in jeder Spalte, jeder Zeile und jedem
Quadranten genau eine Ziffer) jedes 4x4-Sudoku mit 4 Ziffern vollständig
und widerspruchsfrei determiniert sein. Dass das in mindestens einem
Fall geht, habe ich gerade gezeigt. Dass es in jedem Fall geht, ist eine
(falsifizierbare) Hypothese.
Inzwischen glaube ich, dass die Frage, wieviele gelöste Sudokus
einer gegebenen Größe es gibt, allenfalls näherungsweise lösbar ist.
Sudokus der Größe n x n können als lateinische Quadrate mit n Zeilen
und n Spalten unter der zusätzlichen Bedingung, dass es auch n
Quadranten gibt, die alle n Ziffern enthalten, betrachtet werden. Bei
einem 4x4-Sudoku könnte es sein, dass die zusätzliche Bedingung bei
allen lateinischen Quadraten dieser Größe automatisch erfüllt ist. Bei
größeren Sudokus schränkt die zusätzliche Bedingung (Quadranten) die
Anzahl gültiger Permutationen ein. Nun steht aber hier:
http://de.wikipedia.org/wiki/Lateinisches_Quadrat#Anzahl_der_lateinischen_Quadrate
dass die Anzahl gültiger lateinischer Quadrate einer bestimmten
Größenordnung nur näherungsweise bestimmbar ist (was mich wirklich
überrascht; – ich hatte mit einer einfachen Formel oder einem Rechenweg
gerechnet, die das eindeutig bestimmbar machen).
Das von Bergholt empfohlene Buch werde ich mir jedenfalls zulegen.
Das interessiert mich jetzt.
> Gruß,
> Detlef
Bergholt Stuttley Johnson
Aug 23, 2013, 3:14:43 PM8/23/13
to
Marcus Glï¿œder wrote:
>
> Inzwischen glaube ich, dass die Frage, wieviele gelï¿œste Sudokus
> einer gegebenen Grￜￜe es gibt, allenfalls nￜherungsweise lￜsbar ist.
Fï¿œr 9x9 Sudokus haben das Felgenhauer und Jarvis gelï¿œst.
Es gibt 6.670.903.752.021.072.936.960 gelï¿œste Sudokus.
http://www.afjarvis.staff.shef.ac.uk/sudoku/felgenhauer_jarvis_spec1.pdf
>
> Inzwischen glaube ich, dass die Frage, wieviele gelï¿œste Sudokus
> einer gegebenen Grￜￜe es gibt, allenfalls nￜherungsweise lￜsbar ist.
Fï¿œr 9x9 Sudokus haben das Felgenhauer und Jarvis gelï¿œst.
Es gibt 6.670.903.752.021.072.936.960 gelï¿œste Sudokus.
http://www.afjarvis.staff.shef.ac.uk/sudoku/felgenhauer_jarvis_spec1.pdf
Sam Sung
Aug 23, 2013, 5:44:34 PM8/23/13
to
Bergholt Stuttley Johnson schrieb:
> Marcus Gl�der wrote:
>>
>> Inzwischen glaube ich, dass die Frage, wieviele gel�ste Sudokus
>> einer gegebenen Gr��e es gibt, allenfalls n�herungsweise l�sbar ist.
>
> F�r 9x9 Sudokus haben das Felgenhauer und Jarvis gel�st.
> Es gibt 6.670.903.752.021.072.936.960 gel�ste Sudokus.
>
> http://www.afjarvis.staff.shef.ac.uk/sudoku/felgenhauer_jarvis_spec1.pdf
Sch�n!
-
Von der Ableitung zum System
Ableitungsoperator a |- b -- b ist aus a
in endlich vielen Schritten ableitbar.
> Marcus Gl�der wrote:
>>
>> Inzwischen glaube ich, dass die Frage, wieviele gel�ste Sudokus
>> einer gegebenen Gr��e es gibt, allenfalls n�herungsweise l�sbar ist.
>
> F�r 9x9 Sudokus haben das Felgenhauer und Jarvis gel�st.
> Es gibt 6.670.903.752.021.072.936.960 gel�ste Sudokus.
>
> http://www.afjarvis.staff.shef.ac.uk/sudoku/felgenhauer_jarvis_spec1.pdf
Sch�n!
-
Von der Ableitung zum System
Ableitungsoperator a |- b -- b ist aus a
in endlich vielen Schritten ableitbar.
Marcus Glöder
Aug 23, 2013, 5:52:08 PM8/23/13
to
Am 23.08.2013 21:14, schrieb Bergholt Stuttley Johnson:
> http://www.afjarvis.staff.shef.ac.uk/sudoku/felgenhauer_jarvis_spec1.pdf
Hallo Bergholt,
das ist ja genau das, was ich gesucht habe. Ich werde mich wohl eine
weile mit dem Aufsatz beschï¿œftigen. Danke!
Viele Grￜￜe
> http://www.afjarvis.staff.shef.ac.uk/sudoku/felgenhauer_jarvis_spec1.pdf
Hallo Bergholt,
das ist ja genau das, was ich gesucht habe. Ich werde mich wohl eine
weile mit dem Aufsatz beschï¿œftigen. Danke!
Viele Grￜￜe
Peter Kramer
Aug 24, 2013, 6:05:49 AM8/24/13
to
=?UTF-8?B?TWFyY3VzIEdsw7ZkZXI=?= <m.gl...@gmx.de> wrote in
news:5216E721...@gmx.de:
>
> 1. Wieviele verschiedene geloeste Sudokus sind bei einer gegebenen
> Sudoku-Gr�sse (Anzahl der Zeilen, Spalten und Quadranten) m�glich
>
> ----------------------
1,2,3/4,5,6/7,8,9
>
4,5,6/7,8,9/1,2,3
>
7,8,9/1,2,3/4,5,6
> ----------------------
2,3,4/5,6,7/8,9,1
>
5,6,7/8,9,1/2,3,4
>
8,9,1,2,3,4,5,6,7
> ----------------------
3,4,5/6,7,8/9,1,2
>
6,7,8/9,1,2/3,4,5
>
9,1,2/3,4,5/6,7,8
> ----------------------
>
1.) Die k�nnen wir nun noch 8 mal, (modulo 9) mit 1 addieren, also eine
Translation mit 1 (modulo 9). Das gibt insgesamt 9 Grundl�sungen.
Also einFaktor 9.
>
2.) paarweiser Tausch der Zeilen und Spalten pro 3x3 Block horizontal und
vertikal das ergibt weiter 4^3*4^3 M�glichkeiten.
>
3.) paarweiser Tausch der Bl�cke horizontal und vertikal das ergibt
weitere 4^2 M�glichkeiten
>
4.) paarweiser Zirkul�rtausch zweier Ziffern ergibt weitere 81*40
M�glichkeiten
>
also insgesamt:
>
9*4^8*81*40 = 1.911.029.760
>
ungef�hr 1/8 der Reihenanzahl beim Lotto 6 aus 49
>
Das Problem ist lediglich bei vorgegebenen Zahlen die zugeh�rige Menge
an L�sungen zu finden. F�r jede gegebene Teilvorgabe gibt es immer
mehrere L�sungen. H�lt man sich jedoch an die zirkul�re Permutationsregel
sind die L�sungen relativ Kinderleicht zu finden. Es scheint blos
kompliziert zu sein. Es es auch wenn man keine Regel dazu hat.
>
> 2. Wieviele Zellen m�ssen bei einem Sudoku gegebener Gr�sse mindestens
>
Spielt keine Rolle. Je mehr Zellen vorgegeben sind, testo kleiner ist die
L�sungsmenge.
>
> Zusatzfrage: wie m�ssen die vorgegebenen Zellen verteilt sein,
> damit m�glichst wenig davon ben�tigt werden? Oder spielt das keine Rolle?
>
Spielt keine Rolle. Da es immer eine L�sung gibt, ist es egal wieviele
Zahlen man mindestens, egal wie, vorgibt.
>
Das Problem ist lediglich die L�sungen zu der Vorgabe zu finden.
>
Eine vorgegebene Zahl fixiert, 9 Translationen, eine Zeile, eine Spalte,
einen Block, 81 Paartausche.
>
news:5216E721...@gmx.de:
>
> 1. Wieviele verschiedene geloeste Sudokus sind bei einer gegebenen
> Sudoku-Gr�sse (Anzahl der Zeilen, Spalten und Quadranten) m�glich
> (Anzahl der Permutationen,[1] die der Regel entsprechen, dass jede
> Ziffer pro Zeile, Spalte und Quadrant genau einmal vorkommen muss)?
>
Eine Grundl�sung erzielt durch zirkul�re Permutation der Grundreihe:
> Ziffer pro Zeile, Spalte und Quadrant genau einmal vorkommen muss)?
>
>
> ----------------------
1,2,3/4,5,6/7,8,9
>
4,5,6/7,8,9/1,2,3
>
7,8,9/1,2,3/4,5,6
> ----------------------
2,3,4/5,6,7/8,9,1
>
5,6,7/8,9,1/2,3,4
>
8,9,1,2,3,4,5,6,7
> ----------------------
3,4,5/6,7,8/9,1,2
>
6,7,8/9,1,2/3,4,5
>
9,1,2/3,4,5/6,7,8
> ----------------------
>
1.) Die k�nnen wir nun noch 8 mal, (modulo 9) mit 1 addieren, also eine
Translation mit 1 (modulo 9). Das gibt insgesamt 9 Grundl�sungen.
Also einFaktor 9.
>
2.) paarweiser Tausch der Zeilen und Spalten pro 3x3 Block horizontal und
vertikal das ergibt weiter 4^3*4^3 M�glichkeiten.
>
3.) paarweiser Tausch der Bl�cke horizontal und vertikal das ergibt
weitere 4^2 M�glichkeiten
>
4.) paarweiser Zirkul�rtausch zweier Ziffern ergibt weitere 81*40
M�glichkeiten
>
also insgesamt:
>
9*4^8*81*40 = 1.911.029.760
>
ungef�hr 1/8 der Reihenanzahl beim Lotto 6 aus 49
>
Das Problem ist lediglich bei vorgegebenen Zahlen die zugeh�rige Menge
an L�sungen zu finden. F�r jede gegebene Teilvorgabe gibt es immer
mehrere L�sungen. H�lt man sich jedoch an die zirkul�re Permutationsregel
sind die L�sungen relativ Kinderleicht zu finden. Es scheint blos
kompliziert zu sein. Es es auch wenn man keine Regel dazu hat.
>
> 2. Wieviele Zellen m�ssen bei einem Sudoku gegebener Gr�sse mindestens
> vorgegeben werden, damit alle anderen Zellen determiniert und das
> Sudoku damit eindeutig l�sbar ist (Anzahl der Freiheitsgrade[2])?
>
Spielt keine Rolle. Je mehr Zellen vorgegeben sind, testo kleiner ist die
L�sungsmenge.
>
> Zusatzfrage: wie m�ssen die vorgegebenen Zellen verteilt sein,
> damit m�glichst wenig davon ben�tigt werden? Oder spielt das keine Rolle?
>
Spielt keine Rolle. Da es immer eine L�sung gibt, ist es egal wieviele
Zahlen man mindestens, egal wie, vorgibt.
>
Das Problem ist lediglich die L�sungen zu der Vorgabe zu finden.
>
Eine vorgegebene Zahl fixiert, 9 Translationen, eine Zeile, eine Spalte,
einen Block, 81 Paartausche.
>
Peter Kramer
Aug 24, 2013, 7:12:49 AM8/24/13
to
Hans-Peter Diettrich <DrDiet...@aol.com> wrote in
news:b7otrs...@mid.individual.net:
> Marcus Gloeder schrieb:
> zwei Ziffern Probleme bekommt.
>
Nur wenn man die Methode zur sicheren und systematischen L�sung nicht
kennt.
>
Mit der von mir hier ansatzweise aufgezeigten Methode l�sst sich jedes
Sudoku, egal wie gross, auf mathematische einfache Weise systematisch
L�sen, ohne herumzuprobieren oder herumzustochern zu m�ssen oder Probleme
zu bekommen. Sudoku verliert dadurch aber seinen Reiz.
>
news:b7otrs...@mid.individual.net:
> Marcus Gloeder schrieb:
>
>> Wenn die Quadranten b und c festgelegt sind, ist
>> Quadrant d determiniert.
>
> In einem 9*9 Sudoku kann es passieren, dass man erst mit den letzten
>> Wenn die Quadranten b und c festgelegt sind, ist
>> Quadrant d determiniert.
>
> zwei Ziffern Probleme bekommt.
>
Nur wenn man die Methode zur sicheren und systematischen L�sung nicht
kennt.
>
Mit der von mir hier ansatzweise aufgezeigten Methode l�sst sich jedes
Sudoku, egal wie gross, auf mathematische einfache Weise systematisch
L�sen, ohne herumzuprobieren oder herumzustochern zu m�ssen oder Probleme
zu bekommen. Sudoku verliert dadurch aber seinen Reiz.
>
Bergholt Stuttley Johnson
Aug 24, 2013, 7:21:52 AM8/24/13
to
Marcus Glöder wrote:
>
> Wieviele Zellen müssen bei einem Sudoku gegebener Größe mindestens
> vorgegeben werden, damit alle anderen Zellen determiniert und das Sudoku
> damit eindeutig lösbar ist (Anzahl der Freiheitsgrade[2])?
Ich habe das von mir empfohlene Buch vor über
>
> Wieviele Zellen müssen bei einem Sudoku gegebener Größe mindestens
> vorgegeben werden, damit alle anderen Zellen determiniert und das Sudoku
> damit eindeutig lösbar ist (Anzahl der Freiheitsgrade[2])?
einem Jahr gelesen und mich seit dem nicht mehr
mit Sudoku beschäftigt. Zum Zeitpunkt, als das
Buch geschrieben wurde, kannte man viele eindeutig
lösbare Sudokus mit 17 Vorgaben. Es war noch
unbekannt, ob es welche mit nur 16 Vorgaben gibt.
Nun scheint bewiesen zu sein, dass es kein eindeutig
lösbares Sudoku mit nur 16 Vorgaben gibt.
http://arxiv.org/pdf/1201.0749.pdf
Peter Kramer
Aug 24, 2013, 7:32:49 AM8/24/13
to
Bergholt Stuttley Johnson <b...@am.invalid> wrote in
news:MPG.2c81d309c...@news.eternal-september.org:
> Marcus Gl�der wrote:
>>
>> Inzwischen glaube ich, dass die Frage, wieviele gel�ste Sudokus einer
>> gegebenen Gr��e es gibt, allenfalls n�herungsweise l�sbar ist.
>
> F�r 9x9 Sudokus haben das Felgenhauer und Jarvis gel�st. Es gibt
> 6.670.903.752.021.072.936.960 gel�ste Sudokus.
>
Bullshit!
>
> http://www.afjarvis.staff.shef.ac.uk/sudoku/felgenhauer_jarvis_spec1.pdf
>
Welch diletantische Hirnverbiegerei. Geht alles viel einfacher.
>
"This relabelling procedure reduces the number of grids by a factor of
9! = 362880."
>
Ist falsch!!! Genauso wie der diletantische Rest.
>
Bereits wenn man nur den ersten Block B(1,1) fixiert, erfolgt bereits eine
Reduzierung um den Faktor 9!.
>
news:MPG.2c81d309c...@news.eternal-september.org:
> Marcus Gl�der wrote:
>>
>> Inzwischen glaube ich, dass die Frage, wieviele gel�ste Sudokus einer
>> gegebenen Gr��e es gibt, allenfalls n�herungsweise l�sbar ist.
>
> F�r 9x9 Sudokus haben das Felgenhauer und Jarvis gel�st. Es gibt
> 6.670.903.752.021.072.936.960 gel�ste Sudokus.
>
>
> http://www.afjarvis.staff.shef.ac.uk/sudoku/felgenhauer_jarvis_spec1.pdf
>
Welch diletantische Hirnverbiegerei. Geht alles viel einfacher.
>
"This relabelling procedure reduces the number of grids by a factor of
9! = 362880."
>
Ist falsch!!! Genauso wie der diletantische Rest.
>
Bereits wenn man nur den ersten Block B(1,1) fixiert, erfolgt bereits eine
Reduzierung um den Faktor 9!.
>
Peter Kramer
Aug 24, 2013, 7:39:43 AM8/24/13
to
Bergholt Stuttley Johnson <b...@am.invalid> wrote in
news:MPG.2c81d309c...@news.eternal-september.org:
> Marcus Gl�der wrote:
>>
>> Inzwischen glaube ich, dass die Frage, wieviele gel�ste Sudokus einer
>> gegebenen Gr��e es gibt, allenfalls n�herungsweise l�sbar ist.
>
> F�r 9x9 Sudokus haben das Felgenhauer und Jarvis gel�st. Es gibt
> 6.670.903.752.021.072.936.960 gel�ste Sudokus.
>
> http://www.afjarvis.staff.shef.ac.uk/sudoku/felgenhauer_jarvis_spec1.pd
news:MPG.2c81d309c...@news.eternal-september.org:
> Marcus Gl�der wrote:
>>
>> Inzwischen glaube ich, dass die Frage, wieviele gel�ste Sudokus einer
>> gegebenen Gr��e es gibt, allenfalls n�herungsweise l�sbar ist.
>
> F�r 9x9 Sudokus haben das Felgenhauer und Jarvis gel�st. Es gibt
> 6.670.903.752.021.072.936.960 gel�ste Sudokus.
>
> f
>
"First, it is clear that there are N = (9!)9 ways to fill in each of the
blocks B1�B9 in such a way that each block has the digits 1�9."
>
Bl�dsinn! Bei der Beachtung der Regeln des Sudoku geht das nicht.
>
Peter Kramer
Aug 24, 2013, 7:57:18 AM8/24/13
to
Peter Kramer <kra...@freemail.com> wrote in
news:XnsA2268AF...@130.133.4.10:
Fixiert man den Block B(1,1) mit einer der 9! M�glichkeiten, bleiben f�r
die Zeilen und Spalten der Bl�cke B(1,2), B(2,1), B(2,2) jweils nur 6 frei
w�hlbare Zahlen �brig.
>
Abz�glich der �berschneidungen in den Bl�cken.
>
Fixiert man auch diese Bl�cke, so bleiben f�r die Zeilen und Spalten der
Bl�cke B(1,3), B(2,3), B(3,i) jeweils nur noch 3! M�glichkeiten �brig.
>
Abz�glich der �berschneidungen in den Bl�cken.
>
Hinzu kommen dann noch die M�gichkeiten des Zeilen- und Spaltentausches,
die M�glichkeiten des Blockzeilen- und Blockspaltentausches, sowie jene des
paarweisen Elementtausches.
>
Was die beiden Autoren da schreiben ist der pure Bullshit. Die blicken's
nicht.
>
news:XnsA2268AF...@130.133.4.10:
die Zeilen und Spalten der Bl�cke B(1,2), B(2,1), B(2,2) jweils nur 6 frei
w�hlbare Zahlen �brig.
>
Abz�glich der �berschneidungen in den Bl�cken.
>
Fixiert man auch diese Bl�cke, so bleiben f�r die Zeilen und Spalten der
Bl�cke B(1,3), B(2,3), B(3,i) jeweils nur noch 3! M�glichkeiten �brig.
>
Abz�glich der �berschneidungen in den Bl�cken.
>
Hinzu kommen dann noch die M�gichkeiten des Zeilen- und Spaltentausches,
die M�glichkeiten des Blockzeilen- und Blockspaltentausches, sowie jene des
paarweisen Elementtausches.
>
Was die beiden Autoren da schreiben ist der pure Bullshit. Die blicken's
nicht.
>
Bergholt Stuttley Johnson
Aug 24, 2013, 8:44:15 AM8/24/13
to
Bergholt Stuttley Johnson wrote:
> Nun scheint bewiesen zu sein, dass es kein eindeutig
> lï¿œsbares Sudoku mit nur 16 Vorgaben gibt.
> Nun scheint bewiesen zu sein, dass es kein eindeutig
>
> http://arxiv.org/pdf/1201.0749.pdf
Abschnitt 6.3 auf Seite 34!
Da kann ich das Ergebnis wohl nicht auf
meinem Notebook ï¿œberprï¿œfen.
Marcus Glöder
Aug 24, 2013, 8:45:36 AM8/24/13
to
Hallo Bergholt,
vielen Dank fï¿œr den Link. Du schreibst:
> Ich habe das von mir empfohlene Buch vor ï¿œber
Aus dem ersten Satz der Einleitung (weiter habe ich noch nicht gelesen)
des von Dir verlinkten Aufsatzes geht hervor, dass es dabei um
9x9-Sudokus geht. Dass es eine Mindestanzahl an Vorgaben geben muss,
damit eine Sudoku gegebener Grￜￜe eindeutig lￜsbar ist, ist, finde ich,
klar. Die Frage ist nur die: lï¿œsst sich diese Mindestanzahl mit einer
Formel oder einem Rechenweg auf einfache Weise eindeutig bestimmen? oder
muss herumprobiert werden?
Letzteres wï¿œre ja in Bezug auf das andere Problem (Anzahl gï¿œltiger
Lï¿œsungen) wenigstens theoretisch mï¿œglich, indem ein Computer mit einem
Programm gefï¿œttert wird, das ihm die Regeln fï¿œr Sudoku und eine Variable
vorgibt, die die Grￜￜe des Sudoku definiert. Dann probiert der Computer
alle mï¿œglichen Ziffernkombinationen aus,[1] sortiert dann die nach den
Sudoku-Regeln gï¿œltigen aus und zï¿œhlt sie. Ein ï¿œhnliches Programm wï¿œre
auch fï¿œr die Mindestanzahl der nï¿œtigen Vorgaben denkbar. Wie lange bei
dem derzeitigen Stand der Technik ein Computer fï¿œr die Abarbeitung eines
solchen Programms bei Vorgabe eines 9x9-Sudokus brauchen wￜrde, weiￜ ich
nicht. Zur Lï¿œsung der Frage nach dem Leben, dem Universum und allem hat
Deep Thought bekanntermaï¿œen sieben Millionen Jahre gebraucht und dann
als Antwort ￜ42ￜ augespuckt. ;-)
Anmerkungen
[1]
Bei einem 9x9-Sudoku beispielsweise von 81 mal die ￜ0ￜ bis 81 mal die
ￜ9ￜ, was 1 * 10^81 Zahlenkombinationen ergibt, von denen der Lￜwenanteil
allerdings nach Sudoku-Regeln ungï¿œltig sein dï¿œrfte.
vielen Dank fï¿œr den Link. Du schreibst:
> Ich habe das von mir empfohlene Buch vor ï¿œber
> einem Jahr gelesen und mich seit dem nicht mehr
> mit Sudoku beschï¿œftigt. Zum Zeitpunkt, als das
> Buch geschrieben wurde, kannte man viele eindeutig
> lï¿œsbare Sudokus mit 17 Vorgaben. Es war noch
> unbekannt, ob es welche mit nur 16 Vorgaben gibt.
> Nun scheint bewiesen zu sein, dass es kein eindeutig
> lï¿œsbares Sudoku mit nur 16 Vorgaben gibt.
> Nun scheint bewiesen zu sein, dass es kein eindeutig
Aus dem ersten Satz der Einleitung (weiter habe ich noch nicht gelesen)
des von Dir verlinkten Aufsatzes geht hervor, dass es dabei um
9x9-Sudokus geht. Dass es eine Mindestanzahl an Vorgaben geben muss,
damit eine Sudoku gegebener Grￜￜe eindeutig lￜsbar ist, ist, finde ich,
klar. Die Frage ist nur die: lï¿œsst sich diese Mindestanzahl mit einer
Formel oder einem Rechenweg auf einfache Weise eindeutig bestimmen? oder
muss herumprobiert werden?
Letzteres wï¿œre ja in Bezug auf das andere Problem (Anzahl gï¿œltiger
Lï¿œsungen) wenigstens theoretisch mï¿œglich, indem ein Computer mit einem
Programm gefï¿œttert wird, das ihm die Regeln fï¿œr Sudoku und eine Variable
vorgibt, die die Grￜￜe des Sudoku definiert. Dann probiert der Computer
alle mï¿œglichen Ziffernkombinationen aus,[1] sortiert dann die nach den
Sudoku-Regeln gï¿œltigen aus und zï¿œhlt sie. Ein ï¿œhnliches Programm wï¿œre
auch fï¿œr die Mindestanzahl der nï¿œtigen Vorgaben denkbar. Wie lange bei
dem derzeitigen Stand der Technik ein Computer fï¿œr die Abarbeitung eines
solchen Programms bei Vorgabe eines 9x9-Sudokus brauchen wￜrde, weiￜ ich
nicht. Zur Lï¿œsung der Frage nach dem Leben, dem Universum und allem hat
Deep Thought bekanntermaï¿œen sieben Millionen Jahre gebraucht und dann
als Antwort ￜ42ￜ augespuckt. ;-)
Anmerkungen
[1]
Bei einem 9x9-Sudoku beispielsweise von 81 mal die ￜ0ￜ bis 81 mal die
ￜ9ￜ, was 1 * 10^81 Zahlenkombinationen ergibt, von denen der Lￜwenanteil
allerdings nach Sudoku-Regeln ungï¿œltig sein dï¿œrfte.
Marcus Glöder
Aug 24, 2013, 9:00:22 AM8/24/13
to
Am 24.08.2013 14:44, schrieb Bergholt Stuttley Johnson:
> Abschnitt 6.3 auf Seite 34!
> Da kann ich das Ergebnis wohl nicht auf
> meinem Notebook überprüfen.
> Abschnitt 6.3 auf Seite 34!
> Da kann ich das Ergebnis wohl nicht auf
Hallo Bergholt,
da steht:
> The entire computation took about 7.1 million core hours on
> the Stokes machine. Stokes is an SGI Altix ICE 8200EX
> cluster with 320 compute nodes. Each node has two Intel
> (Westmere) Xeon E5650 hex-core processors and 24GB of
> RAM. We divided the computation up into several hundred
> jobs. We started running jobs in January 2011, and we finished
> in December 2011.
Sie haben also tatsächlich Deep Thought bemüht – und es hat nur ein
knappes Jahr gedauert. ;-)
Viele Grüße
Marcus Glöder
Aug 24, 2013, 10:07:28 AM8/24/13
to
Hallo Peter,
mit dem, was Du da schreibst, müsste ich mich erst einmal ausgiebig
beschäftigen. Nur damit ich da was nicht falsch verstehe (und für mein
geisteswissenschaftliche Gehirn): Wenn ich das, was hier
http://de.wikipedia.org/wiki/Modulo#Beispiele
steht nehme, dann ist zum Beispiel
11 modulo 5 = 1
weil
11 : 5 = 2 Rest 1
ist (so wie das in der Grundschule gerechnet wird). »modulo« würde also
den ganzzahligen Rest bei Divisionen angeben. Richtig? Was bedeutet dann
> 1.) Die können wir nun noch 8 mal, (modulo 9) mit 1 addieren, also eine
> Translation mit 1 (modulo 9). Das gibt insgesamt 9 Grundlösungen.
> Also einFaktor 9.
Zu meinem zweiten Problem (Mindestanzahl der Vorgaben, die nötig
sind, um ein Sudoku vorgegebener Größe eindeutig lösen zu können)
schreibst Du:
> Spielt keine Rolle. Da es immer eine Lösung gibt, ist es egal wieviele
mache, gleich Null ist, dann ist das Sudoku (egal, welche Größe es hat),
nicht lösbar. Selbst ein 2x2-Sudoku (was eigentlich kein richtiges
Sudoku mehr ist, weil die Quadranten nur jeweils eine Zelle enthalten,
also Zelle=Quadrant ist) gibt es zwei verschiedene Lösungen, wenn ich
nichts vorgebe:
12
21
21
12
Hier muss ich also genau eine Vorgabe machen, damit alle andern Felder
determiniert sind. Also: es gibt immer eine Mindestanzahl an Feldern,
die ich vorgeben muss, damit alle anderen Felder determiniert sind. Es
steht mir selbstverständlich frei, mehr Felder vorzugeben, soweit das
nicht zu einem Widerspruch führt. Dann wird nur das Sudoku einfacher
lösbar. Aber weniger Felder darf ich nicht vorgeben, weil es dann Felder
gibt, die nicht eindeutig bestimmt sind (das Sudoku ist dann sozusagen
»unterdeterminiert«, wenn ich das mal so sagen darf). Du sagst übrigens
selbst:
> Je mehr Zellen vorgegeben sind, desto kleiner ist die Lösungsmenge.
Mit anderen Worten: je mehr Vorgaben ich mache, desto weniger mögliche
Lösungen gibt es. Das gilt bis zu dem Grenzfall, dass es nur noch eine
mögliche Lösung gibt. Wenn ich /darüber hinaus/ noch weitere Felder
vorgebe, verringert sich nicht mehr die Anzahl möglicher Lösungen (die
ohnehin schon bei ihrem kleinsten möglichen Wert, nämlich 1, angekommen
ist), sondern das Sudoku ist dann nur immer einfacher zu lösen. Das ist,
denke ich, soweit klar.
mit dem, was Du da schreibst, müsste ich mich erst einmal ausgiebig
beschäftigen. Nur damit ich da was nicht falsch verstehe (und für mein
geisteswissenschaftliche Gehirn): Wenn ich das, was hier
http://de.wikipedia.org/wiki/Modulo#Beispiele
steht nehme, dann ist zum Beispiel
11 modulo 5 = 1
weil
11 : 5 = 2 Rest 1
ist (so wie das in der Grundschule gerechnet wird). »modulo« würde also
den ganzzahligen Rest bei Divisionen angeben. Richtig? Was bedeutet dann
> 1.) Die können wir nun noch 8 mal, (modulo 9) mit 1 addieren, also eine
> Translation mit 1 (modulo 9). Das gibt insgesamt 9 Grundlösungen.
> Also einFaktor 9.
Zu meinem zweiten Problem (Mindestanzahl der Vorgaben, die nötig
sind, um ein Sudoku vorgegebener Größe eindeutig lösen zu können)
schreibst Du:
> Spielt keine Rolle. Da es immer eine Lösung gibt, ist es egal wieviele
> Zahlen man mindestens, egal wie, vorgibt.
Das ist nun eindeutig falsch. Wenn die Anzahl der Vorgaben, die ich
mache, gleich Null ist, dann ist das Sudoku (egal, welche Größe es hat),
nicht lösbar. Selbst ein 2x2-Sudoku (was eigentlich kein richtiges
Sudoku mehr ist, weil die Quadranten nur jeweils eine Zelle enthalten,
also Zelle=Quadrant ist) gibt es zwei verschiedene Lösungen, wenn ich
nichts vorgebe:
12
21
21
12
Hier muss ich also genau eine Vorgabe machen, damit alle andern Felder
determiniert sind. Also: es gibt immer eine Mindestanzahl an Feldern,
die ich vorgeben muss, damit alle anderen Felder determiniert sind. Es
steht mir selbstverständlich frei, mehr Felder vorzugeben, soweit das
nicht zu einem Widerspruch führt. Dann wird nur das Sudoku einfacher
lösbar. Aber weniger Felder darf ich nicht vorgeben, weil es dann Felder
gibt, die nicht eindeutig bestimmt sind (das Sudoku ist dann sozusagen
»unterdeterminiert«, wenn ich das mal so sagen darf). Du sagst übrigens
selbst:
> Je mehr Zellen vorgegeben sind, desto kleiner ist die Lösungsmenge.
Mit anderen Worten: je mehr Vorgaben ich mache, desto weniger mögliche
Lösungen gibt es. Das gilt bis zu dem Grenzfall, dass es nur noch eine
mögliche Lösung gibt. Wenn ich /darüber hinaus/ noch weitere Felder
vorgebe, verringert sich nicht mehr die Anzahl möglicher Lösungen (die
ohnehin schon bei ihrem kleinsten möglichen Wert, nämlich 1, angekommen
ist), sondern das Sudoku ist dann nur immer einfacher zu lösen. Das ist,
denke ich, soweit klar.
Hans-Peter Diettrich
Aug 24, 2013, 3:01:46 PM8/24/13
to
Marcus Glï¿œder schrieb:
> Zu meinem zweiten Problem (Mindestanzahl der Vorgaben, die nï¿œtig sind,
> um ein Sudoku vorgegebener Grￜￜe eindeutig lￜsen zu kￜnnen) schreibst Du:
>
>> Spielt keine Rolle. Da es immer eine Lï¿œsung gibt, ist es egal wieviele
> Wenn die Anzahl der Vorgaben, die ich
> mache, gleich Null ist, dann ist das Sudoku (egal, welche Grￜￜe es hat),
> nicht lï¿œsbar.
Wenn keine Vorgaben existieren, ist jede mï¿œgliche Lï¿œsung eine Lï¿œsung -
nur die Eindeutigkeit ist dann nicht mehr gegeben.
Oder andersrum: solange alle vorgegebenen Felder aus einer gï¿œltigen
Lￜsung stammen, lￜￜt sich damit immer eine Lￜsung finden - wenn auch
nicht unbedingt genau die den Vorgaben zugrundeliegende.
> Also: es gibt immer eine Mindestanzahl an Feldern,
> die ich vorgeben muss, damit alle anderen Felder determiniert sind.
Vï¿œllig richtig, ich sehe da keinen Widerspruch.
> Es
> steht mir selbstverstï¿œndlich frei, mehr Felder vorzugeben, soweit das
> nicht zu einem Widerspruch fï¿œhrt.
Deshalb sollte man ja von irgendeinem korrekt ausgefï¿œllten Sudoku
ausgehen, und die Vorgaben aus diesem entnehmen. Dann kann kein
Widerspruch auftreten, ein weiterer Beweis der Lï¿œsbarkeit ist nicht mehr
notwendig.
> Dann wird nur das Sudoku einfacher
> lï¿œsbar. Aber weniger Felder darf ich nicht vorgeben, weil es dann Felder
> selbst:
>
>> Je mehr Zellen vorgegeben sind, desto kleiner ist die Lï¿œsungsmenge.
>
> Mit anderen Worten: je mehr Vorgaben ich mache, desto weniger mï¿œgliche
> Lï¿œsungen gibt es. Das gilt bis zu dem Grenzfall, dass es nur noch eine
> mï¿œgliche Lï¿œsung gibt. Wenn ich /darï¿œber hinaus/ noch weitere Felder
> vorgebe, verringert sich nicht mehr die Anzahl mï¿œglicher Lï¿œsungen (die
> ohnehin schon bei ihrem kleinsten mï¿œglichen Wert, nï¿œmlich 1, angekommen
> ist), sondern das Sudoku ist dann nur immer einfacher zu lï¿œsen. Das ist,
> denke ich, soweit klar.
+1
DoDi
> Zu meinem zweiten Problem (Mindestanzahl der Vorgaben, die nï¿œtig sind,
> um ein Sudoku vorgegebener Grￜￜe eindeutig lￜsen zu kￜnnen) schreibst Du:
>
>> Spielt keine Rolle. Da es immer eine Lï¿œsung gibt, ist es egal wieviele
>> Zahlen man mindestens, egal wie, vorgibt.
>
> Das ist nun eindeutig falsch.
Ich hoffe, das gibt jetzt keinen Streit zwischen den Wissenschaften ;-)
>
> Das ist nun eindeutig falsch.
> Wenn die Anzahl der Vorgaben, die ich
> nicht lï¿œsbar.
Wenn keine Vorgaben existieren, ist jede mï¿œgliche Lï¿œsung eine Lï¿œsung -
nur die Eindeutigkeit ist dann nicht mehr gegeben.
Oder andersrum: solange alle vorgegebenen Felder aus einer gï¿œltigen
Lￜsung stammen, lￜￜt sich damit immer eine Lￜsung finden - wenn auch
nicht unbedingt genau die den Vorgaben zugrundeliegende.
> Also: es gibt immer eine Mindestanzahl an Feldern,
> die ich vorgeben muss, damit alle anderen Felder determiniert sind.
> Es
> steht mir selbstverstï¿œndlich frei, mehr Felder vorzugeben, soweit das
> nicht zu einem Widerspruch fï¿œhrt.
Deshalb sollte man ja von irgendeinem korrekt ausgefï¿œllten Sudoku
ausgehen, und die Vorgaben aus diesem entnehmen. Dann kann kein
Widerspruch auftreten, ein weiterer Beweis der Lï¿œsbarkeit ist nicht mehr
notwendig.
> Dann wird nur das Sudoku einfacher
> gibt, die nicht eindeutig bestimmt sind (das Sudoku ist dann sozusagen
> ￜunterdeterminiertￜ, wenn ich das mal so sagen darf). Du sagst ￜbrigens
> selbst:
>
>> Je mehr Zellen vorgegeben sind, desto kleiner ist die Lï¿œsungsmenge.
>
> Mit anderen Worten: je mehr Vorgaben ich mache, desto weniger mï¿œgliche
> Lï¿œsungen gibt es. Das gilt bis zu dem Grenzfall, dass es nur noch eine
> mï¿œgliche Lï¿œsung gibt. Wenn ich /darï¿œber hinaus/ noch weitere Felder
> vorgebe, verringert sich nicht mehr die Anzahl mï¿œglicher Lï¿œsungen (die
> ohnehin schon bei ihrem kleinsten mï¿œglichen Wert, nï¿œmlich 1, angekommen
> ist), sondern das Sudoku ist dann nur immer einfacher zu lï¿œsen. Das ist,
> denke ich, soweit klar.
+1
DoDi
Detlef Müller
Aug 24, 2013, 4:53:52 PM8/24/13
to
On 24.08.2013 12:05, Peter Kramer wrote:
> =?UTF-8?B?TWFyY3VzIEdsw7ZkZXI=?= <m.gl...@gmx.de> wrote in
> news:5216E721...@gmx.de:
>
>>
>> 1. Wieviele verschiedene geloeste Sudokus sind bei einer gegebenen
>> Sudoku-Grösse (Anzahl der Zeilen, Spalten und Quadranten) möglich
> =?UTF-8?B?TWFyY3VzIEdsw7ZkZXI=?= <m.gl...@gmx.de> wrote in
> news:5216E721...@gmx.de:
>
>>
>> 1. Wieviele verschiedene geloeste Sudokus sind bei einer gegebenen
>> (Anzahl der Permutationen,[1] die der Regel entsprechen, dass jede
>> Ziffer pro Zeile, Spalte und Quadrant genau einmal vorkommen muss)?
>>
> Eine Grundlösung erzielt durch zirkuläre Permutation der Grundreihe:
>> Ziffer pro Zeile, Spalte und Quadrant genau einmal vorkommen muss)?
>>
>> ...
>> ----------------------
>>
> 1.) Die können wir nun noch 8 mal, (modulo 9) mit 1 addieren, also eine
> Translation mit 1 (modulo 9). Das gibt insgesamt 9 Grundlösungen.
> Also einFaktor 9.
Sprich die Ziffern zyklisch vertauschen.
Natürlich gibt es noch viel mehr Permutationen der Ziffern (als nur
die zyklischen Vertauschungen) - und jede davon führt zu einem
weiteren Sudoku.
>>
> 2.) paarweiser Tausch der Zeilen und Spalten pro 3x3 Block horizontal und
Die Operationen verstehe ich nicht.
In einem Block selbst kann ich doch gar nichts vertauschen, ohne die
umgebenden Blöcke zu beachten?!
>>
> 3.) paarweiser Tausch der Blöcke horizontal und vertikal das ergibt
> weitere 4^2 Möglichkeiten
>>
> 4.) paarweiser Zirkulärtausch zweier Ziffern ergibt weitere 81*40
> Möglichkeiten
Genau genommen verstehe ich (außer der zyklischen Zifferntauschung
bzw. "+1 modulo 9") keine einzige der von Dir aufgeführten
Operationen.
Aber nehmen wir an, Du hast hier einige Möglichkeiten gefunden, aus
der Grundlösung weitere Lösungen zu generieren, mit denen Du
>>
> also insgesamt:
>>
> 9*4^8*81*40 = 1.911.029.760
>>
> ungefähr 1/8 der Reihenanzahl beim Lotto 6 aus 49
> also insgesamt:
>>
> 9*4^8*81*40 = 1.911.029.760
>>
>>
Sudokus erhältst
... so fehlt doch nun der Nachweis, daß das auch alle möglichen
Sudoku-Stellungen ergibt.
Warum soll es also nicht noch weitere so nicht erreichbare
Lösungsstellungen geben?
Gruß,
Detlef
Marcus Glöder
Aug 24, 2013, 6:29:19 PM8/24/13
to
Hallo Hans-Peter,
Du schreibst:
> Ich hoffe, das gibt jetzt keinen Streit zwischen den Wissenschaften ;-)
Nö.
>> Wenn die Anzahl der Vorgaben, die ich mache, gleich Null ist, dann ist
> Lösung stammen, läßt sich damit immer eine Lösung finden - wenn auch
lösbar«.
>> Also: es gibt immer eine Mindestanzahl an Feldern, die ich vorgeben
>> muss, damit alle anderen Felder determiniert sind.
>
> Völlig richtig, ich sehe da keinen Widerspruch.
Ich hatte mich auf die folgende Aussage bezogen:
> Da es immer eine Lösung gibt, ist es egal wieviele
dass jedes Sudoku (egal welcher Größe) immer /eindeutig/ lösbar sei,
egal wie viele Felder (Ziffern) vorgegeben werden. In diesem von mir so
verstandenem Sinne habe ich dem widersprochen und den oben zitierten
Satz geschrieben.
>> Es steht mir selbstverständlich frei, mehr Felder vorzugeben, soweit
>> das nicht zu einem Widerspruch führt.
>
> Deshalb sollte man ja von irgendeinem korrekt ausgefüllten Sudoku
> notwendig.
Ack. Allerdings ist es dann immernoch möglich, in dem Sinne »zuwenig«
Vorgaben zu machen, dass einige Felder mehrdeutig bleiben, das Sudoku
also nicht eindeutig ist, oder anders formuliert: mehr als eine gültige
Lösung besitzt.
>> [...] bei ihrem kleinsten möglichen Wert, nämlich 1,[...]
> +1
Ich hatte mich an die Konvention gehalten, bei positiven Zahlen das
Vorzeichen wegzulassen. An sich geht aber auch aus dem Kontext hervor,
dass +1 gemeint ist. Schließlich handelt es sich bei der Anzahl der
möglichen gültigen Lösungen bei einer bestimmten Anzahl vorgegebener
Felder um eine natürliche Zahl. Ich würde, um das Beispiel zu nehmen,
auch bei einer Befragung nicht annehmen, dass sie Anzahl der
vorliegenden ausgefüllten Fragebögen (die Fallzahl n) negativ sein
könnte. Null Fragebögen wären zwar möglich, aber dann könnte ich keine
Auswertung mehr machen.
> DoDi
Du schreibst:
> Ich hoffe, das gibt jetzt keinen Streit zwischen den Wissenschaften ;-)
>> Wenn die Anzahl der Vorgaben, die ich mache, gleich Null ist, dann ist
>> das Sudoku (egal, welche Größe es hat), nicht lösbar.
>
> Wenn keine Vorgaben existieren, ist jede mögliche Lösung eine Lösung -
>
> nur die Eindeutigkeit ist dann nicht mehr gegeben.
>
> Oder andersrum: solange alle vorgegebenen Felder aus einer gültigen
>
> Lösung stammen, läßt sich damit immer eine Lösung finden - wenn auch
> nicht unbedingt genau die den Vorgaben zugrundeliegende.
OK, ich hätte an der Stelle wohl schreiben sollen: »nicht eindeutig
lösbar«.
>> Also: es gibt immer eine Mindestanzahl an Feldern, die ich vorgeben
>> muss, damit alle anderen Felder determiniert sind.
>
Ich hatte mich auf die folgende Aussage bezogen:
> Da es immer eine Lösung gibt, ist es egal wieviele
> Zahlen man mindestens, egal wie, vorgibt.
Das hatte ich aus dem Kontext so verstanden, dass damit gemeint ist,
dass jedes Sudoku (egal welcher Größe) immer /eindeutig/ lösbar sei,
egal wie viele Felder (Ziffern) vorgegeben werden. In diesem von mir so
verstandenem Sinne habe ich dem widersprochen und den oben zitierten
Satz geschrieben.
>> Es steht mir selbstverständlich frei, mehr Felder vorzugeben, soweit
>> das nicht zu einem Widerspruch führt.
>
> Deshalb sollte man ja von irgendeinem korrekt ausgefüllten Sudoku
> ausgehen, und die Vorgaben aus diesem entnehmen. Dann kann kein
> Widerspruch auftreten, ein weiterer Beweis der Lösbarkeit ist nicht mehr
> notwendig.
Ack. Allerdings ist es dann immernoch möglich, in dem Sinne »zuwenig«
Vorgaben zu machen, dass einige Felder mehrdeutig bleiben, das Sudoku
also nicht eindeutig ist, oder anders formuliert: mehr als eine gültige
Lösung besitzt.
>> [...] bei ihrem kleinsten möglichen Wert, nämlich 1,[...]
> +1
Ich hatte mich an die Konvention gehalten, bei positiven Zahlen das
Vorzeichen wegzulassen. An sich geht aber auch aus dem Kontext hervor,
dass +1 gemeint ist. Schließlich handelt es sich bei der Anzahl der
möglichen gültigen Lösungen bei einer bestimmten Anzahl vorgegebener
Felder um eine natürliche Zahl. Ich würde, um das Beispiel zu nehmen,
auch bei einer Befragung nicht annehmen, dass sie Anzahl der
vorliegenden ausgefüllten Fragebögen (die Fallzahl n) negativ sein
könnte. Null Fragebögen wären zwar möglich, aber dann könnte ich keine
Auswertung mehr machen.
> DoDi
Peter Kramer
Aug 25, 2013, 2:01:57 AM8/25/13
to
=?ISO-8859-15?Q?Marcus_Gl=F6der?= <m.gl...@gmx.de> wrote in
news:kvaen3$dmh$1...@dont-email.me:
> Hallo Peter,
>
> mit dem, was Du da schreibst, müsste ich mich erst einmal ausgiebig
> beschäftigen. Nur damit ich da was nicht falsch verstehe (und für mein
> geisteswissenschaftliche Gehirn): Wenn ich das, was hier
>
> http://de.wikipedia.org/wiki/Modulo#Beispiele
>
> steht nehme, dann ist zum Beispiel
>
> 11 modulo 5 = 1
>
Richtig!
eine Lösung, bzw. die Lösungsmenge ist die Menge aller Lösungen.
nicht nur eine Lösung geben. Es gibt immer mehr als eine Lösung, wenn es
noch mehr als 5 freie Zellen in der Vorgabe gibt.
denn zum Tausch zweier Ziffern benötigt man 6 Zellen.
>
Sind also 6 Zellen unbesetzt gibt es nur noch zwei mögliche Lösungen.
>
news:kvaen3$dmh$1...@dont-email.me:
> Hallo Peter,
>
> mit dem, was Du da schreibst, müsste ich mich erst einmal ausgiebig
> beschäftigen. Nur damit ich da was nicht falsch verstehe (und für mein
> geisteswissenschaftliche Gehirn): Wenn ich das, was hier
>
> http://de.wikipedia.org/wiki/Modulo#Beispiele
>
> steht nehme, dann ist zum Beispiel
>
> 11 modulo 5 = 1
>
>
> weil
>
> 11 : 5 = 2 Rest 1
>
> ist (so wie das in der Grundschule gerechnet wird). »modulo« würde
> also den ganzzahligen Rest bei Divisionen angeben. Richtig? Was
> bedeutet dann
>
>> 1.) Die können wir nun noch 8 mal, (modulo 9) mit 1 addieren, also
>> eine Translation mit 1 (modulo 9). Das gibt insgesamt 9
>> Grundlösungen. Also einFaktor 9.
>
> Zu meinem zweiten Problem (Mindestanzahl der Vorgaben, die nötig
> sind, um ein Sudoku vorgegebener Größe eindeutig lösen zu können)
> schreibst Du:
>
>> Spielt keine Rolle. Da es immer eine Lösung gibt, ist es egal
>> wieviele Zahlen man mindestens, egal wie, vorgibt.
>
> Das ist nun eindeutig falsch.
>
Nein.
> weil
>
> 11 : 5 = 2 Rest 1
>
> ist (so wie das in der Grundschule gerechnet wird). »modulo« würde
> also den ganzzahligen Rest bei Divisionen angeben. Richtig? Was
> bedeutet dann
>
>> 1.) Die können wir nun noch 8 mal, (modulo 9) mit 1 addieren, also
>> eine Translation mit 1 (modulo 9). Das gibt insgesamt 9
>> Grundlösungen. Also einFaktor 9.
>
> Zu meinem zweiten Problem (Mindestanzahl der Vorgaben, die nötig
> sind, um ein Sudoku vorgegebener Größe eindeutig lösen zu können)
> schreibst Du:
>
>> Spielt keine Rolle. Da es immer eine Lösung gibt, ist es egal
>> wieviele Zahlen man mindestens, egal wie, vorgibt.
>
> Das ist nun eindeutig falsch.
>
>
> Wenn die Anzahl der Vorgaben, die ich mache, gleich Null ist, dann ist
> das Sudoku (egal, welche Größe es hat), nicht lösbar.
>
Aber selbstverständlich ist es lösbar. Jedwelche gültige Lösung ist dann
> Wenn die Anzahl der Vorgaben, die ich mache, gleich Null ist, dann ist
> das Sudoku (egal, welche Größe es hat), nicht lösbar.
>
eine Lösung, bzw. die Lösungsmenge ist die Menge aller Lösungen.
>
> Also: es gibt immer eine Mindestanzahl an Feldern,
> die ich vorgeben muss, damit alle anderen Felder determiniert sind.
>
Es müssen nicht alle Zellen eindeutig determiniert sein, denn es muss ja
> Also: es gibt immer eine Mindestanzahl an Feldern,
> die ich vorgeben muss, damit alle anderen Felder determiniert sind.
>
nicht nur eine Lösung geben. Es gibt immer mehr als eine Lösung, wenn es
noch mehr als 5 freie Zellen in der Vorgabe gibt.
>
>> Je mehr Zellen vorgegeben sind, desto kleiner ist die Lösungsmenge.
>
> Mit anderen Worten: je mehr Vorgaben ich mache, desto weniger mögliche
> Lösungen gibt es. Das gilt bis zu dem Grenzfall, dass es nur noch eine
> mögliche Lösung gibt.
>
Die einzige Lösung gibt es nur dann wenn maximal 5 Zellen unbesetzt sind,
>> Je mehr Zellen vorgegeben sind, desto kleiner ist die Lösungsmenge.
>
> Mit anderen Worten: je mehr Vorgaben ich mache, desto weniger mögliche
> Lösungen gibt es. Das gilt bis zu dem Grenzfall, dass es nur noch eine
> mögliche Lösung gibt.
>
denn zum Tausch zweier Ziffern benötigt man 6 Zellen.
>
Sind also 6 Zellen unbesetzt gibt es nur noch zwei mögliche Lösungen.
>
Peter Kramer
Aug 25, 2013, 2:08:05 AM8/25/13
to
Hans-Peter Diettrich <DrDiet...@aol.com> wrote in
news:b7sef2...@mid.individual.net:
> Marcus Glöder schrieb:
>
>> Zu meinem zweiten Problem (Mindestanzahl der Vorgaben, die nötig
>> sind, um ein Sudoku vorgegebener Größe eindeutig lösen zu können)
>> schreibst Du:
>> Zu meinem zweiten Problem (Mindestanzahl der Vorgaben, die nötig
>> sind, um ein Sudoku vorgegebener Größe eindeutig lösen zu können)
>>
>>> Spielt keine Rolle. Da es immer eine Lösung gibt, ist es egal
>>> wieviele Zahlen man mindestens, egal wie, vorgibt.
>>
>> Das ist nun eindeutig falsch.
>
> Ich hoffe, das gibt jetzt keinen Streit zwischen den Wissenschaften
> ;-)
>
>> Wenn die Anzahl der Vorgaben, die ich mache, gleich Null ist, dann
>>
>> Das ist nun eindeutig falsch.
>
> Ich hoffe, das gibt jetzt keinen Streit zwischen den Wissenschaften
> ;-)
>
>> Wenn die Anzahl der Vorgaben, die ich mache, gleich Null ist, dann
>> ist das Sudoku (egal, welche Größe es hat), nicht lösbar.
>
(*****)
>
> Wenn keine Vorgaben existieren, ist jede mögliche Lösung eine Lösung -
> nur die Eindeutigkeit ist dann nicht mehr gegeben.
>
Richtig!
>
>
> Oder andersrum: solange alle vorgegebenen Felder aus einer gültigen
> Lösung stammen, ....
>
Das Voraussetzung für jede Vorgabe.
>
> ... läßt sich damit immer eine Lösung finden - wenn auch
> nicht unbedingt genau die den Vorgaben zugrundeliegende.
>
Es lässt sich immer eine den Vorgaben entsprechende Lösung finden.
>
>
>> Also: es gibt immer eine Mindestanzahl an Feldern, die ich vorgeben
>> muss, damit alle anderen Felder determiniert sind.
>
> Völlig richtig, ich sehe da keinen Widerspruch.
>> Also: es gibt immer eine Mindestanzahl an Feldern, die ich vorgeben
>> muss, damit alle anderen Felder determiniert sind.
>
>
Den Widerspruch liferst du selber ;-) siehe(*****)
>
"Wenn keine Vorgaben existieren, ist jede mögliche Lösung eine Lösung"
>
Die Lösungsmenge ist dann Menge aller möglichen Lösungen beim SUDOKU.
>
Peter Kramer
Aug 25, 2013, 2:31:27 AM8/25/13
to
Bergholt Stuttley Johnson <b...@am.invalid> wrote in
news:MPG.2c82b5b9b...@news.eternal-september.org:
> Marcus Glöder wrote:
>>
>> Wieviele Zellen müssen bei einem Sudoku gegebener Größe mindestens
>> vorgegeben werden, damit alle anderen Zellen determiniert und das
>> Sudoku damit eindeutig lösbar ist (Anzahl der Freiheitsgrade[2])?
>
> Ich habe das von mir empfohlene Buch vor über
> einem Jahr gelesen und mich seit dem nicht mehr
> mit Sudoku beschäftigt. Zum Zeitpunkt, als das
> Buch geschrieben wurde, kannte man viele eindeutig
> lösbare Sudokus mit 17 Vorgaben.
>
>
Man kann in einer Blockzeile oder Blockspalte immer zwei unbesetze Zellen
vertauschen um eine neue Lösung zu erzielen.
>
> Es war noch
> unbekannt, ob es welche mit nur 16 Vorgaben gibt.
> Nun scheint bewiesen zu sein, dass es kein eindeutig
> lösbares Sudoku mit nur 16 Vorgaben gibt.
>
Das wäre sonderlich seltsam ;-)
> Es war noch
> unbekannt, ob es welche mit nur 16 Vorgaben gibt.
> Nun scheint bewiesen zu sein, dass es kein eindeutig
> lösbares Sudoku mit nur 16 Vorgaben gibt.
>
>
Eindeutig lösbar, mit einer 'einzigen' Lösung, ist ein SUDOKU (3x3)x(3x3)
=9x9 nur dann, wenn maximal 5 Zellen frei sind, denn zum Tausch zweier
Ziffern benötigt man mindestens 6 Zellen. Ansonsten gibt es immer mehr
als eine Lösung.
>
Durch den Tausch zweier Ziffern über 6 Zellen, erhält man aus einem voll
gültig ausgefüllten Sudoku, eine neue gültige Variante.
>
> http://arxiv.org/pdf/1201.0749.pdf
>
Das wäre sonderlich ;-) Viel Logik-Grips haben die nicht investiert.
>
Jedes SUDOKU mit den Regeln entsprechenden Vorgaben ist lösbar.
>
Was mir aufgefallen ist, die Menschen die sich mit dem Sudoku
beschäftigen denken viel zu kompliziert um die Ecke, ohne systematische
Heransgehensweise.
>
Peter Kramer
Aug 25, 2013, 3:13:10 AM8/25/13
to
=?ISO-8859-15?Q?Marcus_Gl=F6der?= <m.gl...@gmx.de> wrote in news:kvbc44
$p1g$1...@dont-email.me:
>
Schreibt man in ein Sudoku eine noch nicht vorhanden Ziffer in eine
Zelle, sind dadurch, je bereits vorhandem Ziffernpaar, jeweil weitere 5
Zellen bestimmt.
>
Existieren also in einem Sudoku bereits die Ziffern a1,a2,a3,... und man
fügt eine weitere Ziffer x in eine freie Zelle hinzu, so sind dadurch pro
Ziffernpaar (x, a_i) jweils 6 Felder bestimmt. Die muss man dann erst
einmal alle als "Folgeaktion" ausfüllen, bevor man zu einer weiteren
Ziffer in einem weiteren freien Feld übergeht.
>
Man begint also erst einmal mit den bereits in der Aufgabenstellung
gegebenen Ziffenpaaren (a_i, a_j) und füllt damit die daraus pro Paar
resultierenden 5 weitern Felder aus, bevor man noch nicht vorhandene
Ziffern hinzufügt.
>
Das ausfüllen wird dadurch zu einem "Kinderspiel", nach einer rein
"mechanischen Regel-Vorgehensweise" ohne darüber nachdenken zu müssen.
Schlichtweg ein paar banale Ausfüllregeln beachten. Das wird dann schnell
langweilig.
>
Gibt es auch Sudoku-Meisterschaften? Was gibt es da zu gewinnen?
>
$p1g$1...@dont-email.me:
>
Schreibt man in ein Sudoku eine noch nicht vorhanden Ziffer in eine
Zelle, sind dadurch, je bereits vorhandem Ziffernpaar, jeweil weitere 5
Zellen bestimmt.
>
Existieren also in einem Sudoku bereits die Ziffern a1,a2,a3,... und man
fügt eine weitere Ziffer x in eine freie Zelle hinzu, so sind dadurch pro
Ziffernpaar (x, a_i) jweils 6 Felder bestimmt. Die muss man dann erst
einmal alle als "Folgeaktion" ausfüllen, bevor man zu einer weiteren
Ziffer in einem weiteren freien Feld übergeht.
>
Man begint also erst einmal mit den bereits in der Aufgabenstellung
gegebenen Ziffenpaaren (a_i, a_j) und füllt damit die daraus pro Paar
resultierenden 5 weitern Felder aus, bevor man noch nicht vorhandene
Ziffern hinzufügt.
>
Das ausfüllen wird dadurch zu einem "Kinderspiel", nach einer rein
"mechanischen Regel-Vorgehensweise" ohne darüber nachdenken zu müssen.
Schlichtweg ein paar banale Ausfüllregeln beachten. Das wird dann schnell
langweilig.
>
Gibt es auch Sudoku-Meisterschaften? Was gibt es da zu gewinnen?
>
Peter Kramer
Aug 25, 2013, 3:39:07 AM8/25/13
to
Detlef Müller <lef...@arcor.de> wrote in
news:52191dc7$0$9520$9b4e...@newsspool1.arcor-online.net:
> On 24.08.2013 12:05, Peter Kramer wrote:
>> =?UTF-8?B?TWFyY3VzIEdsw7ZkZXI=?= <m.gl...@gmx.de> wrote in
>> news:5216E721...@gmx.de:
>>
>>>
>>> 1. Wieviele verschiedene geloeste Sudokus sind bei einer gegebenen
>>> Sudoku-Grösse (Anzahl der Zeilen, Spalten und Quadranten) möglich
>>> (Anzahl der Permutationen,[1] die der Regel entsprechen, dass jede
>>> Ziffer pro Zeile, Spalte und Quadrant genau einmal vorkommen muss)?
>>>
>> Eine Grundlösung erzielt durch zirkuläre Permutation der Grundreihe:
>>> ... ----------------------
>>>
>> 1.) Die können wir nun noch 8 mal, (modulo 9) mit 1 addieren, also
>> eine Translation mit 1 (modulo 9). Das gibt insgesamt 9
>> Grundlösungen. Also einFaktor 9.
>
> Sprich, die Ziffern zyklisch vertauschen.
>
Richtig, wäre das gleiche.
zu einem gültigen Sudoku.
>
Alle noch zusätzlich *möglichen* Permutationen sind von mir weiter unten
erwähnt.
>
Theoretisch sind durch beliebige Permutation, 9!*9! Gesamtfelder 9x9
möglich. Aber nur ein Bruchteil davon entspricht den Sudokuregeln.
von mir erwähnten, welche eine neue Variante generieren, da ich alle
möglichen Elemente der Sudokustruktur, Zellen, Zeilen, Spalten, Blöcke,
in jeweils einer Transformation berücksichtigt habe.
>
Durch die von mir erwähnten Transformationen kann man aus jedem
beliebigen Sudoku jewelches andere Sudoku generieren. Weitere
Transformationen gibt es nicht und braucht man auch nicht.
>
Fällt dir noch eine weitere Transformation ein, welche aus einem gültigen
Sudoku ein weiteres gültiges Sudoku generieren würde?
>
news:52191dc7$0$9520$9b4e...@newsspool1.arcor-online.net:
> On 24.08.2013 12:05, Peter Kramer wrote:
>> =?UTF-8?B?TWFyY3VzIEdsw7ZkZXI=?= <m.gl...@gmx.de> wrote in
>> news:5216E721...@gmx.de:
>>
>>>
>>> 1. Wieviele verschiedene geloeste Sudokus sind bei einer gegebenen
>>> Sudoku-Grösse (Anzahl der Zeilen, Spalten und Quadranten) möglich
>>> (Anzahl der Permutationen,[1] die der Regel entsprechen, dass jede
>>> Ziffer pro Zeile, Spalte und Quadrant genau einmal vorkommen muss)?
>>>
>> Eine Grundlösung erzielt durch zirkuläre Permutation der Grundreihe:
>>> ... ----------------------
>>>
>> 1.) Die können wir nun noch 8 mal, (modulo 9) mit 1 addieren, also
>> eine Translation mit 1 (modulo 9). Das gibt insgesamt 9
>> Grundlösungen. Also einFaktor 9.
>
>
Richtig, wäre das gleiche.
>
> Natürlich gibt es noch viel mehr Permutationen der Ziffern (als nur
> die zyklischen Vertauschungen) - und jede davon führt zu einem
> weiteren Sudoku.
>
Nein, nicht jede beliebige Permutation in einer Zeile oder Spalte, führt
> Natürlich gibt es noch viel mehr Permutationen der Ziffern (als nur
> die zyklischen Vertauschungen) - und jede davon führt zu einem
> weiteren Sudoku.
>
zu einem gültigen Sudoku.
>
Alle noch zusätzlich *möglichen* Permutationen sind von mir weiter unten
erwähnt.
>
Theoretisch sind durch beliebige Permutation, 9!*9! Gesamtfelder 9x9
möglich. Aber nur ein Bruchteil davon entspricht den Sudokuregeln.
>
>>>
>> 2.) paarweiser Tausch der Zeilen und Spalten pro 3x3 Block horizontal
>> und vertikal das ergibt weiter 4^3*4^3 Möglichkeiten.
>
> Die Operationen verstehe ich nicht. In einem Block selbst kann ich
> doch gar nichts vertauschen, ohne die umgebenden Blöcke zu beachten?!
>
Richtig!
>>>
>> 2.) paarweiser Tausch der Zeilen und Spalten pro 3x3 Block horizontal
>> und vertikal das ergibt weiter 4^3*4^3 Möglichkeiten.
>
> Die Operationen verstehe ich nicht. In einem Block selbst kann ich
> doch gar nichts vertauschen, ohne die umgebenden Blöcke zu beachten?!
>
>
>>>
>> 3.) paarweiser Tausch der Blöcke horizontal und vertikal das ergibt
>> weitere 4^2 Möglichkeiten
>>>
>> 4.) paarweiser Zirkulärtausch zweier Ziffern ergibt weitere 81*40
>> Möglichkeiten
>
> Genau genommen verstehe ich (außer der zyklischen Zifferntauschung
> bzw. "+1 modulo 9") keine einzige der von Dir aufgeführten
> Operationen.
>
> Aber nehmen wir an, Du hast hier einige Möglichkeiten gefunden, aus
> der Grundlösung weitere Lösungen zu generieren, mit denen Du
>
>> also insgesamt:
>>>
>> 9*4^8*81*40 = 1.911.029.760
>>>
>> ungefähr 1/8 der Reihenanzahl beim Lotto 6 aus 49
>
> Sudokus erhältst, so fehlt doch nun der Nachweis, daß das auch alle
>>>
>> 3.) paarweiser Tausch der Blöcke horizontal und vertikal das ergibt
>> weitere 4^2 Möglichkeiten
>>>
>> 4.) paarweiser Zirkulärtausch zweier Ziffern ergibt weitere 81*40
>> Möglichkeiten
>
> Genau genommen verstehe ich (außer der zyklischen Zifferntauschung
> bzw. "+1 modulo 9") keine einzige der von Dir aufgeführten
> Operationen.
>
> Aber nehmen wir an, Du hast hier einige Möglichkeiten gefunden, aus
> der Grundlösung weitere Lösungen zu generieren, mit denen Du
>
>> also insgesamt:
>>>
>> 9*4^8*81*40 = 1.911.029.760
>>>
>> ungefähr 1/8 der Reihenanzahl beim Lotto 6 aus 49
>
> möglichen Sudoku-Stellungen ergibt.
>
> Warum soll es also nicht noch weitere so nicht erreichbare
> Lösungsstellungen geben?
>
Weil es keine weiteren Transformationen des Sudokufeldes gibt, als jene
>
> Warum soll es also nicht noch weitere so nicht erreichbare
> Lösungsstellungen geben?
>
von mir erwähnten, welche eine neue Variante generieren, da ich alle
möglichen Elemente der Sudokustruktur, Zellen, Zeilen, Spalten, Blöcke,
in jeweils einer Transformation berücksichtigt habe.
>
Durch die von mir erwähnten Transformationen kann man aus jedem
beliebigen Sudoku jewelches andere Sudoku generieren. Weitere
Transformationen gibt es nicht und braucht man auch nicht.
>
Fällt dir noch eine weitere Transformation ein, welche aus einem gültigen
Sudoku ein weiteres gültiges Sudoku generieren würde?
>
Bergholt Stuttley Johnson
Aug 25, 2013, 3:49:49 AM8/25/13
to
Peter Kramer wrote:
>
> Bergholt Stuttley Johnson <b...@am.invalid> wrote in
> news:MPG.2c82b5b9b...@news.eternal-september.org:
>
> Bergholt Stuttley Johnson <b...@am.invalid> wrote in
> news:MPG.2c82b5b9b...@news.eternal-september.org:
> > Ich habe das von mir empfohlene Buch vor über
> > einem Jahr gelesen und mich seit dem nicht mehr
> > mit Sudoku beschäftigt. Zum Zeitpunkt, als das
> > Buch geschrieben wurde, kannte man viele eindeutig
> > lösbare Sudokus mit 17 Vorgaben.
> >
> Das kann nicht sein!
>
> > einem Jahr gelesen und mich seit dem nicht mehr
> > mit Sudoku beschäftigt. Zum Zeitpunkt, als das
> > Buch geschrieben wurde, kannte man viele eindeutig
> > lösbare Sudokus mit 17 Vorgaben.
> >
> Das kann nicht sein!
>
> Eindeutig lösbar, mit einer 'einzigen' Lösung, ist ein SUDOKU
> (3x3)x(3x3)=9x9 nur dann, wenn maximal 5 Zellen frei sind
Dann gib mal zu irgendeinem Sudoku auf
http://school.maths.uwa.edu.au/~gordon/sudokumin.php
zwei Lösungen an.
Marcus Glöder
Aug 25, 2013, 3:53:51 AM8/25/13
to
Am 25.08.2013 08:01, schrieb Peter Kramer:
> =?ISO-8859-15?Q?Marcus_Gl=F6der?= <m.gl...@gmx.de> wrote in
> news:kvaen3$dmh$1...@dont-email.me:
>
>> Hallo Peter,
vielen Dank für deine Antwort.
> =?ISO-8859-15?Q?Marcus_Gl=F6der?= <m.gl...@gmx.de> wrote in
> news:kvaen3$dmh$1...@dont-email.me:
>
>> Hallo Peter,
>>
>> steht nehme, dann ist zum Beispiel
>>
>> 11 modulo 5 = 1
>>
> Richtig!
>>
>> weil
>>
>> 11 : 5 = 2 Rest 1
>>
>> ist (so wie das in der Grundschule gerechnet wird). »modulo« würde
>> also den ganzzahligen Rest bei Divisionen angeben. Richtig? Was
>> bedeutet dann
>>
>>> 1.) Die können wir nun noch 8 mal, (modulo 9) mit 1 addieren, also
>>> eine Translation mit 1 (modulo 9). Das gibt insgesamt 9
>>> Grundlösungen. Also einFaktor 9.
>>
>> Zu meinem zweiten Problem (Mindestanzahl der Vorgaben, die nötig
>> sind, um ein Sudoku vorgegebener Größe eindeutig lösen zu können)
>> schreibst Du:
>>
>>> Spielt keine Rolle. Da es immer eine Lösung gibt, ist es egal
>>> wieviele Zahlen man mindestens, egal wie, vorgibt.
>>
>> Das ist nun eindeutig falsch.
>>
> Nein.
>> Wenn die Anzahl der Vorgaben, die ich mache, gleich Null ist, dann ist
>> das Sudoku (egal, welche Größe es hat), nicht lösbar.
>>
> Aber selbstverständlich ist es lösbar. Jedwelche gültige Lösung ist dann
> eine Lösung, bzw. die Lösungsmenge ist die Menge aller Lösungen.
> OK, ich hätte an der Stelle wohl schreiben sollen: »nicht eindeutig lösbar«.
>> Also: es gibt immer eine Mindestanzahl an Feldern,
>> die ich vorgeben muss, damit alle anderen Felder determiniert sind.
>>
> Es müssen nicht alle Zellen eindeutig determiniert sein, denn es muss ja
> nicht nur eine Lösung geben. [...]
>> die ich vorgeben muss, damit alle anderen Felder determiniert sind.
>>
> Es müssen nicht alle Zellen eindeutig determiniert sein, denn es muss ja
Genau darum geht es mir aber: wie viele Vorgaben muss ich mindestens
machen, damit ein Sudoku gegebener Größe genau eine Lösung hat? Nimm
einfach mal die folgenden drei 4x4-Sudokus und versuche sie zu lösen
(das kostet Dich schätzungsweise weniger als eine Minute Deiner Zeit):
eindeutig:
** *2
*1 **
4* **
** 3*
»unterdeterminiert«
** *2
*1 **
4* **
** **
widersprüchlich
** *2
*1 **
4* **
** 31.
Das zweite Sudoku besitzt mehr als eine und das dritte Sudoku gar keine
gültige Lösung. Aus der Sicht eines Menschen, der in einem Café sitzt,
und dort ein Sudoku aus einer der dort herumliegenden Zeitungen löst,
ist nur das erste Sudoku richtig konstruiert. Es hat, anders als das
zweite, genau eine Lösung und führt nicht, wie das dritte, zu
(mindestens) einem Widerspruch.
Um es noch einmal zu sagen, die Frage war: Wieviele Felder muss ich in
einem Sudoku gegebener Größe mindestens vorgeben, damit
alle anderen Felder eindeutig bestimmt sind? bzw.
es nur noch eine gültige Lösung gibt? bzw.
das Sudoku eindeutig lösbar ist?
Alle drei Formulierungen sind bedeuten dasselbe.
> [...] Es gibt immer mehr als eine Lösung, wenn es
> noch mehr als 5 freie Zellen in der Vorgabe gibt.
Hm. In dem von mir oben angegebenen ersten 4x4-Sudoku sind von den 16
Zellen, die das Sudoku hat, 4 vorgegeben und 12 noch frei. das sind
eindeutig mehr als 5 freie Felder. dennoch ist das Sudoku eindeutig
lösbar (hat also nur eine Lösung). Bei 9x9-Sudokus habe ich in einem
anderen Posting gelesen, dass mindestens 17 Vorgaben gemacht werden
müssen. Dann sind aber immernoch 64 Felder frei. Wenn das mit den 5
freien Feldern stimmen würde, müsste ich ja bei einem 9x9-Sudoku 76
Vorgaben machen. Also, ich habe noch in keiner Zeitschrift ein Sudoku
mit so vielen vorgegebenen Zellen gesehen. Und alle waren sie eindeutig
lösbar.
>>
>>> Je mehr Zellen vorgegeben sind, desto kleiner ist die Lösungsmenge.
>>
>> Mit anderen Worten: je mehr Vorgaben ich mache, desto weniger mögliche
>> Lösungen gibt es. Das gilt bis zu dem Grenzfall, dass es nur noch eine
>> mögliche Lösung gibt.
>>
> Die einzige Lösung gibt es nur dann wenn maximal 5 Zellen unbesetzt sind,
> denn zum Tausch zweier Ziffern benötigt man 6 Zellen.
>>
> Sind also 6 Zellen unbesetzt gibt es nur noch zwei mögliche Lösungen.
>>
Hans-Peter Diettrich
Aug 25, 2013, 5:39:49 AM8/25/13
to
Marcus Glöder schrieb:
jedes Komma auf die Goldwaage legen :-[
>>> [...] bei ihrem kleinsten möglichen Wert, nämlich 1,[...]
>> +1
>
> Ich hatte mich an die Konvention gehalten, bei positiven Zahlen das
> Vorzeichen wegzulassen.
Das ist so ein Fall von Mißverständnis. Mit "+1" hatte ich Zustimmung
gemeint, keine Fehlerkorrektur :-)
DoDi
> Hallo Hans-Peter,
>
> Du schreibst:
>
>> Ich hoffe, das gibt jetzt keinen Streit zwischen den Wissenschaften ;-)
>
> Nö.
Das kann leider leicht passieren, vor allem wenn Korinthenausscheider
>
> Du schreibst:
>
>> Ich hoffe, das gibt jetzt keinen Streit zwischen den Wissenschaften ;-)
>
> Nö.
jedes Komma auf die Goldwaage legen :-[
>>> [...] bei ihrem kleinsten möglichen Wert, nämlich 1,[...]
>> +1
>
> Ich hatte mich an die Konvention gehalten, bei positiven Zahlen das
> Vorzeichen wegzulassen.
gemeint, keine Fehlerkorrektur :-)
DoDi
Hans-Peter Diettrich
Aug 25, 2013, 5:58:27 AM8/25/13
to
Peter Kramer schrieb:
> Den Widerspruch liferst du selber ;-) siehe(*****)
Sehe ich immer noch nicht.
> "Wenn keine Vorgaben existieren, ist jede mögliche Lösung eine Lösung"
> Die Lösungsmenge ist dann Menge aller möglichen Lösungen beim SUDOKU.
Wann könnte die Lösungsmenge etwas anderes enthalten als mögliche
Lösungen? ;-)
IMO sollte man zwischen "Lösung" und "Lösungsmenge" unterscheiden.
Während "Lösung" dann eine (einzige) eindeutige Lösung bezeichnen kann,
hat man bei Mengenbegriffen immer eine variable Mächtigkeit (Anzahl
Lösungen). Wobei die leere Menge nicht grundsätzlich ausgeschlossen ist...
BTW ich hasse mehrdeutige Sudokus und habe schon daran gedacht, mir ein
Programm zu schreiben, das eine Vorgabe auf die Anzahl der zugehörigen
Lösungen testet. Aber dann müßte ich mich näher mit der Theorie
befassen, und das könnte mir den Spaß am Knobeln dauerhaft verderben :-(
DoDi
> Den Widerspruch liferst du selber ;-) siehe(*****)
> "Wenn keine Vorgaben existieren, ist jede mögliche Lösung eine Lösung"
> Die Lösungsmenge ist dann Menge aller möglichen Lösungen beim SUDOKU.
Lösungen? ;-)
IMO sollte man zwischen "Lösung" und "Lösungsmenge" unterscheiden.
Während "Lösung" dann eine (einzige) eindeutige Lösung bezeichnen kann,
hat man bei Mengenbegriffen immer eine variable Mächtigkeit (Anzahl
Lösungen). Wobei die leere Menge nicht grundsätzlich ausgeschlossen ist...
BTW ich hasse mehrdeutige Sudokus und habe schon daran gedacht, mir ein
Programm zu schreiben, das eine Vorgabe auf die Anzahl der zugehörigen
Lösungen testet. Aber dann müßte ich mich näher mit der Theorie
befassen, und das könnte mir den Spaß am Knobeln dauerhaft verderben :-(
DoDi
Peter Kramer
Aug 25, 2013, 8:34:16 AM8/25/13
to
=?ISO-8859-15?Q?Marcus_Gl=F6der?= <m.gl...@gmx.de> wrote in
news:kvcd6i$pj5$1...@dont-email.me:
>
> Genau darum geht es mir aber: wie viele Vorgaben muss ich mindestens
> machen, damit ein Sudoku gegebener Gr��e genau eine L�sung hat? Nimm
> einfach mal die folgenden drei 4x4-Sudokus und versuche sie zu l�sen
> (das kostet Dich sch�tzungsweise weniger als eine Minute Deiner Zeit):
>
Also erstens, ein planares 2D-Sudoku(es gibt auch 3D-Sudokus im Raum),
2-Sudoku hat 4x4 Zellen und 2x2 Bl�cke. Was du da unten angibst ist kein
zweier Sudoku.
>
> ** *2
> *1 **
>
Dir f�llt aber schon auf, dass du bei �unterdeterminiert� und
"widerspr�chlich" die gleiche Konfiguration angegeben hast ? ;
>
> 4* * *
> ** 3 1
>
Schau mer mal ;-)
>
>�unterdeterminiert� sagst du????
>
> ** *2
> *1 **
> ** **
>
Wie w�re es mit:
>
4,3,1,2
>
2,1,3,4
>
1,4,2,3
>
3,2,4,1
>
Eine zweimalige Zirkul�rpermutation der Standardkonfiguration.
>
4, *, *, *
>
*, *, 3, 1
>
*, *, *, *
>
Es gibt kein Sudoku mit dieser Verteilung, sie widerspricht den Regeln des
Sudoku. An einer der beiden Stellen, 3 oder 1, muss eine 4 stehen, sagen
die Regeln des Sudoku. Also kann sie auch nicht als Aufgabenstellung
dienen.
>
Es gibt keine unl�sbaren Sudokus, egal welcher Art, schon gar nicht
"undeterminiert" oder "gar keine L�sung", insofern die Aufgabenstellung den
Regeln des Sudoku entspricht.
> das Sudoku eindeutig l�sbar ist?
>
Bei einem widerspruchsfreien 3-Sudoku 9x9, wie auch bei einem
2-Sudoku 4x4, d�rfen maximal 5 Felder frei sein, wenn eine der Zahlen noch
nicht in der Aufgabenstellung vergeben ist.
>
Wenn alle Zahlen vergeben sind, ist die Antwort nicht einfach zu geben.
>
Es kommt darauf an wie oft eine jede Ziffer bereits vergeben ist, wieviele
Ziffern in einem Block gegeben sind, usw.
>
Allein die Anzahl der bereits ausgef�llten Zellen in der Aufgabenstellung,
bestimmt nicht alleine die Eindeutigkeit der L�sung.
>
news:kvcd6i$pj5$1...@dont-email.me:
>
> Genau darum geht es mir aber: wie viele Vorgaben muss ich mindestens
> einfach mal die folgenden drei 4x4-Sudokus und versuche sie zu l�sen
> (das kostet Dich sch�tzungsweise weniger als eine Minute Deiner Zeit):
>
Also erstens, ein planares 2D-Sudoku(es gibt auch 3D-Sudokus im Raum),
2-Sudoku hat 4x4 Zellen und 2x2 Bl�cke. Was du da unten angibst ist kein
zweier Sudoku.
>
> eindeutig:
>
> ** *2
> *1 **
>
> 4* **
> ** 3*
>
>�unterdeterminiert�
>
> ** *2
> *1 **
>
> 4* **
> ** **
>
> widerspr�chlich
> eindeutig:
>
> ** *2
> *1 **
>
> 4* **
> ** 3*
>
>�unterdeterminiert�
>
> ** *2
> *1 **
>
> 4* **
> ** **
>
>
> ** *2
> *1 **
>
Dir f�llt aber schon auf, dass du bei �unterdeterminiert� und
"widerspr�chlich" die gleiche Konfiguration angegeben hast ? ;
>
> 4* * *
> ** 3 1
>
> Das zweite Sudoku besitzt mehr als eine und das dritte Sudoku gar
> keine g�ltige L�sung.
> Das zweite Sudoku besitzt mehr als eine und das dritte Sudoku gar
>
Schau mer mal ;-)
>
>�unterdeterminiert� sagst du????
>
> ** *2
> *1 **
> ** **
>
Wie w�re es mit:
>
4,3,1,2
>
2,1,3,4
>
1,4,2,3
>
3,2,4,1
>
Eine zweimalige Zirkul�rpermutation der Standardkonfiguration.
>
4, *, *, *
>
*, *, 3, 1
>
*, *, *, *
>
Es gibt kein Sudoku mit dieser Verteilung, sie widerspricht den Regeln des
Sudoku. An einer der beiden Stellen, 3 oder 1, muss eine 4 stehen, sagen
die Regeln des Sudoku. Also kann sie auch nicht als Aufgabenstellung
dienen.
>
Es gibt keine unl�sbaren Sudokus, egal welcher Art, schon gar nicht
"undeterminiert" oder "gar keine L�sung", insofern die Aufgabenstellung den
Regeln des Sudoku entspricht.
>
> Um es noch einmal zu sagen, die Frage war: Wieviele Felder muss ich in
> einem Sudoku gegebener Gr��e mindestens vorgeben, damit
> Um es noch einmal zu sagen, die Frage war: Wieviele Felder muss ich in
>
> alle anderen Felder eindeutig bestimmt sind? bzw.
> es nur noch eine g�ltige L�sung gibt? bzw.
> alle anderen Felder eindeutig bestimmt sind? bzw.
> das Sudoku eindeutig l�sbar ist?
>
Bei einem widerspruchsfreien 3-Sudoku 9x9, wie auch bei einem
2-Sudoku 4x4, d�rfen maximal 5 Felder frei sein, wenn eine der Zahlen noch
nicht in der Aufgabenstellung vergeben ist.
>
Wenn alle Zahlen vergeben sind, ist die Antwort nicht einfach zu geben.
>
Es kommt darauf an wie oft eine jede Ziffer bereits vergeben ist, wieviele
Ziffern in einem Block gegeben sind, usw.
>
Allein die Anzahl der bereits ausgef�llten Zellen in der Aufgabenstellung,
bestimmt nicht alleine die Eindeutigkeit der L�sung.
>
Bergholt Stuttley Johnson
Aug 25, 2013, 9:18:59 AM8/25/13
to
Hans-Peter Diettrich wrote:
>
> BTW ich hasse mehrdeutige Sudokus und habe schon daran gedacht, mir
> ein Programm zu schreiben, das eine Vorgabe auf die Anzahl der
> zugehï¿œrigen Lï¿œsungen testet.
>
> BTW ich hasse mehrdeutige Sudokus und habe schon daran gedacht, mir
> ein Programm zu schreiben, das eine Vorgabe auf die Anzahl der
Wozu selber schreiben?
Sudokulï¿œser gibt's wie Sand am Meer.
Hier welche in Haskell:
http://www.haskell.org/haskellwiki/Sudoku
Viele Programme geben *alle* Lï¿œsungen aus.
Die kann man, wenn man nicht selber zï¿œhlen will,
leicht so abï¿œndern, dass sie die Anzahl
der Lï¿œsungen ausgeben.
Hans-Peter Diettrich
Aug 25, 2013, 10:51:10 AM8/25/13
to
Bergholt Stuttley Johnson schrieb:
will ich die (eindeutigen) Sudokus schon noch selbst.
> Hier welche in Haskell:
> http://www.haskell.org/haskellwiki/Sudoku
> Viele Programme geben *alle* Lï¿œsungen aus.
> Die kann man, wenn man nicht selber zï¿œhlen will,
> leicht so abï¿œndern, dass sie die Anzahl
> der Lï¿œsungen ausgeben.
Ich kann kein Haskell, und auch sonst ist es meist nicht so einfach, ein
fertiges Programm zu ï¿œndern. Meist braucht man auch noch den genau dazu
passenden Compiler...
DoDi
> Hans-Peter Diettrich wrote:
>> BTW ich hasse mehrdeutige Sudokus und habe schon daran gedacht, mir
>> ein Programm zu schreiben, das eine Vorgabe auf die Anzahl der
>> zugehï¿œrigen Lï¿œsungen testet.
>
>
> Wozu selber schreiben?
> Sudokulï¿œser gibt's wie Sand am Meer.
Ich will aber keine Lï¿œsungen bekommen, sondern nur die Anzahl. Lï¿œsen
>> BTW ich hasse mehrdeutige Sudokus und habe schon daran gedacht, mir
>> ein Programm zu schreiben, das eine Vorgabe auf die Anzahl der
>> zugehï¿œrigen Lï¿œsungen testet.
>
>
> Wozu selber schreiben?
> Sudokulï¿œser gibt's wie Sand am Meer.
will ich die (eindeutigen) Sudokus schon noch selbst.
> Hier welche in Haskell:
> http://www.haskell.org/haskellwiki/Sudoku
> Viele Programme geben *alle* Lï¿œsungen aus.
> Die kann man, wenn man nicht selber zï¿œhlen will,
> leicht so abï¿œndern, dass sie die Anzahl
> der Lï¿œsungen ausgeben.
fertiges Programm zu ï¿œndern. Meist braucht man auch noch den genau dazu
passenden Compiler...
DoDi
Marcus Glöder
Aug 25, 2013, 12:04:38 PM8/25/13
to
Hallo Peter,
die drei Beispielsudokus habe ich konstruiert, weil sie ganz ohne
Mathematik sehr schnell nachzuvollziehen sind. Um weiteres Herumstochern
im Nebel zu vermeiden (was Du schreibst, verstehe ich leider nicht so
ganz) demonstriere ich einfach mal, wie ich mir das gedacht habe:
Zunï¿œchst wiederhole ich an dieser Stelle einfach mal die
Bezeichnungsweise, die ich in meinem Eingangsposting eingefï¿œhrt habe.
Damit werde ich nï¿œmlich gleich arbeiten:
--- Schnipp ---
Ein 4x4-Sudoku hat 4x4=16 Felder. Die vier Quadranten benenne ich jetzt
mal so:
ab
cd
und die Felder so:
a1 a2 b1 b2
a3 a4 b3 b4
c1 c2 d1 d2
c3 c4 d3 d4
Die Felder habe ich also nach den Quadranten benannt, in denen sie liegen.
--- Schnapp ---
Das erste Sudoku (von mir als ￜeindeutigￜ) bezeichnet, sieht so aus:
** *2
*1 **
4* **
** 3*
Es hat also folgende Vorgaben: 1 in a4, 2 in b2, 4 in c1 und 3 in d3.
Mit den folgenden, ganz unmathematischen und traditionellen, Schritten:
4 in b3
2 in c4
3 in c2
1 in c3
4 in d4
4 in a2
3 in b4
1 in d2
2 in d1
1 in b1
3 in a1
2 in a3
komme ich zu der folgenden eindeutigen Lï¿œsung:
34 12
21 43
43 21
12 34
Nun nehme ich fï¿œr des zweite Beispiel einfach eine Vorgabe weg, so dass
ich nur noch drei Vorgaben habe: 1 in a4, 2 in b2 und 4 in c1. Das
Sudoku sieht dann so aus:
** *2
*1 **
4* **
** **
Nun komme ich durch die folgenden Schritte:
3 in a1
2 in a3
4 in a2
1 in c3
1 in b1
1 in d2
zu der folgenden Situation
34 12
21 **
4* *1
1* **
Jetzt komme ich leider nicht weiter. Die Zellen c2, c4 und d1 kï¿œnnen die
Ziffern 2 oder 3 enthalten, die Zellen b3, b4 und d4 die Ziffern 3 oder
4 und die Zelle d3 die Ziffern 2, 3 oder 4. Mit anderen Worten: dieses
Sudoku hat mehrere gï¿œltige Lï¿œsungen und kann deshalb nicht eindeutig
gelï¿œst werden. Da nur 6 von 13 freien Feldern durch die Vorgaben
eindeutig bestimmt sind, habe ich das ￜunterdetermiertￜ genannt.
Im letzten Beispielsudoku habe ich zu den 4 Vorgaben des ersten
Beispiels noch eine weitere hinzugefï¿œgt, aber mit Absicht an eine
falsche Stelle. In das Feld d4, in das nach dem ersten Sudoku eine 4
gehï¿œrt, habe ich als Vorgabe eine 1 geschrieben. Jetzt habe ich also als
Vorgaben 1 in a4, 2 in b2, 4 in c1, 3 in d3 und 1 in d4. Das sieht dann
so aus:
** *2
*1 **
4* **
** 31
Jetzt komme ich durch die folgenden Schritte:
2 in c4
3 in c2
4 in a2
3 in a1
2 in a3
1 in b1
4 in b3
3 in b4
2 in d1
zu der folgenden Situation:
34 12
21 43
43 2#
#2 31
In den Feldern d2 und c3 ergibt sich jeweils ein Widerspruch (was wegen
der bewusst fehlerhaften Konstruktion auch kein Wunder ist): in beiden
Feldern mï¿œssten sowohl eine 1 als auch eine 4 stehen und gleichzeitig
dï¿œrfen in beiden Feldern weder eine 1 noch eine 4 stehen. Es gibt keine
gï¿œltige Lï¿œsung fï¿œr dieses Sudoku.
Die drei Beispielsudokus habe ich eigentlich konstriert, um zu
zeigen, was ich jeweils mit einem ￜeindeutig lￜsbarenￜ, einem
ￜunterdeterminiertenￜ und einem ￜwidersprￜchlichenￜ Sudoku meine. An
sich ist das auch nicht so schwierig und eigentlich eindeutig, finde ich.
Viele Grￜￜe
die drei Beispielsudokus habe ich konstruiert, weil sie ganz ohne
Mathematik sehr schnell nachzuvollziehen sind. Um weiteres Herumstochern
im Nebel zu vermeiden (was Du schreibst, verstehe ich leider nicht so
ganz) demonstriere ich einfach mal, wie ich mir das gedacht habe:
Zunï¿œchst wiederhole ich an dieser Stelle einfach mal die
Bezeichnungsweise, die ich in meinem Eingangsposting eingefï¿œhrt habe.
Damit werde ich nï¿œmlich gleich arbeiten:
--- Schnipp ---
Ein 4x4-Sudoku hat 4x4=16 Felder. Die vier Quadranten benenne ich jetzt
mal so:
ab
cd
und die Felder so:
a1 a2 b1 b2
a3 a4 b3 b4
c1 c2 d1 d2
c3 c4 d3 d4
Die Felder habe ich also nach den Quadranten benannt, in denen sie liegen.
--- Schnapp ---
Das erste Sudoku (von mir als ￜeindeutigￜ) bezeichnet, sieht so aus:
** *2
*1 **
4* **
** 3*
Mit den folgenden, ganz unmathematischen und traditionellen, Schritten:
4 in b3
2 in c4
3 in c2
1 in c3
4 in d4
4 in a2
3 in b4
1 in d2
2 in d1
1 in b1
3 in a1
2 in a3
komme ich zu der folgenden eindeutigen Lï¿œsung:
34 12
21 43
43 21
12 34
Nun nehme ich fï¿œr des zweite Beispiel einfach eine Vorgabe weg, so dass
ich nur noch drei Vorgaben habe: 1 in a4, 2 in b2 und 4 in c1. Das
Sudoku sieht dann so aus:
** *2
*1 **
4* **
** **
3 in a1
2 in a3
4 in a2
1 in c3
1 in b1
1 in d2
zu der folgenden Situation
34 12
21 **
4* *1
1* **
Jetzt komme ich leider nicht weiter. Die Zellen c2, c4 und d1 kï¿œnnen die
Ziffern 2 oder 3 enthalten, die Zellen b3, b4 und d4 die Ziffern 3 oder
4 und die Zelle d3 die Ziffern 2, 3 oder 4. Mit anderen Worten: dieses
Sudoku hat mehrere gï¿œltige Lï¿œsungen und kann deshalb nicht eindeutig
gelï¿œst werden. Da nur 6 von 13 freien Feldern durch die Vorgaben
eindeutig bestimmt sind, habe ich das ￜunterdetermiertￜ genannt.
Im letzten Beispielsudoku habe ich zu den 4 Vorgaben des ersten
Beispiels noch eine weitere hinzugefï¿œgt, aber mit Absicht an eine
falsche Stelle. In das Feld d4, in das nach dem ersten Sudoku eine 4
gehï¿œrt, habe ich als Vorgabe eine 1 geschrieben. Jetzt habe ich also als
Vorgaben 1 in a4, 2 in b2, 4 in c1, 3 in d3 und 1 in d4. Das sieht dann
so aus:
** *2
*1 **
4* **
Jetzt komme ich durch die folgenden Schritte:
2 in c4
3 in c2
4 in a2
3 in a1
2 in a3
1 in b1
4 in b3
3 in b4
2 in d1
zu der folgenden Situation:
34 12
21 43
43 2#
#2 31
In den Feldern d2 und c3 ergibt sich jeweils ein Widerspruch (was wegen
der bewusst fehlerhaften Konstruktion auch kein Wunder ist): in beiden
Feldern mï¿œssten sowohl eine 1 als auch eine 4 stehen und gleichzeitig
dï¿œrfen in beiden Feldern weder eine 1 noch eine 4 stehen. Es gibt keine
gï¿œltige Lï¿œsung fï¿œr dieses Sudoku.
Die drei Beispielsudokus habe ich eigentlich konstriert, um zu
zeigen, was ich jeweils mit einem ￜeindeutig lￜsbarenￜ, einem
ￜunterdeterminiertenￜ und einem ￜwidersprￜchlichenￜ Sudoku meine. An
sich ist das auch nicht so schwierig und eigentlich eindeutig, finde ich.
Viele Grￜￜe
Detlef Müller
Aug 25, 2013, 4:37:20 PM8/25/13
to
On 25.08.2013 08:31, Peter Kramer wrote:
> Bergholt Stuttley Johnson <b...@am.invalid> wrote in
> news:MPG.2c82b5b9b...@news.eternal-september.org:
>
>> Marcus Gl�der wrote:
> Bergholt Stuttley Johnson <b...@am.invalid> wrote in
> news:MPG.2c82b5b9b...@news.eternal-september.org:
>
>>>
>>> Wieviele Zellen m�ssen bei einem Sudoku gegebener Gr��e mindestens
>>> vorgegeben werden, damit alle anderen Zellen determiniert und das
>>> Sudoku damit eindeutig l�sbar ist (Anzahl der Freiheitsgrade[2])?
>>
>> Ich habe das von mir empfohlene Buch vor �ber
>> einem Jahr gelesen und mich seit dem nicht mehr
>> mit Sudoku besch�ftigt. Zum Zeitpunkt, als das
>> Buch geschrieben wurde, kannte man viele eindeutig
>> l�sbare Sudokus mit 17 Vorgaben.
>>
> Das kann nicht sein!
>>
Ok, das ist ein Wort.
Dann gebe ich jetzt ein Sudoku mit nur 17 Vorgaben
und zwar:
7.. 1.8 ...
.9. ... .32
... ..5 ...
... ... 1..
96. .2. ...
... ... 8..
... ... ...
..5 ..1 ...
32. ... ..6
Und bitte um Angabe von mindestens zwei verschiedenen
Vervollst�ndigungen mit den vorgegebenen 17 Ziffern an
genau den angegebenen Stellen.
Eventuell ist das auch eine Gelegenheit, das geradezu langweilig
mechanische Verfahren zur L�sung zu demonstrieren.
Gru�,
Detlef
Peter Kramer
Aug 26, 2013, 2:07:29 AM8/26/13
to
Bergholt Stuttley Johnson <b...@am.invalid> wrote in
news:MPG.2c83d58b7...@news.eternal-september.org:
>
x x x x x x x 8 x
4 x x x x x x x x
x 8 x x x x x x x
x x x x 6 x 8 x 1
x x 7 x x x 2 x x
x x 1 x 3 x x x x
3 x x 6 x 8 9 x x
x 7 x 9 x x x x x
x x x 3 x 5 x x x
>
>
Lösung1:
>
1 x x x x x 7 8 x
4 x x 7 x x 1 x x
7 8 x 1 x x x x x
x x x x 6 x 8 x 1
x x 7 x x x 2 x x
x x 1 x 3 x x x x
3 x x 6 x 8 9 x x
x 7 x 9 x x x x x
x x x 3 x 5 x x x
>
>
Lösung2:
>
7 x x x x x 1 8 x
4 x x 1 x x 7 x x
1 8 x 7 x x x x x
x x x x 6 x 8 x 1
x x 7 x x x 2 x x
x x 1 x 3 x x x x
3 x x 6 x 8 9 x x
x 7 x 9 x x x x x
x x x 3 x 5 x x x
>
Die fehlenden Ziffern darfst du selber einsetzen.
>
(ein bischen musst du ja auch was leisten zu deiner Neugierigkeit ;-))
>
(falls du es nicht schaffst kann ich das fertige Sudoku hier posten)
>
Ich habe dazu ein bereits ausgefülltes Sudoku verwendet und x eingesetzt.
>
Es sind natürlich noch mehr Lösungen möglich.
>
Bergholt Stuttley Johnson
Aug 26, 2013, 2:33:35 AM8/26/13
to
Peter Kramer wrote:
>
> Bergholt Stuttley Johnson <b...@am.invalid> wrote in
> news:MPG.2c83d58b7...@news.eternal-september.org:
>
> Bergholt Stuttley Johnson <b...@am.invalid> wrote in
Schaumschläger ja zu rechnen.
Detlef Müller
Aug 26, 2013, 5:01:09 AM8/26/13
to
On 26.08.2013 08:07, Peter Kramer wrote:
> Bergholt Stuttley Johnson <b...@am.invalid> wrote in
> news:MPG.2c83d58b7...@news.eternal-september.org:
>
>> Peter Kramer wrote:
>>>
>>> Bergholt Stuttley Johnson <b...@am.invalid> wrote in
>>> news:MPG.2c82b5b9b...@news.eternal-september.org:
>>>> Ich habe das von mir empfohlene Buch vor �ber
> Bergholt Stuttley Johnson <b...@am.invalid> wrote in
> news:MPG.2c83d58b7...@news.eternal-september.org:
>
>> Peter Kramer wrote:
>>>
>>> Bergholt Stuttley Johnson <b...@am.invalid> wrote in
>>> news:MPG.2c82b5b9b...@news.eternal-september.org:
>>>> einem Jahr gelesen und mich seit dem nicht mehr
>>>> mit Sudoku besch�ftigt. Zum Zeitpunkt, als das
>>>> Buch geschrieben wurde, kannte man viele eindeutig
>>>> l�sbare Sudokus mit 17 Vorgaben.
>>>>
>>> Das kann nicht sein!
>>>
>>> Eindeutig l�sbar, mit einer 'einzigen' L�sung, ist ein SUDOKU
>>> (3x3)x(3x3)=9x9 nur dann, wenn maximal 5 Zellen frei sind
>>
>>
>> Dann gib mal zu irgendeinem Sudoku auf
>> http://school.maths.uwa.edu.au/~gordon/sudokumin.php
>> zwei L�sungen an.
>>
>>
>> Dann gib mal zu irgendeinem Sudoku auf
>> http://school.maths.uwa.edu.au/~gordon/sudokumin.php
>>
> (17) Vorgaben:
>>
> x x x x x x x 8 x
> 4 x x x x x x x x
> x 8 x x x x x x x
>
> x x x x 6 x 8 x 1
> x x 7 x x x 2 x x
> x x 1 x 3 x x x x
>
> 3 x x 6 x 8 9 x x
> x 7 x 9 x x x x x
> x x x 3 x 5 x x x
>>
Dieses Sudoku finde ich in der angegebenen Seite �brigens nicht.
> (17) Vorgaben:
>>
> x x x x x x x 8 x
> 4 x x x x x x x x
> x 8 x x x x x x x
>
> x x x x 6 x 8 x 1
> x x 7 x x x 2 x x
> x x 1 x 3 x x x x
>
> 3 x x 6 x 8 9 x x
> x 7 x 9 x x x x x
> x x x 3 x 5 x x x
>>
In der Tat kann ich auch hier zwei verschiedene L�sungen angeben
(die mein Rechner - neben vielen vielen anderen - gefunden hat):
|-----------------|
|1 2 3|4 5 6|7 8 9|
| | | |
|4 5 9|1 8 7|3 6 2|
| | | |
|7 8 6|2 9 3|1 5 4|
|-----------------|
|5 3 4|7 6 2|8 9 1|
| | | |
|8 9 7|5 4 1|2 3 6|
| | | |
|2 6 1|8 3 9|4 7 5|
|-----------------|
|3 4 5|6 1 8|9 2 7|
| | | |
|6 7 8|9 2 4|5 1 3|
| | | |
|9 1 2|3 7 5|6 4 8|
und
|-----------------|
|1 2 3|4 5 6|7 8 9|
| | | |
|4 5 9|1 8 7|3 6 2|
| | | |
|7 8 6|2 9 3|1 5 4|
|-----------------|
|5 3 4|7 6 2|8 9 1|
| | | |
|8 9 7|5 4 1|2 3 6|
| | | |
|2 6 1|8 3 9|4 7 5|
|-----------------|
|3 4 5|6 2 8|9 1 7| <-- Unterschied
| | | |
|6 7 8|9 1 4|5 2 3| <-- Unterschied
| | | |
|9 1 2|3 7 5|6 4 8|
-------------------
Nur ist das Sudoku ja auch nicht von der angegebenen
Quelle, sagen wir zu dieser Tatsache mal lieber:
"Honi soit qui mal y pense".
Probiere es mal mit einem von den richtigen!
Sagen wir doch -um Missverst�ndnisse zu vermeiden- ganz konkret
das erste:
+++++++1+
4++++++++
+2+++++++
++++5+4+7
++8+++3++
++1+9++++
3++4++2++
+5+1+++++
+++8+6+++
Ich bin auf Deine Varianten gespannt!
Gru�,
Detlef
Peter Kramer
Aug 26, 2013, 4:13:43 PM8/26/13
to
Detlef M�ller <lef...@arcor.de> wrote in news:521b19bc$0$9502$9b4e6d93
@newsspool1.arcor-online.net:
>
> Nur ist das Sudoku ja auch nicht von der angegebenen
> Quelle,
>
Die Zahlen nicht, das Muster schon. Es ging ja nur darum ob 17 Vorgaben
ausreichen damit ein Sudoku eindeutig ist. Wie gezeigt, nein.
>
@newsspool1.arcor-online.net:
>
> Nur ist das Sudoku ja auch nicht von der angegebenen
> Quelle,
>
ausreichen damit ein Sudoku eindeutig ist. Wie gezeigt, nein.
>
Bergholt Stuttley Johnson
Aug 26, 2013, 4:27:44 PM8/26/13
to
Peter Kramer wrote:
>
> Detlef Mï¿œller <lef...@arcor.de> wrote in news:521b19bc$0$9502$9b4e6d93
Du bist zu blï¿œd zwischen Existenzquantor
und Allquantor unterscheiden zu kï¿œnnen.
>
> Detlef Mï¿œller <lef...@arcor.de> wrote in news:521b19bc$0$9502$9b4e6d93
und Allquantor unterscheiden zu kï¿œnnen.
Peter Kramer
Aug 26, 2013, 4:39:40 PM8/26/13
to
Detlef M�ller <lef...@arcor.de> wrote in news:521a6b67$0$9515$9b4e6d93
@newsspool1.arcor-online.net:
Ich werde mich von dir nicht provozieren lassen. Dazu habe ich weder die
Zeit noch Lust dazu. Wie in der anderen Antwort gezeigt reichen 17
beliebige Vorgaben generell nicht aus.
>
Liefere mir eine L�sung und ich zeige dir die Varianten.
>
Wie gezeigt gibt es Sudokus bei denen es nicht reicht.
>
Du hast doch selber mehrere L�sungen gefunden.
>
@newsspool1.arcor-online.net:
Zeit noch Lust dazu. Wie in der anderen Antwort gezeigt reichen 17
beliebige Vorgaben generell nicht aus.
>
Liefere mir eine L�sung und ich zeige dir die Varianten.
>
Wie gezeigt gibt es Sudokus bei denen es nicht reicht.
>
Du hast doch selber mehrere L�sungen gefunden.
>
Bergholt Stuttley Johnson
Aug 26, 2013, 4:50:28 PM8/26/13
to
Bergholt Stuttley Johnson wrote:
>
> Du bist zu blï¿œd zwischen Existenzquantor
> und Allquantor unterscheiden zu kï¿œnnen.
Oh Entschuldigung, den Satz kannst du ja nicht verstehen.
>
> Du bist zu blï¿œd zwischen Existenzquantor
> und Allquantor unterscheiden zu kï¿œnnen.
Du bist zu blï¿œd einen Unterschied zischen den folgenden
Aussagen zu erkennen:
(i) Es gibt Sudokus mit 17 Vorgaben, die eindeutig lï¿œsbar sind.
(ii) Alle Sudokus mit 17 Vorgaben sind eindeutig lï¿œsbar.
Hans-Peter Diettrich
Aug 26, 2013, 8:55:17 PM8/26/13
to
Peter Kramer schrieb:
> Detlef Müller <lef...@arcor.de> wrote in news:521b19bc$0$9502$9b4e6d93
IMO ist das eine Frage der Redundanz. Wenn man vorgegebene Felder
entfernen kann, ohne daß sich die Lösungsmenge ändert, dann zählen sie
nicht - wie bei überbestimmten Gleichungssystemen, aus denen so lange
Gleichungen entfernt werden können, bis die minimal notwendige Anzahl
erreicht ist.
DoDi
> Detlef Müller <lef...@arcor.de> wrote in news:521b19bc$0$9502$9b4e6d93
entfernen kann, ohne daß sich die Lösungsmenge ändert, dann zählen sie
nicht - wie bei überbestimmten Gleichungssystemen, aus denen so lange
Gleichungen entfernt werden können, bis die minimal notwendige Anzahl
erreicht ist.
DoDi
Marcus Glöder
Aug 26, 2013, 9:46:21 PM8/26/13
to
Hallo Peter,
Du schreibst:
Sudokus mit 17 Vorgaben eindeutig lösbar sind, sondern nur, dass es
mindestens ein x gibt, von dem gesagt werden kann: x ist ein Sudoku mit
17 Vorgaben und x ist eindeutig lösbar.
E(x) (S(x)&P(x))
S Sudoku mit 17 Vorgaben
P eindeutig lösbar
(Das ist *i* im logischen Quadrat.[1])
Dass es Sudokus mit 17 Vorgaben gibt, die nicht eindeutig lösbar sind,
wie Du sagst, zeigt, dass die Position der Vorgaben ebenfalls eine Rolle
spielt.
Grüße
Marcus
[1]
Vgl. z.B.
http://sternchenland.com/philosophie-woerterbuch/gif/logquad.gif
--
PMs an: m.gl...@gmx.de
Du schreibst:
> Wie gezeigt gibt es Sudokus bei denen es nicht reicht.
Darum geht es nicht. Es ist ja nicht behauptet worden, dass /alle/
Sudokus mit 17 Vorgaben eindeutig lösbar sind, sondern nur, dass es
mindestens ein x gibt, von dem gesagt werden kann: x ist ein Sudoku mit
17 Vorgaben und x ist eindeutig lösbar.
E(x) (S(x)&P(x))
S Sudoku mit 17 Vorgaben
P eindeutig lösbar
(Das ist *i* im logischen Quadrat.[1])
Dass es Sudokus mit 17 Vorgaben gibt, die nicht eindeutig lösbar sind,
wie Du sagst, zeigt, dass die Position der Vorgaben ebenfalls eine Rolle
spielt.
Grüße
Marcus
[1]
Vgl. z.B.
http://sternchenland.com/philosophie-woerterbuch/gif/logquad.gif
--
PMs an: m.gl...@gmx.de
Christian Gollwitzer
Aug 27, 2013, 1:28:12 AM8/27/13
to
Am 25.08.13 09:39, schrieb Peter Kramer:
Nachdem Du deutlich weniger Sudokus rausbekommst als das vorher zitierte
Paper, muss eines davon falsch sein. Vielleicht findest Du hier eine
Antwort dazu?
http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html
Außerdem schreiben Felgenhauer und Jarvis, dass 2003 jemand unabhängig
die gleiche Lösung gefunden hat:
https://groups.google.com/forum/#!topic/rec.puzzles/A7pi7S12oFI
und sie geben in ihrem Paper eine heuristische Abschätzung, die zum
annähernd gleichen Ergebnis führt. Also hast Du entweder eine
Transformation nicht gefunden, es gibt schlicht keine intuitive
Transformation, oder alle drei anderen Ansätze sind falsch.
Christian
> Detlef Müller <lef...@arcor.de> wrote in
>> Aber nehmen wir an, Du hast hier einige Möglichkeiten gefunden, aus
>> der Grundlösung weitere Lösungen zu generieren, mit denen Du
>>
>>> also insgesamt:
>>>>
>>> 9*4^8*81*40 = 1.911.029.760
>>>>
>>> ungefähr 1/8 der Reihenanzahl beim Lotto 6 aus 49
>>
>> Sudokus erhältst, so fehlt doch nun der Nachweis, daß das auch alle
>> möglichen Sudoku-Stellungen ergibt.
>>
>> Warum soll es also nicht noch weitere so nicht erreichbare
>> Lösungsstellungen geben?
>>
> Weil es keine weiteren Transformationen des Sudokufeldes gibt, als jene
> von mir erwähnten, welche eine neue Variante generieren, da ich alle
> möglichen Elemente der Sudokustruktur, Zellen, Zeilen, Spalten, Blöcke,
> in jeweils einer Transformation berücksichtigt habe.
Beweis?
>> der Grundlösung weitere Lösungen zu generieren, mit denen Du
>>
>>> also insgesamt:
>>>>
>>> 9*4^8*81*40 = 1.911.029.760
>>>>
>>> ungefähr 1/8 der Reihenanzahl beim Lotto 6 aus 49
>>
>> Sudokus erhältst, so fehlt doch nun der Nachweis, daß das auch alle
>> möglichen Sudoku-Stellungen ergibt.
>>
>> Warum soll es also nicht noch weitere so nicht erreichbare
>> Lösungsstellungen geben?
>>
> Weil es keine weiteren Transformationen des Sudokufeldes gibt, als jene
> von mir erwähnten, welche eine neue Variante generieren, da ich alle
> möglichen Elemente der Sudokustruktur, Zellen, Zeilen, Spalten, Blöcke,
> in jeweils einer Transformation berücksichtigt habe.
> Durch die von mir erwähnten Transformationen kann man aus jedem
> beliebigen Sudoku jewelches andere Sudoku generieren. Weitere
> Transformationen gibt es nicht und braucht man auch nicht.
>>
> Fällt dir noch eine weitere Transformation ein, welche aus einem gültigen
> Sudoku ein weiteres gültiges Sudoku generieren würde?
"Fällt Dir noch eine ein" ist ja kein Beweis, sondern ein Behauptung.
> beliebigen Sudoku jewelches andere Sudoku generieren. Weitere
> Transformationen gibt es nicht und braucht man auch nicht.
>>
> Fällt dir noch eine weitere Transformation ein, welche aus einem gültigen
> Sudoku ein weiteres gültiges Sudoku generieren würde?
Nachdem Du deutlich weniger Sudokus rausbekommst als das vorher zitierte
Paper, muss eines davon falsch sein. Vielleicht findest Du hier eine
Antwort dazu?
http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html
Außerdem schreiben Felgenhauer und Jarvis, dass 2003 jemand unabhängig
die gleiche Lösung gefunden hat:
https://groups.google.com/forum/#!topic/rec.puzzles/A7pi7S12oFI
und sie geben in ihrem Paper eine heuristische Abschätzung, die zum
annähernd gleichen Ergebnis führt. Also hast Du entweder eine
Transformation nicht gefunden, es gibt schlicht keine intuitive
Transformation, oder alle drei anderen Ansätze sind falsch.
Christian
Marcus Glöder
Aug 27, 2013, 4:13:55 AM8/27/13
to
Hallo Peter,
in diesem Wikipedia-Artikel:
http://de.wikipedia.org/wiki/Sudoku#Die_Mathematik_hinter_Sudoku
wird, was die Anzahl der möglichen gelösten Sudokus betrifft auf den
hier schon diskutierten Artikel von Felgenhauer/Jarvis (2005) verwiesen
und was die Anzahl der mindestens notwendigen Vorgaben für ein eindeutig
lösbares 9x9-Sudoku betrifft, auf McGuire (2011), was hier auch schon
diskutiert worden ist. Es gibt in dem Artikel auch ein sehr schönes
Beispiel für den Fall, dass alle Felder bis auf vier vorgegeben sind und
das Sudoku trotzdem nicht eindeutig lösbar ist.
Viele Grüße
in diesem Wikipedia-Artikel:
http://de.wikipedia.org/wiki/Sudoku#Die_Mathematik_hinter_Sudoku
wird, was die Anzahl der möglichen gelösten Sudokus betrifft auf den
hier schon diskutierten Artikel von Felgenhauer/Jarvis (2005) verwiesen
und was die Anzahl der mindestens notwendigen Vorgaben für ein eindeutig
lösbares 9x9-Sudoku betrifft, auf McGuire (2011), was hier auch schon
diskutiert worden ist. Es gibt in dem Artikel auch ein sehr schönes
Beispiel für den Fall, dass alle Felder bis auf vier vorgegeben sind und
das Sudoku trotzdem nicht eindeutig lösbar ist.
Viele Grüße
Detlef Müller
Aug 27, 2013, 12:05:20 PM8/27/13
to
On 26.08.2013 22:39, Peter Kramer wrote:
> Detlef Müller <lef...@arcor.de> wrote in news:521a6b67$0$9515$9b4e6d93
>>>>>
>>>>> Wieviele Zellen müssen bei einem Sudoku gegebener Größe mindestens
>>>>
>>>> Ich habe das von mir empfohlene Buch vor über
17 ist anscheinend das absolute Minimum für das überhaupt ein
Sudoku existiert, welches mit 17 Vorgaben startet und das
eindeutig lösbar ist. Solche Anfangsstellungen mit eindeutiger
Lösung zu finden ist wohl auch nicht ganz leicht.
>>
> Liefere mir eine Lösung und ich zeige dir die Varianten.
Ok.
Das können wir machen.
Eine Lösung des von mir angegebenen Sudokus ist:
|-----------------|
|7 5 2|1 3 8|6 9 4|
| | | |
|1 9 8|7 4 6|5 3 2|
| | | |
|4 3 6|2 9 5|7 8 1|
|-----------------|
|2 8 3|4 5 9|1 6 7|
| | | |
|9 6 1|8 2 7|3 4 5|
| | | |
|5 7 4|6 1 3|8 2 9|
|-----------------|
|6 1 9|3 7 2|4 5 8|
| | | |
|8 4 5|9 6 1|2 7 3|
| | | |
|3 2 7|5 8 4|9 1 6|
-------------------
Welche Varianten gibt es nun, die ebenfalls in den oben
gegebenen 17 Stellen übereinstimmen?
>>
> Wie gezeigt gibt es Sudokus bei denen es nicht reicht.
Ja, offenbar war die Fragestellung nicht so eindeutig.
Ich habe sie so aufgefasst:
Was ist die kleinste Zahl n, für die ein Sudoku existiert, für
das n Einträge gegeben sind und das dennoch eindeutig lösbar
ist.
Du hast sie vermutlich so gesehen:
Was ist die kleinste Zahl n, für die jedes Sudoku, von dem
n Einträge gegeben sind, automatisch eindeutig lösbar ist.
Hast Du gerade ein Beispiel-Sudoku parat, wo nur 6 Einträge
fehlen und wo dennoch mehrere Lösungen möglich sind?
Gruß,
Detlef
> Detlef Müller <lef...@arcor.de> wrote in news:521a6b67$0$9515$9b4e6d93
> @newsspool1.arcor-online.net:
>
>> On 25.08.2013 08:31, Peter Kramer wrote:
>>> Bergholt Stuttley Johnson <b...@am.invalid> wrote in
>>> news:MPG.2c82b5b9b...@news.eternal-september.org:
>>>
>>>> Marcus Glöder wrote:
>
>> On 25.08.2013 08:31, Peter Kramer wrote:
>>> Bergholt Stuttley Johnson <b...@am.invalid> wrote in
>>> news:MPG.2c82b5b9b...@news.eternal-september.org:
>>>
>>>>>
>>>>> Wieviele Zellen müssen bei einem Sudoku gegebener Größe mindestens
>>>>> vorgegeben werden, damit alle anderen Zellen determiniert und das
>>>>> Sudoku damit eindeutig lösbar ist (Anzahl der Freiheitsgrade[2])?
>>>>
>>>> Ich habe das von mir empfohlene Buch vor über
>>>> einem Jahr gelesen und mich seit dem nicht mehr
>>>> mit Sudoku beschäftigt. Zum Zeitpunkt, als das
>>>> Buch geschrieben wurde, kannte man viele eindeutig
>>>> lösbare Sudokus mit 17 Vorgaben.
>>>>
>>> Das kann nicht sein!
>>
>> Ok, das ist ein Wort.
>>
>> Dann gebe ich jetzt ein Sudoku mit nur 17 Vorgaben
>> und zwar:
>>
>> 7.. 1.8 ...
>> .9. ... .32
>> ... ..5 ...
>>
>> ... ... 1..
>> 96. .2. ...
>> ... ... 8..
>>
>> ... ... ...
>> ..5 ..1 ...
>> 32. ... ..6
>>
>> Und bitte um Angabe von mindestens zwei verschiedenen
>> Vervollständigungen mit den vorgegebenen 17 Ziffern an
>>> Das kann nicht sein!
>>
>> Ok, das ist ein Wort.
>>
>> Dann gebe ich jetzt ein Sudoku mit nur 17 Vorgaben
>> und zwar:
>>
>> 7.. 1.8 ...
>> .9. ... .32
>> ... ..5 ...
>>
>> ... ... 1..
>> 96. .2. ...
>> ... ... 8..
>>
>> ... ... ...
>> ..5 ..1 ...
>> 32. ... ..6
>>
>> Und bitte um Angabe von mindestens zwei verschiedenen
>> genau den angegebenen Stellen.
>>
>> Eventuell ist das auch eine Gelegenheit, das geradezu langweilig
>> mechanische Verfahren zur Lösung zu demonstrieren.
>>
>> Eventuell ist das auch eine Gelegenheit, das geradezu langweilig
>>
> Ich werde mich von dir nicht provozieren lassen. Dazu habe ich weder die
> Zeit noch Lust dazu. Wie in der anderen Antwort gezeigt reichen 17
> beliebige Vorgaben generell nicht aus.
>
Das unterschreibe ich sofort!
> Ich werde mich von dir nicht provozieren lassen. Dazu habe ich weder die
> Zeit noch Lust dazu. Wie in der anderen Antwort gezeigt reichen 17
> beliebige Vorgaben generell nicht aus.
>
17 ist anscheinend das absolute Minimum für das überhaupt ein
Sudoku existiert, welches mit 17 Vorgaben startet und das
eindeutig lösbar ist. Solche Anfangsstellungen mit eindeutiger
Lösung zu finden ist wohl auch nicht ganz leicht.
>>
> Liefere mir eine Lösung und ich zeige dir die Varianten.
Ok.
Das können wir machen.
Eine Lösung des von mir angegebenen Sudokus ist:
|-----------------|
|7 5 2|1 3 8|6 9 4|
| | | |
|1 9 8|7 4 6|5 3 2|
| | | |
|4 3 6|2 9 5|7 8 1|
|-----------------|
|2 8 3|4 5 9|1 6 7|
| | | |
|9 6 1|8 2 7|3 4 5|
| | | |
|5 7 4|6 1 3|8 2 9|
|-----------------|
|6 1 9|3 7 2|4 5 8|
| | | |
|8 4 5|9 6 1|2 7 3|
| | | |
|3 2 7|5 8 4|9 1 6|
-------------------
Welche Varianten gibt es nun, die ebenfalls in den oben
gegebenen 17 Stellen übereinstimmen?
>>
> Wie gezeigt gibt es Sudokus bei denen es nicht reicht.
Ich habe sie so aufgefasst:
Was ist die kleinste Zahl n, für die ein Sudoku existiert, für
das n Einträge gegeben sind und das dennoch eindeutig lösbar
ist.
Du hast sie vermutlich so gesehen:
Was ist die kleinste Zahl n, für die jedes Sudoku, von dem
n Einträge gegeben sind, automatisch eindeutig lösbar ist.
Hast Du gerade ein Beispiel-Sudoku parat, wo nur 6 Einträge
fehlen und wo dennoch mehrere Lösungen möglich sind?
Gruß,
Detlef
Helmut Richter
Aug 27, 2013, 1:14:11 PM8/27/13
to
On Tue, 27 Aug 2013, Detlef Müller wrote:
> Hast Du gerade ein Beispiel-Sudoku parat, wo nur 6 Einträge
> fehlen und wo dennoch mehrere Lösungen möglich sind?
Erst das zyklische Sudoku:
> Hast Du gerade ein Beispiel-Sudoku parat, wo nur 6 Einträge
> fehlen und wo dennoch mehrere Lösungen möglich sind?
123 456 789
456 789 123
789 123 456
234 567 891
567 891 234
891 234 567
345 678 912
678 912 345
912 345 678
Jetzt in der Mitte 1 und 4 vertauschen; es bleibt ein Sudoku:
123 456 789
456 789 123
789 123 456
231 567 894
567 894 231
894 231 567
345 678 912
678 912 345
912 345 678
Jetzt ein Rätsel draus machen:
... 456 789
456 789 123
789 123 456
... 567 894
567 894 231
894 231 567
345 678 912
678 912 345
912 345 678
Ich weiß keinen Grund, warum es mit 4 nicht geht. Kann man beweisen, dass
sich
1.. 2.. ...
2.. 1.. ...
... ... ...
nicht zu einem Sudoku ergänzen lässt?
--
Helmut Richter
Helmut Richter
Aug 27, 2013, 3:06:03 PM8/27/13
to
On Tue, 27 Aug 2013, Helmut Richter wrote:
> Ich weiß keinen Grund, warum es mit 4 nicht geht. Kann man beweisen, dass
> sich
>
> 1.. 2.. ...
> 2.. 1.. ...
> ... ... ...
>
> nicht zu einem Sudoku ergänzen lässt?
Kein Problem:
> Ich weiß keinen Grund, warum es mit 4 nicht geht. Kann man beweisen, dass
> sich
>
> 1.. 2.. ...
> 2.. 1.. ...
> ... ... ...
>
> nicht zu einem Sudoku ergänzen lässt?
.34 .95 678
.56 .78 349
789 436 125
427 619 583
318 752 964
695 384 -1-
963 827 451
572 941 836
841 563 -9-
Das hat jetzt 8 unbesetzte Stellen und 4 Lösungen.
Füllt man die "." mit 1 und 2 oder die "-" mit 2 und 7,
so erhält man jeweils eines mit 4 unbesetzten Stellen und 2 Lösungen.
--
Helmut Richter
Marcus Glöder
Aug 27, 2013, 3:44:38 PM8/27/13
to
Am 27.08.2013 21:06, schrieb Helmut Richter:
> .34 .95 678
> .56 .78 349
> 789 436 125
>
> 427 619 583
> 318 752 964
> 695 384 -1-
>
> 963 827 451
> 572 941 836
> 841 563 -9-
Daraus lässt sich erkennen, dass es auch Sudokus mit nur 4 freien
> .34 .95 678
> .56 .78 349
> 789 436 125
>
> 427 619 583
> 318 752 964
> 695 384 -1-
>
> 963 827 451
> 572 941 836
> 841 563 -9-
Feldern (unbesetzten Stellen) gibt, die nicht eindeutig lösbar sind. Um
das Beispiel zu nehmen:
.34 .95 678
.56 .78 349
789 436 125
427 619 583
318 752 964
963 827 451
572 941 836
Entweder in a1 und b4 ist jeweils eine 1 und in a4 und b1 eine 2 oder in
a4 und b1 jeweils eine 1 und in a1 und b4 jeweils eine 2. Das ergibt
zwei Lösungen. Damit ist das Sudoku (77 Vorgaben) nicht eindeutig
lösbar. Das war aber eigentlich gar nicht die Frage. Sondern:
> Was ist die kleinste Zahl n, für die ein Sudoku existiert, für
> das n Einträge gegeben sind und das dennoch eindeutig lösbar
> ist.
Detlef Müller
Aug 27, 2013, 5:13:19 PM8/27/13
to
Was ist die minimale Anzahl N_min, für die gilt:
Aus jeder vollständigen Sudoku-Anordnung kann man so geschickt
81-N_min Angaben entfernen, so daß mit den verbleibenden N_min Angaben
das Sudoku eindeutig rekonstruiert werden kann.
Eine dumme obere Schranke ist jedenfalls n=78, denn wenn nur drei
Zellen frei sind, liegt eine davon sicher in einer ansonsten
besetzten Zeile oder Spalte, ist also bestimmt, danach liegen
die anderen nach dem selben Motto fest.
Natürlich geht auf Anhieb viel mehr:
von der Ausgangsstellung stets eine ganze Zeile weglassen ...
und zusätzlich eine Spalte, sowie aus den 4
verbleibenden unangetasteten Blöcken je eine Zelle.
Damit wären 21 Zellen auf jeden Fall und bei jedem Sudoku
redundant (entspricht n=50).
Und das ohne Ansehen der Belegung!
Sicher kommt man weiter, wenn man auf die Besetzung
eingeht (z.B. aus den Blöcken links nur die 1,2 und
3 - Einträge entfernen etc.)
Gruß,
Detlef
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Helmut Richter
Aug 28, 2013, 5:17:11 AM8/28/13
to
On Tue, 27 Aug 2013, Marcus Glöder wrote:
> Entweder in a1 und b4 ist jeweils eine 1 und in a4 und b1 eine 2 oder in a4
> und b1 jeweils eine 1 und in a1 und b4 jeweils eine 2. Das ergibt zwei
> Lösungen.
Meine Rede.
> Entweder in a1 und b4 ist jeweils eine 1 und in a4 und b1 eine 2 oder in a4
> und b1 jeweils eine 1 und in a1 und b4 jeweils eine 2. Das ergibt zwei
> Lösungen.
> Damit ist das Sudoku (77 Vorgaben) nicht eindeutig lösbar. Das war
> aber eigentlich gar nicht die Frage. Sondern:
beiden Beiträge gestern vom Vorposter zitiert. Es tut mir leid, wenn das nicht
die Frage ist, die du gerne beantwortet gehabt hättest.
> > Was ist die kleinste Zahl n, für die ein Sudoku existiert, für
> > das n Einträge gegeben sind und das dennoch eindeutig lösbar
> > ist.
schon bewiesen. Diese Zahl ist verblüffend niedrig, denn:
Es gibt (ebenfalls lt. WP) 6670903752021072936960 verschiedene Sudokus,
triviale Transformationen mit eingerechnet. Mit k Vorgaben kann man höchstens
9^k Sudokus unterscheiden. Also gehts nicht unter k=23, denn
log(6670903752021072936960)/log(9)=22.9. Wo ist der Fehler?
Die Aufgabe, bei der die Milchmädchenrechnung richtig gewesen wäre, ist die folgende.
A macht ein Sudoku und lässt es B nach folgenden Spielregeln lösen:
1. B bezeichnet die Position von k Feldern, die er für die Lösung braucht.
2. A nennt die Zahlen, die in diesen Feldern stehen.
3. B löst das Sudoku.
Dann kann das für k<23 nicht immer funktionieren. was natürlich nicht heißt,
dass es eine Felderauswahl von 23 Feldern gibt, die immer ausreicht.
Bei dem lösbaren 17er Sudoku wurden aber die gegebenen Felder vom
Aufgabensteller ausgewählt, der mehr weiß als B. Wir können mit Sicherheit
sagen, dass nicht alle Sudokus mit diesen 17 Feldern lösbar sind, wohl können
es aber einzelne sein (mindestens die 362880, die durch Vertauschen der
Ziffern aus dem einen bekannten hervorgehen).
--
Helmut Richter
Helmut Richter
Aug 28, 2013, 5:20:48 AM8/28/13
to
On Tue, 27 Aug 2013, Detlef Müller wrote:
> Das führt wieder auf eine andere imo interessante Sudoku-Frage:
>
> Was ist die minimale Anzahl N_min, für die gilt:
>
> Aus jeder vollständigen Sudoku-Anordnung kann man so geschickt
> 81-N_min Angaben entfernen, so daß mit den verbleibenden N_min Angaben
> das Sudoku eindeutig rekonstruiert werden kann.
Aus meinem anderen Beitrag heute geht hervor, dass N_min >= 23.
> Das führt wieder auf eine andere imo interessante Sudoku-Frage:
>
> Was ist die minimale Anzahl N_min, für die gilt:
>
> Aus jeder vollständigen Sudoku-Anordnung kann man so geschickt
> 81-N_min Angaben entfernen, so daß mit den verbleibenden N_min Angaben
> das Sudoku eindeutig rekonstruiert werden kann.
Aus dem Bauch heraus tippe ich auf 24 oder 25: die 23 war sehr knapp, aber
wenn man Luft hat, geht recht viel.
--
Helmut Richter
Detlef Müller
Aug 28, 2013, 5:47:10 AM8/28/13
to
Stellung nach einer minimalen Vorgaben-Konstellation sucht (Zeit
müsste man haben).
Vermutlich wird simples Backtracking zu einer kombinatorischen Explosion
gleich am Anfang führen.
Wenn der Part "wegdiskutiert" ist braucht der Check auf Eindeutigkeit
gegen Ende immer mehr Zeit ...
Helmut Richter
Aug 28, 2013, 6:14:50 AM8/28/13
to
On Wed, 28 Aug 2013, Detlef Müller wrote:
> On 28.08.2013 11:20, Helmut Richter wrote:
> > On Tue, 27 Aug 2013, Detlef Müller wrote:
> >
> > > Das führt wieder auf eine andere imo interessante Sudoku-Frage:
> > >
> > > Was ist die minimale Anzahl N_min, für die gilt:
> > >
> > > Aus jeder vollständigen Sudoku-Anordnung kann man so geschickt
> > > 81-N_min Angaben entfernen, so daß mit den verbleibenden N_min Angaben
> > > das Sudoku eindeutig rekonstruiert werden kann.
> >
> > Aus meinem anderen Beitrag heute geht hervor, dass N_min >= 23.
> >
> > Aus dem Bauch heraus tippe ich auf 24 oder 25: die 23 war sehr knapp, aber
> > wenn man Luft hat, geht recht viel.
Den Tipp erhalte ich nicht aufrecht. Wahrscheinlich ist die Zahl viel höher.
> On 28.08.2013 11:20, Helmut Richter wrote:
> > On Tue, 27 Aug 2013, Detlef Müller wrote:
> >
> > > Das führt wieder auf eine andere imo interessante Sudoku-Frage:
> > >
> > > Was ist die minimale Anzahl N_min, für die gilt:
> > >
> > > Aus jeder vollständigen Sudoku-Anordnung kann man so geschickt
> > > 81-N_min Angaben entfernen, so daß mit den verbleibenden N_min Angaben
> > > das Sudoku eindeutig rekonstruiert werden kann.
> >
> > Aus meinem anderen Beitrag heute geht hervor, dass N_min >= 23.
> >
> > Aus dem Bauch heraus tippe ich auf 24 oder 25: die 23 war sehr knapp, aber
> > wenn man Luft hat, geht recht viel.
Das intuitive Argument "wenns nicht zu knapp ist, reichts meistens" gilt in
anderen Konstellationen, nämlich wenn man sich nicht vorher festlegt.
Spiel 1:
A macht ein Sudoku, B sieht es nicht, sondern muss nach dem Wert einzelner
Felder fragen. Wieviele Fragen reichen immer aus? Da gilt die Schätzung,
dass es 23 oder wenig mehr sind.
Spile 2:
B legt k Felder fest, dann macht A ein Sudoku, von dem er die Zahlen auf den
vorher festgelegten Feldern verraten muss. Da kann er dafür sorgen, dass auf
B's Feldern immer im Wesentlichen dieselben Zahlen liegen, die dann bald
redundant festliegen, während die übrigen immer noch viele Möglichkeiten
haben.
Deine Frage ist wohl eher Spiel 2.
> Mich reizt es ja ein Programm zu schreiben, daß zu einer gegebenen
> Stellung nach einer minimalen Vorgaben-Konstellation sucht (Zeit
> müsste man haben).
>
> Vermutlich wird simples Backtracking zu einer kombinatorischen Explosion
> gleich am Anfang führen.
Für Spiel 1 kann man ja so vorgehen, dass man anfangs gleichmäßig
verteilt, etwa die Positionen der 1en und 2en eines zufällig gewählten
anderen Sudokus hernimmt. Dann berechnet man alle Lösungen, die noch
möglich sind -- das sind viele, aber nicht explosiv viele. Dann schaut
man, wieviel man bei jedem noch unbekannten Feld *mindestens* erfährt,
wenn man die Zahl im Feld wüsste, und sucht sich das informativste Feld
heraus.
--
Helmut Richter
wolfgang zeidler
Aug 28, 2013, 3:56:48 PM8/28/13
to
durch die Wegnahme von 4 Ziffern in ein nicht eindeutig
lösbares Rätsel umformen läßt.
Hinreichende Bedingung dafür sollte die Existenz zweier
Ziffern a und b sowie die Existenz eines "Problemrechtecks"
mit folgenden Eigenschaften sein:
- die Eckpunkte des Rechtecks werden von den Ziffern
a und b gebildet.
- die Eckpunkte des Rechtecks liegen in
( genau ! ) zwei unterschiedlichen sudoku-Quadranten.
Grobe Überlegungen zur Wahrscheinlichkeit der Existenz eines
"Problemrechtecks", dessen Rand-Quadranten horizotal
nebeneinander liegen:
Wahrscheinlichkeit W1a dafür, daß z.B. in Spalte 1 und 9
z.B. die Ziffern 4 und 5 gegeneinander vertauschten
Zeilenindex haben, sollte 1 / 64 sein.
Wahrscheinlichkeit W1b dafür, daß die beiden Zeilenindexe zur
selben Zeilengruppe ( 123 oder 456 oder 789 ) gehören: 1 / 4
W1 = W1a * W1b = 1 / 256
M1 = Anzahl der Möglichkeiten 2 Ziffern zu wählen: 36
M2 = Anzahl der Möglichkeiten 2 Spalten zu wählen,
die nicht zur selben Spaltengruppe gehören : 27
Wahrscheinlichkeit W dafür, daß *KEIN* Problemrechteck vorhanden ist:
W = ( 255 / 256 ) ^ ( 36 * 27 ) = ca. 0.02227455819046525
Analog für "Problemrechtecks", dessen Rand-Quadranten vertikal
nebeneinander liegen:
W1a = 1 / 64 ; W1b = 3 / 4 ; W1 = 3 / 256
M1 = 36 ; M2 = 9 ( weil diesmal: zur selben Spaltengruppe )
W = ( 253 / 256 ) ^ ( 36 * 9 ) = ca. 0.02194320699514788
Ups, beide Ergebnisse sollten nach meinem Verständnis gleich sein,
ich hoffe die Differenz von 0.0003313511953173705 ~ 1.5 %
läßt sich mit Rechenungenauigkeit erklären.
--
http://wzwz.de/mail
wolfgang zeidler
Aug 28, 2013, 4:41:35 PM8/28/13
to
wolfgang zeidler wrote:
> Ich vermute, daß sich ( fast ? ) jedes vollständige Sudoku
> durch die Wegnahme von 4 Ziffern in ein nicht eindeutig
> lösbares Rätsel umformen läßt.
>
> Hinreichende Bedingung dafür sollte die Existenz zweier
> Ziffern a und b sowie die Existenz eines "Problemrechtecks"
> mit folgenden Eigenschaften sein:
> - die Eckpunkte des Rechtecks werden von den Ziffern
> a und b gebildet.
> - die Eckpunkte des Rechtecks liegen in
> ( genau ! ) zwei unterschiedlichen sudoku-Quadranten.
>
Als praktischer Nachtrag:
> Ich vermute, daß sich ( fast ? ) jedes vollständige Sudoku
> durch die Wegnahme von 4 Ziffern in ein nicht eindeutig
> lösbares Rätsel umformen läßt.
>
> Hinreichende Bedingung dafür sollte die Existenz zweier
> Ziffern a und b sowie die Existenz eines "Problemrechtecks"
> mit folgenden Eigenschaften sein:
> - die Eckpunkte des Rechtecks werden von den Ziffern
> a und b gebildet.
> - die Eckpunkte des Rechtecks liegen in
> ( genau ! ) zwei unterschiedlichen sudoku-Quadranten.
>
Untersuchung eines von sueddeutsche.de gelieferten sudokos
mit einem script.
Das Wort "Lösung" wurde in Anführungszeichen gesetzt,
weil z.B. "Lösung" 3 eine falsche Lösung ist,
die Sterne = Rechteckdreiecke liegen in _vier_
verschiedenen sudoku-Quadranten.
Original :
579 168 432
126 473 958
438 529 671
914 732 865
385 346 127
267 851 349
693 215 784
842 397 516
751 684 293
"Lösung" 1 :
5*9 168 4*2
126 473 958
4*8 529 6*1
914 732 865
385 346 127
267 851 349
693 215 784
842 397 516
751 684 293
"Lösung" 2 :
57* 16* 432
126 473 958
43* 52* 671
914 732 865
385 346 127
267 851 349
693 215 784
842 397 516
751 684 293
"Lösung" 3 :
5*9 *68 432
126 473 958
438 529 671
9*4 *32 865
385 346 127
267 851 349
693 215 784
842 397 516
751 684 293
"Lösung" 4 :
579 1*8 4*2
126 473 958
438 529 671
914 7*2 8*5
385 346 127
267 851 349
693 215 784
842 397 516
751 684 293
"Lösung" 5 :
579 *6* 432
126 473 958
438 529 671
914 732 865
385 346 127
267 *5* 349
693 215 784
842 397 516
751 684 293
"Lösung" 6 :
579 168 **2
126 473 958
438 529 671
914 732 865
385 346 127
267 851 **9
693 215 784
842 397 516
751 684 293
"Lösung" 7 :
579 *68 4*2
126 473 958
438 529 671
914 732 865
385 346 127
267 851 349
693 215 784
842 *97 5*6
751 684 293
"Lösung" 8 :
**9 168 432
126 473 958
438 529 671
914 732 865
385 346 127
267 851 349
693 215 784
842 397 516
**1 684 293
"Lösung" 9 :
579 168 432
126 473 958
4*8 529 *71
914 732 865
385 346 127
2*7 851 *49
693 215 784
842 397 516
751 684 293
"Lösung" 10 :
579 168 432
126 473 958
438 52* 67*
914 732 865
385 346 127
267 85* 34*
693 215 784
842 397 516
751 684 293
"Lösung" 11 :
579 168 432
126 473 958
438 529 671
9*4 732 *65
3*5 346 *27
267 851 349
693 215 784
842 397 516
751 684 293
"Lösung" 12 :
579 168 432
126 473 958
438 529 671
914 73* 8*5
385 34* 1*7
267 851 349
693 215 784
842 397 516
751 684 293
"Lösung" 13 :
579 168 432
126 473 958
438 529 671
914 732 865
385 34* 12*
267 851 349
693 215 784
842 39* 51*
751 684 293
"Lösung" 14 :
579 168 432
126 473 958
438 529 671
914 732 865
*85 346 12*
267 851 349
693 215 784
842 397 516
*51 684 29*
"Lösung" 15 :
579 168 432
126 473 958
438 529 671
914 732 865
385 346 127
26* 851 *49
69* 215 *84
842 397 516
751 684 293
"Lösung" 16 :
579 168 432
126 473 958
438 529 671
914 732 865
385 346 127
267 8** 349
693 2** 784
842 397 516
751 684 293
"Lösung" 17 :
579 168 432
126 473 958
438 529 671
914 732 865
385 346 127
267 851 349
69* *15 784
84* *97 516
751 684 293
"Lösung" 18 :
579 168 432
126 473 958
438 529 671
914 732 865
385 346 127
267 851 349
693 21* *84
842 39* *16
751 684 293
"Lösung" 19 :
579 168 432
126 473 958
438 529 671
914 732 865
385 346 127
267 851 349
693 215 784
842 *97 51*
751 *84 29*
--
http://wzwz.de/mail
Peter Kramer
Sep 1, 2013, 4:02:42 AM9/1/13
to
Bergholt Stuttley Johnson <b...@am.invalid> wrote in
news:MPG.2c85de015...@news.eternal-september.org:
> Bergholt Stuttley Johnson wrote:
>>
Mensch, verpiss dich doch du Vollidiot. Wenn du mal sachlich diskutieren
gelernt hast ohnen andauernd andere pers�nlch anzugreifen kannst du
wiederkommen.
>
EOD
>
Marcus Glöder
Sep 2, 2013, 6:47:14 PM9/2/13
to
Hallo Bergholt, hallo Peter
bei solchen Sï¿œtzen oder Satzfragmenten wie:
> Du bist zu blï¿œd [...]
oder
> Mensch, verpiss dich doch du Vollidiot.
geht mir so durch den Kopf, dass es hier doch nur um zwei klar umrissene
Probleme bei Sudoku geht. Das lï¿œsst sich doch
> [...] sachlich diskutieren
ohne dass wir uns gegenseitig mit Verbalinjurien bewerfen (und wer weiￜ,
womit sonst). Da macht diskutieren auch keinen Spaￜ mehr. In meinem
privaten Leben habe ich im Moment ziemlich viel zu tun, so dass ich mich
erst in ein paar Wochen wieder melden kann (siehe mein anderes Posting).
Dennoch wï¿œrde ich ganz gerne auf den ersten Abschnitt aus den
Usenet-Netiquetten hinweisen:
http://www.usenetverwaltung.org/netiquette/#nr1
Viele Grￜￜe
bei solchen Sï¿œtzen oder Satzfragmenten wie:
> Du bist zu blï¿œd [...]
oder
> Mensch, verpiss dich doch du Vollidiot.
Probleme bei Sudoku geht. Das lï¿œsst sich doch
> [...] sachlich diskutieren
ohne dass wir uns gegenseitig mit Verbalinjurien bewerfen (und wer weiￜ,
womit sonst). Da macht diskutieren auch keinen Spaￜ mehr. In meinem
privaten Leben habe ich im Moment ziemlich viel zu tun, so dass ich mich
erst in ein paar Wochen wieder melden kann (siehe mein anderes Posting).
Dennoch wï¿œrde ich ganz gerne auf den ersten Abschnitt aus den
Usenet-Netiquetten hinweisen:
http://www.usenetverwaltung.org/netiquette/#nr1
Viele Grￜￜe
0 new messages