Sudoku ohne Ziffernvorgabe

13.08.2020, 15:02

Dopap

Sudoku ohne Ziffernvorgabe

es liegt ein leeres Sudoku vor. Zu den üblichen Regeln gibt es in diesem Falle natürlich noch Zusatzregeln damit es lösbar wird.
Ein simpler brute force Ansatz liefert $\begin{eqnarray*} 9^{81}\approx 2\cdot 10^{77} \end{eqnarray*}$ mögliche Matrizen. Zu viel. Deshalb

Wieviele echte Sudokus gibt es ?
Wieviele Sudokus gibt es, wenn zusätzlich Felder im Abstand $\begin{eqnarray*} \sqrt 5 \end{eqnarray*}$ = Springerzug im Schach keine gleichen Ziffern haben dürfen ?

Eine andere Frage wäre, wie man das programmieren könnte.

13.08.2020, 15:21

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
Wieviele echte Sudokus gibt es ?

Laut http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf sind es $\begin{eqnarray*} 6\,670\,903\,752\,021\,072\,936\,960\approx 6.7\cdot 10^{21} \end{eqnarray*}$ .

Hab den Artikel kurz überflogen: Anscheinend haben die Autoren den Bruteforce-Aufwand durch diverse Vorbetrachtungen soweit heruntergeschraubt, dass ein 2005-PC letztlich nur noch ca. zwei Minuten rechnen musste.

13.08.2020, 15:35

G130820

Auf diesen Beitrag antworten »

Wenn pro Sekunde auf der Welt 1 Sudoko gelöst würde, dauert das ca. 2*10^14 Jahre,alle Varianten durchzuspielen, also ca. 15000-mal die Zeit seit dem Urknall.

13.08.2020, 15:52

Steffen Bühler

Auf diesen Beitrag antworten »

Wobei die Zahl schon in diesem Artikel auf $\begin{eqnarray*} 3 \ 546 \ 146 \ 300 \ 288 \approx 3,5 \cdot 10^{12} \end{eqnarray*}$ reduziert wird, weil natürlich Redundanzen auftreten. Wiki zitiert einen späteren Jarvis-Artikel, wo er das Ganze sogar nur auf $\begin{eqnarray*} 5 \ 472 \ 730 \ 538 \approx 5,5 \cdot 10^9 \end{eqnarray*}$ eindampft. Dann hätte man's in schlappen 175 Jahren durch.

Viele Grüße
Steffen

13.08.2020, 17:05

Dopap

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
...
Laut http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf sind es $\begin{eqnarray*} 6\,670\,903\,752\,021\,072\,936\,960\approx 6.7\cdot 10^{21} \end{eqnarray*}$ .

Hab den Artikel kurz überflogen: Anscheinend haben die Autoren den Bruteforce-Aufwand durch diverse Vorbetrachtungen soweit heruntergeschraubt, dass ein 2005-PC letztlich nur noch ca. zwei Minuten rechnen musste.

Was genau hat der 2005 PC in 2 Minuten berechnet. Werde da nicht schlau.

@ Stefan Bühler: $\begin{eqnarray*} 5.5 \cdot 10^9 \end{eqnarray*}$ von was? Etwa in dem Sinne, dass die entsprechenden Matrizen verschieden sind?
Ich nenne diese Sudokus "Sudoku-Matrizen", d.h. 2 derartige Sudokus sind verschieden wenn die Differenz der Matrizen nicht die Nullmatrix ist.

13.08.2020, 17:32

Steffen Bühler

Auf diesen Beitrag antworten »

Laut dem pdf haben sie es geschafft, einen Algorithmus zu schreiben, der bei gegebenen ersten drei Sudoku-Zeilen sämtliche Möglichkeiten für die restlichen sechs Zeilen berechnet. Diesen wiederum haben sie dann geschwindigkeitsoptimiert.

Es lässt sich natürlich streiten, ob ein Sudoku ein anderes wird, wenn man es um 90° dreht oder spiegelt. Oder einfach z.B. alle 9en und 2en gegeneinander austauscht. Du siehst hier als Purist offenbar einen Unterschied, aber wenn Du die beiden Sudokus hintereinander lösen müsstest, würdest Du beim zweiten wahrscheinlich schneller sein. Darauf beruht wohl die Reduzierung.

13.08.2020, 18:06

Dopap

Auf diesen Beitrag antworten »

genau, es wird immer wieder von verschieden geschrieben ohne das genau zu definieren.
Es geht ja nicht um die Anzahl möglicher Aufgaben sondern nur um die Anzahl korrekt gefüllter Sudokus. Da bin ich gerne Pedant.

So gibt es in obigen strengen Sinne genau $\begin{eqnarray*} \,\,2^{27}3^{14}7^2 5^{3}11\approx 4.3\cdot 10^{19} \end{eqnarray*}$
verschiedene beim 3x3x3 Zauberwürfel durch Verdrehen erreichbare ortsfeste Stellungen.

Neue Frage »

Antworten »

Sudoku ohne Ziffernvorgabe

Verwandte Themen