µit - März

progandy

Zitat von Andy

...anders wirds schwer, ich weiss^^. Aber das scheint das Problem zu sein. PeeTheBee hatte in einem anderen Thread etwas zu Speicherlecks in Autoit gesagt, jetzt kann ich mir wenigstens ansehen, wie sich so etwas äußern kann.
@Canyon, beschreibe mal in einer Gui ca 5000-6000x einige Buttons mit GuictrlsetData und bewege dann mal ein Fenster drüber....
ciao
Andy

ich hab da kein Problem

Spoiler anzeigen

[autoit]

GUICreate("hz")
$a = GUICtrlCreateButton("1",10,10,100)
$b = GUICtrlCreateButton("1",10,50,100)
$c = GUICtrlCreateButton("1",10,80,100)
$d = GUICtrlCreateButton("1",10,100,100)
$e = GUICtrlCreateButton("1",10,120,100)
GUISetState()
For $i = 1 To 6000
GUICtrlSetData($a,$i)
GUICtrlSetData($b,$i)
GUICtrlSetData($c,$i)
GUICtrlSetData($d,$i)
GUICtrlSetData($e,$i)
Next
While GUIGetMsg()<>-3
WEnd

[/autoit]

Canyon

also ich weis nicht wieso deine buttons so oft beschrieben werden?!

meine gui sieht (noch) dann so aus.

selbst wenn in einem feld am anfang die zahlen 1 - 9 stehen, wird maximal 9 mal aktualisiert, bis es eine möglichkeit gibt (die wird dann groß geschrieben)

Canyon

NoNever

so wenn ihr eifrig dabei seid eure solver zu machen hab ich mal eine Zeitmessung gemacht.

Spoiler anzeigen

[autoit]

Dim $loesung[26], $Zeit[26], $Sudoku[26]
$Sudoku[1] = 000670900360005028805002100020506004009407000700100583070054261000703000084090050
$Sudoku[2] = 628009000109056004500872001900510467807000030060020900004907103000201709091000280
$Sudoku[3] = 076930000000108400300026000045080130010567090200310058068002005704000982020003710
$Sudoku[4] = 120500360300009020007208004019000873403897001002350400000000087850016900200980140
$Sudoku[5] = 906020100020050460000009730004260070700030608030871204800700041213000090490308006
$Sudoku[6] = 007000300050908004900030060070004080102070900000500006800010000000000405060007000
$Sudoku[7] = 060070008900104070003000500200007000008050906030900020000600010805000000000030007
$Sudoku[8] = 000400050107000000000060003800003000001070904060900080040030001900502030006000700
$Sudoku[9] = 004010050050900208300006000020000100000403000005000060000700005901004030070060900
$Sudoku[10] = 500000006004902010070050900020004060900060803007100000000080200401000000000006070
$Sudoku[11] = 009050200500000004000907000000204000100000005003010600035060720010000080074080510
$Sudoku[12] = 700100002010070000008005300800000650006809000400300000009004000503600000000003071
$Sudoku[13] = 200000140001209000500800000600700003070060000002004800009005000408100000000008067
$Sudoku[14] = 000300150309001000200800000008009000100502000002000046600400007040060000005003200
$Sudoku[15] = 003500100000010050700004008240000800000809002000700600000006009000200407015007000
$Sudoku[16] = 000003050060004008800170000000710042040008700009005800790800000003050070004000200
$Sudoku[17] = 000000000009040602087006010020004038040039000010008046064003050003050401000000000
$Sudoku[18] = 000007002010000000000250108002030090006405000800090005004000609000500007607002840
$Sudoku[19] = 000000000073080500092003070004070800708036020900000000000019650010000290000240000
$Sudoku[20] = 060050002800000010000002600000020000500903208007010394006074000010006050200035000
$Sudoku[21] = 004002080002000401500070060820040007060005100700000000090000023003098000000201600
$Sudoku[22] = 000000000205980430006207009000030280040000000000090170009508006502460790000000000
$Sudoku[23] = 000000800000640005009700004248000601060009000971000403003100008000570006000000700
$Sudoku[24] = 000000020000008539000596080000000350051000700904700200402810000500040000086300000
$Sudoku[25] = 000020000020000100365840070001050020840000000003060080214680030070000500000010000

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

$file = FileOpen("ergebnisse.txt", 1)
For $i = 1 To 25
$Timer = TimerInit()
$Loesung[$i] = _sudoku_solve($Sudoku[$i])
$Zeit[$i] = TimerDiff($Timer)
FileWriteLine($file, $i)
FileWriteLine($file, "Sudoku:" & $Sudoku[$i] & @CRLF)
FileWriteLine($file, "Lösung:" & $Loesung[$i] & @CRLF)
FileWriteLine($file, "Zeit:" & $Zeit[$i] & @CRLF)
FileWriteLine($file, @CRLF)
Next
$gesamt = 0
For $i = 1 To 25
$gesamt += $Zeit[$i]
Next
$durchschnitt = $gesamt / 25
FileWriteLine($file, "durchschnitt:" & $durchschnitt)
FileClose($file)

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit]

den Befehl _sudoku_solve müsst ihr durch euren ersetzten....
hoffe euch gefällt es-...

**eukalyptus**

So ich hab jetzt mal einen Benchmark erstellt und 10 logisch lösbare und 10 backtrack-Sudokus beigefügt.

Falls jemand Probleme mit diesen Sudokus hat (zu schwer, zu leicht, usw...) dann bitte gleich posten!
(Un wenn jemand meint, ich hätte mir die Sudokus extra für mein Script ausgesucht, dann ersetze ich auch gerne die Sudokus gegen andere Vorschläge...;))

autoit.de/wcf/attachment/4278/

Da mein Script noch kein Backtrack kann, poste ich nur mal meine logischen Ergebnise:

Code

Sudoku Logisch 1 Richtig - Benötigte Zeit: 312.79506194223
Sudoku Logisch 2 Richtig - Benötigte Zeit: 244.420170720022
Sudoku Logisch 3 Richtig - Benötigte Zeit: 266.318484611871
Sudoku Logisch 4 Richtig - Benötigte Zeit: 272.166993291047
Sudoku Logisch 5 Richtig - Benötigte Zeit: 330.572461025074
Sudoku Logisch 6 Richtig - Benötigte Zeit: 769.037964322281
Sudoku Logisch 7 Richtig - Benötigte Zeit: 633.289147084336
Sudoku Logisch 8 Richtig - Benötigte Zeit: 1956.07067378675
Sudoku Logisch 9 Richtig - Benötigte Zeit: 713.07386832684
Sudoku Logisch 10 Richtig - Benötigte Zeit: 750.123549222038


Ergebnis Logisch: Zeit gesammt: 6247.86837433249 Zeit Durchschnitt: 624.786837433249

Alles anzeigen

lgE

Reeder

Hallo
Eine Frage:
Sind Objekte erlaubt?
Ich würde gerne sowas hier nutzen:

[autoit]

$feld = ObjCreate("System.Collections.ArrayList")

[/autoit][autoit][/autoit][autoit][/autoit]

Bin mir aber nicht sicher, ob das noch zu den Autoit-Mittel zählt.

progandy

Da System.Collections.ArrayList ein COM-Objekt aus dem .NET-Framework ist, muss dieses installiert sein. Ich denkne, damit gehört das nicht mehr zu den AutoItmitteln.

//Edit: Aber in diesem Wettbewerb ist das ja nicht verboten Includes und DLLs sind erlaubt, wenn es in der Aufgabe nicht verboten ist.

**Andy**

Hi,

eukalyptus, bei deinen Vorschlägen für den backtrace-Benchmark haben die meisten Sudokus mehrere Lösungen! Dein Benchmark bewertet nur eine richtige Lösung.

Zitat von Reeder

Sind Objekte erlaubt?
Ich würde gerne sowas hier nutzen: AutoIt-Quellcode
1 $feld = ObjCreate("System.Collections.ArrayList")
Bin mir aber nicht sicher, ob das noch zu den Autoit-Mittel zählt.

Ich stimme für grenzwertig^^

Zitat von progandy

//Edit: Aber in diesem Wettbewerb ist das ja nicht verboten Includes und DLLs sind erlaubt, wenn es in der Aufgabe nicht verboten ist.

Verspäteter Aprilscherz
Ich hatte die Aufgabe so aufgefasst, in AutoIt eine Lösung zu scripten. Daher fallen m.E. sämtliche "externen" Dll´s usw. aus dem Rahmen. Es gibt fix-und fertige sehr gut dokumentierte Sudoku-solver-Dll´s downzuloaden. Auch in C++ oder mit irgendeiner anderen der .Net-Varianten selbstgeschriebene "Hilfskonstruktionen" würde ich nur "ausser Konkurrenz" bewerten.
Oder wir lassen direkt so etwas zu....

[autoit]

Run("Sudoku-Solve.EXE "&$sudokustring)

[/autoit]

ciao
Andy

**eukalyptus**

Hi

Kannst du bitte mal überprüfen, ob die Sudokus mehr als 2 Lösungen haben?
Mit 2 kann mein Benchmark noch umgehen...

Also generell sind ext. Dll´s verboten, außer sie sind in der Aufgabenstellung erlaubt!
Sonst schreib ich meinen Solver in Pascal und bin um Meilen schneller...
Oda nehm gleich einen fertigen Solver ausm Netz...

lgE

prizma

Zitat

Also generell sind ext. Dll´s verboten,

Hehe hatte ich ja noch gar nicht daran gedacht. Ja ist wohl besser alle DLLs zu verbieten, die nicht zur Win-Api gehören.

Habe auch das Problem mit den zwei Lösungen und bei der Gesamtauswertung werden alle vorher als richtig befundenen Strings als falsch Protokolliert.

progandy

Zitat von eukalyptus

Also generell sind ext. Dll´s verboten, außer sie sind in der Aufgabenstellung erlaubt!

Zitat von Regeln

6. Das Skript
Includes und DLL`s jeglicher Art sind erlaubt. Ich behalte mir aber vor
einzelne bei entsprechenden Aufgaben doch zu verbieten, wenn diese die
Aufgabe fast von selbst lösen würden.

**eukalyptus**

Ich hab jetzt den Benchmark so umgeschrieben, daß er jedes richtige Ergebnis akzeptiert.
Ein richtiges Sudoku hat in den Quersummen (Horizontal, Vertikal & Block) jeweils 45 - sobald dies der Fall ist, wird das Ergebnis als richtig bewertet.

Download in meinem vorletzten Post...

So sieht die Auswertung aus:

Code

Sudoku Logisch 1 Falsch
Sudoku Logisch 2 Falsch
Sudoku Logisch 3 Falsch
Sudoku Logisch 4 Falsch
Sudoku Logisch 5 Falsch
Sudoku Logisch 6 Falsch
Sudoku Logisch 7 Falsch
Sudoku Logisch 8 Falsch
Sudoku Logisch 9 Falsch
Sudoku Logisch 10 Falsch


Ergebnis Logisch: Zeit gesammt: 0.135492080697407 Zeit Durchschnitt: 0.0135492080697407


Sudoku Backtrack 1 Falsch
Sudoku Backtrack 2 Falsch
Sudoku Backtrack 3 Falsch
Sudoku Backtrack 4 Falsch
Sudoku Backtrack 5 Falsch
Sudoku Backtrack 6 Falsch
Sudoku Backtrack 7 Falsch
Sudoku Backtrack 8 Falsch
Sudoku Backtrack 9 Falsch
Sudoku Backtrack 10 Falsch


Ergebnis Logisch: Zeit gesammt: 0.135492080697407 Zeit Durchschnitt: 0.0135492080697407
Ergebnis Backtrack: Zeit gesammt: 0.132419064434167 Zeit Durchschnitt: 0.0132419064434167
Ergebnis gelöste Sudokus: 0

Alles anzeigen

lgE

**Andy**

Moinz!

Wie funktioniert eigentlich das trennen der beiden Lösungswege Logisch/Backtrack?
Zzt. gibt es ja nur eine Funktion _solvesudoku, und bei mir fängt das backtracken natürlich erst dann an, wenn alle logischen Lösungen ausgereizt sind. D.h. fürs backtracken hätte ich gegenüber einem "reinen" Backtracker schon einen ziemlichen Vorsprung an bereits gelösten Feldern.
Zumindest bei mir ist es nämlich so, dass der logische Löser einige Faktoren schneller ist wie mein Backtrack-Algorithmus. Unfair?!

Andererseits muss das ja nix heissen, vielleicht ist mein bt-Algorithmus um Faktoren langsamer wie eurer....(das befürchte ich jedenfalls )

Habe mal bissl mit den (von mir) nicht logisch lösbaren Sudokus gespielt. U.a. habe ich das Sudoku viermal jeweils um 90° gedreht berechnen lassen und Zeitunterschiede bis zum Faktor 100 beim backtracken festgestellt. Ergebnis: Wenns lange dauert, dann hat man nur in der verkehrten Ecke angefangen^^. Ich habe jedenfalls keinen Zusammenhang finden können, der die optimale Anfangsecke zum backtracken feststellt. Trotzdem oder besser genau deswegen würde ich den Test dahingehend erweitern, jedes Sudoku 4x backtracken zu lassen (jeweils 90° gedreht). Zeit = Gesamtzeit oder Durchschnitt oder wie auch immer.....

Spoiler anzeigen

[autoit]

func _drehen($string) ;sudoku um 90° im Uhrzeigersinn drehen
dim $neustring=""
for $sp=9 to 1 step -1
for $ze=81 to 1 step -9
$neustring=$neustring&stringmid($String,$ze-$sp+1,1)
Next
Next
return $neustring
EndFunc

[/autoit]

ciao
andy

limette

@euka:
Durchschnitt von 600 is ja nicht schlecht
Meine Frage: Wie gut ist dein PC ?
Das macht nämlich 'ne ganze Menge aus; - mein Laptop mit 2x 1,6 Ghz hat 'n Durchschnitt von ca. 800,
der Rechner von 'nem Kumpel mit 4x 3,2 Ghz rast da mit 300ms Durchschnitt lang...

**Andy**

Bei dem v eukalyptus freundlicherweise bereitgestellten Benchmark habe ich bei den logischen auf einem 1,2ghz pIII celeron einen Durchschnit von 256, auf nem amd 4850 sind die zeiten exakt 3x schneller.
Der Backtrackbench läuft nicht durch, Sudoku nr 4 ist nicht lösbar bzw es gibt zuwenig Vorgaben, mittlerweile habe ich dieses Sudoku im inet bei einigen Solvern testen lassen, überall dasselbe Ergebnis.Ich stelle bald mal einige Rätsel incl Lösung online.

Reeder

Mein Script läuft zwar noch nicht so, wie ich es mir vorstelle, aber es löst schon
alle Aufgaben. Auch Nummer 4 aus dem Backtrackbereich.

Spoiler anzeigen

Sudoku Logisch 1 Richtig - Benötigte Zeit: 74.1091395694146
Sudoku Logisch 2 Richtig - Benötigte Zeit: 74.4228665933799
Sudoku Logisch 3 Richtig - Benötigte Zeit: 70.5715391201954
Sudoku Logisch 4 Richtig - Benötigte Zeit: 74.9408095162933
Sudoku Logisch 5 Richtig - Benötigte Zeit: 73.3758061429595
Sudoku Logisch 6 Richtig - Benötigte Zeit: 187.552049212959
Sudoku Logisch 7 Richtig - Benötigte Zeit: 161.976731679585
Sudoku Logisch 8 Richtig - Benötigte Zeit: 867.360795855339
Sudoku Logisch 9 Richtig - Benötigte Zeit: 339.676132022366
Sudoku Logisch 10 Richtig - Benötigte Zeit: 285.429293387847

Ergebnis Logisch: Zeit gesammt: 2209.41516310034 Zeit Durchschnitt: 220.941516310034

Sudoku Backtrack 1 Richtig - Benötigte Zeit: 2969.48969771298
Sudoku Backtrack 2 Richtig - Benötigte Zeit: 12353.9505719302
Sudoku Backtrack 3 Richtig - Benötigte Zeit: 919.845119980333
Sudoku Backtrack 4 Richtig - Benötigte Zeit: 996.378869381444
Sudoku Backtrack 5 Richtig - Benötigte Zeit: 10552.7026479622
Sudoku Backtrack 6 Richtig - Benötigte Zeit: 2182.44581364391
Sudoku Backtrack 7 Richtig - Benötigte Zeit: 819.679875514905
Sudoku Backtrack 8 Richtig - Benötigte Zeit: 3705.46144831257
Sudoku Backtrack 9 Richtig - Benötigte Zeit: 685.027566352707
Sudoku Backtrack 10 Richtig - Benötigte Zeit: 12384.5150710495

Ergebnis Logisch: Zeit gesammt: 2209.41516310034 Zeit Durchschnitt: 220.941516310034
Ergebnis Backtrack: Zeit gesammt: 47569.4966818408 Zeit Durchschnitt: 4756.94966818408
Ergebnis gelöste Sudokus: 20

**eukalyptus**

Zuwenig Vorgaben bei Backtracking geht nicht
sondern nur falsche Vorgaben...

Ein Backtrackalgorithmus muß auch ein leeres Sudoku korrekt befüllen können.

Nr. 4 hat folgende Lösung:

Code

947  165  283  
823  974  516  
651  328  947  


478  596  132  
516  432  879  
239  817  465  


764  251  398  
385  749  621  
192  683  754

Alles anzeigen

Ach ja, ich hab einen Intel Core2 T7200 @ 2,00 GHz
Aber wenn ich noch etwas Zeit finde, dann wird mein Algo noch etwas schneller

Edit: Lösung oben ist vom 5 Sudoku, hier Lösung 4:

Code

953  762  841  
624  815  973  
871  349  652  


289  457  136  
165  283  497  
437  691  285  


796  524  318  
318  976  524  
542  138  769

Alles anzeigen

**Andy**

Zitat

Ein Backtrackalgorithmus muß auch ein leeres Sudoku korrekt befüllen können.

stimmt, macht meiner in 0,5 sec.

jetzt sag mir mal, warum der ein "fast volles" sudoku wie dieses hier 000060080020000000001000000070000102500030000000000400004201000300700600000000050
nicht löst, aber sonst alle^^

**autoBert**

Hallo @ Andy,

dieses Sudoku wird laut dem Grader auf Sudoku Solver by Andrew Steward mit Extreme Grade Overall Score 847 bewertet. Die Solution-Count-Funktion auf der Webseite bricht ab:

Zitat

All Solutions to a Sudoku
Timed Out!

There are simply too few clues for a solution count to be able to return a value in a reasonable amount of time. This may or may not be a valid sudoku with a single solution

Und ich dachte, dass ich mit diesem mühsam erstellten Sudoku schon ein schweres geschafft hätte.

100020008020004070003500600005400000300000407002006010004305700030000080000060009

Es wird mit Diabolic Grade Overall Score 489 bewertet. Die Solution-Count-Funktion meldet nach 389779 Rekursionen 1 mögliche Lösung

Du kannst ja mal deinen Solver daran testen.

Viel Spaß damit wünscht dir (Auto)Bert

Ps. ein leeres Sudoku bricht die Solution-Count-Funktion auch ab

Zitat

All Solutions to a Sudoku
There are at least 500 solutions. Stopped computing beyond 500.
(recursed 11962 times)

**Andy**

Hi zusammen,

Zitat

dieses Sudoku wird laut dem Grader auf Sudoku Solver by Andrew Steward mit Extreme Grade Overall Score 847 bewertet. Die Solution-Count-Funktion auf der Webseite bricht ab:

ja, weil sein Solver nach einer bestimmten Zeit abbricht. Habe Mailkontakt mit ihm.
Ich habe das Sudoku übrigens auch gelöst, nach 5h und über 54 Millionen Iterationen. Wenn man den "klassischen" Backtracking-Ansatz verfolgt, kommt man irgendwann genau an diese Stelle. Die Iterationstiefe ist ja gewissermaßen festgelegt sobald man einen bestimmten "Weg" einschlägt. Das meinte ich in einem meiner früheren Postings mit dem Drehen des Sudokus um 90 Grad und völlig unterschiedlichen Laufzeiten.
Das heisst, sobald ein irgendwie gearteter Backtrackingalgorithmus verwendet wird, ist die Laufzeit definitiv abhängig vom eingeschlagenen Weg des Algorithmus. Somit ist, sobald der Weg nicht in der Aufgabe vorgegeben ist, die Laufzeit zufällig!, bzw nicht miteinander vergleichbar.
Einfaches Beispiel, das o.a. Sudoku:
Ich betrachte in der ersten Zeile die ersten 4 Felder, nach dem Ausschliessen der Möglichkeiten bleiben im Feld (1,1) die Ziffern 4,7,9 übrig, im Feld (1,2) die Ziffern 3,4,5,9 und im Feld (1,3) die 3,5,7,9 übrig, für (1,4) bleibt 1,3,4,5,9.
Jetzt jage ich meinen Solver zweimal durch dieses Sudoku. Einmal lasse ich die Auswahlschleife für die Möglichkeiten im einzelnen Feld von klein nach groß laufen (For $i=klein to groß, die Reihenfolge im Feld 1 wäre also 4,7,9 im zweiten Feld 3,4,5,9 usw), im anderen Fall von groß nach klein (for $i=groß to klein d.h.Reihenfolge ist 9,7,4 im zweiten Feld 9,5,4,3 usw).
Das Ergebnis ist gerade in diesem Sudoku frappierend.
Um allein im ersten Feld ausgehend von der 4 zur 7 zu kommen, gibt es Aufgrund der Struktur des Sudokus ca 25 Millionen Möglichkeiten, die folgenden Felder zu setzen, bis erkannt wird, dass die 4 nicht an dieser Stelle sitzen kann. Dito mit der 7 (weitere ca 20Mio Möglichkeiten), dann die 9, JUHU, Treffer! Also weiter im zweiten Feld, Test auf 3, dann 4, jeweils wieder mit ca 3 Mio Möglichkeiten, Treffer bei 5. Im dritten Feld erst die 3, dann 5 Treffer bei der 7, jetzt ist das Sudoku aber schon so "weit" gelöst, dass für alle restlichen Felder im gesamten Sudoku nur noch eine Handvoll Möglichkeiten übrigbleiben und in einigen Schritten gelöst ist.
Puhhhh.....
Also schnell die innerste Schleife "umprogrammiert", d.h. nur die Auswahlrichtung geändert (also For $i=groß to klein) und nun nochmal den identischen Algorithmus angeworfen.
Erstes Feld, erste Möglichkeit ist nun die 9, PENG, Treffer. Zweites Feld die 5 (die 9 ist ja schon im ersten Feld), Hoppla, durch die 9 im ersten Feld verringern sich die Möglichkeiten im gesamten Sudoku auf einige Hunderttausend. Nächste Ziffer ist im zweiten Feld die 4, PENG, Treffer. Weiter zum 3. Feld, die erste Möglichkeit ist die 7, PENG, Treffer! uswusf...

Bei einer langsamen (interpretierten) Programmiersprache wie Autoit fällt das sofort auf, der völlig identische Algorithmus als compiliertes C-Programm löst selbst das für ihn "schimmste" Sudoku in Millisekunden! Ich habe von Java-Programmierern gelesen, bei denen die Startzeit der Laufzeitumgebung stärker in die "Lösungszeit" eines Sudokus reingespielt hat, wie der eigentliche Algorithmus

Zusammenfassend: Es gibt nicht DEN schnellsten Algorithmus, sondern nur den schnellsten für ein bestimmtes Sudoku. Der Rest ist Programmiersprachen-Knowhow. Ähnlich wie beim Passwortcracken.
Sehr deutlich wird das, wenn man sich die Theorie hinter den "Dancing Links" von Don Knuth anschaut. Hier oder hier. Diese Methode löst u.a. ein Sudoku "relativ" schnell, im Endeffekt ist es ein Backtrackingalgorithmus der von einer "zufälligen" Startposition ausgeht. s.o.^^

**Andy**

Zitat

Und ich dachte, dass ich mit diesem mühsam erstellten Sudoku schon ein schweres geschafft hätte.

100020008020004070003500600005400000300000407002006010004305700030000080000060009

Es wird mit Diabolic Grade Overall Score 489 bewertet. Die Solution-Count-Funktion meldet nach 389779 Rekursionen 1 mögliche Lösung

Du kannst ja mal deinen Solver daran testen.

3,8 sekunden auf einem PIII 1,2 ghz^^

*edit* 25 Sekunden, wenn vorher keine Möglichkeiten für die einzelnen Felder aussortiert wurden