Gibt es noch Leute die sich mit ihrem Solver beschäftigen? Wir sollten uns überlegen, wie wir das hinbekommen mit der Auswertung.
Ansonsten könnten wir ja mal konstruktiv unsere Skripte bewerten bzw. testen warum etwas nicht funktioniert bzw. manche Strings nur mit langer Rechenzeit gelöst werden können.
Hi,
ich habe meinen Solver auf der Basis der Strategien eines (durchschnittlichen) menschlichen Spielers erstellt und versucht, diese Regeln in ein Script zu verpacken, was mir aber eher schlecht als Recht gelungen ist^^. Vieles wird mehrfach berechnet, da ist noch massig Raum für Optimierungen.
Naja, Grafikausgabe muss ja auch sein, schön bunt, damit man den Lösungsweg verfolgen kann 
Für die Lösung der 25 von Alina vorgegebenen Puzzles braucht ein 1,2Ghz-PIII ca. 10 Sekunden (ohne Grafikausgabe). Von den 35 Sudokus bei der Auswertung bekomme ich mit meinem Script 4 nicht gelöst.
Allerdings ist mindestens ein Sudoku dort dabei, dass mit "herkömmlichen" Strategien nicht lösbar ist, d.h. eine reine Aufgabe für einen Bruteforce-Numbercruncher. Ich vermute, prizma und eukalyptus machen solch ein Skript.
Um schnellstmöglich Ergebnisse zu bekommen würde ich die drei einfachen Regeln in einen rekursiven Algorithmus packen und auf ein 3-d-Array loslassen....aber dazu fehlt mir zzt noch der Antrieb. 
Ausserdem hat meine Frau schon ganz komisch geguckt als ich ihr von virtuellen Maschinen und DOS und einem Assembler vorgeschwärmt habe.
Die unterschiedliche Lauflänge beim crunchen hängt einfach von der Startposition und den Abbruchkriterien ab. Ca 60 Anfangsfelder, jedes mit ca 3 Möglichkeiten, und dann noch mit 10 "schlechten " Feldern angefangen...dann läuft sich der Algorithmus tot.
ciao
Andy
Hast recht ich benutze eine backtracking Methode. Hatte mit C++ keine Probleme mit der Rechenzeit/bruteforce. Da ich annahm diese Lösung leicht in AutoIt zu portieren staunte ich nicht schlecht als ich das Ergebnis sah was nicht annähernd an die Geschwindigkeit des C++ Solvers rankommt. Ich denke/hoffe, dass ich da was übersehen habe.
Bin mal auf Deinen Lösugsweg gespannt habe selbst allerdings keine Lust/Zeit mich auf anderen Weg an das Thema heranzumachen.
Werde mal die ganzen Aufgaben durch meinen Solver jagen, evntl. habe ich gerade die Falschen erwischt...
ich hab leidetr nicht die zeit um auch einen solver zu schreiden, aber ich hab da was, was trotsdem interessant sein könnte.
es ist so eine art msgbax, nur dass das sudoku angezeigt wird:
#include <GUIConstantsEx.au3>
#include <StaticConstants.au3>
_Sudoku_Display( "Titel des fensters", "000300800640800050875000001500070206000090000209080005400000769020008013007005000")
[/autoit] [autoit][/autoit] [autoit]Func _Sudoku_Display( $titel, $input)
$l = 30
$g = GUICreate( $titel, $l*9+10, $l*9+10+30)
For $loop2 = $l/2-1 To $l/2-1+$l*8 Step $l
For $loop = 5+1 To 5+1+$l*8 Step $l
If StringLeft( $input, 1) <> 0 Then
$label = StringLeft( $input, 1)
Else
$label = ""
EndIf
GUICtrlCreateLabel( $label, $loop, $loop2, $l-1, $l/2, $SS_Center)
$input = StringTrimLeft( $input, 1)
Next
Next
GUICtrlCreateGraphic( 5, 5, $l*9, $l*9)
;~ Striche Horizontal
GUICtrlSetGraphic( -1, $GUI_GR_COLOR, 0x999999)
For $loop=0 To $l*9 Step $l
If $loop = $l * 3 Or $loop = $l * 6 Or $loop = 0 Or $loop = $l * 9 Then GUICtrlSetGraphic( -1, $GUI_GR_COLOR, 0x000000)
GUICtrlSetGraphic( -1, $GUI_GR_MOVE, 0, $loop)
GUICtrlSetGraphic( -1, $GUI_GR_LINE, $l*9, $loop)
If $loop = $l * 3 Or $loop = $l * 6 Or $loop = 0 Or $loop = $l * 9 Then GUICtrlSetGraphic( -1, $GUI_GR_COLOR, 0x999999)
Next
;~ Striche Vertikal
For $loop=0 To $l*9 Step $l
If $loop = $l * 3 Or $loop = $l * 6 Or $loop = 0 Or $loop = $l * 9 Then GUICtrlSetGraphic( -1, $GUI_GR_COLOR, 0x000000)
GUICtrlSetGraphic( -1, $GUI_GR_MOVE, $loop, 0)
GUICtrlSetGraphic( -1, $GUI_GR_LINE, $loop, $l*9)
If $loop = $l * 3 Or $loop = $l * 6 Or $loop = 0 Or $loop = $l * 9 Then GUICtrlSetGraphic( -1, $GUI_GR_COLOR, 0x999999)
Next
$button = GUICtrlCreateButton( " OK ", $l*4.5-45, $l*9+10, 100, 25)
GUISetState()
$msg = GUIGetMsg()
While $msg <> $button
$msg = GUIGetMsg()
WEnd
EndFunc
die besonderheit ist die variable $l. dursch sie kann man die größe (fast) belibig verändern.
ich hoffe das die funktion das format auch richtig wiedergibt.
lg
Canyon
//EDIT: ich freu mich natürlich über feedback 
Da ich niemals alle Strategien umsetzen kann, veröffentliche ich hiermit mein Skript. Vielleicht gibts dem einen oder anderen einen Tipp.
Es ist inkl. GUI und so...
/Edit: Auf allgemeinen Wunsch Code entfernt.
@Canyon sieht gut aus werde ich vielleicht einbinden in mein Skript.
@L3viathan2142 Das hier ist ein Wettbewerb in dem es darum geht den schnellsten/effektivsten Algorithmus für eine Sudoku Lösung zu finden.
Ich habe auch schon angesprochen die Lösungen zu veröffentlichen, da ich das Gefühl hatte der µit - März verläuft sich im Sand was aber noch nicht wirklich von den Teilnehmern diskutiert wurde. EIne Lösung zu präsentieren ist meiner Meinung nach etwas zu früh und läuft damit in Gefahr ohne Absprache damit aufzuhören.
Ich fände es nicht gut jetzt schon über die Skripte zu diskutieren.
Nein, aufgeben und die Lösungen veröffentlichen finde ich nicht gut. Warum auch?
Einige haben doch bereits fertige Scripte (wenn ich das richtig interpretiere). Vielleicht könnten wir uns auf bestimmte Sudokus einigen, sodass man nicht alle Strategien umsetzen muss und somit die Effektivität des (bisherigen) Algorithmus erhöhen kann. Sprich: mehr in Richtung Speed zielen, als auf das lösen aller Sudokus.
ich bin jetzt kurzfristig krank geworden, sodass ich evtl. doch zeit für den solver habe.
mir ist der wetbewerb nicht soo wichtig. ihr könnt meinetwegen schon vergleichen, ich stell dann meine lösung einfach rein, wenn se fertig ist
Canyon
Oscar
Ja wegen mir. Da ich nichts mehr an meinem Skript ändern werde (ohne Hilfe) könnten wir uns darauf einigen.
Eine Mindestanzahl von vollständigen Lösungen sollten es aber schon sein.
Wie wäre es einen Tester zu schreiben, der nach einer bestimmten Zeit (2-3 Min) den laufenden String abbricht und zum Schluss die sagen wir mal 10 schnellsten als Durchschnitt nimmt?
Das Skript sollte selber erkennen ob es das Sudoku lösen kann.
Also wenn alle Technike einmal durch sind abbrechen.
Hi
Das Skript sollte selber erkennen ob es das Sudoku lösen kann.
Also wenn alle Technike einmal durch sind abbrechen.
Ja, so solls sein....es gibt auch "einfache" sudokus, die aber trotzdem relativ lange brauchen um gelöst zu werden. Bei Alina waren 2-3 dabei, die könnte man ja mit in die Testsuite aufnehmen.
Da ich niemals alle Strategien umsetzen kann.....
Geht mir auch so, ich habe die 4-5 "normalen" Strategien eines m.E. Durchschnittsspielers versucht umzusetzen.
Wie wäre es einen Tester zu schreiben, der nach einer bestimmten Zeit (2-3 Min) den laufenden String abbricht und zum Schluss die sagen wir mal 10 schnellsten als Durchschnitt nimmt?
Finde ich nicht gut, das ist wie der linpack-test bei den prozessoren, dann werden die solver auf die testsuite hinoptimiert^^
Man könnte sich ggf auf eine Handvoll Sudokus einigen, 60 haben wir ja schon vorliegen hier im Thread. Die "schwierigen" (d.h. ohne bruteforce nicht lösbaren) könnte man ja rausnehmen.
ciao
Andy
Mal sagen möchte, das alle Beispiele die ich gepostet habe von mir binnen 5 Minuten fertig waren.
Also nichts besonderes !
da bin ich ma gespannt 
wer macht eig alles noch mit?
Mal sagen möchte, das alle Beispiele die ich gepostet habe von mir binnen 5 Minuten fertig waren.
Also nichts besonderes !
Genau das meine ich...wenn 29 von deinen 30 Rätseln per "Strategie" in 10 Sekunden gelöst werden und ich für das restliche eine Rätsel per bruteforce dann die restlichen 5 Minuten brauche (oder ohne bruteforce garnicht lösen kann?!), wo ist denn da die "Fairness"?
Sicher könnte man sagen, im Endeffekt kommt das aufs gleiche raus, dann hat der "Stratege" Pech gehabt, Im anderen Fall läüfts genau umgekehrt: dann hat der Stratege mal "Glück" und löst alle 30 Rätsel in 10 Sekunden und der Bruteforcer ist weit abgeschlagen. Er (Sie ) findet zwar zu den lösbaren Sudokus die (oder sogar alle moglichen) Lösungen, das dauert aber entsprechend lange. Verzwickt!?
ciao
Andy
wer macht eig alles noch mit?
Ich bin noch dabei. Ich möchte nur gerne, dass ein Datum fixiert wird, dass die Sudokus fixiert werden, und dass die Testschnittstelle fixiert wird. Dann arbeite ich gezielt darauf hin, und dann weiß ich dann auch, ob ich mein Skript noch verbessern muss oder nicht.
Also ich bin mal dafür, daß wir den Abgabetermin auf 30. April festlegen.
Ein Sudokusolver sollte alle lösbaren Sudokus lösen können. Falls wir nur logisch lösbare verwenden, dann werden die Scripte natürlich rein auf die Testsuite optimiert und sind generell eigentlich wertlos.
Wenn wir andererseits nur schwere Sudokus vorgeben, dann haben die logischen Scripte das Nachsehen.
Deshalb mein Vorschlag:
Unsere Testsuite enthält 10 leichte, rein logisch lösbare Sudokus und 10 schwere, welche nur via Backtracking gelöst werden können.
Man muß somit eine gesunde Mischung aus Logik und Backtracking erstellen.
Und dann mehrere Bewertungen:
Wer löst die logischen Sudokus am schnellsten
Wer die Backtracking-Sudokus am schnellsten
und wer löst die meisten Sudokus
Somit können dann auch alle mitmachen, die z.b. nur rein logische Scripte erstellen wollen...
wenn ich Zeit hab, dann kann ich bis Anfang April eine Testsuite erstellen...
was haltet ihr davon?
E
Ich finde den Vorschlag von eukalyptus gut.
Damit wäre jeder Seite bedient. Wenn wir den Wettbewerb um einen Monat verlängern was schon ziemlich viel ist werde ich mir auch überlegen einen Solver der mit Logik löst zu schreiben.
Bin also dabei.
Hallo zusammen,
ein guter Vorschlag von eukalyptus!
Ich bin mittlerweile dabei, meinen Logik-basierten Solver mit backtracking "auszubauen", d.h. erst schnellstmöglich (per Strategie) viele Felder vollmachen, und erst wenn nichts mehr geht....bruteforce...
Allerdings funktioniert das nur bis zu einem gewissen Grad. Wenn sehr "schwierige" Sudokus gelöst werden müssen, dann bricht das Script irgendwann ohne Fehlermeldung ab. Scheint an der Rekursionstiefe zu hängen. Lt. Taskmanager ist aber noch reichlich Speicher vorhanden.
Während das Script im backtracking läuft, gebe ich die Zwischenergebnisse auf die Konsole aus. Gleichzeitig wird jeder Sprung in eine neue Rekursion mit einer 1-sekündigen messagebox angezeigt.Irgendwann mitten im Ablauf gibt es keine Messageboxen mehr, sondern nur noch Konsolenausgaben. Die letzte angezeigte msgbox ist riesengroß und hat Grafikfehler. Einige Sekunden später beendet sich das Script ohne Fehlermeldung.
Ich versuche natürlich, möglichst "sauber" aus den Rekursionen (und Funktionen) rauszukommen, d.h. keine Speicherleichen zu hinterlassen. Wahrscheinlich liegt der Hase aber in der per auskommentierten ;GUISetState(@SW_SHOW) "unsichtbaren" Grafikausgabe begraben.
Für die "sichtbare" Version des Lösungsvorgangs verwende ich eine GUI mit einer 9x9 Sudoku-Matrix, diese Matrix habe ich mit Buttons realisiert. Wenn jetzt einige Sudokus gelöst wurden, und man ein kleines Fensterchen (z.B. die msgbox) über die GUI bewegt, dann flackern die Buttons und zeigen alle bisher dort angezeigten Zahlen an 
, als ob 100 Buttons übereinanderliegen und jeder dieser Buttons schnell mal "ganz nach oben" wollte....irgendwie auch nicht ganz astrein 
Jedenfalls mache ich weiter, es werden noch 2 Strategien eingebaut, und dann versuche ich bissl speed rauszuholen. Mit Sicherheit gibts für 30 Programmzeilen einen einzigen Befehl 
ciao
Andy
hi all
also wie mir grad auffällt bin ich echt selten doof.
ich les 30.april und beeil mich dann übers we, um noch was lauffähiges hinzubringen (schon doof, wer den unterschied zwischen märz und apil nicht kennt ). esw läuft auch schon, aber es löst nur die gaaaaanz einfachen sudokus.
ich werd weiter dranbleiben und villeicht mal in ereweiterte gebiete vordringen.
soweit sogut
Canyon
PS @ Andy: meine gui ist mit labels und die kann auch mögliche zahlen anzeigen, die in das feld kommen könnten. wenn du den inhalt verändern willst, würde ich zu GuiCtrlSetData raten.
würde ich zu GuiCtrlSetData raten.
...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
