Inicio / algoritmo del solucionador de Sokoban
Guía del algoritmo de Sokoban

Algoritmo de Sokoban: cómo la búsqueda encuentra una solución

Un algoritmo de Sokoban convierte el rompecabezas en una búsqueda de estados del tablero. Registra las cajas, el suelo alcanzable, los empujes legales y las posiciones ya conocidas.

Esta guía explica cómo funciona un solucionador, no es otra guía de clics. Usa la página del solucionador online para introducir un tablero ASCII y obtener una ruta.

Actualizado el 16 de noviembre de 2026Para jugadores, diseñadores de niveles y programadores curiosos

Tablero de Sokoban con cajas, objetivos, paredes y casillas de acceso

Un solucionador evalúa el tablero como un grafo de estados, no solo como una imagen.

Respuesta rápida: En resumen: el solucionador guarda un estado compacto, calcula por relleno las casillas accesibles, genera solo empujes legales y descarta estados repetidos o claramente bloqueados. Conserva enlaces al estado anterior para convertir una solución encontrada en una secuencia de movimientos.

La unidad útil suele ser un empuje, no un paso con las flechas. Caminar entre empujes cambia la posición del jugador, pero no mueve cajas. Por eso el tablero puede tratarse como un grafo: un nodo es una posición conocida y una arista es un empuje legal con el recorrido necesario para situarse detrás de la siguiente caja.

El grafo es grande porque los empujes no siempre pueden deshacerse. Para mover una caja hay que situarse al otro lado; no se puede tirar de ella para sacarla de una esquina. Cada nodo debe conservar información suficiente sobre las casillas ocupadas por cajas y las que el jugador alcanza sin moverlas.

Cuando todas las metas están ocupadas, el solucionador sigue los enlaces a los estados anteriores hasta el inicio y reconstruye la ruta. La secuencia de direcciones puede contener muchos pasos, pero las decisiones importantes son los empujes que cambiaron el estado.

Cómo se representa el estado del tablero

El tablero tiene datos fijos y variables. Paredes y metas se leen una sola vez. Cambian las coordenadas de las cajas y la región accesible del jugador. Dos posiciones del jugador suelen ser equivalentes si puede caminar entre ellas sin atravesar cajas. Normalizarlas evita llenar la cola con posiciones de paso duplicadas.

Parte del estadoQué registraPor qué importa
Paredes y metasGeometría fijaDefine las casillas transitables y la condición de victoria.
Configuración de cajasUna coordenada por cajaDetermina empujes y asignaciones a metas posibles.
Región del jugadorSuelo accesible sin empujarIndica desde qué lados se pueden empujar las cajas.
Predecesor y acciónEstado anterior y dirección del empujePermite reproducir la ruta, en vez de responder solo sí o no.

Una tabla de transposiciones, o conjunto de visitados, guarda una clave por estado normalizado. Repetir la misma configuración de cajas y región accesible no revela continuaciones nuevas. Es un intercambio de memoria por velocidad.

Tablero de Sokoban para planificar el orden de cajas con una meta restringida y zona de espera libre

Diagrama explicativo: el orden de las cajas cambia los estados accesibles después de cada empuje. La imagen ilustra la idea; no es una captura del código.

Cómo crece la frontera de búsqueda

Tras leer un estado, se calcula mediante relleno la zona transitable. Para cada caja se comprueban cuatro direcciones. Un empuje es legal si el destino es suelo vacío y el jugador alcanza la casilla opuesta. Después se crea un estado nuevo con la caja desplazada y la región accesible recalculada.

El orden de búsqueda cambia las garantías. La búsqueda en anchura explora primero secuencias cortas de empujes y minimiza su número cuando todas las aristas cuestan lo mismo. La búsqueda en profundidad sigue una rama y necesita menos memoria de frontera, pero puede perder tiempo en una rama inútil. La búsqueda de coste uniforme o A* combina costes con una heurística; sus propiedades y calidad determinan qué garantiza el resultado.

  1. Leer.Identificar paredes, metas, cajas y jugador; rechazar cantidades incorrectas o símbolos no admitidos.
  2. Alcanzar.Marcar el suelo accesible sin mover cajas.
  3. Expandir.Generar empujes con casillas de apoyo y destino válidas.
  4. Podar y registrar.Omitir duplicados y bloqueos evidentes, guardando predecesor y empuje.
  5. Terminar.Detenerse al cubrir las metas o informar de que no se encontró ruta dentro del límite.

No hace falta guardar cada recorrido a pie por separado. Tras un empuje, una región accesible normalizada basta para generar los siguientes. Eso permite un solucionador compacto y práctico en el navegador.

Por qué importa podar los bloqueos

Sin poda se pierde tiempo en posiciones que nunca llevan a una solución. La regla más sencilla es una esquina sin meta: una caja junto a dos paredes perpendiculares no puede salir y la rama se descarta. También se comprueban tramos de pared sin meta compatible, grupos 2×2 inmóviles y cajas que cierran pasillos de una casilla.

Algunos fallos afectan al acceso, aunque las cajas aún se muevan. Una meta ocupada correctamente puede bloquear el único apoyo de otra caja. Dos cajas pueden deslizarse, pero el jugador ya no alcanza el lado necesario para separarlas. Son casos más difíciles; por eso se combinan reglas simples, comprobación de duplicados y un presupuesto finito.

Bloqueo de esquina en Sokoban para explicar la poda de búsqueda

Un bloqueo de esquina se reconoce antes de profundizar en la búsqueda. Los problemas de acceso más sutiles necesitan comprobaciones de estado más amplias.

La poda exige cuidar la corrección: una regla demasiado agresiva puede eliminar una ruta ganadora poco habitual. Las herramientas pequeñas deben explicar sus límites de poda y no presentar cada resultado sin solución como una prueba.

Coste de empujar, caminar y usar heurísticas

Antes de hablar de la «solución más corta» hay que definir la medida. Una ruta óptima en empujes minimiza movimientos de cajas; una óptima en movimientos incluye los pasos del jugador. Pueden entrar en conflicto: rodear una sala puede ahorrar un empuje y mantener una asignación segura. El solucionador debe priorizar costes y etiquetar el resultado.

Una heurística estima cuánto falta para terminar. Una estimación básica asigna cajas a metas mediante distancias de cuadrícula y añade penalizaciones por cajas atrapadas junto a paredes. Las paredes, apoyos y orden de cajas complican la ruta real. La estimación sirve para priorizar estados prometedores, no para demostrar una distancia exacta.

En tableros pequeños conviene mostrar la secuencia, los empujes, los pasos y los estados examinados. Así se compara la respuesta con un plan propio sin confundirla con un óptimo no demostrado.

Seguimiento de un tablero pequeño

En este ejemplo de una caja, # es pared, . es meta, $ es caja y @ es jugador.

#####
# . #
# $ #
# @ #
#####

La región inicial incluye la casilla del jugador y el suelo bajo la caja. Hay un empuje legal: situarse debajo y empujar hacia arriba hasta la meta. Se registra la coordenada nueva, se recalcula la región accesible y se detectan todas las metas ocupadas. El enlace al predecesor permite reconstruir el recorrido necesario seguido de un empuje.

En un tablero difícil, la frontera contiene varios empujes candidatos. Una rama que acaba en una esquina desaparece con la poda, mientras otra sigue en la cola. Esa es la diferencia entre probar al azar y recordar lo que la búsqueda ha establecido.

Cuándo se detiene el solucionador

Hay varias razones para detenerse: cantidades distintas de cajas y metas, símbolos no admitidos o ausencia del jugador invalidan la entrada. Un tablero válido puede superar límites seguros de filas, columnas, cajas o estados visitados. También puede agotarse la frontera de una búsqueda limitada sin encontrar solución.

Solo el último caso en una búsqueda completa y sin límites justifica afirmar matemáticamente que es irresoluble. Las herramientas pequeñas limitan el trabajo para mantener la respuesta de la página. Ante un aviso, reduce el tablero, busca bloqueos o planifica hacia atrás. El solucionador de Sokoban asociado documenta sus límites para tableros pequeños y devuelve un mensaje claro en vez de ejecutarse indefinidamente.

Quienes crean niveles pueden verificar una ruta con el solucionador y después probarla con personas para comprobar que la idea se entiende. La guía de diseño de niveles de Sokoban explica ese proceso; este artículo explica su búsqueda subyacente.

Preguntas frecuentes del algoritmo de Sokoban

¿Qué es un algoritmo solucionador de Sokoban?

Es un procedimiento de búsqueda que representa cajas y jugador, genera empujes legales, descarta bloqueos conocidos y reconstruye una ruta cuando se cubren todas las metas.

¿Examina cada pulsación de las flechas?

Normalmente agrupa los desplazamientos en una región accesible y expande los empujes como aristas principales. Así elimina muchas rutas a pie equivalentes.

¿Por qué la poda de bloqueos acelera la búsqueda?

Descarta ramas con esquinas sin meta, grupos inmóviles y pasillos cerrados antes de gastar tiempo en sus estados posteriores.

¿La primera ruta encontrada es la más corta?

Solo si el orden de búsqueda y el modelo de costes lo garantizan. Un solucionador limitado puede devolver una ruta útil sin demostrar que minimiza los empujes o los movimientos.

¿Qué significa alcanzar el límite de búsqueda?

La herramienta agotó su presupuesto de seguridad antes de demostrar una ruta o su imposibilidad. Prueba un tablero menor o revisa el estado manualmente; el aviso no demuestra que no haya solución.

Fuentes y lecturas recomendadas

Los estados y regiones accesibles se contrastan con la referencia de solucionadores de la wiki de Sokoban. Los ejemplos de orden siguen Algoritmos básicos de búsqueda en Sokoban. Pavel Klavik trata el crecimiento del espacio de estados y las estimaciones de distancia en su documentación del solucionador de Sokoban. Son fuentes sobre Sokoban estándar; los límites de esta herramienta proceden del solucionador Zeek enlazado.

Resuelve un tablero pequeño y examina el resultado

Pega un tablero ASCII en el solucionador del navegador y vuelve para relacionar la secuencia con estados, empujes y poda.

Abrir el solucionador de Sokoban