hi@all

(mein erster beitrag hier)

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

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.

alzaimar hat folgendes geschrieben:

markieren 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??

ghost_assassin hat folgendes geschrieben:

alzaimar hat folgendes geschrieben: markieren 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.