Sudoko - solved!

Posted by André Mühlnikel at May 2, 2009 10:14 p.m.

Es hat mich einfach nicht in Ruhe gelassen … also habe ich einen Solver für Sudokus gebaut. Da ich aber „Ausprobieren“ nicht für „logisch erschließen“ halte, habe ich demonstrativ diesen Lösungsweg weggelassen

Wers ausprobieren möchte, kann hier sehr schön Beispiele finden und die Lösungen nachvollziehen – einfach dazu am Ende des Skripts das Log-Level auf 5 setzen, dann erhält man die detaillierte Finde-Systematik ausgegeben. Hier muss ebenfalls (da ich zu faul und unwissend in Bezug auf Python bin) der Dateiname der Input-Datei jeweils angepasst werden!

Ein paar Notizen zur Vorgehensweise:

• Quasi-Singles sind Werte, die innerhalb eines Blockes (also 3×3-Feldes) in nur einer Zeile oder Spalte zu finden sind, und somit in der restlichen Zeile bzw. Spalte ausgeschlossen werden können.
• Unknown Singles sind solche Felder, die nach Ausschluss aller durch Zeile, Spalte und Block wegfallenden Optionen nur noch einen möglichen Wert enthalten. Wurden sie allerdings auf diese Weise einmal erkannt, werden sie danach zu „Known Singles“, damit sie nicht immer wieder aufs neue verarbeitet werden und das Programm irgendwann terminieren kann.
• Single Options sind diejenigen Felder, die, obwohl sie selbst noch mehr als einen möglichen Wert zur Verfügung haben, innerhalb ihres Blocks oder ihrer Zeile/Spalte das einzige Vorkommen eines dieser Werte sind und somit zwingend auf diesen Wert festzulegen sind.

Alles klar? Fragen beantworte ich gerne (auch in den Kommentaren)!

No comments | Defined tags for this entry: programming, python, scripting, fun, Sudoku

Comments

No comments