@K1773R
die Testroutine gibt sowohl in die Konsole, als auch in eine Msgbox aus.
Allerdings gibt die Testroutine nichts aus, wenn von dir kein Sudokusolver ausgewählt wurde s. Zeilen 1-5. Dieser ist hier im Thread von den Teilnehmern downzuloaden und per #include einzubinden.
ciao
Andy
Beiträge von Andy
-
-
Hallo,
habe eben stundenlang Tests von allen Teilnehmern durchlaufen lassen und die Ergebnisse in einen Beitrag eingestellt und dann beim Forumsbeitrag statt VORSCHAU die F5 gedrückt....
Naja, jedenfalls bin ich für eine Umdefinierung der F5-Taste in SCITE!!!!!!EINSELF
Habe nochmal eine kleine Testroutine geschrieben:
Spoiler anzeigen
[autoit];#include "j:\desktop\autots\Sudokusolver_eukalyptus.au3"
[/autoit] [autoit][/autoit] [autoit]
;#include "j:\desktop\autots\Sudoku.au3"
;#include "j:\desktop\autots\Sudoku-helfer.au3"
;#include "j:\desktop\autots\leviathan\Sudoku_leviathan.au3"
;#include "j:\desktop\autots\leviathan\blackmail.au3"
Dim $testarray[100]$testarray[1] = "000670900360005028805002100020506004009407000700100583070054261000703000084090050"
[/autoit] [autoit][/autoit] [autoit]
$testarray[2] = "628009000109056004500872001900510467807000030060020900004907103000201709091000280"
$testarray[3] = "076930000000108400300026000045080130010567090200310058068002005704000982020003710"
$testarray[4] = "120500360300009020007208004019000873403897001002350400000000087850016900200980140"
$testarray[5] = "906020100020050460000009730004260070700030608030871204800700041213000090490308006"
$testarray[6] = "007000300050908004900030060070004080102070900000500006800010000000000405060007000"
$testarray[7] = "060070008900104070003000500200007000008050906030900020000600010805000000000030007"
$testarray[8] = "000400050107000000000060003800003000001070904060900080040030001900502030006000700"
$testarray[9] = "004010050050900208300006000020000100000403000005000060000700005901004030070060900"
$testarray[10] = "500000006004902010070050900020004060900060803007100000000080200401000000000006070"
$testarray[11] = "009050200500000004000907000000204000100000005003010600035060720010000080074080510"
$testarray[12] = "200000140001209000500800000600700003070060000002004800009005000408100000000008067"
$testarray[13] = "000300150309001000200800000008009000100502000002000046600400007040060000005003200"
$testarray[14] = "003500100000010050700004008240000800000809002000700600000006009000200407015007000"
$testarray[15] = "000003050060004008800170000000710042040008700009005800790800000003050070004000200"
$testarray[16] = "000000000009040602087006010020004038040039000010008046064003050003050401000000000"
$testarray[17] = "000007002010000000000250108002030090006405000800090005004000609000500007607002840"
$testarray[18] = "000000000073080500092003070004070800708036020900000000000019650010000290000240000"
$testarray[19] = "060050002800000010000002600000020000500903208007010394006074000010006050200035000"
$testarray[20] = "004002080002000401500070060820040007060005100700000000090000023003098000000201600"
$testarray[21] = "000000000205980430006207009000030280040000000000090170009508006502460790000000000"
$testarray[22] = "000000800000640005009700004248000601060009000971000403003100008000570006000000700"
$testarray[23] = "000000020000008539000596080000000350051000700904700200402810000500040000086300000"
$testarray[24] = "000020000020000100365840070001050020840000000003060080214680030070000500000010000"
$testarray[25] = "700100002010070000008005300800000650006809000400300000009004000503600000000003071"
$testarray[26] = "100050000006009000080200004040030008007000060900000100030800002000004050000010700"
$testarray[27] = "000300800640800050875000001500070206000090000209080005400000769020008013007005000"
$testarray[28] = "050060001004800070800000052200057030000000000030690005790000008010006500500030060"
$testarray[29] = "080004060002000009760000012000806000800000003000107000670005041100000700050900020"
$testarray[30] = "000000000005010700070602090009020800060835010004070500030408020001090400000000000"
$testarray[31] = "060090050704050609000362000006005700982030546003600100000246000601070308050010060"
$testarray[32] = "007000000000010000000040005000008900400000000906007000008609000000000050030000041"
$testarray[33] = "530070000600195000098000060800060003400803001700020006060000280000419005000080079"
$testarray[34] = "100050000006009000080200004040030008007000060900000100030800002000004050000010700"
$testarray[35] = "000000103900050000000000800060020070001000000000300000000001460720000050000800000"
$testarray[36] = "000670900360005028805002100020506004009407000700100583070054261000703000084090050"
$testarray[37] = "628009000109056004500872001900510467807000030060020900004907103000201709091000280"
$testarray[38] = "076930000000108400300026000045080130010567090200310058068002005704000982020003710"
$testarray[39] = "120500360300009020007208004019000873403897001002350400000000087850016900200980140"
$testarray[40] = "906020100020050460000009730004260070700030608030871204800700041213000090490308006"
$testarray[41] = "007000300050908004900030060070004080102070900000500006800010000000000405060007000"
$testarray[42] = "060070008900104070003000500200007000008050906030900020000600010805000000000030007"
$testarray[43] = "000400050107000000000060003800003000001070904060900080040030001900502030006000700"
$testarray[44] = "004010050050900208300006000020000100000403000005000060000700005901004030070060900"
$testarray[45] = "500000006004902010070050900020004060900060803007100000000080200401000000000006070"
$testarray[46] = "009050200500000004000907000000204000100000005003010600035060720010000080074080510"
$testarray[47] = "700100002010070000008005300800000650006809000400300000009004000503600000000003071"
$testarray[48] = "200000140001209000500800000600700003070060000002004800009005000408100000000008067"
$testarray[49] = "000300150309001000200800000008009000100502000002000046600400007040060000005003200"
$testarray[50] = "000020000020000100365840070001050020840000000003060080214680030070000500000010000"
$testarray[51] = "003500100000010050700004008240000800000809002000700600000006009000200407015007000"
$testarray[52] = "000003050060004008800170000000710042040008700009005800790800000003050070004000200"
$testarray[53] = "000000000009040602087006010020004038040039000010008046064003050003050401000000000"
$testarray[54] = "000007002010000000000250108002030090006405000800090005004000609000500007607002840"
$testarray[55] = "000000000073080500092003070004070800708036020900000000000019650010000290000240000"
$testarray[56] = "060050002800000010000002600000020000500903208007010394006074000010006050200035000"
$testarray[57] = "004002080002000401500070060820040007060005100700000000090000023003098000000201600"
$testarray[58] = "000000000205980430006207009000030280040000000000090170009508006502460790000000000"
$testarray[59] = "000000800000640005009700004248000601060009000971000403003100008000570006000000700"
$testarray[60] = "000000020000008539000596080000000350051000700904700200402810000500040000086300000"
$testarray[61] = "000000103000050000000000800060020070001000000000300000000001460720000050000800000"
$testarray[62] = "100050000006009000080200004040030008007000060900000100030800002000004050000010700"
$testarray[63] = "000300800640800050805000001500070206000090000209080005400000709020008013007005000"
$testarray[64] = "050060001004800070800000052200057030000000000030690005790000008010006500500030060"
$testarray[65] = ".6....92..7.23.8.....7.1...8..........56.84..........3...4.7.....3.15.6..92....4."
$testarray[66] = "000000000005010700070602090009020800060835010004070500030408000001090400000000000"
$testarray[67] = "060090050000050609000362000006005700982030546003600100000246000601070308050010060"
$testarray[68] = "007000000000010000000040005000008900400000000906007000008609000000000050030000040"
$testarray[69] = "530070000600005000098000060800060003400803001700020006060000280000400005000080079"
$testarray[70] = "100050000006009000080200004040030008007000060900000100030800002000004050000010700"
$testarray[71] = "007000000000010000000040005000008900400000000906007000008609000000000050030000040"
$testarray[72] = "004620590000000200090700060060400370003000800089003050040001080001000000058074900"
$testarray[73] = "000060080020000000001000000070000102500030000000000400004201000300700600000000050"
$testarray[74] = "000000000000050000000000000060000000000000000070000000000000000800000000000000000"
$testarray[75] = "500000009020100070008000300040600000000050000000207010003000800060004020900000005"
$testarray[76] = "530000009020100070008000300040600000000050000000207010003000800060004020900000005" ;11 gefunden von nr 75_test()
[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]
ExitFunc _test()
[/autoit] [autoit][/autoit] [autoit]
Local $summe = 0, $brute = 0, $bruteflag = 0, $brutecounter = 0, $triple = 0, $rekurs = 0, $anzahlgefunden
Local $timer1 = 0, $geloeste = 0, $start = "", $solved, $loesung, $file, $z, $r, $s, $timer, $t, $beststring
$timer1 = TimerInit()
$geloeste = 0
For $p = 1 To 76 ;anzahl der zu prüfenden Sudokus anpassen
$start = $testarray[$p]
;$start = FileReadLine("vielesudokus.txt", $p) ;36000 sudokus
;$start = FileReadLine("35kergebnis.txt", $p)
;$start = FileReadLine("sudoku-loesung.dat", $p)
;$start = FileReadLine("boese_sudokus.txt",$p)
$summe += 1
$solved = 0
$timer = TimerInit()
$loesung = _solvesudoku($start);blackmails solver gibt nach einer gewissen zeit Strings zurück, die zwar gelöste Sudokus sind,
[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]
;aber mit dem Rätsel nichts zu tun haben
If _geloestx($loesung) = 1 And $loesung <> "123457689456189327789263514245631978317948265968725143531876492672394851894512736" Then
$geloeste = $geloeste + 1
$solved = 1
EndIf
$t = Int(TimerDiff($timer))
If $solved = 0 Then
$file = FileOpen("sudoku-loesung.dat", 1)
FileWriteLine($file, $start)
FileClose($file)
EndIf
ConsoleWrite($p & " " & $t & " " & $loesung & " " & $rekurs & " " & Int(TimerDiff($timer1) / 1000) & @CRLF)
Next
ConsoleWrite(@CRLF & "Sudokus: " & $geloeste & " von " & $summe & " gelöst in: " & (TimerDiff($timer1) / 1000) & " Sekunden" & @CRLF & @CRLF)
MsgBox(0, "Geloeste Sudokus: " & $geloeste, "Zeit: " & (TimerDiff($timer1) / 1000) & @CRLF & $anzahlgefunden & @CRLF & $summe)
EndFunc ;==>_testFunc _geloestx($String) ;prüfen, ob 81er-string=reguläres sudoku d.h. nur eine ziffer in zeile/spalte/kasten
[/autoit] [autoit][/autoit] [autoit]
If StringLen($String) <> 81 Or StringInStr($String, "+") Then Return 3
Local $spalten[10]
Local $zeilen[10]
Local $box[10]For $i = 1 To 81 Step 9 ;string in zeilen und kasten
[/autoit] [autoit][/autoit] [autoit]
$z = Int($i / 9) + 1
$zeilen[$z] = StringMid($String, $i, 9)
If _zifferdoppeltx($zeilen[$z]) <> 0 Then Return 0 ; msgbox(0,"ziffer in zeile "&$zeile[$z]&" doppelt","")
$s = Int($i / 27)
For $p = 0 To 2
$r = ($s * 3) + $p + 1
$box[$r] = $box[$r] & StringMid($zeilen[$z], ($p * 3) + 1, 3)If _zifferdoppeltx($box[$r]) <> 0 Then Return 0 ;msgbox(0,"ziffer in box "&$box[$r]&" doppelt","")
[/autoit] [autoit][/autoit] [autoit]
Next
Next
For $z = 1 To 9
For $i = 1 To 9 ;ersetzen mit stringregexp
$spalten[$z] = $spalten[$z] & StringMid($zeilen[$i], $z, 1)
Next
If _zifferdoppeltx($spalten[$z]) <> 0 Then Return 0 ;msgbox(0,"ziffer in spalte "&$spalten[$z]&" doppelt","")
NextIf StringInStr($String, "0") Then
[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]
Return 2 ;Teilstring ist bisher ok
Else
Return 1 ;sudoku ist komplett gelöst
EndIf
EndFunc ;==>_geloestx;================================================================================================
[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]
Func _zifferdoppeltx($test) ;wenn ziffer doppelt im string, dann return 1
If StringRegExp($test, "([1-9]).*\1") Then
Return 1
Else
Return 0
EndIf
EndFunc ;==>_zifferdoppeltxFunc _ziffernureinmalx($test, $a)
[/autoit] [autoit][/autoit] [autoit]
If StringInStr($test, $a) <> 0 And StringInStr($test, $a, 0, 2) = 0 Then
Return 1
Else
Return 0
EndIf
EndFunc ;==>_ziffernureinmalx;================================================================================================
[/autoit]Damit wurden, genau wie bei den 20 Sudokus, in etwa ähnliche Ergebnisse von Blackmail, Eukalyptus und mir erzielt.
Eukalyptus´ Backtracker scheint keine "Strategie" zum vorzeitigen Abbruch eingebaut zu haben, daher dauern einige Sudokus sehr lange, ich habe diese nach 10min abgebrochen. Bei den gelösten Sudokus (bis nr 72) löst er in etwa genauso schnell wie Blackmails und meiner.
Blackmails Solver gibt bei einigen Sudokus immer denselben String zurück, der zwar eine Lösung ist (leeres sudoku ausgefüllt?), aber mit der richtigen Lösung nichts zu tun hat^^Hier nochmal meine Ergebnisse von den 20 Sudokus von allen Teilnehmern. Leviathans Solver bekam ich auf die schnelle nicht so umgestrickt, dass er mit der Testroutine verwendbar war.
Spoiler anzeigen
Ergebnisse:
Eukalyptus:
Sudoku Logisch 1 Richtig - Benötigte Zeit: 93.4297515466351
Sudoku Logisch 2 Richtig - Benötigte Zeit: 105.856749950063
Sudoku Logisch 3 Richtig - Benötigte Zeit: 105.742489618094
Sudoku Logisch 4 Richtig - Benötigte Zeit: 115.882605191442
Sudoku Logisch 5 Richtig - Benötigte Zeit: 106.442578595883
Sudoku Logisch 6 Richtig - Benötigte Zeit: 183.615515379748
Sudoku Logisch 7 Richtig - Benötigte Zeit: 221.026415368434
Sudoku Logisch 8 Richtig - Benötigte Zeit: 338.589401725638
Sudoku Logisch 9 Richtig - Benötigte Zeit: 235.669896593003
Sudoku Logisch 10 Richtig - Benötigte Zeit: 189.285789115656Ergebnis Logisch: Zeit gesammt: 1695.5411930846 Zeit Durchschnitt: 169.55411930846
Sudoku Backtrack 1 Richtig - Benötigte Zeit: 2104.27889578145
Sudoku Backtrack 2 Richtig - Benötigte Zeit: 6025.03893651288
Sudoku Backtrack 3 Richtig - Benötigte Zeit: 536.318163341989
Sudoku Backtrack 4 Richtig - Benötigte Zeit: 4865.44826227914
Sudoku Backtrack 5 Richtig - Benötigte Zeit: 1026.22372396492
Sudoku Backtrack 6 Richtig - Benötigte Zeit: 611.057829975597
Sudoku Backtrack 7 Richtig - Benötigte Zeit: 287.264163462116
Sudoku Backtrack 8 Richtig - Benötigte Zeit: 1973.48154583893
Sudoku Backtrack 9 Richtig - Benötigte Zeit: 479.377965635297
Sudoku Backtrack 10 Richtig - Benötigte Zeit: 5339.63087487376Ergebnis Logisch: Zeit gesammt: 1695.5411930846 Zeit Durchschnitt: 169.55411930846
Ergebnis Backtrack: Zeit gesammt: 23248.1203616661 Zeit Durchschnitt: 2324.81203616661
Ergebnis gelöste Sudokus: 20Funkey;
Sudoku Logisch 1 Richtig - Benötigte Zeit: 2292.75983400125
Sudoku Logisch 2 Richtig - Benötigte Zeit: 698.101574362105
Sudoku Logisch 3 Richtig - Benötigte Zeit: 796.123809031595
Sudoku Logisch 4 Richtig - Benötigte Zeit: 655.608743569364
Sudoku Logisch 5 Richtig - Benötigte Zeit: 1045.41638671954
Sudoku Logisch 6 Richtig - Benötigte Zeit: 3069.28171038498
Sudoku Logisch 7 Richtig - Benötigte Zeit: 3742.71869748809
Sudoku Logisch 8 Falsch
Sudoku Logisch 9 Richtig - Benötigte Zeit: 3357.70076923184
Sudoku Logisch 10 Richtig - Benötigte Zeit: 3224.0416030529Ergebnis Logisch: Zeit gesammt: 24134.5634710557 Zeit Durchschnitt: 2413.45634710557
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 FalschErgebnis Logisch: Zeit gesammt: 24134.5634710557 Zeit Durchschnitt: 2413.45634710557
Ergebnis Backtrack: Zeit gesammt: 53114.8849923663 Zeit Durchschnitt: 5311.48849923663
Ergebnis gelöste Sudokus: 9Andy:
Sudoku Logisch 1 Richtig - Benötigte Zeit: 113.587062042802
Sudoku Logisch 2 Richtig - Benötigte Zeit: 127.377641571764
Sudoku Logisch 3 Richtig - Benötigte Zeit: 123.374618841221
Sudoku Logisch 4 Richtig - Benötigte Zeit: 133.249616920586
Sudoku Logisch 5 Richtig - Benötigte Zeit: 125.700612787379
Sudoku Logisch 6 Richtig - Benötigte Zeit: 177.553013022605
Sudoku Logisch 7 Richtig - Benötigte Zeit: 186.293509370604
Sudoku Logisch 8 Richtig - Benötigte Zeit: 347.171218688409
Sudoku Logisch 9 Richtig - Benötigte Zeit: 184.979096505282
Sudoku Logisch 10 Richtig - Benötigte Zeit: 168.307983277204Ergebnis Logisch: Zeit gesammt: 1687.59437302786 Zeit Durchschnitt: 168.759437302786
Sudoku Backtrack 1 Richtig - Benötigte Zeit: 1795.74750422191
Sudoku Backtrack 2 Richtig - Benötigte Zeit: 3889.11858909442
Sudoku Backtrack 3 Richtig - Benötigte Zeit: 719.368243729301
Sudoku Backtrack 4 Richtig - Benötigte Zeit: 2355.40550544832
Sudoku Backtrack 5 Richtig - Benötigte Zeit: 1066.96689104341
Sudoku Backtrack 6 Richtig - Benötigte Zeit: 673.677241101872
Sudoku Backtrack 7 Richtig - Benötigte Zeit: 257.63386128684
Sudoku Backtrack 8 Richtig - Benötigte Zeit: 1662.56800794514
Sudoku Backtrack 9 Richtig - Benötigte Zeit: 671.487856696871
Sudoku Backtrack 10 Richtig - Benötigte Zeit: 3905.29857845061Ergebnis Logisch: Zeit gesammt: 1687.59437302786 Zeit Durchschnitt: 168.759437302786
Ergebnis Backtrack: Zeit gesammt: 16997.2722790187 Zeit Durchschnitt: 1699.72722790187
Ergebnis gelöste Sudokus: 20Blackmail:
Sudoku Logisch 1 Richtig - Benötigte Zeit: 154.968857773823
Sudoku Logisch 2 Richtig - Benötigte Zeit: 131.527330987598
Sudoku Logisch 3 Richtig - Benötigte Zeit: 138.637731890506
Sudoku Logisch 4 Richtig - Benötigte Zeit: 138.389655668528
Sudoku Logisch 5 Richtig - Benötigte Zeit: 139.44258278636
Sudoku Logisch 6 Richtig - Benötigte Zeit: 250.024514288827
Sudoku Logisch 7 Richtig - Benötigte Zeit: 256.196248405873
Sudoku Logisch 8 Richtig - Benötigte Zeit: 377.978206727391
Sudoku Logisch 9 Richtig - Benötigte Zeit: 242.500932381071
Sudoku Logisch 10 Richtig - Benötigte Zeit: 253.150051193657Ergebnis Logisch: Zeit gesammt: 2082.81611210363 Zeit Durchschnitt: 208.281611210363
Sudoku Backtrack 1 Richtig - Benötigte Zeit: 1137.50155396845
Sudoku Backtrack 2 Richtig - Benötigte Zeit: 9556.92385484747
Sudoku Backtrack 3 Richtig - Benötigte Zeit: 457.79896606971
Sudoku Backtrack 4 Richtig - Benötigte Zeit: 504.163517989018
Sudoku Backtrack 5 Richtig - Benötigte Zeit: 888.127960397201
Sudoku Backtrack 6 Richtig - Benötigte Zeit: 842.655700654692
Sudoku Backtrack 7 Richtig - Benötigte Zeit: 241.729605298998
Sudoku Backtrack 8 Richtig - Benötigte Zeit: 1102.31691457993
Sudoku Backtrack 9 Richtig - Benötigte Zeit: 576.927514530478
Sudoku Backtrack 10 Richtig - Benötigte Zeit: 9595.4762406954Ergebnis Logisch: Zeit gesammt: 2082.81611210363 Zeit Durchschnitt: 208.281611210363
Ergebnis Backtrack: Zeit gesammt: 24903.6218290313 Zeit Durchschnitt: 2490.36218290313
Ergebnis gelöste Sudokus: 203 Sieger, glücklichen Herzwunsch allen^^
-
Habe meinen Solver wieder etwas beschleunigt, durch geringe Änderungen in der BacktrackSTRATEGIE, nicht im eigentlichen Bruteforce-Algorithmus.
Die "verbratenen" Zeiten bei den Strategien gehen beim Lösen mehrerer Sudokus gegenüber den Backtrackzeiten völlig unter.
Es hat also m.E. keinen Sinn, z.B. bei der Strategie "HiddenTriple" 30 Millisekunden einzusparen um beim Backtracken dann MINUTEN zu brauchen.Daher möchte ich die "Backtrack-Strategie" zur Diskussion stellen:
Reines Backtracken hat nur Sinn, wenn in endlicher Zeit die Lösung gefunden werden kann. Im Laufe dieses Threads und beim Lösen der Sudokus ist einigen auch klar geworden, dass es fürs Backtracken "gute" und "schlechte" (will heissen sehr lange für die Lösung brauchende) Sudokus gibt.
Um ein "schlechtes" Sudoku trotzdem schnell zu lösen, benutze ich folgendes Vorgehen, eine Kombination aus Logiklöser und klassischem Backtrack.DO
Suchen des nächsten Feldes mit 2 Möglichkeiten, wenn dieses nicht existiert, suche Feld mit 3 Möglichkeiten.
Nimm eine dieser Möglichkeiten an und löse logisch.
- Bisher wie gehabt, aber ich habe festgestellt, dass auch die "schlechtesten" Sudokus sofort mittels "Logik" lösbar sind, wenn 5 zusätzliche richtige Felder in das Rätsel eingebaut werden. Also kann man IMMER nach 5 fehlgeschlagenen Versuchen aus dem Backtrack raus, d.h. wenn nach 5 zusätzlich gesetzten Feldern keine logische Lösung existiert, dann ist diese Kombination der 5 Möglichkeiten falsch
Wenn keine Lösung zu finden ist, dann versuche klassisches Backtrack, aber mit geringer Rekursionstiefe.
"Einfache" Sudokus sind in kürzester Zeit mittels klassischem Backtrack zu lösen, d.h. die Lösung wird schon nach relativ wenigen Rekursionen gefunden. In der Annahme, daß das zu lösende Sudoku mit den 5 zusätzlich gesetzten Felder "einfach" ist, wird das Backtracken auf 1000-2000 Rekursionen beschränkt!
LOOP solange, bis eine Lösung gefunden wurde, oder noch nicht 5 Felder gesetzt sind.Man kann jetzt an vielen Sudokus ausprobieren, welche Änderungen schneller zur Lösung führen. Indem man an den Parametern Anzahl der Felder (5 oder 6 oder 7) oder der Rekursionstiefe beim Backtracken (1000 oder 2000-5000) dreht, bekommt man eine schnelle Lösung (oder garkeine) oder aber eine sichere Lösung nach längerer Zeit. Ich habe mir einige der "schlechten" Sudokus geschnappt und dann solange an den Parametern geschraubt, bis sie erstens gelöst waren und zweitens relativ schnell^^
Aber vielleicht hat ja einer von euch eine ganz andere Idee!?
-
ja, ähnlich mache ichs zzt...
thx nochmals -
[autoit]
$string = '2462361231234567567' ; 4 und 3 kommen doppelt vor, werden trotzdem als lösung ausgegeben
[/autoit]
;$string = '83211234756567' ; 8 und 4 kommen jeweils nur einmal vor
MsgBox(0,0, StringRegExpReplace($string, '(\d+)(.*)\1', '\3'))
Hallo Oscar, habe dein Beispiel nachvollzogen. Die Idee ist schonmal ein Anfang, funktioniert so aber nur, wenn der String geordnet ist, denn deine RegEx findet die Ziffern zwischen den mindestens doppelt vorkommenden Ziffern und maskiert diese aus.
Bsp. 22344 findet die 3, weil match 22 und 44 aber
23244 findet nicht, weil match 232 (alles zw den beiden 2ern) und 44
auch 1234123 findet nicht, weil 123 doppelt vorkommt und match 1234123 , jetzt aber die \3 durch \2 ersetzt ist da die 4
#+grmblfx -
Hallo Oscar,
Vielen Dank!
Auf StringRegExpReplace() statt StringRegExp() muss man auch erstmal kommen....
thx
Andy -
funkey
thx, aber dein Script "vereinzelt" alle im String vorkommenden Ziffern, ich bräuchte aber einen Treffer auf der 4, da diese Ziffer die einzige im String ist, die nur einmal vorkommt. -
Hallo zusammen,
gibt es eine Möglichkeit in einem String von Ziffern die jeweils NUR EINMAL vorkommende Ziffer zu finden?
Bsp.: "1231234567567" findet die 4, oder die Position innerhalb des Strings.Wenn es die Möglichkeit gäbe, alle einfach vorkommenden Ziffern zu finden wäre das natürlich optimal.
Zzt. löse ich diese Aufgabe mit stringinstr() und der überprüfung auf das 2. Vorkommen der Ziffer im String, eliminieren usw. bis nur noch nicht mehrfach vorkommende Ziffern übrigbleiben. Aber da ich mich ein bisschen intensiver mit den StringRegExp()-Möglichkeiten auseinandersetzen wollte und schon einige Stunden mit div. Online-RegEx-Trainern verbracht habe, fand ich das eine schöne Übung
...
ausserdem könnte die RegEx Zeit in meinem Sudoku-Solver sparenthx vorab
Andy -
Zitat
...und herausfinden, in welcher Reihenfolge man die Strategien am besten durchlaufen lässt.
da habe ich auch lange rumexperimentiert. Eigentlich gibts nur die Standard-Antwort:" Je nach Sudoku unterschiedlich!"
Aber idR sind die "schnellen" Strategien besser vorne und die langsamen (bei mir z.B. hidden triples) hinten.
Ich lasse die "Einer finden"-Strategien so lange durchlaufen (do/loop), bis nichts mehr gefunden bzw eliminiert werden kann, erst danach die naked pairs usw bis hin zu den hidden triples.Jedenfalls gibt dein Solver ganz schön Gas, ich lasse den grade die ersten 5000 Sudokus lösen
ciao
Andy -
eukalyptus
Klasse Idee, die Möglichkeiten mit BitAND zu vergleichen und mit BitXOR zu eliminieren, hat mich einige Minuten und 2 Tassen Kaffe gekostet um überhaupt zu kapieren was da vor sich geht^^
Leider rennt sich dein Backtrack-Algorithmus zu Tode, ich hätte gern mal die ersten 5000 Sudokus aus der Liste durchlaufen lassen aber schon beim achten Sudoku habe ich nach 1/4h rechnen ohne Lösung abgebrochen.Nach dem neidvollen Sichten eurer "schönen" Guis hat mich jetzt doch der Ehrgeiz gepackt, wenigstens eine "sichtbare" Lösungsfindung anzubieten^^...morgen.....vielleicht.....
-
Hallo,
anbei mein "Brocken", die GUI ist abgeschaltet, bzw war nur zum verfolgen des Lösungswegs implementiert.
Nach dem auskommentieren der Zeile 158 kann man in der Konsole die Lösungen verfolgen, ungelöste Sudokus werden in eine Datei geschrieben.ciao
AndyDer Inhalt kann nicht angezeigt werden, da er nicht mehr verfügbar ist. -
Hi,
ok, Abgabe morgen, aber das mit dem Archiv schenk ich mir^^
Wir tauschen die Scripte aus und jeder lässt dann die ersten 5.000 oder 10.000 Sudokus aus der Liste mit den Scripten der anderen Teilnehmer durchlaufen.
So haben wir mehrere Ergebnisse auf verschiedenen Rechnern. Ich habe nämlich festgestellt, daß mein Sudokuscript und auch andere Autoit-Projekte relativ anfällig auf die "Aktivität" des Rechners reagieren. Beim Lösen immer derselben 10 Sudokus waren teilweise Zeitunterschiede von bis zu 100% feststellbar.
ciao
Andy -
Hallo zusammen,
ich bin bis heute Abend off, dann stelle ich mein Script einfach hier in den Thread.
ciao und schönen Tag
Andy -
langsam wirds was.....
Spoiler anzeigen
Code
Alles anzeigenSudoku Logisch 1 Richtig - Benötigte Zeit: 41.9824307279277 Sudoku Logisch 2 Richtig - Benötigte Zeit: 36.8063538801719 Sudoku Logisch 3 Richtig - Benötigte Zeit: 37.0792935973706 Sudoku Logisch 4 Richtig - Benötigte Zeit: 37.8369317888167 Sudoku Logisch 5 Richtig - Benötigte Zeit: 37.0097316837754 Sudoku Logisch 6 Richtig - Benötigte Zeit: 53.7353211092471 Sudoku Logisch 7 Richtig - Benötigte Zeit: 54.037594163504 Sudoku Logisch 8 Richtig - Benötigte Zeit: 108.977817013056 Sudoku Logisch 9 Richtig - Benötigte Zeit: 52.7798924164943 Sudoku Logisch 10 Richtig - Benötigte Zeit: 52.3301145816019 Ergebnis Logisch: Zeit gesammt: 512.575480961966 Zeit Durchschnitt: 51.2575480961966 Sudoku Backtrack 1 Richtig - Benötigte Zeit: 578.548949657009 Sudoku Backtrack 2 Richtig - Benötigte Zeit: 1274.71787615465 Sudoku Backtrack 3 Richtig - Benötigte Zeit: 218.915253195588 Sudoku Backtrack 4 Richtig - Benötigte Zeit: 710.951252184286 Sudoku Backtrack 5 Richtig - Benötigte Zeit: 196.600126552397 Sudoku Backtrack 6 Richtig - Benötigte Zeit: 80.6689118309729 Sudoku Backtrack 7 Richtig - Benötigte Zeit: 524.099012584002 Sudoku Backtrack 8 Richtig - Benötigte Zeit: 206.273143653733 Sudoku Backtrack 9 Richtig - Benötigte Zeit: 1264.2746494317 Sudoku Backtrack 10 Richtig - Benötigte Zeit: 284.52442978088 Ergebnis Logisch: Zeit gesammt: 512.575480961966 Zeit Durchschnitt: 51.2575480961966 Ergebnis Backtrack: Zeit gesammt: 5339.57360502522 Zeit Durchschnitt: 533.957360502522 Ergebnis gelöste Sudokus: 20eukalyptus
fetten RESPEKT von mir! Für reines BT sieht das schon ziemlich schnell aus.
ABER! Bei "passenden" Sudokus ist Backtrack sehr schnell, bei einigen kann BT mithalten, und wenn die Sudokus "böse" sind, dann gute Nacht....
Böse Sudokus:Spoiler anzeigen
ZitatAlles anzeigen500080200740000000000000000002050000000600007800000040060700000001000500000304000
602050000000003040000000000430008000010000200000000700500270000000000081000600000
602050000000004030000000000430008000010000200000000700500270000000000081000600000
602700000000800130000000090400000700030090000000010000500400600010000020000000000
700080000000000104000000200000102000200000030000400500051030000000006070040000000
000701600500080000000000000000600701208090000400000000000020050070300000000000080
002100400083000000000000000500400700600020000010000000000008063100700000000000080
000800001900000500000000000410050000003000080000000700000108040020300000500000600
051000000000300080000070000020501006800000040000700000000000201300040000000000500 -
Zitat
Unglaublich! Wie hast Du denn das hingekriegt? Ich wüsste nicht, wo ich noch so viel Zeit rausholen sollte ...
Hab mal die einzelnen Sequenzen im Programmablauf von der Zeit her analysiert, da hat mich beinahe der Schlag getroffen.
bsp: Lösungszeit für ein einfachstes Sudoku (logisch, Lösung nur durch finden der einmalig vorkommenden Möglichkeit in einer Zeile) gesamt: 300ms.Einzelzeiten:
Sudokustring einlesen und die Ziffern in ein Array schreiben, die leeren Felder mit 1-9 ausfüllen.....10ms
Array zum Lösen vorbereiten, d.h. in den "leeren" Feldern die Möglichkeiten eliminieren, d.h. jeweils nur eine Ziffer in Zeile/Spalte/Box, also das "jungfräuliche" Sudoku auf dem Papier.....240ms
Der eigentliche Lösungsvorgang (finde alle nur einmal in der Spalte/Zeile vorkommenden Möglichkeiten) per Funktion _soloincol(), ca 60 Ziffern in . ..... 35ms
Restzeit von einigen Millisekunden für das Prüfen der Lösung und Ausgabe...15msUber 240ms, d.h, 2/3 der kompletten Zeit wurde bei mir verbraten, nur um das Array für die Lösung vorzubereiten . Da musste der Wurm drin sein! So wars auch, ein dezentes IF an der richtigen Stelle wirkt Wunder, sodann geschmeidig auf die F5-Taste gehämmert und schwupp wurden aus den 240ms nur noch 90
Neue Gesamtlösungszeit: 150ms => Geschwindigkeit verdoppelt!
Gut, so einfach geht es leider nicht immer, zzt hänge ich an den hidden Triples, diese Funktion dauert bei mir zumindest laaaaange, ich hoffe da auf die stringregexpr()-Spezialisten unter euch, da sollte was machbar sein ..... -
Hab mal nachgelegt^^
Spoiler anzeigen
Code
Alles anzeigenSudoku Logisch 1 Richtig - Benötigte Zeit: 37.8402841701948 Sudoku Logisch 2 Richtig - Benötigte Zeit: 38.508804890007 Sudoku Logisch 3 Richtig - Benötigte Zeit: 36.4680427261007 Sudoku Logisch 4 Richtig - Benötigte Zeit: 35.7780108924458 Sudoku Logisch 5 Richtig - Benötigte Zeit: 36.3205379454651 Sudoku Logisch 6 Richtig - Benötigte Zeit: 55.2165149481289 Sudoku Logisch 7 Richtig - Benötigte Zeit: 56.1644007827811 Sudoku Logisch 8 Richtig - Benötigte Zeit: 188.753877937 Sudoku Logisch 9 Richtig - Benötigte Zeit: 56.1630039572069 Sudoku Logisch 10 Richtig - Benötigte Zeit: 55.7791562894167 Ergebnis Logisch: Zeit gesammt: 596.992634538747 Zeit Durchschnitt: 59.6992634538747 -
Als ich angefangen habe, wusste ich nicht was naked, hidden oder sonstwie bei Andrew Stuart bezeichnete Strategien sind, ich habe einfach versucht die Strategie "wie auf dem Papier" programmtechnisch umzusetzen. Und auch die Funktion so genannt^^
Ich könnte "paarinreihe" natürlich in "pointing pairs" umbenennen, das habe ich bei den "hidden pairs" auch gemacht, aber einfach nur deswegen, weil mir mein eigener Name der Funktion noch bescheuerter vorkam :o)
ZitatDurchschnitt: 83.2767293049815
beeindruckend, aber ich befürchte, da geht noch was^^
-
...es geht dem Ende zu
Keine Ahnung ob gut oder schlecht, aber hier mal mein "Kurzvorschlussergebnis". Die Sudokus habe ich der schon von mir verlinkten Liste entnommen und auf einer 2,3GHZ-Maschine durchrauschen lassenSpoiler anzeigen
Code
Alles anzeigenSudokus: 34998 von 35000 gelöst in: 12203 Sekunden Strategietreffer: Übriggebliebene Zahlen im Kasten (Check): 322468 Solorowcol Kasten: 3363 solorowcol Zeile: 4395 solorowcol Spalte: 1208 soloinrow : 741612 soloincol : 944756 solokasten : 132496 paarimkasten : 524896 paarinreihe : 53758 nakedpair : 25898 hidden pair/triple : 85589 Backtrack : 5206Die 2 nicht gelösten Sudokus werden zwar auch gelöst, allerdings "leidet" dann die Gesamtzeit etwas^^ d.h. Verlängerung um einige Minuten.
Man erkennt die Strategietreffer, d.h. gezählt wurde die Elimination von Möglichkeiten innerhalb eines Feldes bzw. der Treffer auf eine Möglichkeit.
Ungefähr 1/6 der Sudokus sind nicht mit meinen einfachen Strategien zu lösen (im Schnitt dauert damit die Lösung 100ms), das "Backtracken" dieser 5206 Puzzles braucht aber 80% der Gesamtzeit!
Weiterhin sind geschätzte 80% der backgetrackten (oder heisst das gebacktrackten ?!) Sudokus innerhalb der ersten 2-3 Sekunden gelöst.
Ich sitze gerade am finetuning, da holt man bei einigen Sudokus eben mal den Faktor 3 an Zeit raus mit ändern eines "kleinen" Parameters innerhalb der Rekursion.Wie siehts bei euch aus?
eukalyptus
Wir könnten den bereits bekannten SudokuBenchMark.au3 verwenden und mit einigen Sudokus erweitern, ich denke insgesamt 40-50 Stück sollten reichen. Man könnte diese ja in verschiedene "Schwierigkeitsstufen" einteilen. So wäre für jeden etwas dabei. Oder wir wählen aus der großen Liste einfach per Zufall 50 Stück aus und jeder von uns stellt noch 2-3 seiner "bösesten" Sudokus zur Verfügung^^Andy
-
Hallo zusammen,
in der C´t 7/2009 ist ab Seite 102 ein m.E. relativ einfaches Verfahren beschrieben, um Programme an einzelne Prozessorkerne zu binden. Beispielsweise ein Virenscan über mehrere Festplatten.
Bei einer "seriellen" Batchdatei werden die einzelnen Scans nacheinander abgearbeitet.
Scanne LW C: , schreibe danach das Ergebnis in Logdatei
Scanne LW D: , schreibe danach das Ergebnis in Logdatei
Scanne LW E: , schreibe danach das Ergebnis in Logdatei
Scanne LW F: , schreibe danach das Ergebnis in Logdatei
Solch oder ähnliche Batches laufen aber nur auf einem Prozessorkern, d.h. bei einem Duo- Triple- oder Quadcore schuftet einer der Kerne neben dem "normalen" Windowsgedöns an der Batchdatei , während die anderen 3 Kerne im Sleepmodus verweilen.Ab Vista kann man über den Windows-START-Befehl und dem Parameter /AFFINITY die Programme auf die einzelnen Prozessorkerne verteilen. Ausserdem kann man auch die Basispriorität einstellen.
Bei einer "parallelen" Batchdatei werden die Aufgaben verteilt und gleichzeitig auf den Kernen eines Quadcore gestartet:
Scanne LW C: , schreibe danach das Ergebnis in Logdatei > Starte dieses Programm auf Kern 1
Scanne LW D: , schreibe danach das Ergebnis in Logdatei > Starte dieses Programm auf Kern 2
Scanne LW E: , schreibe danach das Ergebnis in Logdatei > Starte dieses Programm auf Kern 3
Scanne LW F: , schreibe danach das Ergebnis in Logdatei > Starte dieses Programm auf Kern 4
Jetzt schuften alle 4 Kerne und üblicherweise ist der Scan über alle Platten wesentlich früher fertig.
Das funktioniert selbst auf einem "alten" P4 mit Hyperthreating einwandfrei.Mr. "A20-Gate" Andreas Stiller von der C´t hat das Programm Launch erstellt, dass auch unter XP das Verteilen von Aufgaben an die einzelnen Kerne vereinfacht.
Somit kann man einige Anwendungen teilweise extrem beschleunigen.
Ich habe mit meinem Sudoku-Solver 35000 Sudokus lösen lassen. Auf einem Dualcore aufgeteilt in 2mal je 17500 Sudokus waren alle 35000 Sudokus exakt nach der Hälfte der Zeit gelöst!Da sollte sich ggf auch mit AutoIt etwas "drumherumstricken" lassen.....
ciao
Andy -
Hallo zusammen,
als Opera-Nutzer der ersten Stunde empfand ich die Implementierung der Mausgesten als beste Erfindung seit Bestehen der Maus
Mittlerweile ist man so daran gewöhnt, dass man auch in anderen Programmen diese "Schnellzugriffe" nutzen will, Ihr seid auf dem richtigen Weg!
HAUT REIN!!!!Andy