Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Sudoku Rekursion


ghost_assassin - Mo 02.01.06 11:53
Titel: Sudoku Rekursion
hi@all

(mein erster beitrag hier) :lol:

das thema wurde zwar schon im forum
besprochen, hab mich auch erkundigt,
trotzdem bin ich nicht schlüssig geworden:

jeder kennt doch die sudoku rätsel (hoffe ich)
ich wollt nun einen löser bauen und bin auch
recht weit alleine gekommen:

mein prog besteht aus 2 stringgrids
einmal eingabe und einmal ausgabe

nun hab ich als erstes mal alle eingabe
felder in die ausgabe felder geschrieben

danach gibts eine funktion sinnvollezahlenerstellen
die für jedes leere feld aus den gegebenen
sudoku alle verbleibenden zahlenmöglichkeiten errechnet

das wird solange wiederholt, bis es keine weitere
eindeutige zuordnung mehr gibt

nun wollt ich per durchprobieren alle
restlichen möglichkeiten abdecken

folgendes problem: ich hab noch eine unbestimmte
anzahl leerer felder , die dazugehörigen möglichkeiten
und keinen genauen plan wies geht
das ganze hat was mit rekursion zu tun,
aber die kann ich nicht mehr(hatte das nurmal in der schule)

ich bräuchte mal einen guten denkanstoss
möglichst einfachen quellcode
delphi habsch noch nicht soo lange


alzaimar - Mo 02.01.06 12:03

Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
 
Function Rekursion (S : TAktuellerStand) : Boolean;
Begin
  If EndstellungEreicht (S) Then Return True
  K := ErstelleListeAllerMöglichenKandidaten;
  If Length (K) = 0 Then Return False  // Keine weiteren Züge möglich, Sackgasse
  For Each x in K Do begin
    Führe x in S aus
    If Rekursion (S) Then Return True; // Lösung gefunden 
    Nimm Zug x aus S zurück
    End
  Return False                         // Keine Lösung gefunden
End;

Der klassische Ansatz für Try and Error. Nacheinander werden alle Möglichkeiten durchprobiert. Jede (Zug)-Möglichkeit wird ausgeführt, und dann erfolgt der Rekursionsabstieg. Bei Misserfolg wird dann der Zug zurückgenommen und der nächste ausprobiert.

Erste Optimierungsmöglichkeit: Die Liste K der möglichen Züge wird so sortiert, das die Züge, die warscheinlicher zum Erfolg führen, zuerst ausprobiert werden.


ghost_assassin - Mo 02.01.06 16:18
user profile iconalzaimar hat folgendes geschrieben:


Quelltext 
1:
 
K := ErstelleListeAllerMöglichenKandidaten;



vielleicht hast du was falsch verstanden:
ich hab jetzt ein array in dem für bestimmte
koordinaten strings stehen
generierte zahlen, und eine von ihnen
passt in einer bestimmten möglichkeit...

die strings sind unterschiedlich lang
also bspw:

str1:123
str2:4567

nun soll er alle möglichkeiten ausspucken.
dabei wollt ich einfach nur die einzelnen teile
der strings abfragen: str1[a]+str2[b]
problem: ich hab ca. 50 strings
und müsste nun, um alle möglichkeiten zu generieren
50 for schleifen machen:

for a:=1 to length(str1) do
for b:=1 to length(str2) do

usw...

das wollte ich rekursiv machen...
und sobald er eine möglichkeit hat,
prüft er die und wenn sie eben stimmt
ausspucken und aufhören

wie ich dann die möglichkeiten durchlaufen lasse
weiß ich ungefähr, aber das generieren muss
rekursiv geschehen, ich hab nur keinen schimmer, wie??


alzaimar - Mo 02.01.06 16:56
user profile iconghost_assassin hat folgendes geschrieben:
user profile iconalzaimar hat folgendes geschrieben:


Quelltext 
1:
 
K := ErstelleListeAllerMöglichenKandidaten;



vielleicht hast du was falsch verstanden:

Nein, habe ich nicht.
Mein Pseudocode ist das Grundgerüst für ein allgemeingültiges Backtracking-Verfahren. ('Rekursion'). Die von Dir zitierte Routine würde eine Liste aller möglichen 'Züge' erstellen. Ob das Sudoku, Schach oder sonstwas ist, ist doch egal.
Bei Dir (Sudoku) wäre das eine Liste aller möglichen Tupel (Feld, Nr). Ob man sich erst eine Liste erstellt, und die dann durchprobiert, oder einfach das Spielfeld durchgeht, ist irrelevant. Ersters ist flexibler hinsichtlich der Optimierungsmöglichkeiten, letzters einfacher in der Implementierung.

Wenn Du dich allerdings noch nicht mit Rekursion auskennst, ist das natürlich blöd, denn Sudoku ist nicht gerade das Trivialste, um Rekursion zu lernen...

Rekursion ist eigentlich ganz einfach, aber es muss einmal *Klick* im Hirn gemacht haben, damit man es kapiert.


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!