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