Búsqueda en profundidad

Ejercicio de los sapos y las ranas

Hay 7 rocas en un lago, en 6 de ellas hay 3 ranas y 3 sapos una en cada una de esas rocas, la séptima esta vacía y en el medio de las otras 6 rocas. Las ranas están todas ubicadas de forma seguida en las 3 rocas al lado izquierdo de la roca vacía y los sapos en la parte derecha de igual forma. Se busca llevar a las ranas donde están los sapos y viceversa, teniendo en cuenta que las ranas pueden saltar por encima de los sapos, pero los sapos no pueden hacer lo mismo y solo pueden saltar al espacio vació. Tampoco puede haber mas de 1 rana y/o sapo en una roca.

Estado inicial:

Estado final:

Espacio estado: 43 aproximadamente
Solucion
1: S1 S2 S3 O R1 R2 R3
2: S1 S2 O S3 R1 R2 R3
3: S1 S2 R1 S3 O R2 R3
4: S1 S2 R1 O S3 R2 R3
5: S1 S2 O R1 S3 R2 R3
6: S1 O S2 R1 S3 R2 R3
7: S1 R1 S2 O S3 R2 R3
8: S1 R1 S2 R2 S3 O R3
9: S1 R1 S2 R2 O S3 R3
10: S1 R1 S2 O R2 S3 R3
11: S1 R1 O S2 R2 S3 R3
12: S1 O R1 S2 R2 S3 R3
13: O S1 R1 S2 R2 S3 R3
14: R1 S1 O S2 R2 S3 R3
15: R1 S1 R2 S2 O S3 R3
16: R1 S1 R2 S2 R3 S3 O
17: R1 S1 R2 S2 R3 O S3
18: R1 S1 R2 S2 O R3 S3
19: R1 S1 R2 O S2 R3 S3
20: R1 S1 O R2 S2 R3 S3
21: R1 O S1 R2 S2 R3 S3
22: R1 R2 S1 O S2 R3 S3
23: R1 R2 S1 R3 S2 O S3
24: R1 R2 S1 R3 O S2 S3
25: R1 R2 S1 O R3 S2 S3
26: R1 R2 O S1 R3 S2 S3
27: R1 R2 R3 S1 O S2 S3
28: R1 R2 R3 O S1 S2 S3

Árbol del problema:



Algoritmo de búsqueda en profundidad para la solución: