Давайте сделаем так, чтобы в конце игры над таблицей написалось, за какое минимальное количество ходов можно было выиграть.
Если хорошенько обдумать вопрос, то можно придумать несложный алгоритм, как определить указанное.
Реализуйте поставленную задачу. Задача со звездочкой - можно пропустить:)