µit - März

So hab jetzt mein Script mal überarbeitet und es ist viel schneller, als vorher
jedoch löse ich z.z. nichtmal die Hälfte der Sudokus

Aber es ist ja noch etwas Zeit

Mein aktueller Benchmark:

Ich hoffe, ich bekomme auch Logisch Nr.8 noch hin, ohne viel an Speed einzubüßen!

Und bei den anderen muß ich mir sowieso noch was überlegen...

lgE

Hi

Zwischenbericht:
Das schon angesprochene Grmblfxx#!" - Sudoku habe ich durch ein anderes ersetzt, um den Backtracktest durchlaufen zu lassen. Langsam komme ich mir bescheuert vor....
Hier gibts eine Datei mit über 40tausend 17er Sudokus, viel Spass damit^^

2,5 ghz amd 4850

Ich hab auch Probleme mit dem 5ten BT-Sudoku!
Kannst du deins bitte posten, dann tausch ich es beim Benchmark aus.

lgE

EDIT: Ich hab jetzt einfach das 5 (4 in der Ini) gelöscht und hinten ein leeres angehängt.
Es ist ja auch interessant, wie lange ein BT hierfür braucht...

Neue INI:

Mein aktueller Benchmark:

lgE

Leute, ich scheide aus xD
Fühl mich hier schon ganz, ganz klein

Brauche nur für die Backtracks über ne Viertelstunde...
Ich glaub' ich hab' den Sinn von Backtrack nicht verstanden - bei mir ist das einfach Bruteforce ? :pinch:

BackTrack:

Man probiert für jedes Feld jede mögliche Zahl und überprüft, ob diese Zahl den Regeln entspricht (darf nur 1 mal in einer Reihe vorkommen usw.)
Wenn dies nicht der Fall ist, dann 1 Schritt zurück.
Diese Funktion sollte (muß) rekursiv sein.
Wenn man mit Hilfe der logischen Algo´s die Anzahl der Möglichkeiten schon reduziert hat, dann ist auch der BT-Algo schneller...

Zur Geschwindigkeit allgemein: Man hat doch für jedes Feld eine Variable, welche die noch möglichen Zahlen beinhaltet.
Dazu kann man einen String oder ein Array nehmen; Oder auch eine andere Möglichkeit, wie ich sie verwende (wird aber noch nicht verraten ;))
Hier kann man viel Geschwindigkeit rausholen.

lgE

Zitat

Leute, ich scheide aus xD
Fühl mich hier schon ganz, ganz klein

Limette, du sprichst mir aus der Seele^^
Ich habe mich auch zu einem Wettrennen zu "wer hat den Größten" hinreissen lassen...shame on me.....
Viel wichtiger sollte doch sein, gemeinsam an einem Projekt zu arbeiten bzw zu diskutieren und zum guten Schluss hat jeder noch etwas gelernt.
limette, sieh es einfach so, dabeisein ist alles! Frage, und dir wird geantwortet...

Aber zum Thema:

Zitat

Brauche nur für die Backtracks über ne Viertelstunde...
Ich glaub' ich hab' den Sinn von Backtrack nicht verstanden - bei mir ist das einfach Bruteforce ?

Ja, genau! Die Vorgehensweise solltest du begriffen haben, ansonsten würde dein Rechner nicht ne Viertelstunde, sondern nen Viertelmonat brauchen^^.

Ich geh mal ins OffTopic.Ganz, ganz "früher" gabs nur "arschlahme" Rechner, wenn eine Software also trotzdem viele Daten verarbeiten musste, dann war erste Priorität, auch ein schnelles Programm zu schreiben. Ein "langsames" Programm war auch auf Rechnern der neuesten Generation langsam. Wer mal Programme nach der Anzahl der Takte der einzelnen Prozessorbefehle optimieren musste, vergisst das nicht mehr .....und will sowas auch nie mehr machen
Heutzutage kann jeder für kleines Geld eine Maschine kaufen, die es vor 10-15 Jahren lockerst unter die TOP500 der Supercomputer geschafft hätte. Damit ist auch "langsame" Software plötzlich schnell

limette, sieh es mal so, wenn wir diese Aufgabenstellung in einer "schnellen" Programmiersprache machen würden, dann hätte dein Algorithmus den kompletten Benchmark in (ich phantasiere jetzt mal) 460 Millisekunden erledigt und der "Gewinnercode" hätte halt nur 120 Millisekunden gebraucht. Und jetzt ganz ehrlich und aufrichtig, ob man eine Aufgabe nun 340ms früher oder später erledigt hat, ist idr völlig Schnurz.
Wenn es dich trotzdem fuchst (hehe ), dann lass dir helfen. Schön ist jedenfalls, dass du mitmachst.

Ich bin mittlerweile so weit, dass ich nur noch alternative Ideen zur Beschleunigung von "speziellen" Lösungen verfolge. Mir fehlt erstens das AutoIt-Knowhow, und auch von Programmierung bzw Informatik(z.B. StringRegExp ) habe ich keine bis nur wenig Ahnung. Andererseits habe ich in den Weiten des Inet mittlerweile viel zuviel zur Problematik vom Lösen von Sudokus u.Ä. gelesen.
Normalerweise kennt man sein Problem vorher, kann es analysieren und dementsprechende Software schreiben. Ob aber ein Sudoku von deinem Programm schnell oder langsam gelöst wird, dass weisst du erst nachher! Auch ob es günstiger ist logisch zu lösen oder mit dem Backtracker, weiss man erst wenn man jede der Varianten probiert hat....
Das "Backtracking" ist in ca 80 Zeilen Code völlig erledigt, der Rest von meinen 1500 Spaghetti-Zeilen (jaja, Kommentare sind auch dabei ) verteilt sich auf die einfachen logischen Lösungsansätze und bissl drumherum......

Aber als Tip, mit der Kombination Logische Lösung, Zufallsschuss und Backtracking lassen sich mit bissl "Glück" auch die härtesten Sudokus sehr schnell knacken.

HAUT REIN!!!!

Andy

Hehe
Kleiner Roman

Hm ja, mein Backtrack ist schon diese Kombination aus Ausprobieren und der 1. logischen Methode, dem Ausstreichen
der Möglichkeiten...

Zitat

Die Vorgehensweise solltest du begriffen haben, ansonsten würde dein Rechner nicht ne Viertelstunde, sondern nen Viertelmonat brauchen^^.

Hab aus Spaß mal ein reines Bruteforce geschrieben, also durchrattern aller Möglichkeiten..
Wobei die erste die wäre, dass jedes Feld die "1" besitzt, also halt richtiges Ausprobieren mit Check nach Einsetzen des letzten Feldes
Naja, meine Programme sind nicht die schnellsten, aber bei 1000 ausprobierten Lösungen pro Sekunde würde das immerhin ...
9^(9^2) / 1000 = 9^81 / 1000 = 1.9662705 × 10^74 Sekunden dauern.
Sagt mal, entweder ich bin irgendwie schlecht in Mathe, oder das sind tatsächlich 6.23073524 × 10^66 Jahre xD

Zitat

Wer mal Programme nach der Anzahl der Takte der einzelnen Prozessorbefehle optimieren musste, vergisst das nicht mehr

Woha. Das ist natürlich hart

Zitat

wenn wir diese Aufgabenstellung in einer "schnellen" Programmiersprache machen würden

Dann könnte man aber auch die eigentliche Qualität des Algos nicht mehr so gut bestimmen
Wobei AutoIt wirklich nicht unbedingt die schnellste ist, wie ich bereits feststellen musste, als ich mal das
Sieb des Eratosthenes (wem das nichts sagt: suche nach Primzahlen) umgesetzt habe:
In AutoIt sowie in C++ ...
Kein Vergleich.

Zitat

Und jetzt ganz ehrlich und aufrichtig, ob man eine Aufgabe nun 340ms früher oder später erledigt hat, ist idr völlig Schnurz.

Jau. Aber ob es nun 15 min oder 15 sec dauert, das ist dann doch relevant ...

@euka:
Freaks
Ich werde mir hinterher auf jeden Fall eure Skripte reinziehen,- wenn ich da nichts lernen kann, ..... =)

Zitat

also halt richtiges Ausprobieren mit Check nach Einsetzen des letzten Feldes

das ist natürlich auch bissl arg^^
Wenn du aber beim Setzen des Feldes erstmal nachschaust, ob diese Zahl in Zeile, Spalte, 9erKasten enthalten ist, dann reduzieren sich die Möglichkeiten gewaltig. Wie lange brauchst du denn, um ein völlig leeres Sudoku zu füllen?

Ich wünschte, meine Ergebnisse wären am Anfang so gut gewesen wie deine....

zzt. lasse ich die schon hier angesprochenen 17er Sudokus in 1000er-Packs durchlaufen. Hauptsächlich, um den Backtrack noch zu optimieren, aber da stecke ich grade in einem Dilemma.
Manchmal spart ja eine einzige durch Logik entfernte Ziffer einige Minuten an Backtrackzeit. Gelöst bekomme ich jetzt alle Sudokus, aber Backtracken alleine ist m.E. bei "ungünstigen" Puzzles viel zu langsam.

Bin jedenfalls gespannt wie ein Flitzebogen auf die Scripte der AutoIt-Profis....

Zitat

Wenn du aber beim Setzen des Feldes erstmal nachschaust, ob diese Zahl in Zeile, Spalte, 9erKasten enthalten ist, dann reduzieren sich die Möglichkeiten gewaltig. Wie lange brauchst du denn, um ein völlig leeres Sudoku zu füllen?

Naja, das wär dann ja schon fast 'n vernünftiges Backtrack Wollte damit ja das ganz extreme ausprobieren

Für ein leeres Sudoku brauche ich... viel zu lange..
Bin aber bisher auch nicht dazu gekommen, das zu optimieren. Mal sehen, mach die Funktion vielleicht nochmal ganz neu..
Denn rund 50 sec sind nicht schnell.. x)

Zitat

Ich verstehe das so, das jeder seine Algorithmen implementiert und die Skripte auf alle 20 Sudokus losgelassen werden, also keine Trennung logische Sudokus nur mit logischen Strategien und BT-Sudokus mit Backtrack.

Ich würde sogar noch weiter gehen und vorschlagen, dass jeder Interessierte eine Handvoll "seiner" Sudokus zur Verfügung stellt, damit aus allen gesammelten Sudokus eine "Suite" zusammengestellt werden kann. Das könnten ruhig hundert Sudokus oder auch mehr werden!
Logisch lösbare könnte man noch unterscheiden in "einfache" und "schwere", aber ob das unbedingt sein muss sei dahingestellt. Ich wage zu behaupten, daß bei diesen Sudokus selbst ein "langsamer" logischer Lösungsalgorithmus immer schneller sein wird wie ein Backtracker.

Daß es, je nach verwendetem Backtrack-Algorithmus, günstige und weniger günstige Sudokus gibt, wird jedem klar sein. Ich habe beim Durchrechnen von den schon von mir angesprochenen ca 36000 Sudokus in der Liste eine Handvoll gefunden, die meinem Algorithmus garnicht schmecken ^^.Landet so einer zufällig in der Auswahlliste, dann hab ich verschi******......
Andererseits, ist die Liste vorher bekannt, dann besteht natürlich die Gefahr, seinen Algorithmus darauf zu "optimieren". Dieses Spielchen gibts ja, seit gebenchmarkt wird.

ciao
Andy

Dafür, daß es sich um den März-Wettbewerb handelt, einigen wir uns doch ziemlich bald

Wer macht eigentlich die Auswertung?
Dieser Jemand soll dann Sudokus für die Analyse auswählen.
Und auch entscheiden, nach welchen Kriterien bewertet werden soll.

Ich denke, es wird keinen "besten" Solver geben, sondern mehrere...
Den Solver mit der schönsten Strategie (unabhängig von der Geschwindigkeit)
Den Solver, der im Durchschnitt am schnellsten löst
Den programmiertechnisch schnellsten Solver
Den schönsten, reinen Backtracker
usw...

Und daraus kombinieren wir dann die besten Elemente zu einem gescheiten Solver.

lgE

...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 lassen

Sudokus: 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           :  5206

Die 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

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)

Zitat

Durchschnitt: 83.2767293049815

beeindruckend, aber ich befürchte, da geht noch was^^

Hab mal nachgelegt^^

Sudoku 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