Unlösbare Sudoku

Es gibt 10 Antworten in diesem Thema. Der letzte Beitrag () ist von Niko Ortner.

    Unlösbare Sudoku

    Ich habe heute in zwei Ausgaben einer Zeitschrift je ein unlösbares Sudoku gefunden, bzw. gehe ich davon aus, dass sie unlösbar sind.

    Sudoku 1:

    Mein Lösungsprogramm ist bis hierher gekommen (graue Felder sind vorgegeben, grüne sind gelöst, die kleinen Zahlen in den Feldern oben zeigen die Kandidaten an):

    Der SudokuSolver von @Firedroide ist jedoch auf folgendes Ergebnis gekommen:

    Dabei wird das im Screenshot blau markierte Feld als erstes gelöst. Ich kann aber nicht nachvollziehen, wie das Programm da drauf kommt.

    Sudoku 2:

    Mein Lösungsprogramm findet hier garkeine weiteren Felder, da es keine Felder mit nur einem Kandidat gibt und es keine Kandidaten gibt, die nur in einem Feld einer Zeile/Spalte/3x3-Gruppe vorkommen können:

    Und auch der SudokuSolver kann keine weiteren Felder finden.

    Irgendwelche Ideen?

    Übrigens: Für mich ist ein Sudoku, das zwar aufgrund der vorgegebenen Felder nur eine einzige mögliche Kombination von nicht-vorgegebenen Feldern hat, das aber von den vorgegebenen Feldern durch die Sudoku-Regeln nicht direkt hergeleitet werden kann (d.h. man muss Kombinationen ausprobieren), kein gutes Sudoku. Vor allem, da man mit Stift und Papier nicht einfach Felder ausradieren und neu probieren kann.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils
    @exc-jdbi
    Ich stehe gerade etwas auf dem Schlauch.
    Deine Lösung für Sudoku 1 stimmt mit der überein, die Firedroides SudokuSolver gefunden hat, aber ich verstehe trotzdem nicht, wie diese Lösung zustande kommt.
    (Gibt es zwischen den beiden Rastern in vb-paradise.de/index.php/Attachment/40282-Loesung-png/ einen Unterschied?)

    Und wenn Sudoku 2 mehrere mögliche Lösungen hat, dann ist es nicht eindeutig lösbar.
    Also... macht es meiner Meinung nach nicht Sinn, das in einer Zeitschrift zu bringen.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    Niko Ortner schrieb:

    Und auch der SudokuSolver kann keine weiteren Felder finden.
    Im zweiten Sudoku sehe ich im Quadrat unten Mitte in der unteren Zeile außen die Kandidaten 3 und 8.

    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    @Niko Ortner: Ist zwar fast OT, aber: Ist Dein SudokuSolver vollautomatisiert? Du könntest ja noch die Möglichkeit einbauen, wenn das Programm nicht weiterkommt, dass man in die verbliebenden Felder selber Ziffern einträgt und dann das Programm weiterrechnet. Es wird ja dann anzeigen, ob die menschlichen Vermutungen zulässig sind oder nicht.
    Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von „VaporiZed“, mal wieder aus Grammatikgründen.

    Aufgrund spontaner Selbsteintrübung sind all meine Glaskugeln beim Hersteller. Lasst mich daher bitte nicht den Spekulatiusbackmodus wechseln.
    Mahlzeit

    Das ist mir auch gleich aufgefallan, dass beim ersten Sudoko 2 genau identische Lösungen brechnet werden.
    Kann mir das jetzt auf den ersten Blick nicht gerade erklären, da ich bei der Berechnung geschaut habe, dass er die Zeilen-, Spalten, und Blockkwerte jeweils nur einmal nehmen soll. Müsste mal wieder in den Code reinschauen.

    Edit:
    Mein Programm habe ich so aufgebaut, dass ich jedem leeren Feld die Möglichkeit gebe, eine Zahl zwischen 1 - 9 zu sein. Hierbei werden die Zeilen-, Spalten und Blockkombinationen jeweils immer kurz geprüft, so das gewährleistet ist, dass keine doppelten Werte vergeben werden.
    Das habe ich rekursiv gelöst. D.h. auf jeder rekursiven Ebene, vergibt er nach einem betimmten Schema einem leeren Feld eine noch vorhandene Zahl, und prüft ob die Zahl keine Regeln verletzt. Und dies macht er so lange, bis das Sudoku komplett gefüllt ist mit Zahlen.

    So im Nachhinein betrachtet. War ein interessante Projekt. Zu meinen Anfangszeiten in Vb.Net.


    Freundliche Grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „exc-jdbi“ ()

    @RodFromGermany
    Diese hier?:

    Wie kommst Du darauf?

    @VaporiZed
    Spricht eigentlich nichts dagegen, das auch zu automatisieren, oder?
    Aber wie ich bereits eingangs erwähnt habe: Ich finde es nicht sinnvoll, wenn man raten muss.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils
    @Niko Ortner Ja.
    Durch hingucken.
    Die 3 und die 8 sind auf der Mittelachse senkrecht und in den beiden oberen Zeilen der unteren 3er-Gruppe, da bleiben nur die genannten übrig.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Hallo,

    um bei deinem Sudoku 1 weiter zu kommen muss dein Programm die Strategie: "Naked Pair" beherschen. Es gibt noch viele weitere Sudokustrategien welche früher oder später nötig werden. Wenn du die perfekte Anleitung suchst, kann ich dir die Website sudokuwiki.org/sudoku.htm sehr empfehlen. Hier kannst du ein beliebiges Sudoku vorgeben und es anschließend Schritt für Schritt lösen lassen, wobei jeweils immer mit den einfachsten Strategien begonnen wird und nur sobald diese fehlschlägt eine "intelligentere"-Strategie genutzt wird.
    Du musst bei diesem Sudoku also noch lange nicht raten, nur dein Programm erweitern.
    MfG
    Aha, auf eine Erklärung wie die von Maximilian1989 habe ich gewartet. Jetzt verstehe ich nämlich, wie man darauf kommt. Das wusste ich vorher nicht, deshalb habe ich erst nicht verstanden, warum das, was RodFromGermany und exc-jdbi erwähnt haben, zur Lösung beiträgt.
    Danke also dafür. Ich werde versuchen, das ins Programm einzubauen.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils