Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
SudokuSolver
MasterMax
myCSharp.de - Member

Avatar #avatar-2173.gif


Dabei seit:
Beiträge: 280
Herkunft: Deutschland

Themenstarter:

SudokuSolver

beantworten | zitieren | melden

Ich habe mir neulich einen Sudoku-Löse-Algorithmus ausgedacht. Vermutlich ist das Vorgehen ein Standardvorgehen und es gibt bessere, aber ich konnte bis jetzt jedes 9x9 Sudoku in weniger als 0.1sec lösen.

Idee des rekursiven Algorithmus:
  • Prüfe für jede nicht ausgefüllte Position, welche Zahlen möglich wären. Ist nur eine Zahl möglich, dann hat man eine Zahl gefunden, ist keine Zahl möglich, dann return false;
  • Prüfe, ob sich aus der Tatsache, dass jede Zahl in jeder Zeile, Spalte und in jedem Kästchen genau einmal vorkommen muss weitere Zahlen finden lassen
  • Wenn keine eindeutige Zahl mehr gefunden werden kann, dann suche die Position, wo die Anzahl an möglichen Zahlen für diese Position am kleinsten ist. Trage nach und nach jede mögliche Zahl ein und rufe den Algorithmus rekursiv auf.

Ich habe den Algorithmus getestet: er findet zuverlässig und sehr schnell eine Lösung, falls existent. Wenn das Sudoku unlösbar ist, dann wird dies auch schnell erkannt.

Der anfängliche Algorithmus (ohne zusätzliche Analyse von Zeilen und Spalten) hat ca. 3 min zum lösen eines schweren Sudokus gebraucht. Daher habe ich den 2. Tab (den Algo beim lösen beobachten) eingebaut, der jetzt überflüssig ist.

Anbei die Projektmappe incl. Code. Code habe ich eigentlich nur für mich und ohne Kommentare geschrieben. Da es aber so effizient läuft, möchte ich es doch veröffentlichen
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von MasterMax am .
Attachments
-=MasterMax=-
private Nachricht | Beiträge des Benutzers
MasterMax
myCSharp.de - Member

Avatar #avatar-2173.gif


Dabei seit:
Beiträge: 280
Herkunft: Deutschland

Themenstarter:

beantworten | zitieren | melden

Screenshot
Attachments
-=MasterMax=-
private Nachricht | Beiträge des Benutzers