Sudoku Rekursiv

[qui]

Unlängst habe ich für einen Freund einige Beispielprogramme zur rekursiven Programmierung geschrieben - unter anderem einen Sudoku-Löser - und da schon einige Programme diesem Brettspiel im PureBoard gepostet wurden, stelle ich ihn zur Verfügung.
Bitte dreht beim Ausprobieren den Debugger ab, da sonst die Laufzeit enorm wird. Auf meinem Athlon XP komme ich so auf ungefähr 2000 Checks pro Sekunde und reale Beispiele brauchen etwa im Bereich von einer halben Million Checks.
Das Userinterface ist etwas sehr spartanisch, aber der Fokus lag ja auf dem Algorithmus. Bei Bedarf kann man jederzeit mit dem [Exit]-Knopf abbrechen.

Code: Alles auswählen

; PureBasic 4.10 (Windows - x86)
; 2008 Feb by qui

;--- sudoku 
EnableExplicit

;--- globale Variable
Global Zaehler.l ; wieviele versuche
Global Startzeit.l; Laufzeit
Global Loesung.s ; hier wird die ggf gefundene loesung notiert
Global EWindow.l, EGadget.l
Global NWindow.l, NStatusBar.l, NGadgetList.l, NButtonStart.l, NButtonExit.l

;--- schnelle funktion zum auslesen eines feldes (i,j) aus dem brett; liefert 0 fuer freies Feld und 1 bis 9
Procedure.l Feld(*Brett,i.l,j.l)
ProcedureReturn PeekB(*Brett+(i-1)*9+j-1)-48
EndProcedure

;--- schnelle funktion zum setzen eines feldes (i,j) auf wert k (muss 1 bis 9 sein) im brett
Procedure Setze(*Brett,i.l,j.l,k.l)
 PokeB(*Brett+(i-1)*9+j-1,48+k)
EndProcedure

;--- pruefen ob in zeile oder spalte oder subfeld des brettes doppelte ziffern stehen
Procedure.l Doppelte(*Brett)
Protected i.l, j.l, i1.l, j1.l, fi.l, fj.l, k.l, f.l
 For i=1 To 8 ; alle zeilen
  For j=1 To 8 ; alle spalten
   f=Feld(*Brett,i,j) ; das feld fuer schnellen zugriff in variable speichern
   If f>0 ; feld definiert
    For k=i+1 To 9 ; für rest der zeile
     If f=Feld(*Brett,k,j) ; und bereits in zeile vorhanden
      ProcedureReturn 1
     EndIf
    Next k
    For k=j+1 To 9 ; für rest der spalte
     If f=Feld(*Brett,i,k) ; und bereits in spalte vorhanden
      ProcedureReturn 1
     EndIf
    Next k
   EndIf
  Next j
 Next i
 For fi=0 To 6 Step 3 ; alle felder zeilen
  For fj=0 To 6 Step 3 ; alle felder spalten
   For i=1 To 3 ; alle felder im feld zeilen
    For j=1 To 3 ; alle felder im feld spaten
     f=Feld(*Brett,fi+i,fj+j) ; fuer schnellen zugriff speichern
     If f>0 ; feld definiert
      For i1=1 To 3 ; alle anderen felder in diesem feld zeilen
       For j1=1 To 3 ; alle anderen felder in diesem feld spalten
        If (i1<>i) Or (j1<>j) ; nicht mit eigenem feld vergleichen
         If f=Feld(*Brett,fi+i1,fj+j1)
          ProcedureReturn 1 ; in subfeld doppelt
         EndIf
        EndIf
       Next j1
      Next i1
     EndIf
    Next j
   Next i
  Next fj
 Next fi        
 ProcedureReturn 0
EndProcedure

;--- nachsehen, ob schon alle felder mit ziffern besetzt sind
Procedure Fertig(*Brett)
Protected i.l, j.l
 For i=1 To 9 ; alle zeilen
  For j=1 To 9 ; alle spalten
   If Feld(*Brett,i,j)=0 ; ist feld 0
    ProcedureReturn 0 ; noch nicht fertig
   EndIf
  Next j
 Next i
 ProcedureReturn 1 ; alles geprüft, war keines 0 -> also fertig
EndProcedure

;--- nimm das gegebene brett und suche eine loesung
Procedure.l Suche(Brett.s)
Protected i.l, j.l, k.l, z.l, s.s
 If Doppelte(@Brett)
  ProcedureReturn 0 ; es gibt bereits doppelte ziffern, nicht weitermachen
 EndIf
 If Fertig(@Brett)
  Loesung=Brett
  ProcedureReturn 1 ; es gibt eine loesung, notieren und schluss machen
 EndIf

 Zaehler=Zaehler+1 ; zaehle die kombinationen 
 If (Zaehler % 1000)=0 ; alle 1000 wird eine neue statuszeile aufgebaut
  s=Str(Zaehler)+" Checks " ; mit anzahl der versuche
  z=Date()-Startzeit;
  s=s+Str(z)+" Secs " ; laufzeit
  If z>0
   s=s+Str(Zaehler/z)+" C/s" ; wenn schon >0 sekunden -> versuche/sekunde berechnen
  EndIf
  StatusBarText(NStatusbar,0,s) ; alle 1000 ausgeben, damit man sieht, ob das programm noch laeuft
  If WindowEvent()=#PB_Event_Gadget ; event prüfen aber nicht abwarten -> damit das programm nicht "einfriert"
   If EventGadget()=NButtonExit ; war der knopf für ende und aus
    End ; das machen wir dann
   EndIf 
  EndIf
 EndIf 
   
 For i=1 To 9 ; alle zeilen
  For j=1 To 9 ; alle spalten
   If Feld(@Brett,i,j)=0 ; ist das feld noch zu besetzen
    For k=1 To 9 ; probiere alle ziffern
     Setze(@Brett,i,j,k) ; setze ein und
     If Suche(Brett) ; versuche diese kombination
      ProcedureReturn 1 ; es wurde 1 zuruekgemeldet = loesung gefunden -> einfach beenden
     EndIf
    Next k
   EndIf
  Next j
 Next i
 ProcedureReturn 0
EndProcedure

;--- das userinterface
Procedure Start()
 Protected i.l,j.l,k.l
 Protected Dim NString.l(9,9)
 Protected Brett.s
 Protected Dim p.l(9)
 
 p(1)=10: p(2)=35: p(3)=60: p(4)=90: p(5)=115: p(6)=140: p(7)=170: p(8)=195: p(9)=220 ; Positionen der Eingabefelder
 NWindow=OpenWindow(#PB_Any, 100,100, 250, 310, "Sudoku", #PB_Window_TitleBar | #PB_Window_WindowCentered ) ; das Eingabefenster
 NStatusBar=CreateStatusBar(#PB_Any,WindowID(NWindow)) ; Status des Programmes
 AddStatusBarField(250) ; zeit an, wieviele Versuche bereits gemacht wurden
 NGadgetList=CreateGadgetList(WindowID(NWindow)) ; liste der gadgets
 For i=1 To 9 ; alle zeilen
  For j=1 To 9 ; alle spalten
   NString(i,j)=StringGadget(#PB_Any, p(j), p(i), 20,20,"",#PB_String_BorderLess)  ; erzeuge ein eingabefeld, merke die nummer in array
  Next j
 Next i
 NButtonStart=ButtonGadget(#PB_Any,   10, 260, 50, 20, "Start")  ; beginne mit versuchen
 NButtonExit =ButtonGadget(#PB_Any,  190, 260, 50, 20, "Exit")  ; abbruch und ausstieg
 Repeat
  EWindow=WaitWindowEvent() ; warte auf aktion des users
  If EWindow=#PB_Event_Gadget ; ein gadget (eingabefeld oder button)
   EGadget=EventGadget() ; welches?
   Brett="" ; leere aufgabenspeicher
   If EGadget=NButtonStart ; es war der knopf für start
    For i=1 To 9 ; alle zeilen
     For j=1 To 9 ; alle spalten
      k=Val(GetGadgetText(NString(i,j))) ; mache aus eingabefeld eine zahl (wenn leer oder mist wird es null)
      If (k<1) Or (k>9) ; zahl im gültigen bereich
       SetGadgetText(NString(i,j),"") ; nein - feld löschen
       Brett=Brett+"0" ; eine 0 in das aufgabefeld rein
      Else
       SetGadgetText(NString(i,j),Str(k)) ; richtige zahl wieder setzen
       Brett=Brett+Str(k) ; und in das aufgabefeld reinschreiben
      EndIf
     Next j
    Next i
    Zaehler=0 ; wir beginnen mit zaehler mit 0
    Startzeit=Date() ; Anfangszeit
    StatusBarText(NStatusBar,0,"Start!") ; damit bis zur ersten anzeige (nach 1000 versuchen) was drinnen steht
    Loesung="" ; loesung loeschen 
    If Suche(Brett) ; nach loesung suchen
     MessageRequester("Sudoku","Lösung gefunden!",#PB_MessageRequester_Ok)
     k=1 ; ausgabe der lösung, beginnt bei ertem zeichen
     For i=1 To 9 ; alle zeilen
      For j=1 To 9 ; alle spalten
       SetGadgetText(NString(i,j),Mid(Loesung,k,1)) ; das (i-1)*9+j te zeichen auf feld(i,j) setzen
       k=k+1 ; nächstes zeichen
      Next j
     Next i
    Else
     MessageRequester("Sudoku","Keine Lösung gefunden!",#PB_MessageRequester_Ok) ; nix gefunden
    EndIf
   EndIf
  EndIf 
 Until (EWindow=#PB_Event_CloseWindow) Or (EGadget=NButtonExit) ; bis fenster zu oder exit
EndProcedure

Start() ; rufe start auf

[Laurin]

2000 Checks/Sek.? Ist das nicht etwas wenig. Auf den Diskussionsseiten von Wikipedia zu dem Thema gibt es C-Codes, die um einiges schneller sind.
Da kommt die Lösung nach etwa einer Sekunde, bei dir wohl so erst nach 5 Minuten (0,5 Mio durch 2000).
Vorschläge für eine Optimierung hab ich diese:
- Du benutzt für f eine 1-Byte-Variablen, Long ist wohl schneller.
- Du speicherst die Zahlen in einem String. Ein Zahlenarray ist da schneller, weil du dann auf Str() verzichten kannst.
Edit: Hm, jetzt blicke ich das erst richtig. Du machst das über Pointer. Die Sache mit einem Array wäre aber trotzdem einen Versuch wert, vllt wird es ja doch etwas schneller.


Dennoch ist eine schicke Sache, weil ich selber sehr gerne Sudokus löse. Kannst du auch einen Rätzelgenerator schreiben? Den würde ich dann wohl regelmäßig benutzen

Kannst du da nochmal nach den

Code: Alles auswählen

-Tags schauen. Irgendwie nimmt das Forum die nicht an.

[crossroads]

Kannst du da nochmal nach den

Code: Alles auswählen

-Tags schauen. Irgendwie nimmt das Forum die nicht an.[/quote]

@qui
Schau mal, ob in Deinem User-Profil "BBCode immer aktivieren" deaktiviert ist - wenn ja: dann aktivieren :wink:

[qui]

Kannst du da nochmal nach den

Code: Alles auswählen

-Tags schauen. Irgendwie nimmt das Forum die nicht an.[/quote]

@qui
Schau mal, ob in Deinem User-Profil "BBCode immer aktivieren" deaktiviert ist - wenn ja: dann aktivieren :wink:[/quote]

Vielen Dank - habe BBCode jetzt in meinem Profil aktiviert.

[qui]

2000 Checks/Sek.? Ist das nicht etwas wenig. Auf den Diskussionsseiten von Wikipedia zu dem Thema gibt es C-Codes, die um einiges schneller sind.
Da kommt die Lösung nach etwa einer Sekunde, bei dir wohl so erst nach 5 Minuten (0,5 Mio durch 2000).
Vorschläge für eine Optimierung hab ich diese:
- Du benutzt für f eine 1-Byte-Variablen, Long ist wohl schneller.
- Du speicherst die Zahlen in einem String. Ein Zahlenarray ist da schneller, weil du dann auf Str() verzichten kannst.
Edit: Hm, jetzt blicke ich das erst richtig. Du machst das über Pointer. Die Sache mit einem Array wäre aber trotzdem einen Versuch wert, vllt wird es ja doch etwas schneller.


Dennoch ist eine schicke Sache, weil ich selber sehr gerne Sudokus löse. Kannst du auch einen Rätzelgenerator schreiben? Den würde ich dann wohl regelmäßig benutzen ;)

Kannst du da nochmal nach den [ code ]-Tags schauen. Irgendwie nimmt das Forum die nicht an.

Vielen Dank für den Hinweis mit den BBCodes - sind jetzt in meinem Profil aktiviert.

Besten Dank auch für die Blumen, freut mich immer.

Ad Tempo: 5 Minuten ist richtig, aber Tempo ganz allein ist bei der Entwicklung nicht im Vordergrund gestanden, siehe weiter unten. Außerdem ist mein XP schon nicht mehr der jüngste - auf aktuellen Geräten ist es sicher schneller.

Ad Lösungsansatz/Speicherformat:
Prinzipiell ist es eine Demonstration rekursiver Programmierung und dazu muss ich den Brettstand übergeben. Zuerst wollte ich es mit einem Byte-Array machen, das wäre auch didaktisch schöner gewesen. Dann hat sich aber gezeigt, dass in PB diese per Reference übergeben werden, was hier nicht brauchbar ist. Daher bin ich dann auf Strings ausgewichen, in denen die Zeilen/Spaltenstruktur linear abgebildet wird. Zum besseren Zugriff verwende ich dann Routinen mit direktem Speicheraufruf, die ich aber in les- und verstehbare Funktionen eingebettet habe - ein Kompromiss.
Übrigens habe ich versucht, so viele long-Variable wie möglich als Bytes zu deklarieren, was aber sogar langsamer wurde. Auch Versuche, die Multiplikationen mit 9 (Zeilenstruktur) als vielfache Additionen zu schreiben brachten nichts.
Wie angeregt liefere ich das Programm weiter unten in C formuliert für Geschwindigkeitsversuche. Bitte um Nachsicht - ist ja ein PureBASIC-Forum. Ist allerdings nur "trocken" Übersetzt und nicht getestet.
Ein Generator wäre leicht möglich: Dazu würde ich ein Zufallsbrett mit einem oder wenigen gesetzten Feldern durchlaufen lassen und dann in der Lösung so viele Felder weglassen, bis es die gewünschte Schwierigkeit hat. Möchte nichts fix versprechen, aber wenn einmal wieder Zeit und Lust habe, schaue ich mir das an.

Code: Alles auswählen

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char loesung[9][9];

void notiereloesung(char brett[9][9])
{
	int i,j;
	for (i=0;i<=8;i++){
		for (j=0;j<=8;j++) loesung[i][j]=brett[i][j];}
}

void ausgabe(char brett[9][9])
{
    int i,j;

    printf("\n");
    for (i=0;i<9;i++){
        for (j=0;j<9;j++){
            if (brett[i][j]=='0') printf(". "); else printf("%c ",brett[i][j]);
            if ((j==2)||(j==5)) printf("| ");
        }
        printf("\n");
        if ((i==2)||(i==5)) printf("------+-------+-------\n");
    }
}

int doppelte(char brett[9][9])
{
	int i,j,i1,j1,fi,fj,k;

	for (i=0;i<=7;i++){
		for (j=0;j<=7;j++){
			if ((brett[i][j]>='0')&&(brett[i][j]<='9')){
				for (k=i+1;k<=8;k++){
					if (brett[i][j]==brett[k][j]) return 1;
				}
				for (k=j+1;k<=8;k++){
					if (brett[i][j]==brett[i][k]) return 1;
				}
			}
		}
	}
	for (fi=0;fi<=2;fi++){
		for (fj=0;fj<=2;fj++){
			for (i=0;i<=2;i++){
				for (j=0;j<=2;j++){
					if ((brett[fi*3+i][fj*3+j]>='0')&&(brett[fi*3+i][fj*3+j]<='9')){
						for (i1=0;i1<=2;i1++){
							for (j1=0;j1<=2;j1++){
								if ((i1!=i)||(j1!=j)) {
									if (brett[fi*3+i][fj*3+j]==brett[fi*3+i1][fj*3+j1]) return 1;
								}
							}
						}
					}
				}
			}
		}
	}
	return 0;
}

int fertig(char brett[9][9])
{
	int i,j;

	for (i=0;i<=8;i++){
		for (j=0;j<=8;j++){
			if ((brett[i][j]<'1')||(brett[i][j]>'9')){
				return 0;
			}
		}
	}

	return 1;
}

int suche(char brett[9][9])
{
 int i,j,k;

 if (doppelte(brett)) return 0;
 if (fertig(brett))
 {
   notiereloesung(brett);
   return 1;
 }

 ausgabe(brett);

 for (i=0;i<=8;i++){
	 for (j=0;j<=8;j++) {
		 if (brett[i][j]!='0') {
			 for (k=1;k<=9;k++){
				 brett[i][j]=(char) (k +(int)'0');
				 if (suche(brett)) return 1;
				}
			}
		}
	}
 return(0);
}


int main(int argc,char *argv[])
{
 char brett[9][9];

 brett[0][0]='0'; ...... hier das aufgabenfeld definieren ... brett[8][8]='0';
 printf("Die Aufgabe:\n");
 ausgabe(brett);
 if (suche(brett))
    printf("Gefundene Loesung\n");
    ausgabe(brett);
 getchar();

    return 0;
}

[qui]

Bitte um Nachsicht, aber ich habe nun in meinem Profil das BBCode deaktivieren auf nein - trotzdem scheint es noch nicht zu klappen. Werde hoffentlich noch draufkommen. Aller Anfang ist eben schwer ....

[Kiffi]

<OT>

Bitte um Nachsicht

manchmal spinnt auch das phpBB beim Formatieren des Codes.
Muss also nicht unbedingt an Dir liegen

</OT>

Grüße ... Kiffi

[bobobo]

na klar .. die badehose des nichtschwimmerbauerns.



wenn oberhalb des codeteils im text ein eröffnender codetag drinsteht dem
kein schließender sondern ein zweiter öffnender folgt, dann ist das eben
laut der codetaglogik des boards falsch.

In zweitem posting hab ich das im text auftauchende öffnende code-tag
etwas verleerzeichend, damit dieses nicht als codetag umgesetzt wird.

genug nun

[qui]

@Laurin: Auf Grundlage des Lösungsprogrammes war der Generator nicht schwer zu erstellen. Ich beginne mit einem leeren Brett und probiere nicht systematisch jedes leere Feld von 1 bis 9 sondern alle Ziffern in zufälliger Reihe. Da ich hier nicht unbedingt eine Lösung finden will, breche ich nach einigen 1000 Versuchen einfach ab und versuche es nochmal. Es hat sich gezeigt, dass ich so wesentlich schneller die nächste Aufgabe erhalte.
Von der so gefundenen Lösung steiche ich zufällig einen gewissen Anteil (Schieberegler in der Mitte, links leicht - rechts schwer) an Feldern raus, damit es eine Sudoku-Aufgabe wird und das zeige ich dann an. Viel Spaß damit.
PS: Ist noch nicht sonderlich gut getestet, hat aber einige Dutzend Aufgaben klaglos generiert.

Code: Alles auswählen

; PureBasic 4.10 (Windows - x86)
; 2008 Mar by qui

;--- sudokugenerator
EnableExplicit

;--- ordne die 9 möglichen ziffern in zufälliger reihung an
Procedure ZufallsReihe(z.l(1))
 Protected i.l, h.l, t1.l, t2.l
 For i=1 To 9 
  z(i)=i
 Next i
 For i=1 To 9
  t1=Round(Random(8)+1,0)
  t2=Round(Random(8)+1,0)
  h=z(t1) : z(t1)=z(t2) : z(t2)=h
 Next i
EndProcedure

;--- globale Variable
Global Zaehler.l ; wieviele versuche
Global Loesung.s ; hier wird die ggf gefundene loesung notiert
Global EWindow.l, EGadget.l
Global NWindow.l, NStatusBar.l, NGadgetList.l, NButtonStart.l, NButtonExit.l, NTrackBar.l

;--- schnelle funktion zum auslesen eines feldes (i,j) aus dem brett; liefert 0 fuer freies Feld und 1 bis 9
Procedure.l Feld(*Brett,i.l,j.l)
ProcedureReturn PeekB(*Brett+(i-1)*9+j-1)-48
EndProcedure

;--- schnelle funktion zum setzen eines feldes (i,j) auf wert k (muss 1 bis 9 sein) im brett
Procedure Setze(*Brett,i.l,j.l,k.l)
 PokeB(*Brett+(i-1)*9+j-1,48+k)
EndProcedure

;--- pruefen ob in zeile oder spalte oder subfeld des brettes doppelte ziffern stehen
Procedure.l Doppelte(*Brett)
Protected i.l, j.l, i1.l, j1.l, fi.l, fj.l, k.l, f.l
 For i=1 To 8 ; alle zeilen
  For j=1 To 8 ; alle spalten
   f=Feld(*Brett,i,j) ; das feld fuer schnellen zugriff in variable speichern
   If f>0 ; feld definiert
    For k=i+1 To 9 ; für rest der zeile
     If f=Feld(*Brett,k,j) ; und bereits in zeile vorhanden
      ProcedureReturn 1
     EndIf
    Next k
    For k=j+1 To 9 ; für rest der spalte
     If f=Feld(*Brett,i,k) ; und bereits in spalte vorhanden
      ProcedureReturn 1
     EndIf
    Next k
   EndIf
  Next j
 Next i
 For fi=0 To 6 Step 3 ; alle felder zeilen
  For fj=0 To 6 Step 3 ; alle felder spalten
   For i=1 To 3 ; alle felder im feld zeilen
    For j=1 To 3 ; alle felder im feld spaten
     f=Feld(*Brett,fi+i,fj+j) ; fuer schnellen zugriff speichern
     If f>0 ; feld definiert
      For i1=1 To 3 ; alle anderen felder in diesem feld zeilen
       For j1=1 To 3 ; alle anderen felder in diesem feld spalten
        If (i1<>i) Or (j1<>j) ; nicht mit eigenem feld vergleichen
         If f=Feld(*Brett,fi+i1,fj+j1)
          ProcedureReturn 1 ; in subfeld doppelt
         EndIf
        EndIf
       Next j1
      Next i1
     EndIf
    Next j
   Next i
  Next fj
 Next fi        
 ProcedureReturn 0
EndProcedure

;--- nachsehen, ob schon alle felder mit ziffern besetzt sind
Procedure Fertig(*Brett)
Protected i.l, j.l
 For i=1 To 9 ; alle zeilen
  For j=1 To 9 ; alle spalten
   If Feld(*Brett,i,j)=0 ; ist feld 0
    ProcedureReturn 0 ; noch nicht fertig
   EndIf
  Next j
 Next i
 ProcedureReturn 1 ; alles geprüft, war keines 0 -> also fertig
EndProcedure

;--- nimm das gegebene brett und suche eine loesung
Procedure.l Suche(Brett.s)
Protected i.l, j.l, k.l
Protected Dim z.l(9)
 If Doppelte(@Brett)
  ProcedureReturn 0 ; es gibt bereits doppelte ziffern, nicht weitermachen
 EndIf
 If Fertig(@Brett)
  Loesung=Brett
  ProcedureReturn 1 ; es gibt eine loesung, notieren und schluss machen
 EndIf

 Zaehler=Zaehler+1 ; zaehle die kombinationen 
 If (Zaehler % 100)=0 ; alle 100 wird nach windowevents gesehen
  If WindowEvent()=#PB_Event_Gadget ; event prüfen aber nicht abwarten -> damit das programm nicht "einfriert"
   If EventGadget()=NButtonExit ; war der knopf für ende und aus
    End ; das machen wir dann
   EndIf 
  EndIf
  StatusBarText(NStatusBar,0,RSet("",((zaehler/100)%50),"-")+">") ; laufzeitanzeige
 EndIf 
 
 If Zaehler>5000
  ProcedureReturn 0 ; nachdem wir nicht eine aufgabe unbedingt lösen sondern nur welche erzeugen wollen -> abbruch+neuer versuch
 EndIf
    
 For i=1 To 9 ; alle zeilen
  For j=1 To 9 ; alle spalten
   If Feld(@Brett,i,j)=0 ; ist das feld noch zu besetzen
    ZufallsReihe(z())
    For k=1 To 9 ; probiere alle ziffern, in zufälliger reihung
     Setze(@Brett,i,j,z(k)) ; setze ein und
     If Suche(Brett) ; versuche diese kombination
      ProcedureReturn 1 ; es wurde 1 zuruekgemeldet = loesung gefunden -> einfach beenden
     EndIf
    Next k
   EndIf
  Next j
 Next i
 ProcedureReturn 0
EndProcedure

;--- das userinterface
Procedure Start()
 Protected i.l,j.l,k.l,s.l, d.l
 Protected Dim NString.l(9,9)
 Protected Brett.s
 Protected Dim p.l(9)
 
 p(1)=10: p(2)=35: p(3)=60: p(4)=90: p(5)=115: p(6)=140: p(7)=170: p(8)=195: p(9)=220 ; Positionen der Eingabefelder
 NWindow=OpenWindow(#PB_Any, 100,100, 250, 310, "Sudokugenerator", #PB_Window_TitleBar | #PB_Window_WindowCentered ) ; das Eingabefenster
 NStatusBar=CreateStatusBar(#PB_Any,WindowID(NWindow)) ; Status des Programmes
 AddStatusBarField(250) ; zeit an, dass programm läuft
 NGadgetList=CreateGadgetList(WindowID(NWindow)) ; liste der gadgets
 For i=1 To 9 ; alle zeilen
  For j=1 To 9 ; alle spalten
   NString(i,j)=StringGadget(#PB_Any, p(j), p(i), 20,20,"",#PB_String_BorderLess)  ; erzeuge ein eingabefeld, merke die nummer in array
  Next j
 Next i
 NTrackbar=TrackBarGadget(#PB_Any, 70,260,100,40,1,5,#PB_TrackBar_Ticks) ; zum einstellen der schwierigkeit
 NButtonStart=ButtonGadget(#PB_Any,   10, 260, 50, 20, "Start")  ; beginne mit versuchen
 NButtonExit =ButtonGadget(#PB_Any,  190, 260, 50, 20, "Exit")  ; abbruch und ausstieg
 Repeat
  EWindow=WaitWindowEvent() ; warte auf aktion des users
  If EWindow=#PB_Event_Gadget ; ein gadget (eingabefeld oder button)
   EGadget=EventGadget() ; welches?
   If EGadget=NButtonStart ; es war der knopf für start
 
    Repeat
     Brett=""
     Brett=Brett+"000000000"
     Brett=Brett+"000000000"
     Brett=Brett+"000000000"
     Brett=Brett+"000000000"
     Brett=Brett+"000000000"
     Brett=Brett+"000000000"
     Brett=Brett+"000000000"
     Brett=Brett+"000000000"
     Brett=Brett+"000000000"
     Zaehler=0 ; wir beginnen mit zaehler mit 0
     Loesung="" ; loesung loeschen 
     StatusBarText(NStatusBar,0,"*") ; start des programmes anzeigen
     s=Suche(Brett) ; nach loesung suchen
     StatusBarText(NStatusBar,0,"") ; statuszeile leeren
     If s
      d=GetGadgetState(NTrackBar) ; hole schwierigkeitsgrad
      k=1 ; ausgabe der lösung, beginnt bei erstem zeichen
      For i=1 To 9 ; alle zeilen
       For j=1 To 9 ; alle spalten
        SetGadgetText(NString(i,j),Mid(Loesung,k,1)) ; das (i-1)*9+j te zeichen auf feld(i,j) setzen
        k=k+1 ; nächstes zeichen
       Next j
      Next i 
      For i=1 To 9 ; alle zeilen
       For j=1 To 9 ; alle spalten
        If Int(Random(d))<>0 ; je nach schwierigkeit
         SetGadgetText(NString(i,j),"") ; lösche das feld 
        EndIf 
       Next j
      Next i
     EndIf
    Until s
    
   EndIf
  EndIf 
 Until (EWindow=#PB_Event_CloseWindow) Or (EGadget=NButtonExit) ; bis fenster zu oder exit
EndProcedure

Start() ; rufe start auf