ANEXO: Programa para la resolución de laberintos [PASCAL]


        
Los laberintos pueden resolverse con una amplia diversidad de algoritmos. En el siguiente ejemplo se utiliza un algoritmo recursivo que determina si un laberinto tiene o no solución y muestra una de ellas. El presente programa no evalúa todas las posibles soluciones ni muestra la solución óptima, se detiene al encontrar alguna de ellas, sea cual sea, o en caso de no hallar ninguna.

Ejemplo de ejecución del programa
            
            El laberinto se genera aleatoriamente usando una matriz rectangular para guardar los datos, pudiendo determinar el usuario sus dimensiones y las posiciones de entrada y salida. La matriz mínima válida es una 2x3, dos filas y tres columnas. Las posiciones de entrada y de salida no pueden estar situadas ni en la primera ni en la última columna de la matriz. La entrada se ubica siempre en la última fila y la salida en la primera.
            La solución hallada se muestra gráficamente y en forma de coordenadas. Las coordenadas indican por orden el camino de salida con pares de números (X – Y), siendo X el valor de la fila e Y el valor de la columna.



            La recursividad o recursión consume bastantes recursos de memoria por lo que el tamaño de los laberintos que es posible solucionar varía notablemente según el ordenador en el que se ejecuta el programa. 


            El código del programa completo en lenguaje Turbo PASCAL es el siguiente:



PROGRAM laberinto (INPUT, OUTPUT);
{por TDM para Arqui-2 (2009)}

USES CRT;


CONST limitematriz = 80;


TYPE tcelda = (libre, muro, visitada);

     tmatriz = ARRAY [1..limitematriz, 1..limitematriz] OF tcelda;

     tdireccion = (inicio, norte, este, oeste, sur);


CONST pasox: ARRAY[inicio..sur] OF INTEGER = (0,-1,0,0,1);

      pasoy: ARRAY[inicio..sur] OF INTEGER = (0,0,1,-1,0);


VAR matriz :tmatriz;

    direccion :tdireccion;

    nfilas, ncolumnas  :INTEGER;

    xentrada, yentrada, xsalida, ysalida :INTEGER;

    haysalida :BOOLEAN;


    recorrido :STRING;




FUNCTION valor_obligado (limiteinf, limitesup :INTEGER; texto :STRING):INTEGER;


VAR valor :INTEGER;


BEGIN

     REPEAT

           WRITE(texto);
           READLN(valor)


     UNTIL (valor > limiteinf) AND (valor < limitesup);

     valor_obligado := valor

END;



PROCEDURE introducir_datos (VAR pnfilas, pncolumnas, pxentrada, pyentrada, pxsalida, pysalida :INTEGER);


BEGIN

     CLRSCR;
     TEXTCOLOR(7);

     pnfilas := valor_obligado (0, limitematriz, 'Introduzca el numero de filas: ');
     pncolumnas := valor_obligado (0, limitematriz, 'Introduzca el numero de columnas: ');


     xentrada := nfilas;
     pyentrada:= valor_obligado (1, pncolumnas, 'Introduzca la posicion de la entrada (valor < numero columnas): ');

     xsalida := 1;
     pysalida:= valor_obligado (1, pncolumnas, 'Introduzca la posicion de la salida (valor < numero columnas): ');

END;



FUNCTION hueco_ciego (pmatriz :tmatriz; fila, columna :INTEGER) :BOOLEAN;


VAR cegado :INTEGER;


BEGIN

     cegado := 0;


     IF pmatriz[fila-1, columna] = muro THEN cegado := cegado +1;
     IF pmatriz[fila+1, columna] = muro THEN cegado := cegado +1;
     IF pmatriz[fila, columna-1] = muro THEN cegado := cegado +1;
     IF pmatriz[fila, columna+1] = muro THEN cegado := cegado +1;


     IF cegado = 4 THEN hueco_ciego := TRUE ELSE hueco_ciego:= FALSE


END;



PROCEDURE crear_laberinto ( VAR pmatriz :tmatriz; pnfilas, pncolumnas, pxentrada, pyentrada, pxsalida, pysalida :INTEGER);

VAR i, j :INTEGER;


BEGIN


     {CREAR BORDES}

     FOR i:= 1 TO pnfilas DO

         BEGIN

              pmatriz [i,1] := muro;
              pmatriz [i, pncolumnas] := muro

         END;

     FOR i:= 2 TO ncolumnas -1 DO

         BEGIN

              pmatriz [1,i] := muro;
              pmatriz [pnfilas, i] := muro;
              pmatriz [pnfilas+1, i] := muro;

         END;

     {COLOCAR ENTRADA Y SALIDA}

     pmatriz [pxentrada, pyentrada] := libre;
     pmatriz [pxsalida, pysalida] := libre;


     {GENERACION DEL INTERIOR DEL LABERINTO}


     RANDOMIZE;


     FOR i:= 2 TO pnfilas -1 DO

         FOR j:= 2 TO ncolumnas -1 DO

             IF (pmatriz [i, j-1] = muro) AND (pmatriz[i-1,j] = muro) THEN

                        pmatriz [i,j] := libre

             ELSE
                        IF RANDOM(2) = 0 THEN

                                     pmatriz [i,j] := muro

                        ELSE
                                     pmatriz [i,j] := libre;

     {DESBLOQUEAR ENTRADA / SALIDA}


     IF pxentrada = 1 THEN pmatriz [pxentrada +1, pyentrada] := libre;
     IF pyentrada = 1 THEN pmatriz [pxentrada, pyentrada +1] := libre;
     IF pxentrada = pnfilas THEN pmatriz [pxentrada -1, pyentrada] := libre;
     IF pyentrada = pncolumnas THEN pmatriz [pxentrada, pyentrada -1] := libre;

     IF pxsalida = 1 THEN pmatriz [pxsalida+1, pysalida] := libre;
     IF pysalida = 1 THEN pmatriz [pxsalida, pysalida +1] := libre;
     IF pxsalida = pnfilas THEN pmatriz [pxsalida -1, pysalida] := libre;
     IF pysalida = pncolumnas THEN pmatriz [pxsalida, pysalida -1] := libre;


     {ELIMINAR HUECOS CIEGOS}


     FOR i:= 2 TO pnfilas -1 DO

         FOR j:= 2 TO pncolumnas -1 DO

             IF hueco_ciego (pmatriz, i,j) THEN

                IF j < pncolumnas-1 THEN pmatriz[i, j+1] := libre

                   ELSE

                       IF i < pnfilas -1 THEN pmatriz[i+1, j] := libre;


END;



PROCEDURE dibujar_laberinto (pmatriz :tmatriz; pnfilas, pncolumnas :INTEGER);


VAR i,j  :INTEGER;


BEGIN


     CLRSCR;

     TEXTCOLOR(10);

     FOR i:= 1 TO pnfilas DO

         BEGIN

              FOR j:= 1 TO pncolumnas DO

                  IF pmatriz[i,j] = muro THEN

                          WRITE (CHR(219))
                  ELSE
                          WRITE (' ');

              WRITELN

         END;


      TEXTCOLOR(15);

      WRITELN;

END;




PROCEDURE escribir_recorrido (p_recorrido :STRING);


VAR i :INTEGER;


BEGIN

     TEXTCOLOR(7);

     WRITELN ('RECORRIDO DE SALIDA:');

     FOR i:= 1 TO LENGTH(p_recorrido) DIV 2 DO

           WRITE('(', ORD(p_recorrido[2*i-1]), '-', ORD(p_recorrido[2*i]), ') ');

     WRITE('(', xsalida, '-', ysalida, ')');

     WRITELN;

END;




PROCEDURE trazar_salida (p_recorrido :STRING);


VAR i:INTEGER;


BEGIN


      FOR i:= 1 TO LENGTH(p_recorrido) DIV 2 DO

          BEGIN


              GOTOXY(ORD(p_recorrido[2*i]), ORD(p_recorrido[2*i-1]));
              TEXTCOLOR(14); WRITE('*');

              GOTOXY(ncolumnas+1, nfilas); TEXTCOLOR(7);WRITE(' Trazando...',i);

              DELAY(700);
              GOTOXY(ORD(p_recorrido[2*i]), ORD(p_recorrido[2*i-1]));
              TEXTCOLOR(14); WRITE('.');

          END;


      GOTOXY(ysalida, xsalida);TEXTCOLOR(14); WRITE('*');
      GOTOXY(ncolumnas+1, nfilas); TEXTCOLOR(7);WRITE(' Trazando...',i);

      DELAY(700);
      GOTOXY(ysalida, xsalida);TEXTCOLOR(14); WRITE('.');

      GOTOXY(ncolumnas+1, nfilas); WRITE(' Trazados ',LENGTH(p_recorrido) DIV 2 +1,' pasos');


END;




PROCEDURE resolver (px, py :INTEGER; VAR p_recorrido :STRING);

VAR pdireccion :tdireccion;

BEGIN

     pdireccion := inicio;

     REPEAT


           pdireccion := SUCC(pdireccion);



           IF matriz[px + pasox[pdireccion], py + pasoy[pdireccion]] = libre THEN

              BEGIN

                   p_recorrido:= p_recorrido + CHR(px) + CHR(py);

                   px:= px + pasox[pdireccion];
                   py:= py + pasoy[pdireccion];


                   matriz[px, py] := visitada;



                   IF (px = xsalida) AND (py = ysalida) THEN


                       haysalida := TRUE

                   ELSE

                       resolver(px, py, p_recorrido);

                       IF (NOT haysalida) THEN

                          BEGIN


                               matriz[px, py] := libre;

                               px:= px - pasox[pdireccion];
                               py:= py - pasoy[pdireccion];

                               DELETE(p_recorrido, LENGTH(p_recorrido)-1, 2);

                          END;

              END;



     UNTIL (pdireccion = sur) OR haysalida;


END;





BEGIN  {COMIENZO DEL PROGRAMA PRINCIPAL}


       introducir_datos (nfilas, ncolumnas, xentrada, yentrada, xsalida, ysalida);


       crear_laberinto (matriz, nfilas, ncolumnas, xentrada, yentrada, xsalida, ysalida);

       dibujar_laberinto(matriz, nfilas, ncolumnas);


       haysalida := FALSE;
       resolver(xentrada,yentrada, recorrido);



       IF haysalida THEN

          BEGIN

               WRITELN('EL LABERINTO TIENE SOLUCION'); WRITELN;

               escribir_recorrido(recorrido);

               trazar_salida(recorrido);

          END

       ELSE
               WRITE('EL LABERINTO NO TIENE SOLUCION');



       READKEY;

       CLRSCR

END.



No hay comentarios:

Publicar un comentario