Rejulla rectangular: Sobre una rejilla, cada estado tiene cuatro sucesores, entonces el árbol de búsqueda, incluyendo estados repetidos, tiene 4 d hojas; pero hay sólo 2d 2 estados distintos en dpasos desde cualquier estado. Para d = 20, significa aproximadamente
un billón de nodos, pero aproximadamente 800 estados distintos.