Sudoku-Backtracking Algorithmus "Tutorial" gesucht

[WeenerChild]

Jaja, sudoku-Solver gibts wie Eelektronen am Meer und auch so manches Tutorial. Aber ich habe noch keins gefunden, durch das ich "durchgestiegen" wäre.

Also könnte mal jemand, der solche Algorithmen aus dem Handgelenk schüttelt einfach mal posten, was das minimum ist, um eine bruteforce sudokusolver Funktion zu schreiben?

Der Einfachheit halber gehen wir mal von einem eindimensionalen Array aus, welches das Sudoku enthält.

Programmiersprache die ich anpeile ist perl, wobei es letztendlich ja sprachenunabhängig ist. (Deswegen hab ichs auch hier gepostet...)
Ich würde neben pseudo- und perl-code auch noch python-code "verstehen", wobei mir wörtliche Erläuterungen lieber wären. Oder wenn jemand einen guten Link zu dem Thema hat (gerne auch auf Englisch), postet ihn doch.

Nochmal worums mir geht: Backtracking Algorithmen finde ich etwas, naja, "kompliziert" und ich habe Probleme den Überblick zu behalten etc.
Wäre also nett wenn jemand den "nackten" Algorithmus und dessen "Vorraussetzungen" (ließ: Übergabeparameter der rekursiven Funktion, zb Array mit bereits "gegangenen" Lösungen, das sudoku selbst, etc.) erläutern könnte.
(Und natürlich sollte das auch "verständlich" sein, also bitte keiner auf die Idee kommen den "berüchtigten" perl 3-liner zu posten..)

[mehlvogel]

Backtracking an sich ist nicht sehr kompliziert. Das Prinzip ist, wenn du nicht mehr weiter weißt, rate den nächsten Schritt und versuche damit weiterzukommen. Wenn du dann mitkriegst, dass du in eine Sackgasse gelaufen bist, mache alle Schritte rückgängig und rate an der letzten Stelle erneut.

Für ein Sudoku kann man das nun folgendermaßen adaptieren: (Das Feld sei ein 9x9 Array und eine 0 bedeutet im Array, das der Wert noch nicht gesetzt ist)
- Suche nächstes Feld das 0 ist
- Suche Zahl aus [1,9] die an dieser Stelle erlaubt ist. Falls es keine solche Zahl gibt, gib False zurück
- Setze Zahl im Feld und rufe die Prozedur rekursiv mit neuem Feld auf.
- Falls die Prozedur False zurückgibt, mache Änderung rückgängig und versuche nächste Zahl. Gibt die Prozedur eine Lösung zurück, gib diese Lösung zurück.

Dieses Schritte lassen sich leicht in (schnell runtergeschriebenes) Python übertragen:

def soduko(field):
- Suche nächstes Feld das 0 ist


for i, x in enumerate(field):
for j, y in enumerate(x):
if y == 0:

- Suche Zahl aus [1,9] die an dieser Stelle erlaubt ist. Falls es keine solche Zahl gibt, gib False zurück


for n in range(1, 10):
if allowed(field, n, i, j):
...
return False

- Setze Zahl im Feld und rufe die Prozedur rekursiv mit neuem Feld auf.


field[i][j] = n
if soduko(field) != False:

- Falls die Prozedur False zurückgibt, mache Änderung rückgängig und versuche nächste Zahl. Gibt die Prozedur eine Lösung zurück, gib diese Lösung zurück.


return field
field[i][j] = 0


Die allowed() Funktion prüft ob die Zahl an der Position erlaubt ist.

[bischi]

Sollte man Sudokus nicht ohne raten lösen können? Ich würd einfach für jedes Feld alle möglichen Zahlen speichern, und dann systematisch ausschliessen, welche das nicht gehen. Das ganze dann wiederholt durchgehen.

MfG Bischi

[mehlvogel]

Sollte man Sudokus nicht ohne raten lösen können? Ich würd einfach für jedes Feld alle möglichen Zahlen speichern, und dann systematisch ausschliessen, welche das nicht gehen. Das ganze dann wiederholt durchgehen.


Das Problem Sudokus (beliebiger Größe) zu lösen ist NP-vollständig [1]. Das ist bei einem 9x9 Feld sicherlich unproblematisch weil durchprobieren schnell genug ist, aber wahrscheinlich wirst du keinen effizienten Algorithmus finden.

Mein Code hat aber nicht den Anspruch die effizienteste Methode zu sein, sondern zu verdeutlichen wie Backtracking in diesem konkreten Fall funktioniert. Unabhängig davon, dass es bestimmt noch andere Methoden zum lösen gibt (siehe z.B. Wikipedia).

[1] http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdf

[WeenerChild]

Also natürlich löst man sudokus am Besten mit Logik. (Im RL wegen dem (des? :s) Rätselspaß und beim Programmieren weils ungleich performanter ist.) Allerdings lassen sich (afaik) nicht alle Sudokus auch "nur" mit Logik (ließ: ohne trial'n'error) lösen, ich glaube im wiki-Artikel gibt es ein zwei Beispiele für besonders harte Sudokus auf die das so zutrifft.
Logische Lösungsalgorithmen habe ich auch schon und die sind (zumindest für mich) auch wesentlich "einfacher" zu verstehen/produzieren.
Aber darum gings ja hier nicht, mir geht es speziell um den bruteforce Algorithmus via backtracking, der immer zum Ziel kommt, insofern denn ein Ziel existiert. (Dauert halt nur manchmal etwas länger..)

Soar, nun zu mehlvogel, erstmal sehr vielen Dank, dass du gepostet hast. Du hast meine Frage ja eigentlich quasi beantwortet, aber eigentlich quasi kannte ich das vorher soweit auch schon und theoretisch versteh ichs wohl auch, aber in der Praxis habe ich noch keinen sudoku-solver (via backtracking) zum Laufen bekommen. Und ich will auch Niemandem zumuten diese ganzen quellcode-Würste zu debuggen...
Also ich poste jetzt hier mal meine "neueste" Funktion, so ziemlich nach der "Anleitung" von mehlwurm kreiert mit Anpassungen an individuelle Funktionen etc.:

sub useBruteforce()
{
my ($pos, @sudoku) = @_;
if (&isSolved(@sudoku)) {return 1}
my $next = &getNextFreeField($pos, @sudoku);
if ($next)
{
my @validDigits = split(//, &getValidDigits($pos, @sudoku));
foreach (@validDigits)
{
$sudoku[$next] = $_;
if (&useBruteforce($next, @sudoku)) {return @sudoku}
}
}
else {return 0}
}
Die Funktionen tun das, was ihr Name verspricht, wenn die aktuelle Position "frei" ist gibt getNextFreeField die aktuelle Position zurück, wenn das Ende erreicht ist gibt es 0 zurück (deswegen die if-Verzweigung..). getValidDigits returned einen String mit den Ziffern, sodass ich den erst splitten muss zum drüberiterieren...
Mal das Postulat vorangestellt, dass das "backend" soweit funktioniert, ist in dieser Funktion irgendwo ein fataler Denkfehler ala Brett-vorm-Kopf?
Bizarrerweise bricht dieser Algorithmus bei Position 8 ab... (mit ein Paar backtracking "Versuchen", allerdings geht der Algo nur ein mal auf Position 2 bei meinem Beispiel-Sudoku (siehe wiki) zurück, was sinnlos erscheint, da Position zwei 3 Mögliche Kandidaten hat (1, 2 und 4, wird von getValidDigits so auch returned, allerdings "probiert" dar algo nur 1 und 2..)...) Ich verstehs nicht, wie kann der überhaupt abbrechen, solange es noch leere Felder gibt? WTF?
Es gibt 2 return-Fälle (naja, eigentlich 3...) und da es nie zu einer Lösung kommt, müsste das Ende des Feldes erreicht sein....

BTW: noch eine Frage: das mindeste, um ein Sudoku auf Richtigkeit zu überprüfen ist doch zu checken, ob die Ziffern von 1-9 in einer/m Zeile/Spalte/Quadrat maximal einmal vorkommen. Das führt zu dem Problem: wie komme ich an die Zahlen des jeweiligen "Quadrats"? Wie hast du das zum Beispiel gelöst mehlwurm? (ich habs gelöst, aber irgendwie immernoch ziemlich kompliziert...) Und @ dein Python code, sorry, aber ich versteh nur Bahnhof. Das enumerate Statement versteh ich, aber warum muss man zum Beispiel "am Ende" das Feld wieder zurücksetzen, damit der Algorithmus beim Scheitern das "Originalsudoku" wieder ausgibt? Oder gibts noch andere Gründe?
Und was macht die Allowed Funktion? Prüft die halt die Sudoku-Regeln (sprich: 1-9 nur jeweils einmal pro Zeile/Spalte/Quadrat)?

Danke nochmal an (alle) Poster!

[mehlvogel]

Was allowed() bei mir macht ist im Prinzip zu schauen, ob die übergebene Zahl in der Zeile / Spalte oder dem passenden 3x3 Block vorkommt. Die Koordinaten von dem Block kann man leicht aus bekannten x,y Koordinaten berechnen. Der Block geht von [3*int(x/3)..3*int(x/3) + 3]x[3*int(y/3)..3*int(y/3)+3].

Ich setze das Feld wieder zurück auf 0, weil (a) meine allowed() Methode ansonsten nicht funktioniert und ich zu faul war, da noch mehr Gedanken dran zu verschwenden. Der Code für die Methode ist auch dementsprechend rustikal implementiert. (b) Führt das beim Abbrechen der Rekursion zu Problemen, da dann die Feldwerte noch auf irgendwelche Zahlen gesetzt sein könnten - ein Beispiel zu konstruieren gelingt mir jetzt grad aus dem Kopf nicht. Evtl. solltest du dir mal die Sudoku Variable ausgeben lassen, um zu schauen was mit ihr passiert. Beim Backtracking allgemein ist es wichtig, dass man alle Änderungen wieder rückgängig macht.

Was deinen Code sonst angeht: Ich bin nicht so bewandert in Perl. Von der Logik würde ich mal schauen ob es einen Unterschied macht, wenn du das return nicht in den else Block packst. Das Problem könnte auftreten, wenn die innere for-Schleife ohne Ergebnis beendet wird (nämlich wenn für jede Zahl der rekursive Aufruf fehlschlägt), dann gibt deine Methode nichts zurück.

[BlueJay]

Also könnte mal jemand, der solche Algorithmen aus dem Handgelenk schüttelt einfach mal posten, was das minimum ist, um eine bruteforce sudokusolver Funktion zu schreiben?


Hier einer der ältesten Knacker, "ujas Sieb", ziemlich brute force:

1. belade jede nicht eindeutige Zelle mit der Menge 1..9.
2. entferne in jeder nicht eindeutigen Zelle das Element, was laut Regel nicht vorkommen darf (Ziffer im gleicher Reihe, Spalte oder Quadranten)
3. falls in einer Zelle nur 1 Element übrig ist, markiere diese als neue eindeutige Zelle.
Falls es keine weiteren eindeutigen Zellen gibt, weiter mit 4, sonst weiter mit 2.
4. Sind alle Zellen eindeutig, ist das Sudoku gelöst, sonst gibt es wenigstens so viele Lösungen wie Elemente in der Zelle, die die wenigsten Elemente hat.
Beim generieren sollte man diese dann "öffnen", und den Knacker nochmal über das Sudokurätsel laufen lassen.

Dieser Algo hat bis jetzt jedes perfekie Sudoku geknackt.

so long,
BlueJay

[WeenerChild]

Der Algorithmus den du beschreibts BlueJay hat nichts mit bruteforce oder gar backtracking zu tun. Das ist ehrlich gesagt die naivste Form des logischen Lösungsalgorithmus, nämlich jener, welcher die Spielregeln direkt anwendet. Damit kann man längst nicht alle sudokus lösen.

More recently, an even more perplexing puzzle has been developed, which has become known as "Qassim Hamza". This puzzle has proven to be extremely daunting, though using the weighted decision-tree pruning method (http://en.wikipedia.org/wiki/Decision-tree_pruning) mentioned above, a human could solve it in 6245 logical steps with no random quessing.
Es wird denke ich auch sudokus geben, die man gar nicht mit Logik lösen kann.

Des Weiteren habe ich mein Brett vorm Kopf gefunden:
Nachdem ich die nächste freie Position berechne hole ich mir die gültigen Möglichkeiten für die aktuelle Position und nicht für die nächste, die ich gerade über getNextFreeField bezogen habe.. (diese "beiden" sind (afaik) nur dann gleich, wenn das erste Feld gleich frei ist..)
Sprich in der geposteten Funktion musste ich

my @validDigits = split(//, &getValidDigits($pos, @sudoku));
in

my @validDigits = split(//, &getValidDigits($next, @sudoku));
umändern, damits funktioniert.

Allerdings ist diese Funktion (und die "im Hintergrund abreitenden" Funktionen) extrem unperformant, weswegen man solche Funktionen nur auf sudokus "loslassen" sollte, die sich wirklich überhaupt nicht mit "intelligenten" Mitteln lösen lassen.
(Auch ist meine gepostete Funktion noch so ziemlich ein worst-case was performance angeht, zum Beispiel checke ich jedes mal, ob das Sudoku gelöst ist, anstatt es nur in der else-Verzweigung zu tun. (Sprich: nur, wenn das Ende des Spielfelds erreicht ist.) Allein mit dieser Optimierung löst der Algorithmus das oben angesprochene Sudoku in 6 Minuten und 18 Sekunden (:x) statt vorher 15 Minuten und 48 Sekunden.... Also immernoch grausig unperformant..)

Danke nochmal für die Antworten.

[mehlvogel]

Allein mit dieser Optimierung löst der Algorithmus das oben angesprochene Sudoku in 6 Minuten und 18 Sekunden (:x) statt vorher 15 Minuten und 48 Sekunden.... Also immernoch grausig unperformant..)


Meine Python Variante von oben braucht nur gut 30 Sekunden für "Qassim Hamza"... obwohl ich nicht glaube, dass der Code oben wirklich optimiert ist. Würde mich mal interessieren warum trotzdem so ein signifikanter Unterschied da ist.

[WeenerChild]

Naja, weil ich ein Sc***ß-Coder bin. Das Ding hat über 150 Zeilen code und ne Unmenge ranziger Funktionen. Eventuell könnte es auch an meinem Rechner liegen, vielleicht könntest du deinen Python-Code mal *komplett* (also ausführbar) posten/ans Post anhängen, dann kann ich mal schaun, ob das bei mir auch so schnell geht. Hier mal ein paar Funktionen:

sub isIn()
{
my ($item, @Array) = @_;
my $count = 0;
foreach (@Array) {if (($_ == $item) or ($_ eq $item)) {$count++}}
return $count
}

sub getRow()
{
my ($y, @sudoku) = @_;
return @{$sudoku[$y]}
}

sub getCol()
{
my ($x, @sudoku) = @_;
my @column;
foreach (0..8) {push(@column, ${sudoku[$_][$x]})}
return @column
}

sub getSec()
{
my ($x, $y, @sudoku) = @_;
my @sector;
my $intX = 3*int($x/3);
my $intY = 3*int($y/3);
foreach my $i ($intY..$intY+2)
{
foreach my $j ($intX..$intX+2)
{
push(@sector, ${sudoku[$i][$j]})
}
}
return @sector
}

sub getNextFreeField()
{
my ($x, $y, @sudoku) = @_;
foreach my $i ($y..8)
{
if ($i == $y)
{
foreach my $j ($x..8)
{
unless (${sudoku[$i][$j]}) {return ($j, $i)}
}
}
else
{
foreach my $j (0..8)
{
unless (${sudoku[$i][$j]}) {return ($j, $i)}
}
}
}
return (-1, -1) # Reached the end of the sudoku, without finding a free field.
}

Wie du siehst foreach-Schleifen ohne Ende und für jeden Furz eine eigene Funktion (getRow() ist beispielsweise völlig sinnfrei, weil man das auch "direkt" in der Originalfunktion so machen könnte (auf die Referenz zugreifen), aber ich spalte das irgendwie gerne alles in schön benennbare Teile auf, kA...)
(Und btw: die Sektor Funktion habe ich so von dir "übernommen"...)

[mehlvogel]

hmm... die getRow, getCol und getSec Methoden lassen sich in Python sehr elegant lösen (siehe allowed() Methode) und eine getNextFreeField() Methode habe ich mir durch 2 for-Schleifen gespart. Eine isSolved() Methode ist denk ich überflüssig. Da der Algorithmus nur valide Zahlen einsetzt, ist das Sudoku gelöst, sobald es keine freien Felder mehr gibt. Wenn du deine Brute Force Methode also dementsprechend umbaust (also return 0 direkt nach der "foreach (@validDigits)" Schleife und ein "return @sudoku" in den else Block) könntest du dir diesen Aufruf wahrscheinlich generell sparen.

Ich kann dir den Python code anhängen. Wenn du ihn ausführen willst, brauchst du nen Python interpreter, dann haust du den Code einfach in eine Datei und führst "python dateiname" aus. Bei mir läuft der Kram übrigens auf einem Core Duo.


def allowed(field, number, x, y):
blockx, blocky = 3 * int(x/3), 3 * int(y/3)
return not (number in field[x] or
number in [t[y] for t in field] or
number in [x for t in field[blockx:blockx+3] for x in t[blocky:blocky+3]])

def sudoku(field):
for i, x in enumerate(field):
for j, y in enumerate(x):
if y == 0:
for n in range(1, 10):
if allowed(field, n, i, j):
field[i][j] = n
if soduko(field) != False:
return field
field[i][j] = 0
return False

## Execute some sudoku
field = [[0,0,0,7,0,0,8,0,0],
[0,0,0,0,4,0,0,3,0],
[0,0,0,0,0,9,0,0,1],
[6,0,0,5,0,0,0,0,0],
[0,1,0,0,3,0,0,4,0],
[0,0,5,0,0,1,0,0,7],
[5,0,0,2,0,0,6,0,0],
[0,3,0,0,8,0,0,9,0],
[0,0,7,0,0,0,0,0,2]]
for x in field:
print x
print "+++++++++++++++++++++++++++"
field = sudoku(field)
for x in field:
print x

[WeenerChild]

Hm, also ja, ich bin noch nicht so in perl drin und denke eigentlich auch noch mehr in python Begriffen. Ich hab wohl jetzt heraus gefunden, dass man "list comprehension" am Besten mit map "emulieren" würde und dass man auch oft hashes anstatt arrays benutzen soll. Denn es gibt in zum Beispiel in perl keine straightforward-Konstruktion die dem python-statement

if bla in array:
...entspricht. Das fand ich schon arg seltsam und als ichs dann in perldoc nachgeschlagen hab, stand (/steht) da doch tatsächlich: Use a hash. (Es gibt die Funktion "exists" für hash-Keys..)
Naja, also ich habe mal die von dir angesprochenen "Optimierungen" gemacht und außerdem noch kleine Änderungen hier und da. Zum Beispiel habe ich jetzt einfach wie du 2 geschachtelte for-Schleifen statt der getNextFreeField Funktion. Eine andere große Änderung war, dass ich zuerst immer das gesamte Sudoku rekursiv kopiert habe (in python würde man das mit deepcopy machen), damit ich das Sudoku selbst "unberührt" lasse.. (Weil 2D Arrays kann man ja nur mit Referenzen realisieren..)
Dann ist mir aufgefallen wie dämlich/unperformant das ist und ich hab einfach das Sudoku "in place" verändert und dafür die von mir vorher angezweifelte Zeile "${sudoku[$nextY][$nextX]} = 0;" am Ende der foreach-Schleife der Backtracking-Funktion hinzugefügt, sodass es nun mit dem Lösen des "Qassim Hamza" "nur noch" ca. 3 Minuten beschäftigt ist:

time ./foo.pl
...
real 2m43.926s
user 2m26.628s
sys 0m0.019s
während deine Python Variante ca. eine Minute braucht:

time ./bar.py
...
real 0m55.407s
user 0m43.688s
sys 0m0.022s


Hier mal die neuere Funktion: (diesmal bearbeitet sie ein 2D-Array)

sub useBruteforce() {
my ($x, $y, @sudoku) = @_;
foreach my $nextY (0..8) {
foreach my $nextX (0..8) {
unless (${sudoku[$nextY][$nextX]}) {
my @validDigits = &getValidDigits($nextX, $nextY, @sudoku);
foreach (@validDigits) {
${sudoku[$nextY][$nextX]} = $_;
if (&useBruteforce($nextX, $nextY, @sudoku)) {return @sudoku}
}
${sudoku[$nextY][$nextX]} = 0;
return 0
}
}
}
return 1
}
(Außerdem habe ich meinen Klammerstil geändert, weil perl einen einfach zu soooo vielen curly-braces zwingt, dass der andere Stil einfach viel zu "aufgebläht" war..)

Also ich denke wenn ich das wirklich intelligent optimieren will sollte ich irgendwie map und hashes reinbringen und die Logik damit komprimieren. Als "Inspiration" kann ich ja immer diese Lösung hier nehmen (http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html), die nach genauem Hinsehen doch nicht soooo kompliziert ist. Naja, wenn ich das irgendwann "optimiert" haben sollte, melde ich mich zurück :X

[BlueJay]

Der Algorithmus den du beschreibts BlueJay hat nichts mit bruteforce oder gar backtracking zu tun. Das ist ehrlich gesagt die naivste Form des logischen Lösungsalgorithmus, nämlich jener, welcher die Spielregeln direkt anwendet. Damit kann man längst nicht alle sudokus lösen.


Ach ja, hatte das Backtracking in der Überschrift glatt überlesen.
Aber brute force ist es todsicher ;), auch wenn es nicht nach Try-and-Error vorgeht.
Und diese kreuzbrave, naive Methode beinhaltet Scannen, Crosshatching, Auszählen, Eliminieren und natürlich deren Kombinationen, nach nur 1 Felddurchlauf alles vollautomatisch :D

(Wikipedia: Sudoku, Abschnitt Analytische Methoden)
http://de.wikipedia.org/wiki/Sudoku
(Ausprobieren/Hypothese habe ich bisher noch nicht benötigt.)
Vgl. auch hier:
http://www.janko.at/Raetsel/Sudoku/Regeln.htm



Es wird denke ich auch sudokus geben, die man gar nicht mit Logik lösen kann.

Gibt es, die haben dann mehrere Lösungen und werden meist beim Generieren als imperfekt verworfen.

Btw., kannst du mir mal ein paar (perfekte) Sudokus, schicken, bei denen man mit dem Sieb nicht mehr weiterkommt? Würde das Spiel endlich mal wieder interessant machen und mir Gelegenheit geben, neue Algos auszuprobieren.

so long,
Bluejay

[WeenerChild]

Aaaaalso, nach etwas Lektüre über map und grep und ein wenig Fragerei in #perl @ irc.freenode.net besteht der backtracking Algorithmus jetzt aus exakt 3 Funktionen, nimmt ein 2D-Array an und sieht so aus:
für code siehe ein Posting weiter..
Also ich habs auf diese drei Funktionen "heruntergeschrumpf" und die (am häufigsten aufgerufene) Funktion getValidDigits sogut es geht optimiert, und siehe da, jetzt kann es einigermaßen mit deiner unoptimierten python Lösung mithalten:

time ./spam.pl
...
real 1m6.691s
user 1m2.714s
sys 0m0.013s
vs.

time ./eggs.py
...
real 0m58.653s
user 0m43.935s
sys 0m0.014s
Und btw, die von mir erwähnte obfu "solve sudokus in 3 lines of perl" (http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html) ist nicht gerade auf performance optimiert, sondern eher auf kryptische Erscheinung:

time echo '0007008000000400300000090016005000000100300400050 01007500200600030080090007000002'|./sudobfu.pl
...
real 2m44.275s
user 2m16.623s
sys 0m0.014sAlso auch nicht gerade fix..

Ich hänge mal ein Perl-Skript mit tk-GUI an, dann ist das sudoku Eintippen nicht so anstrengend. Allerdings ist die Gefühlte Zeit, die das Ding mit GUI zum Lösen des gleichen sudokus braucht um einiges länger, ich war jedoch zu faul das jetzt mit time zu überprüfen... (Während des Prüfvorgangs friert die GUI btw ein, dass kann man sicherlich irgendwie verhindern (threads?), aber das ist eine andere Baustelle. Außerdem macht der cheque Button auch noch nicht sinnvolleres als symetrische Ästhetik zu gewährleisten..)

Und @BlueJay: bruteforce ist für mich sinnfrei einfach ausprobieren biss es passt. Also nix mit möglichst intelligent Regeln anwenden etc.
Und du hast Algorithmen, die ohne trial'n'error das "Top 1465 Number 77" (http://upload.wikimedia.org/wikipedia/en/7/7c/Top1465number77.JPG) oder das "Qassim Hamza" (http://upload.wikimedia.org/wikipedia/en/e/eb/Qassim_Hamza_Memorial.JPG) lösen können? Hm, und naja, letztlich ist ein Sudoku ja immer durch Logik definiert, von daher könnte man sagen man kann alle (eindeutigen) Sudokus "mit Logik" lösen... Aber ich würde wildes rumprobieren nicht Logik nennen..

[BlueJay]

Und @BlueJay: bruteforce ist für mich sinnfrei einfach ausprobieren biss es passt. Also nix mit möglichst intelligent Regeln anwenden etc.

Brute force ist für mich, von einer vorgegebenen Lösungsmenge einfach ohne raffinierten Algo alles rauszuschmeissen, was nicht passt. Sinnfrei ist es nicht, wenn Randbedingungen die Lösungsmenge einengen.

Es ist nicht auf das Durchschreiten von Entscheidungsbäumen beschränkt.:D

Und wie du richtig festgestellt hast, ist die oben vorgestellte Methode naiv, auch wenn Wikipedia sie in Hieroglyphen verpackt hat.



Und du hast Algorithmen, die ohne trial'n'error das "Top 1465 Number 77" (http://upload.wikimedia.org/wikipedia/en/7/7c/Top1465number77.JPG) oder das "Qassim Hamza" (http://upload.wikimedia.org/wikipedia/en/e/eb/Qassim_Hamza_Memorial.JPG) lösen können? Hm, und naja, letztlich ist ein Sudoku ja immer durch Logik definiert, von daher könnte man sagen man kann alle (eindeutigen) Sudokus "mit Logik" lösen... Aber ich würde wildes rumprobieren nicht Logik nennen..

Danke für die Links!
Mein Plan ist es, wenn das Sieb nicht weiterkommt, die Zelle mit der kleinsten Menge zu nehmen und mit jeder Ziffer die Lösung zu prüfen. Der Algo ist soweit fertig, aber es fehlte bisher an Testkandidaten.

Ich habe das Sieb bisher auf die janko.at-Seite losgelassen sowie auf etliche vom Rätselverlag veröffentliche Sudokus der Kategorie "schwer". Dann habe ich mal einen Generator (eher eine Datenbank) hier rumliegen gehabt mit "extra schwer", hier gab es regelmäßig mehrere Lösungen.

Btw. die Monte-Carlo-Methode ist IMHO immer noch ein anerkanntes mathematisches Verfahren. :)

so long,
BlueJay

[WeenerChild]

die Zelle mit der kleinsten Menge zu nehmen und mit jeder Ziffer die Lösung zu prüfen.OMG, NATÜRLICH *Schuppen von den Augen fall*
Das schränkt die Anzahl der durchzugehenden Möglichkeiten ja astronomisch ein.
Damn, die Idee ist so gut, die hab ich dir gleich mal geklaut :P
Jetzt schafft der Algo das "Qassim Hamza" in 22 Sekunden :D

sub getSec {
my ($x, $y, @sudoku) = @_;
my @sector;
my $intX = 3*int($x/3);
my $intY = 3*int($y/3);
foreach my $i ($intY..$intY+2) {
foreach my $j ($intX..$intX+2) {
if (${sudoku[$i][$j]}) {push(@sector, ${sudoku[$i][$j]})}
}
}
return @sector
}

sub getValidDigits {
my ($x, $y, @sudoku) = @_;
my @row = grep(($_), @{$sudoku[$y]});
my @col = map {${sudoku[$_][$x]} ? ${sudoku[$_][$x]} : ()} (0..8);
my @sec = getSec($x, $y, @sudoku);
my %digitPresence = map {$_, 1} (@row, @col, @sec);
return grep $_ ne '' && !exists $digitPresence{$_}, (1..9)
}

sub getNextFreeField {
my @sudoku = @_;
my ($nextX, $nextY) = (-1, -1);
my $count = 10;
foreach my $y (0..8) {
foreach my $x (0..8) {
unless (${sudoku[$y][$x]}) {
my @validDigits = getValidDigits($x, $y, @sudoku);
if (@validDigits < $count) {
($nextX, $nextY) = ($x, $y);
$count = @validDigits
}
}
}
}
return ($nextX, $nextY)
}

sub useBruteforce {
my ($x, $y, @sudoku) = @_;
my ($nextX, $nextY) = getNextFreeField(@sudoku);
unless ($nextX == -1) {
foreach (getValidDigits($nextX, $nextY, @sudoku)) {
${sudoku[$nextY][$nextX]} = $_;
if (useBruteforce($nextX, $nextY, @sudoku)) {return 1}
}
${sudoku[$nextY][$nextX]} = 0;
return 0
}
return 1
}
Jetzt halt wieder mit getNextFreeField-Funktion, die die Position mit den wenigsten Möglichkeiten (oder -1, -1 beim Ende des Feldes) returned. Supi, \o/

BTW: zu meinem früher geposteten code: Ich habe da zwei Undinge gemacht, die sich gegenseitig aufgehoben haben. (#perl told me!) Nämlich einmal Funktionen als (mit?) Prototypen deklariert, die keine Argumente annehmen (sub foo(){...}) und danach beim Aufrufen perl gesagt, er solle das doch bitte einfach ignorieren (&foo(@args)). Also ich häng mal das neue Skript an mein älteres Post an. (Mit neuem Algo und "richtigerer" Syntax..)
Ansonsten geht auch diese bash Zeile zum "bereinigen" der unsauberen Syntax:

cat sudoku.pl.txt | \
perl -pe 's/^(sub \w+)\(\)/$1/;s/(?<!\\|&)&(\w+)(?=\()/$1/g;s/(?<!\\|&)&(\w+)(?!\()/$1()/g' \
> tmp.lol && mv tmp.lol sudoku.pl.txt

Edit: Ich glaube inzwischen kann man den Thread dank meiner "perl-pollution" bereits in "Skriptsprachen" verschieben...

[BlueJay]

Stimmt, das Sieb engt die Auswahl der möglichen Lösungen nur ein.
(1.Link)
Eine Lösung habe ich bisher noch nicht gefunden, aber endlich einen Denksport für nächste Woche ;)