Через какой алгоритм решать эту задачу?

Типичная задача на поиск в пространстве состояний, см. Нильс Нильсон "Принципы искусственного интеллекта". Постановка ьипична для задач робототехники: у робота есть конечное число допустимых действий, он должен перевести задачу из одного состояния в другое.
Граф заранее строить не нужно! Находясь в вершине-состоянии можем построить соседние вершины, в данной задаче их не более 4. Как правильно было замечено выше, решение - поиск в ширину / глубину из стартового состояния с подсчётом посещённых вершин.