C Sokoban Rekursiv Lösung

Hallo,
habe versucht Sokoban Labyrinths rekursiv zu lösen in C. Leider klappt es nicht wie gewünscht. Vielleicht hat ja wer ein Tipp für mich?!
Code:
--------------------------------

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

#define z 7
#define s 6

int freie_ziele=0;

// Anzahl der leeren Ziele (!=*), zugleich Anzahl der Kisten, die noch ans Ziel geschoben werden müssen

char soko[z][s]={   {'#' , '#' , '#' , '#' , ' ' , ' '}, 
               {'#' , ' ' , '.' , '#' , ' ' , ' '}, 
               {'#' , ' ' , ' ' , '#' , '#' , '#'}, 
               {'#' , '*' , '@' , ' ' , ' ' , '#'}, 
               {'#' , ' ' , ' ' , '$' , ' ' , '#'}, 
               {'#' , ' ' , ' ' , '#' , '#' , '#'}, 
               {'#' , '#' , '#' , '#' , ' ' , ' '}   };

// #=Mauer   .=Ziel für Kiste   *=Kiste am Ziel      $=Kiste      @=Sokoban (Schieber)

void lauf_nach(int,int,int);
void Ausgabe();
int main() {
   int ze, sp, i, j;

   for (i=0; i<z; i++) 
      for (j=0; j<s; j++) {
         if(soko[i][j]=='$')
            freie_ziele++;
         if(soko[i][j]=='@') {
            ze=i;
            sp=j;
         }
      }
   Ausgabe();
   lauf_nach(ze,sp,1);
   Ausgabe();
   system("pause");
   return 0;
}

void lauf_nach(int ze,int sp,int ri) {
   char wert;

   switch (ri) {
   case 1: wert=soko[ze-1][sp];
      break;
   case 2: wert=soko[ze][sp+1];
      break;
   case 3: wert=soko[ze+1][sp];
      break;
   case 4: wert=soko[ze][sp-1];
      break;
   }

   if (soko[ze][sp] != '#' && soko[ze][sp]!=';') {
      if(soko[ze][sp]=='$') {
         if(wert!='#' && soko[ze][sp]!='|') {
            soko[ze][sp]='|';
            //soko[ze][sp]=' ';
            if(wert=='.') {
               switch(ri) {
               case 1: soko[ze-1][sp]='*';
                  break;
               case 2: soko[ze][sp+1]='*';
                  break;
               case 3: soko[ze+1][sp]='*';
                  break;
               case 4: soko[ze][sp-1]='*';
                  break;
               }
               freie_ziele--;
            }
            if(wert==' ') {
               switch(ri) {
               case 1: soko[ze-1][sp]='$';
                  break;
               case 2: soko[ze][sp+1]='$';
                  break;
               case 3: soko[ze+1][sp]='$';
                  break;
               case 4: soko[ze][sp-1]='$';
                  break;
               }
            }
            lauf_nach(ze-1,sp,1);
            lauf_nach(ze,sp+1,2);
            lauf_nach(ze+1,sp,3);
            lauf_nach(ze,sp-1,4);
            soko[ze][sp]=' ';
         }
      }
      else {
         soko[ze][sp]=';';
         lauf_nach(ze-1,sp,1);
         lauf_nach(ze,sp+1,2);
         lauf_nach(ze+1,sp,3);
         lauf_nach(ze,sp-1,4);
         soko[ze][sp]=' ';
      }
   }
}

void Ausgabe() {
   int i, j;
   for (i=0; i<z; i++) {
      for (j=0; j<s; j++)
         printf("%c", soko[i][j]);
      printf("\n");
   }
}

[edit]hab mal Code-Tags eingefügt und die anderen Beiträge mit Code-Tags gelöscht[/edit]

[ Dieser Beitrag wurde am 01.07.2003 um 17:21 Uhr von kingruedi editiert. ]

benutz den code-tag

So jetzt ist es viel besser lesbar

Weiss keiner einen Algorithmus als Lösung für dieses Spiel?
Ist das Problem evt. NP-vollständig, d.h. der Algorithmus benötigt exponentielle Rechenzeit und ist somit undurchführbar?

Bitte hilft mir!!!
Danke Leutz

japro

naja du müsstest mindestens alle positionen speichern die du schonmal hattest. weil sonst kann es zu schliefen kommen -> ewige laufzeit.

Ich glaube dein Fehler liegt in diesen Zeilen:

if(soko[ze][sp]!='#' && soko[ze][sp]!=';')
{
if(soko[ze][sp]=='$')
{
if(wert!='#' && soko[ze][sp]!='|')
{
soko[ze][sp]='|';
if(wert=='.')
{
...
}

Wahrscheinlich meinst du hier die neue Position des Schiebers, es ist aber noch die alte, weil du in der ersten

switch

-Verzweigung in der Funktion

void lauf_nach (int ze, int sp, int ri)

gar nicht die Position änderst, sondern dir nur den Wert des neuen Standfeldes merkst.
Vielleicht solltest du noch ein Variablenpaar definieren, als Koordinaten des aktuellen Standfeldes des Schiebers in der Matrix. Wenn der Schieber läuft nehmen die Koordinaten des Schiebers dann immer die Werte vom neuen ze und sp an.

Kannst du damit was anfangen ?

Jester

Das Problem bei einer solchen Rekursivlösung ist, daß ganz viele Sachen doppelt gerechnet werden:

Geh nach rechts, geh nach unten ...
Geh nach unten, geh nach rechts ...

ergeben genau die selbe Konstellation, sind aber für das Programm dann was anderes.
Du könntest versuchen jeder Stellung einen eindeutigen Code zuzuordnen und dann mit Hashing bereits berechnete Stellungen zu vermerken.
Auf die Art und Weise kannst Du Dir vielleicht was sparen.