Sokoban es un clásico puzzle de puzle de los años 80 en el que el jugador empuja cada caja hasta una casilla objetivo. La variante publicada por Menachem Kornreich añade una regla adicional: el portero también debe terminar sobre una meta, de modo que cada tablero tiene una meta más que cajas. Los controles disponibles son las teclas de flecha, W A S D o el panel en pantalla, con deshacer y reinicio.
El objetivo es alcanzar ese estado en el menor número de movimientos posible. Para varios tableros se muestra el número óptimo de movimientos. En los niveles 1 a 14, un solver de A basado en macros de empuje —donde cada arista es un empujón completo de una caja, costeado como el camino más corto del portero hasta el punto de empuje más uno— devuelve la solución probadamente óptima. Para acelerar la búsqueda, las cajas se empaquetan en una máscara de bits compacta y el portero en un entero adicional, de modo que cada estado ocupa unos 8 bytes en lugar de un objeto de ~1 KB. La frontera de A utiliza una cola tipo dial y un conjunto de visitados implementado como tabla hash de direccionamiento abierto, con poda mediante casillas muertas y una cota inferior consciente de paredes.
El tablero 15 es la excepción: su búsqueda óptima exploraría unos 49 millones de estados y necesitaría más de 1 GB de memoria. Su óptimo, 184 movimientos, se calculó offline con una versión C++ nativa paralela del mismo algoritmo y se verifica por reproducción; la página solo lo reproduce.