Was ist das Big-O von Sudoku mit Brute-Force-Backtracking?

Question

Ich frage mich, was der Big-O einer einfachen Brute Force Backtracking Sudoku-Algorithmus war.

Sudoku hat 4 Constraints:

1. Zelle - eine Zelle eine Nummer max
2. Region enthalten kann - Zahlen in der Region müssen alle verschiedenen
3. Reihe sein - Zahlen auf der gleichen Reihe alle sein muß verschiedene
4. Spalte - Zahlen auf der gleichen Spalte müssen alle verschiedenen

Angesichts der 9x9-Gitter sein:

3|___|___________ 
_|_ _|_ _ _ _ _ _ 
_|___|_ _ _ _ _ _ 
_|_ _ _ _ _ _ _ _ 
_|_ _ _ _ _ _ _ _ 
_|_ _ _ _ _ _ _ _ 
_|_ _ _ _ _ _ _ _ 
_|_ _ _ _ _ _ _ _ 
_|_ _ _ _ _ _ _ _ 

glaube ich, dass die Zeile, Spalte und Region Einschränkungen sind alle O (N!) Da (n) (n-1) (n-2) (n-3) (n-4) (n- 5) (n-6) (n-7) (n-8) für jede Zeile, Spalte und Region, wenn sie gefüllt werden.

Aber da es mindestens 17 gegebene Lösungen für eine einzigartige 9x9 Sudoku Lösung geben muss, bin ich mir jetzt nicht sicher. Die Anzahl der Permutationen ist O (n^(n^2 - k)), wobei k = 17 für reine Brute-Force ist, aber dies schließt keine Constraint-Befriedigung ein, die sicher entweder exponentiell O (c^n) oder faktoriell O ist (n!) zumindest.

Also ist die Frage wieder, was ist das Big-O von Sudoku mit Brute-Force-Backtracking mit Constraint Zufriedenheit und warum? O (log n!)?

Answer 1

Obwohl diese Antwort vielleicht etwas wählerisch ist, ist die Komplexität O(1); da Sudoku auf einem Raster fester Größe von 9*9 Zellen gespielt wird und jede Zelle genau einen von 9 unterschiedlichen Zuständen zuweist, nämlich eine Zuweisung eines der Werte in {1,...,9}, verwendet ein Brute-Force-Ansatz zur Erweiterung einer gegebenen Teilaufgabe konstante Zeit. Ansonsten müsste geklärt werden, was genau die in der Frage genannte n wäre.

aber sagen, dass wenn n soll die Größe der Leiterplatte sein, dh es gibt n*n, m die Anzahl der möglichen Zustände pro Zelle ist, ist b1 die Zahl der Regionen und b2 ist die Region, Größe (dh jede der b1 Regionen hat b2*b2 Zellen) die Laufzeit Komplexität kann grob durch die folgenden Überlegungen geschätzt werden. Es gibt m^(n*n) Zustände des Boards; Überprüfen, ob ein Zustand des Boards in Bezug auf die Sudou-Regeln legal ist, erfordert (n^2)*b1*(b2^2) Operationen, nämlich Prüfen der Eindeutigkeit jedes Zellenzustands in jeder Zeile, Spalte und Block. Insgesamt kann eine mögliche Zuordnung festgelegt werden

Schritte.