Algorithmuskomplexität (Big-O) von Sudoku-Löser

Question

Ich bin auf der Suche nach dem "Wie finden Sie es", weil ich keine Ahnung habe, wie man die Algorithmuskomplexität meines Programms finden.

ich einen Sudoku-Löser mit Java, geschrieben ohne Effizienz im Vordergrund (ich wollte es versuchen rekursiv arbeiten zu lassen, was ich konnte mit!)

Einige Hintergrundinformationen:

meine Strategie, um zu bestimmen Rückzieher beschäftigt , für ein gegebenes Sudoku-Rätsel, ob das Puzzle nur eine einzigartige Lösung hat oder nicht. Also lese ich grundsätzlich in einem gegebenen Puzzle und löse es. Sobald ich eine Lösung gefunden habe, bin ich nicht unbedingt fertig, muss weiter nach weiteren Lösungen suchen. Am Ende kommt eines von drei möglichen Ergebnissen: Das Puzzle ist überhaupt nicht lösbar, das Puzzle hat eine einzigartige Lösung oder das Puzzle hat mehrere Lösungen.

Mein Programm liest die Puzzle-Koordinaten aus einer Datei ein, die für jede gegebene Ziffer eine Zeile hat, bestehend aus Zeile, Spalte und Ziffer. Durch meine eigene Konvention ist das obere linke Quadrat von 7 als 007. geschrieben

Umsetzung:

ich die Werte laden in, aus der Datei, und sie in einem Array 2-D gespeichert ich nach unten gehen die Array, bis ich einen Blank (ungefüllten Wert) finde, und setze ihn auf 1. Und überprüfe auf Konflikte (ob der Wert, den ich eingegeben habe, gültig ist oder nicht). Wenn ja, gehe ich zum nächsten Wert. Wenn Nein, ich den Wert um 1 erhöhen, bis ich eine Ziffer finde, die funktioniert, oder wenn keine von ihnen funktioniert (1 bis 9), gehe ich einen Schritt zum letzten Wert zurück, den ich eingestellt habe, und ich inkrementiere diesen Rekursion). Ich bin fertig gelöst, wenn alle 81 Elemente gefüllt wurden, ohne Konflikte. Wenn Lösungen gefunden werden, drucke ich sie auf dem Terminal. Andernfalls, wenn ich versuche, auf dem ERSTEN Element, das ich ursprünglich geändert habe, "einen Schritt zurückzugehen", bedeutet dies, dass es keine Lösungen gab.

Wie kann meine Programme Algorithmus Komplexität? Ich dachte, es könnte linear [O (n)], aber ich Zugriff auf die mehrfach Array, so dass ich bin mir nicht sicher :(

Jede Hilfe

Answer 1

O (n^m geschätzt) wobei n die Anzahl der Möglichkeiten für jedes Quadrat ist (das heißt, 9 in klassischem Sudoku) und m ist die Anzahl der Räume, die leer sind.

Dies kann einen Single aus nur durch arbeiten nach hinten zu sehen ist Wenn es nur ein Leerzeichen gibt, dann haben Sie n Möglichkeiten, die Sie im schlimmsten Fall durcharbeiten müssen. Wenn es zwei Rohlinge sind, dann müssen Sie arbeiten durch n Möglichkeiten für den ersten Rohling und n Möglichkeiten für den zweiten Zuschnitt für jede der Möglichkeiten für den ersten Rohling. Bei drei Rohlinge sind, dann müssen Sie arbeiten durch n Möglichkeiten für den ersten Rohling. Jede dieser Möglichkeiten wird ein Puzzle mit zwei Rohlingen ergeben, die n^2 Möglichkeiten.

Dieser Algorithmus führt eine Tiefensuche durch die möglichen Lösungen. Jede Ebene des Diagramms repräsentiert die Auswahlmöglichkeiten für ein einzelnes Quadrat. Die Tiefe des Diagramms ist die Anzahl der Quadrate, die ausgefüllt werden müssen.Mit einem Verzweigungsfaktor von n und einer Tiefe von m, um eine Lösung in der graphischen Darstellung zu finden, hat eine Worst-Case-Leistung von O (n ^m).

Answer 2

In vielen Sudokus gibt es ein paar Zahlen, die direkt mit ein paar Gedanken platziert werden können. Indem Sie eine Zahl in die erste leere Zelle setzen, geben Sie viele Möglichkeiten auf, die Möglichkeiten zu reduzieren. Wenn die ersten zehn leeren Zellen viele Möglichkeiten haben, erhalten Sie ein exponentielles Wachstum. Ich würde die Fragen stellen:

Wo in der ersten Zeile kann die Nummer 1 gehen?

Wo in der ersten Zeile kann die Nummer 2 gehen?

...

Wo in der letzten Zeile kann 9 die Zahl gehen?

Gleich, aber mit neun Spalten?

Gleich aber mit den neun Boxen?

Welche Nummer kann in die erste Zelle gehen?

Welche Nummer kann in die 81. Zelle gehen?

Das sind 324 Fragen. Wenn eine Frage genau eine Antwort hat, wählen Sie diese Antwort. Wenn irgendeine Frage überhaupt keine Antwort hat, rückt ihr zurück. Wenn jede Frage zwei oder mehr Antworten hat, wählen Sie eine Frage mit der minimalen Anzahl von Antworten.

Sie kann exponentielles Wachstum, aber nur für Probleme, die wirklich hart sind.