← Volver a los ejercicios

El grafo de estados por capas

La capa k reúne los estados que están a k pasos de (1, {1}): los que se alcanzan desde la capa k - 1 con un movimiento o con un cambio de luz y no aparecieron antes. Se predice una capa a la vez marcando sus estados en la rejilla: cada fila es la habitación donde se está y cada columna, un conjunto de luces prendidas. Al comprobar se ve qué faltó y qué sobró, con la razón. Cuando una capa sale vacía, la búsqueda se agotó.

La villa

Puertas:
Interruptores:
Se parte de (1, {1}) y la meta es .

Capa 1

Las capas confirmadas

Todavía ninguna. La capa 0 es solo (1, {1}).