Laufzeitberechnung - Sudoku Backtracking

[java1Ec]

Hallo zusammen,
da ich ein Programm geschrieben habe das mithilfe von Backtracking Sudokus löst, möchte ich nun auch eine Laufzeitbestimmung machen.
Folgende Ansätze habe ich:

Fehler in Sudoku finden:
Bevor der Backtracking algorithmus ausgeführt wird, wird kontrolliert ob das Sudoku nicht von Anfang an einen Fehler hat.
Er geht jedes Feld(Textfeld) im sudoku[][] durch -> 81 Felder
für jedes Feld muss er kontrollieren ob horizontal,vertikal oder in der Box schon einmal diese Zahl vorkommt -> 81*(9+9+9) im worst case, oder?

Laufzeitberechnung des Algorithmus:
ich habe eine 9x9 große Matrix, zu beginn gehe ich davon aus das noch kein Wert eingetragen ist:
stimmt es das das eintragen der ersten Zeile 9! = 1*2*...*9 ist?
Bzw. (9-n)! wobei n die Anzahl der schon belegten Felder ist.
Ich bräuchte dringend Hilfe !
Desweiteren habe ich eine Variable int laufzeit erstellt die immer dann erhöht wird wenn die checkmethoden ausgeführt werden oder eine Zahl eingetragen wird.

dadurch bin ich dann auf die Rechnung 45x81 gekommen.
45 = 1+2+3+4+5+6+7+8+9 ; 9x9 = 81 felder.

Diese Werte sind ziemlich identisch, aber ist das überhaupt richtig?

Vielen Dank im Voraus!

 

[Marco13]

Das mit der Überprüfung könnte stimmen.
Beim eigentlichen Backtracking wäre es eher...
Für Zahl 1 gibt es 81 Möglichkeiten
Für Zahl 2 gibt es 80 Möglichkeiten
Für Zahl 3 gibt es 79 Möglichkeiten...
...
D.h. eigentlich 81! Möglichkeiten - aber natürlich sind das nur die Möglichkeiten - wenn man in's erste Feld eine 1 schreibt, und ins 2. auch eine 1, dann bricht er ja wegen der Überprüfung sofort ab.

Was ist denn das Ziel dieser Betrachtungen?

 

[java1Ec]

Danke erstmal für die Antwort,

ein wirkliches Ziel gibt es nicht, es ist jedoch interessant heraus zu finden warum mein Algorithmus innerhalb von 16ms alle Sudokus dieser Welt (9x9 Matrix) lösen kann. Da gerade, Algorithmen die Backtracking verwenden, hohe Laufzeiten zugesagt werden.
Leider weiß ich immer noch nicht wie ich eine allgemein gültige Formel für die Berechnung der Laufzeit aufstellen kann.

 

[Marco13]

Backtracking ist nur so langsam, wie das pruning schlecht ist. Wenn dein Algorithmus wäre

solve()
{
    if (alle Felder voll)
    {
        if (isValid) return solution;
    }
    else
    {
        besetzeNächstesFreiesFeld();
        solve();
        macheZugRückgängig();
    }
}

würde er auch ein paar Milliarden mal so lange brauchen, wie die Zeit seit dem letzten Urknall. Aber in dem Moment, wo man bei jedem Feld auf Gültigkeit prüft, oder (was, wie ich mich dumpf zu erinnern glaube, noch deutlich besser ist) von vornherein "mitschreibt", welche Möglichkeiten es für die einzelnen Felder noch gibt, ist das natürlich was anderes. Falls du letzteres gemacht hast sind es natürlich nicht 81! Möglichkeiten... (wie viele... da müßt' ich jetzt überlegen, ist schon "spät")

 

[vimar]

also der ansatz in "prolog" ist folgender:

da sagt man einfach:

fülle die felder so dass die eigenschaften stimmen: horizontal nur jeweils 1-9, vertikal nur 1-9 und in jedem block nur 1-9.

ich weiss nicht ob man das in java so machen kann, ich denke nicht: aber man könnte auch einfach randomisiert das sudoku mit zahlen füllen, mehrere threads machen, und schauen für welchen thread die bedingungen erfüllt sind.

 

[java1Ec]

Danke für die Antworten, ich habe mich jedoch glaube ich nicht richtig ausgedrückt.

Das Programm ist schon fertig! Mein Algorithmus geht genau nach diesem Prinzip vor, er versucht die Zahlen von 1 - 9 einzutragen und guckt ob alle Bedingungen erfüllt sind oder nicht.
Wenn sie nicht erfüllt werden können bricht er die aktuelle Rekursionsebene ab und erhöht die vorherige Zahl um den nächstmöglichen Wert.

Meine Frage war eine ganz andere:
Ich interessiere mich nun für den Mathematischen Ansatz.
Eine Zeile hat genau 9! Möglichkeiten, das steht fest.
Doch wie viele Möglichkeiten hat dann die nächste Zeile?
9! geht ja nicht, da mind. eine Möglichkeit durch die obere Zeile ausgeschlossen werden kann.
Jedoch 8! kann es auch nicht sein ...
Wie gesagt ich stehe auf dem Schlauch

 

[Sonecc]

Zur Info: Es gibt 6.670.903.752.021.072.936.960 (bzw. 5.472.730.538 wenn man Permutationen und Co nicht beachtet) mögliche verschiedene 9x9 Sudokus. (Sudoku ? Wikipedia)

Interessant fand ich dabei folgende Info:

Je weniger Felder in einem Sudoku-Rätsel vorbelegt sind, desto schwerer zu lösen ist es in der Regel. Abbildung 4 zeigt ein eindeutig lösbares Sudoku mit nur 17 vorbelegten Feldern. Die Vermutung, dass 17 die minimale Anzahl an vorbelegten Feldern ist, für die ein eindeutig lösbares Rätsel existiert, bewies 2011 ein Forschungsteam um Gary McGuire (University College Dublin) mit Hilfe von Computern. Die von ihm programmierte erschöpfende Suche benötigte sieben Millionen Stunden Rechenzeit parallel auf Hunderten von Prozessoren.

 

[java1Ec]

Wow vielen Dank, dass hat mich schon um einiges weiter gebracht. Ich bin anscheinend zu doof zum googlen.

Wenn ich das jetzt richtig verstehe, kann die gar keine eindeutige laufzeitberechnung durchführen?
Wenn wir annehmen das das Sudoku komplett leer ist dann heißt es ja: (9!)^9.
Ist damit impliziert das jede Zeile, Spalte und Box unterschiedlich sein muss?
Und vorallem wie kann ich die Formel erweitern sodass ich die Anzahl der vorgegebenen Felder auch noch mit drinnen habe? Beispielsweise für eine Zeile würde es ja heißen:

N = anzahl belegter Felder = 3

Also (9-N)! -> 6! verschiedene Möglichkeiten, richtig?
Wenn aber insgesamt N = 17 ist, dann dann kann ich ja nicht rechnen ((9-N)!)^9, dann würde die fakultät ja negativ sein.
Ich hoffe ihr versteht mein Problem? :shock: