Kleiner Tip zu Sudoku erbeten

  • Andreas: Ich merke gerade etwas. Es waren nicht die "hellen" Zahlen, die im Originalspiel vorgegeben waren (in meinen Screenshots grau hinterlegt, sondern es waren die dunklen Zahlen, die vorgegeben waren. Damit ist das Spiel mit recht vielen Werten hinterlegt und sieht so aus:

    Und ja, jetzt gibt es genau eine Lösung. Du mußt morgen also nicht mehr schauen :)

    Die maximale Rekursionstiefe dieses Spiels liegt bei 6. Das ist schon mal was für die grauen Zellen... :)

  • Ich würde sowas momentan nicht in Code bekommen!!!

    Dua Di ned owi ("Lass Dir keine grauen Haare wachsen") -- ich auch nicht.

    schlizbäda

  • Hallo schnasseldag,


    Andreas: Ich merke gerade etwas. Es waren nicht die "hellen" Zahlen, die im Originalspiel vorgegeben waren (in meinen Screenshots grau hinterlegt, sondern es waren die dunklen Zahlen, die vorgegeben waren. Damit ist das Spiel mit recht vielen Werten hinterlegt und sieht so aus:

    Und ja, jetzt gibt es genau eine Lösung. Du mußt morgen also nicht mehr schauen :)

    Die maximale Rekursionstiefe dieses Spiels liegt bei 6. Das ist schon mal was für die grauen Zellen... :)

    gut, dass Du jetzt damit herauskommst. Ich hätte sonst ernsthaft an Deinem Programmier- (sagt man das so?) Verstand zu zweifeln begonnen...

    Das Sudoku, das fred0815 da aufgetischt hatte, ist selbst mit Papier und Stift nicht so trivial einfach lösbar. Denn bei dieser Stufe ("single colouring") ist echt grübeln angesagt. Die Schritte davor sind nicht übermäßig schwer - und danach echt einfach.

    Vor einiger Zeit hatte ich auch ein kniffliges Sudoku gehabt. Es war aber auch nur deswegen knifflig, weil mir ein Übertragungsfehler passiert ist. Und plötzlich wurden sehr selten anzutreffende Strategien in Serie fällig.


    Ehrlich gesagt, finde ich es viel spannender, Sudokus zu erzeugen, die Mathematik, die dahintersteckt, und immer wieder eine Zahl zu entfernen oder eben eine seltenere Strategie anzuwenden und systematisch an bestimmten Stellen mehr als ein Feld zu entfernen... und nachzuweisen, dass es weiterhin nur eine Lösung besitzt.


    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

    Einmal editiert, zuletzt von Andreas (13. Dezember 2017 um 20:50)

  • Hallo Andreas,

    ja, zweifle ruhig an meinen Programmierverstand. Wenn Du wüßtest, wie häufig ich in meinem Leben durch 0 dividiert habe... ;)

    Einen vernünftigen Sudokugenerator zu schreiben ist tatsächlich komplizierter, als einen Solver, da der Generator vermutlich selbst einen Solver benötigt. Widmen wir uns zunächst mal dem Solver und schauen uns ein Sudoku an, welches in der oberen Ecke lediglich eine "1" besitzt und was der Solver dafür als erste Lösung findet.

    Die erste Zeile sieht schon irgendwie sehr "sortiert" aus - gell?! Versuchen wir's mal mit einer "2".

    Das ist jetzt nicht wirklich anders. Und bei einer "3" ergibt sich das folgende Bild:

    Kurzum, der Algorithmus bringt eine gewisse Symmetrie in die Lösung. Vergleicht man nun verschiedene Lösungsiterationen bei gleicher Ausgangsbesetzung, dann erkennt man wiederum die Arbeitsweise des Algorithmus. Man könnte nun so vorgehen, daß der (rekursive Backtracking-) Algorithmus nicht immer den gleichen Rekursionspfad wählt, sondern zufällig einen anderen. Das ist aber rechenintensiv und programmiertechnisch aufwändiger. Daher habe ich mich entschieden, einen anderen Weg zu gehen.

    Im vorliegenden Fall erkennt man leicht, daß man durch die Permutation einer einzelnen Ziffer 9 unterschiedliche Spiele der 1. Lösungsgeneration erzeugen könnte. Man könnte nun meinen, daß man ja nur jeweils eine zufällige "große" Zahl an generierten Lösungen wählen müßte, um ein durchaus "anderes" Sudoku daraus erzeugen zu können. Schauen wir uns also mal die 7239ste Lösung an, wenn der Startwert "3" beträgt.

    Das sieht in den oberen Reihen wiederum "ganz schön gleich" aus. Erst unten ändert sich was. Und die 1Millionste Lösung...

    Auch nicht wirklich überwältigend.

    Also ging ich einen anderen Weg und erstellte zur Generierung die komplette erste Zeile aus Zufallszahlen. Damit ergeben sich also 9! = 362880 unterschiedliche Speiel für die jeweils erste Lösung. Das sollte für die meisten Hobbysudokuer genügend unterschiedliche Spiele sein.

    Im nächsten Schritt erzeugt man das fertige Spiel mittels des Solvers. Soweit ist das noch alles überschaubar. Aber jetzt beginnt die Crux! Wie definiert man Level wie "einfach", "mittel" oder "schwierig"? Ist es die reine Anzahl fehlender Ziffern im Quadrat? Ist es die maximale Rekursionstiefe, die zur Lösung benötigt wird? Sind "4 x Rekursionstiefe 3" nun leichter als "1 x Rekusrionstiefe 5"? Die Rekursionstiefe erscheint mir schon irgendwie ein Maß für den Schwierigkeitsgrad zu sein, bestimmt ihn aber vermutlich nicht allein. Zudem kann der Lösungsweg darüber entscheiden, welche Rekursionstiefe notwendig ist. Das ist insofern ungeschickt, weil dann nicht nur der komplette Lösungsraum durchsucht werden müßte, sondern auch alle möglichen Arten wie man zur Lösung zu gelangen könnte. D.h. in jedem Backtrackingzug überlegt man sich nicht nur zunächst für die nächste Zelle einen möglichn Wert sondern generiert für alle übrigen Zellen jeweils alle möglichen Werte und startet dann wieder eine rekursive Tiefensuche. Das ist also auch nicht so das Gelbe vom Ei.

    Es gibt aber auch noch ein (vermeintlich) viel einfacheres Problem. Um ein Spiel zu erstellen, generieren wir uns also erst mal eine der 9! Lösungen und nehmen dann mal ein Kästchen weg. Aber welches? Das links oben? Und dann das rechts daneben? Und dann das daneben? Man merkt schon. Clever wegnehmen ist gar nicht so einfach, wenn's nicht monoton aussehen soll. Ok, also zufällig wegnehmen. Zufallszahlengenerator angeworfen und nimm weg das 1., nimm weg das 2. .., und dabei immer schön schauen, daß immer genau eine Lösung übrigbleibt. Irgendwann wird's schwierig, weil der Zufallszahlengenerator ein Kästchen wegnimmt, wleches auf einmal zu mehreren Lösungen führt. Also bleibt das drin. Nehmen wir also das nächste. Mist auch daneben gegriffen! Jetzt sind auf einmal sogar 10 Lösungen möglich! Nun steht man vor dem Dilemma, daß man schon 20 Kästchen weggenommen hat, aber irgenwie nicht weiterkommt, weil man besser das 3. Kästchen stehengelassen hätte. Den Fehler haben wir also schon ganz früh beim Wegnehmen gemacht, nun kommen wir nicht weiter, ohne dabei mehrdeutige Spiele zu erzeugen. Man erkennt leicht, daß das Wegnehmen ebenfalls über einen Backtracker erfolgen muß. Blöd nur, wenn der zufallsgesteuert ausgelegt wurde, um schöne "durchmischte" Spiele zu erzeugen. Das macht die Angelegenheit undeterministisch.

    Ich hatte mich daher darauf beschränkt, einfach Zahlen zu entfernen und auf die Eindeutigkeit der möglichen Lösungen zu verzichten. Nachdem ich auch keinen guten Ansatz zur Definition "leicht" mittel", "schwer" gefunden hatte, beließ ich es dabei und baute nur noch eine Analysemöglichkeit zur Ermittlung der Rekursionstiefe rein.

    Vielleicht gibt's im Forum ja einen, der das bis zum Ende durchgezogen hat?! Wäre schön etwas über andere Ansätze zu lernen :)

    Schöne Grüße

    schnasseldag

    Und was das alles mit dem Raspi zu tun hat - ähm, ja, stammel... sicherlich gibt's auch Sudokuprogramme für den Raspi?! OT Ende ;)

  • Hallo Schnasseldag,

    ich bin ja wieder hin und weg, wenn Du schreibst...

    Ich habe damals - schätzungsweise 2014 - bei meinem lausigsten Projekt überhaupt abends sehr viel im Hotel programmiert, um nicht völlig den Verstand zu verlieren. Ein bisschen ist wohl geblieben.

    Mein Sudoku-Generator geht einen anderen Weg. Das mit dem wegnehmen ist klar, und schauen, ob nach dem Wegnehmen die Anzahl der möglichen Lösungen 1 nicht übersteigt, ist auch klar.

    Was ich damals gemacht habe, besteht darin, die einzelnen Strategien in umgekehrter Richtung zu gehen. Dann besteht zwar die Möglichkeit, je nach der Systematik, wie der menschliche Sudoku-Kämpfer zu Werke geht, kompliziertere Strategien zu umgehen. Meistens bleibt aber etwas davon zurück oder führt zu anderen teilweise noch komplexeren Strategien. Oder die implizierte Strategie zeigt sich erst, nachdem andere Dinge gelöst wurden.

    Wenn das hier im Thread so weiter geht, dann packe ich den Code wohl noch mal aus.

    Die Einstufung als "leicht", "mittel" oder "schwer" definiere ich als Anzahl oder Verteilung komplexerer Strategien. Alles, was über

    • Hidden Singles
    • Naked Pairs/Triples/Quadruples...
    • Hidden Pairs/Triples/Quadruples...
    • Pointing Pairs
    • Box Line/Reduction

    hinausgeht, gehört für mich in die Kategorie "mittel" oder "schwer". Und wenn der Lösungsweg bereits in einem frühen Stadium die komplexeren Strategien erfordert, um überhaupt "Streichungen" der Kandidaten zu ermöglichen, dann geht es in Richtung "schwer" (insbesondere dann, wenn dort mehrere komplexere Strategien angewendet werden müssen.

    Und letztlich werden Strategien berichtet, von denen ich nicht wirklich behaupten kann, dass ich sie nachvollziehen könnte. Für mich gehen einige in Richtung "doch irgendwie geraten - kann so sein, muss es aber nicht".

    Interessant dabei ist auch, dass die Anzahl der vorgegebenen Felder nichts mit dem Schwierigkeitsgrad oder der Dauer der Lösung zu tun hat.


    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

    2 Mal editiert, zuletzt von Andreas (13. Dezember 2017 um 22:50)

  • Hi fred0815,

    Wieso ? Steht doch schon im Off-Topic-Bereich. :dau2::rofl:

    wieso das denn?

    Mein Sudoku-Programm läuft auch auf den bisherigen RaspberryPi-Modellen.

    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

  • Hallo noisefloor,

    den PROLOG-Quellcode für einen Sudoku-Solver habe ich auch schon gesehen. Der ist verblüffend überschaubar. Aber aus dem Code lernt man auch nichts.

    Du meinst den hier? (SWI-Prolog - das aktuell in Entwicklung befindliche Icon Tutorial Teil 32 enthält auch ein paar Seiten über diese Prolog-Variante...)

    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

    Einmal editiert, zuletzt von Andreas (14. Dezember 2017 um 20:06)

  • Hallo,

    nee, der Code war anders. Hatte auch nicht swiprolog genutzt sondern eine andere Implementierung. Vielleicht gprologg, bin mir aber nicht mehr sicher...

    Zitat


    Aber aus dem Code lernt man auch nichts.

    Das stimmt wohl. Die Logik-Programmierung ist komplett anders, als das, was man von "normalen" Programmiersprache so gewöhnt ist :)

    Gruß, noisefloor

  • Hallo noisefloor,

    der hier ist auch nicht schlecht...


    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

Jetzt mitmachen!

Du hast noch kein Benutzerkonto auf unserer Seite? Registriere dich kostenlos und nimm an unserer Community teil!