Sudoku Löser programmieren - ohne raten

...komplette Frage anzeigen

2 Antworten

Ja, das geht. Ich habe ein Lösungsprogramm programmiert, allerdings noch in Turbo - Pascal. Das Prinzip beruht auf der trial and error Methode. Zeilenweise Feld für Feld (nur die freien) beginnend mit 1 prüfen, ob diese Zahl gesetzt werden kann, wenn nicht, weiter mit der nächsten Zahl. Dann zum nächsten Feld. Ist bis zur 9 keine Zahl setzbar, zurückspringen, die dort gesetzte Zahl um eins erhöhen und das Verfahren läuft wieder an. Handelt es sich nach dem Rücksprung um eine 9, noch eins zurückspringen usw. Die meisten Sudokus brauchen etwa 3000 bis 50000 Anläufe. Das ist zeitlich fast nichts. Ich habe eins gefunden, das braucht 240093 Anläufe. Sollte ein Sudoku allerdings einen Widerspruch in sich haben, gerät man in eine Endlosschleife. Wenn Du den Quelltext gebrauchen kannst, sage mir, wie ich ihn übermitteln könnte. Gruß Logo 67

Kann dein Programm auch ganz schwere Sudokus lösen ???

Also ich bin mit meinem Sudoku-Löser soweit, dass er 3 Methoden durchläuft, bis er absolut nichts mehr findet.

in der ersten Methode schaut er sich jedes Feld an und guckt wie viele möglichkeiten es gibt und wenn es nur eine ist, dann wird diese Zahl rein geschrieben. (also ich glaube so wie bei dir =)

die zweite Methode durchsucht alle reihen und spalten nach leeren feldern und schaut dann welche zahlen noch fehlen. Dann wird reihe nochmal durchsuch und es wird geschaut, welche Zahl überhaupt wo rein passen kann.

und die dritte methode schaut in welcher reihe, in welcher spalte und in welchem quadrat jede zahl vorkommen kann

und jede der Methoden findet zahlen, die von der anderen Methode nicht gefunden werden

ABEER die ganz schweren Sudokus kann es nicht lösen, aber bei denen komm ich selbst auch nicht mehr weiter

0

Hey Sponge,

Ich habe auch schonmal so ein Sudoku programmiert -

Es ist so:

bei leichten Sudokus gibt es welche die sogar mehrdeutig sind --> mindestens hier musst du raten, weil es ja nicht "EINE" richtige Lösung gibt.

Aber auch bei den Schweren kommst du ohne Raten nicht weiter, das ist der Ansatz den ich in meinem Programm verfolgt habe.

  • Alle vorhandenen Logiken ausnutzen zum berechnen
  • wenn keine Logik mehr vorhanden eine Zahl raten (nach geltenden Regeln natürlich)
  • Weiterrechnen
  • bis gelöst
  • oder bis Fehler auftritt
  • bei Fehler die letzte geratene Zahl durch eine Andere ersetzen

Sowas kann ganz schön rechenintensiv werden ; )

Freu dich über deine 4GHz

Viel Glück damit

P.S.: Das Programmiertechnisch interessante sind die verschachtelten Schleifen in variabler Tiefe - rein interessehalber: Welche Sprache benutzt du?

also ich habe bereits 3 Methoden geschrieben, die nach zahlen durchsuchen.

diese Methoden durchlaufe ich dann in einer Schleife, bis er in keiner Methode mehr etwas finden kann.

Und ich verwende dafür C#

0
@sponge9394

Ja, und dann geht es nach oben genanntem Muster weiter ; ) brauchst noch eine Methode zum "Zahlenraten" und eine "Steuerungsmethode" die beschließt wie es nach jedem Schleifendurchlauf weitergeht... Aber dein Weg ist richtig.

Es gäbe noch einen ganz anderen Ansatz das anzugehen:

Wenn du das Sudoku-Feld selber erstellst, kannst du es erst "vollständig" erstellen, dann beliebig viele Felder rausnehmen lassen und so den Schwierigkeitsgrad des Sudokus einstellen. Wenn du die rausgenommenen Zahlen speicherst kannst du es danach ohne Raten lösen ^^

0

Was möchtest Du wissen?