[C/C#/C++] Sudoku Solver v1.1 - Neuer Algorithmus! *update*

Dieses Thema im Forum "Projekte / Codes" wurde erstellt von Pac_-_man, 13. September 2007 .

  1. 13. September 2007
    Zuletzt von einem Moderator bearbeitet: 14. April 2017
    Sudoku Solver v1.1 - Neuer Algorithmus! *update*

    Hallo!

    Habe mich mal rangesetzt und nen Algorithmus für Sudokus programmiert. Er kann leider (noch) nicht die ganz schweren lösen, aber für leichte bis mittlere funktioniert er ganz gut (zumindest bei den Sudokus, die ich ausprobiert habe). Könnt ihn ja mal ausprobieren und vlt. was dazu schreiben... Bei Interesse würd ich den Code auch weitergeben... Die grafische Oberläche ist mit dem CBuilder von Borland gemacht worden.
    Ich denke mal ich werde noch versuchen ihn etwas auszubessern, deshalb hab ich mal einfach v1.0 hintendrangehängt...

    Soooo habs jetzt endlich richtig fertig. Hab nen neuen Algorithmus geschrieben der eigentlich so gut wie alle Sudokus lösen können müsste. Habs einmal upgedated...

    Download v1.0: Sudoku Solver v1.0

    Download v1.1: Sudoku Solver v1.1

    Screenshot:

    Bild=down!

    MFG
    Pacman
     
  2. 13. September 2007
    AW: Sudoku Solver - Eigener Algorithmus

    hab zuerst ein "schweres" gestestet da es gerade aufgeschlagen war: er hat die linke seite ausgefüllt (komplett falsch) und danahc nichts mehr

    bei den leichten klappt bis jetzt alles einwandfrei
     
  3. 14. September 2007
    AW: Sudoku Solver - Eigener Algorithmus

    Ja, also er kann bis jetzt nur leichte bis mittlere... Aber das er Fehler beim schweren gemacht hat, hatte ich noch nicht... kann er eigentlich auch garnicht... meistens hat dann der benutzer was falsch eingegeben...
    Bin gerade dabei den Algorithmus noch etwas zu erweitern... mir ist da noch was eingefallen... werd das dann mal updaten...

    MFG
    Pacman
     
  4. 14. September 2007
    AW: Sudoku Solver - Eigener Algorithmus

    Vllt hatte das Sudoku auch nur mehrere Lösungen...
    Aber ansonsten schon ganz nice. Wenn er jetz noch schwerere könnte wärs noch cooler^^
    Was ich auch toll finden würde wäre, wenn er Sudokus direkt aus einer Datei einlesen kann. Kann man ja so machen, dass anstatt der leeren Stelle eine 0 steht...
     
  5. 18. September 2007
    AW: Sudoku Solver - Eigener Algorithmus

    eigentlich ist es relativ einfach so was zu programmieren

    ich hatte das so gelöst
    das er das erste leere feld ermittelt
    dort die erste möglichezahl einsetzt
    dan zum nächsten feld wieter geht und so weiter und so fort

    stößt er auf ein feld für das es keine gültige zahl gibt geht er ein feld zurück und pobiert dort eine andere zahl aus
    und so lies sich recht schnell jedes sudoku lösen

    für die nicht vorhandene formatierung kan ich nichts
    solltest du weitere fragen haben sag bescheid

    wie erstellst du eigentlich momentan deine sudokus?

    Spoiler
    public boolean loesen() //lösst ein vorgegebenes sudoku in kürzester zeit
    {
    if (this.kontrollieren(true) == false)
    {
    if (this.durchzaehlen() != 81) //sollten noch nicht alle felder ausgefüllt sein
    {
    for (int y = 0;y < this.felder.length; y++) // erhöht die zeile sobald alle spalten in einer
    { // zeile durchlaufen sind
    for (int x = 0;x < this.felder.length; x++) // erhöht die spalten nummer um 1
    {
    if (this.staticFelder[x][y] == false) // kontrolliert ob das feld verändert werden darf
    { // ist das feld vor dem lösen belegt darf es nicht geändert werden
    int moeglichkeiten[] = this.moeglichkeitenErmitteln(x, y); // möglichkeiten ermitteln
    if (moeglichkeiten.length == 0) //keine möglichkeiten vorhanden
    {
    this.felder[x][y] = 0; // das aktuelle feld wieder auf 0 setzen
    if (x <= 0){y -= 1;x = 8;} // prüfen ob am anfang der zeile angelangt wen ja wird im letzten feld der voherigen zeile weiter gemacht
    else {x -= 1;} //andernfalls ein feld zurück gehen
    while(this.staticFelder[x][y] == true)// solange das jetzt aktuelle feld statisch ist
    {
    if (x <= 0){y -= 1;x = 8;} // prüfen ob am anfang der zeile angelangt wen ja wird im letzten feld der voherigen zeile weiter gemacht
    else {x -= 1;} //andernfalls ein feld zurück gehen
    }
    if (x <= 0){y -= 1;x = 8;} // prüfen ob am anfang der zeile angelangt wen ja wird im letzten feld der voherigen zeile weiter gemacht
    else {x -= 1;} //andernfalls ein feld zurück gehen
    }
    else{this.felder[x][y] = moeglichkeiten[0];} //möglichkeit 1 im array ins feld setzen

    }
    }
    }
    }
    }
    return false;
    }
     
  6. 18. September 2007
    AW: Sudoku Solver - Eigener Algorithmus

    Uuups -.- schon wieder ausversehen Bedankt naja

    also hab auch mal ein schweres Probiert un muss sagen ist nicht ganz so falsch...aber bei den einfachen ist es einwandfrei gelaufen bw ist raus
     
  7. 19. September 2007
    AW: Sudoku Solver - Eigener Algorithmus

    Ich würde mich wirklich für den Source interessieren, denn so wie ich das bis jetzt verstehe ist deiner wie der von Wikipedia(Klick!)... Hat die gleichen Probleme etc.

    mfg r90
     
  8. 20. September 2007
    AW: Sudoku Solver - Eigener Algorithmus

    keine Ahnung wie der von Wikipedia funktioniert.... Kann dir den Source gerne schicken wenn du willst. Ist nicht sehr viel, da er einfach nur nach den Regeln prueft. Das Programm sucht das erste leere Feld und prueft dann die Moeglichkeiten dieses Feldes. Wenn es nur eine Moegliche Loesung gibt, dann wird sie eingetragen. Das ganze laeuft solange, bis er keine neuen Loesungen mehr findet...

    Bin aber gerade dabei einen Algorithmus fuer wirklich jedes Sudoku zu schreiben. Und zwar soll es eine Art Backtracking Algorithmus werden. Ich glaube das ist auch so ähnlich wie Micro86 das oben gepostet hat. Aber ich versuch das dann per Rekursion... Mal schauen ob ich das hinbekomme... Ist eigentlich nicht so wild, aber manchmal kommt man einfach nicht weiter...

    MFG
    Pacman
     
  9. 21. September 2007
    AW: Sudoku Solver - Eigener Algorithmus

    ich habe die erstellung des sudokus rekursiv gestalltet
    is wirklich nicht so die große sache

    das war auch eins meiner ersten sachen in java und als komplett oop das erste
    aber es gibt da sicher noch einiges an verbesserungen und optimierungen
     
  10. 2. Oktober 2007
    AW: Sudoku Solver v1.1 - Neuer Algorithmus! *update*

    hi!

    jetzt hab ichs endlich soweit, das er auch die schweren Sudokus hinbekommt, die nicht mehr auf analytischen weg zu lösen sind...

    MFG
    Pacman
     
  11. 2. Oktober 2007
    Zuletzt von einem Moderator bearbeitet: 15. April 2017
    AW: Sudoku Solver v1.1 - Neuer Algorithmus! *update*

    Habs grade mit einem schweren Soduku aus dem Internet probiert und es hat funktioniert :]

    Trotzdem stören mich zwei Sachen:

    1. ich fände es gut, wenn die Linien, die das Feld in die einzelnen Abschnitte unterteilen, fett wären (siehe Screenshot)
    2. wenn man mit der Maus auf eine Zelle klickt und anschließend auf der Tastatur auf eine Zahl drückt, wird die Zahl nicht eingetragen. Man muss sie erst oben in das weiße Kästchen eingeben und auf "eintragen" klicken. Wäre schön, wenn man die Zahlen direkt eingeben könnte, ohne jedesmal auf "eintragen" klicken zu müssen ^^


    Außerdem ist mir noch aufgefallen, dass die Eingabe von Buchstaben oder mehreren Zahlen in eine Zelle nicht verhindert wird. Könnte man evtl. noch verbessern^^


    Ansonsten: gute Arbeit :klatsch:



    Screenshot

    sudokusolverme3.jpg
    {img-src: //img218.imageshack.us/img218/6750/sudokusolverme3.jpg}
     
  12. 2. Oktober 2007
    AW: Sudoku Solver v1.1 - Neuer Algorithmus! *update*

    was mir noch auffällt:
    -man kann zahlen eintragen, die größer als 9 sind
    - man kann mehere zellen nich gleichzeitig löschen
    - es kommt keine fehlermeldung wenn etwas falsch ist bzw wenn eine zahl mehrmal in einer einheit ist


    kann man auch iwie sodokus reinkopieren?
     
  13. 5. Oktober 2007
    AW: Sudoku Solver v1.1 - Neuer Algorithmus! *update*

    hi!

    Ja stimmt... mir ging es erstmal nur um den algorithmus selbst. Man kann sicher noch einiges verbessern. ein problem ist z.B. auch noch, dass wenn ein Sudoku nicht lösbar ist, er in einer Endlosschleife festhängt. Das müsste man auch noch abfangen...

    Zu den durchgezogenen Linien: Ich hab die GUI mit Borland gemacht und weiß ehrlichgesagt nicht, wie man bei einer sogenannten StringGrid die Linien-Stärke verändern kann... wenns jemand weiß, bitte melden!

    @Gibbon: Man kann man die Zahlen über den Nummernblock eintragen. Blöd ist nur wenn man nen Laptop hat oder so. Ich weiß aber auch nicht wie man das Zahlenfeld über den Buchstaben abfragen kann. Irgendwie hab ich da keine virtuellen Keys für gefunden... Wenn das jemand weiß, bitte auch melden!

    Werd mich jetzt nochmal dran setzen und die GUI überarbeiten...
     
  14. 5. Oktober 2007
    AW: Sudoku Solver v1.1 - Neuer Algorithmus! *update*

    Hey Pacman,

    cooles Tool. Der Algorithmus würd mich mal interessieren. Wie macht man denn sowas?

    Als kleinen Verbesserungsvorschlag möchte ich anmerken, dass eine Fortschrittsanzeige schön wär. Hatte eben ein Rätsel, bei dem Dein Tool nahezu 100% Prozessorlast verursacht hat (bis ich den Prozess gekillt hab).

    Echt ne Spitzenarbeit, gefällt mir gut.

    BG MaxDev
     
  15. 5. Oktober 2007
    AW: Sudoku Solver v1.1 - Neuer Algorithmus! *update*

    Hiho,

    dein Programm hat noch einen kleinen Schönheitsfehler.
    Du solltest eine Überprüfung einbauen, die eine Warnung an den Benutzer ausgibt, wenn der Benutzer ausversehen 2 gleiche Zahlen in eine Reihe stellt. Dein Algorithmus rechnet sich danach nämlich tot


    MfG
    Sancezz
     
  16. 5. Oktober 2007
    AW: Sudoku Solver v1.1 - Neuer Algorithmus! *update*

    für alle diejenigen die der sourcecode interessiert hab ich hier meinen sudokusolver aus dem studium hervorgekramt. gelöst wirds mittels backtrackingverfahren.

    Code:
    /*this function tries to place a value to row,clm*/
    bool placeVal(int row, int clm)
    {
     int val; 
     if (clm == 9)
     {
     row++; /*jump into next row*/
     clm = 0; /*start in column 0*/
     }/*if*/
     if (row == 9)/*Solution found -> return true*/
     return true; 
     if (gSudoku[row][clm] == 0)
     {
     for (val = 1; val <= 9; val++)
     {
     if (ValFits(row,clm,val)) 
     {
     gSudoku[row][clm] = val; /*setting this value to row,clm is possible*/
     if (placeVal(row,clm+1)) /*call placeVal with next column, if row could be set to 9 return true*/
     return true; 
     }/*if*/
     }/*for*/
     gSudoku[row][clm] = 0; /*no val could be set, step back*/
     }/*if*/
     else 
     if (placeVal(row,clm+1))
     return true; /*if row could be set to 9, return true*/ 
     return false; /*not possible to set a value, return with false*/ 
    }/*placeVal*/
    
    /*this function checks if its possible to place the val to row, clm*/
    bool ValFits(int row, int clm, int val)
    {
     int runClm, runRow,runQrow, runQclm;
     /*check vertical*/
     for (runRow = 0; runRow < 9; runRow++)
     if (gSudoku[runRow][clm] == val)
     return false;
     
     /*check horizontal*/
     for (runClm = 0; runClm < 9; runClm++)
     if (gSudoku[row][runClm] == val)
     return false;
     
     /*check 3x3 field*/
     while ((row % 3) != 0) /*step back to row 0, 3 or 6*/
     row--;
     
     while ((clm % 3) != 0) /*step back to column 0, 3 or 6*/ 
     clm--;
     
     for (runQrow = row; runQrow <= row+2; runQrow++)
     for (runQclm = clm; runQclm <= clm+2; runQclm++)
     if (gSudoku[runQrow][runQclm] == val)
     return false; 
     
     return true;/*value can be set, return true*/ 
    }/*ValFits*/
    
    zum programm selber: sieht sehr nice aus, n hartes stück arbeit bis die sudokus wirklich so gelöst werden wie sie sollen ...
     
  17. 5. Oktober 2007
    AW: Sudoku Solver v1.1 - Neuer Algorithmus! *update*

    @Virtuell Keys(0..9):
    48..57, 96..105 (NUM)

    @StringGrid:
    Einfach bei dem Zeichenevent "OnDrawCell" mit "Canvas" die Entsprechende
    Linie "dicker" Zeichnen.

    @Topic:
    Kein schlechtes Programm, jedoch ehrlich gesagt ich kann es nicht wirklich gebrauchen
    und wenn dann vielleicht zum Lösen von Sudokus in Zeitschriften bei denen man Preise
    gewinnen kann ^^

    Mfg Rushh0ur
     
  18. 5. Oktober 2007
    AW: Sudoku Solver v1.1 - Neuer Algorithmus! *update*

    ahh! vielen dank @rushhour!

    @naca7: ganz genau, ich hab es per Backtracking Algorithmus gemacht... Und sowas macht man aufm Studium auch? Ich würde gerne technische Informatik studieren und da gibts dann auch Module mit Algorithmik. Find sowas hammer interessant...

    Bei Interesse würde ich sogar mein gesamtes Projekt uppen... War echt n hartes Stück Arbeit bis alles so funktionierte wie es soll, aber wenn mans dann fertig hat und sich das nochmal anschaut, ist es dann doch nicht sooo besonders, dass man den source nicht vlt auch weitergeben würde...

    Bei Interesse ->PN

    MFG
    Pacman
     
  19. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.