Sudoku

Neue Frage »

STORCH Auf diesen Beitrag antworten »
Sudoku
Hi,

habt ihr ne Ahnung wie man nen Sudoku selbst erstellt. Ich hab irgendwas mit Algorithmus gehört, kann mir dadrunter aber nichts vorstellen??

Ich hoffe ihr könnt mir helfen, ist nämlich sehr, sehr wichtig!!

DANKE
STORCH
Mathespezialschüler Auf diesen Beitrag antworten »

Verschoben
AD Auf diesen Beitrag antworten »

Solche eher algorithmischen Fragen sind auch im Informatikerboard willkommen.
quarague Auf diesen Beitrag antworten »

wenn du nur ein einzelnes brauchst funktioniert ein ausgefülltes nehmen und ein paar Zahlen weglassen. Die Eindeutigkeit kannst du testen indem du versuchst, es selber zu lösen.
sqrt(2) Auf diesen Beitrag antworten »

Zum Ausfüllen bietet sich ein Backtracking-Algorithmus an (Fragen dazu, wie Arthur schon sagte, am besten im Informatikerboard), zur automatischen Prüfung auf Unterbestimmtheit kannst du dir ja mal das angehängte Programm ansehen.
therisen Auf diesen Beitrag antworten »

Hallo,

schau doch mal hier: http://de.wikipedia.org/wiki/Sudoku#Algorithmus

Das dürfte für den Anfang genügen, wenn du dir nur darunter etwas vorstellen willst.

Gruß, therisen
 
 
PrototypeX29A Auf diesen Beitrag antworten »

Ich behaupte gerne, dass die Anzahl der moeglichen Loesungen (komplett ausgefuellte 9x9 Sudoku-felder) sehr gering ist (kleiner als 100.000 smile ), wenn man zwei Loesungen die sich durch Zeilen- und Spalten-Vertauschungen sowie Permutation der Zahlen ineinander ueberfuehren lassen, als identisch betrachtet.

Ich hab das mal fuer die ersten zwei Zeilen durchprobiert und komme fuer Sudokus bei denen genau die obersten achtzehn Felder ausgefuellt sind nur auf weniger als 20 voneinander verschiedene Grundformen.
Mit der naechsten Zeile werden es auch nicht wesentlich mehr, deswegen glaube dass die Anzahl der Loesungen nicht besonders gross ist und die Zahl der minimalen Raetsel ebenfalls sehr gering smile

Ein Raetsel betrachte ich als minimal, wenn man keine Zahl wegnehmen kann ohne dass es sich die Zahl der Loesungen veraendert.

Gegenmeinungen? smile
carsten Auf diesen Beitrag antworten »

ich koennte mir sehr gut vorstellen, dass die Anzahl der "minimalen Raetsel" zu ein und der selben Loesung (Sudoku hat immer genau eine Loesung) ziemlich gross sein kann.
Es gibt Onlineversionen, die die Raetsel durchnummerieren und da gibt es arg viele. In wie weit die alle minimal sind und durch Zahlenpermutationen ineinander ueberfuehren lassen habe ich mir nicht ueberlegt.

Zeilen- sowie Spalten vertauschen wird ja auch sehr eingeschraenkt, geht ja nur mit bestimmten Zeilen/Spalten smile .

Dazu gibt es doch aber sicher schon Betrachtungen?! Hat da mal jemand nachgesehen?
system-agent Auf diesen Beitrag antworten »

wieso sind die lösungen eindeutig? gibts wirklich zu jedem nur eine eindeutige lösung?
Anirahtak Auf diesen Beitrag antworten »

Zitat:
Original von PrototypeX29A
Ich behaupte gerne, dass die Anzahl der moeglichen Loesungen (komplett ausgefuellte 9x9 Sudoku-felder) sehr gering ist (kleiner als 100.000 smile ), wenn man zwei Loesungen die sich durch Zeilen- und Spalten-Vertauschungen sowie Permutation der Zahlen ineinander ueberfuehren lassen, als identisch betrachtet.


Hallo,
im Spektrum der Wissenschaft (Ausgabe März 2006) gibt es einen ganzen Artikel über Sudokus.
Darin steht, dass es 5.472.730.538 verschiedene Möglichkeiten gibt die Felder nach den Sudoku-Regel auszufüllt. Verschieden bedeutet hierbei, dass sie nicht durch Spiegelung, Drehung, "kästchentreuer Permutation der Zeilen und Spalten" ineinander übergeführt werden können.

http://www.wissenschaft-online.de/artikel/800106
http://www.wissenschaft-online.de/spektr..._06_03_S100.pdf

Gruß
Anirahtak
PrototypeX29A Auf diesen Beitrag antworten »

Ok die Zahl ist etwas groesser als meine Schaetzung, aber immer noch recht klein, ausserdem mach ich ja noch zwei weitere Permutationen smile

Jetzt wo die Frage geklaert ist, kann ich ja beruhigt schlafen.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »