Как найти минимальное количество ходов?

Question

Примечание: - Я решил вышеупомянутую проблему с помощью метода обратного отслеживания, пробуя различные способы, я нахожусь в поиске очень эффективного пути / шаблона.

Нам дана шахматная доскаразмер 'N' X 'N'.Но он может содержать любое количество белых квадратов и черных квадратов, которые тоже в любом порядке.

Скажем, есть 'a'-квадраты белого цвета и 'b'-квадраты черного цвета,затем

[a + b = n * n]

Мы должны продолжать делать ход с черными квадратами на шахматной доске, пока не останется хода.

Вот что происходит в движении: -

1) Мы выбираем черный квадрат в координате :-( строка, столбец) и перемещаем его в (строка-1, столбец + 1), только есликоордината (строка-1, столбец + 1) также содержит черный квадрат.После перемещения в новую позицию старая позиция, т. Е. [Строка, столбец] становится пустой, т. Е. Ее цвет становится белым.

ИЛИ

2) Мы выбираемчерный квадрат в координате :-( строка, столбец) и переместите его в (строка-1, столбец-1), только если координата (строка-1, столбец-1) также содержит черный квадрат. После того, как он перемещен в новую позицию, старая позиция, т. Е. [Строка, столбец] становится пустой, т. Е. Ее цвет становится белым.

Мы должны закончить эту игру за наименьшее количествоходы и вопрос в том, чтобы найти последовательность этих ходов.

Позволяет обозначить черный квадрат "1" и белый квадрат "0" .. ...

Пример: -

3X3 шахматная доска: -

0 1 0

1 0 1

0 0 0

Последовательность ходов, которыезаканчивает игру за минимальное количество ходов: -

1) Переместите черный квадрат на [1,0] в [0,1] ... Теперь шахматная доска выглядит следующим образом: -

0 1 0

0 0 1

0 0 0

2) Перемещаем черный квадратe на [1,2] - [0,1], и шахматная доска выглядит следующим образом: -

0 1 0

0 0 0

0 0 0

Теперь не осталось действительных ходов, и игра заканчивается: -)

Учитывая шахматную доску размером 'N' x 'N' и любую конфигурацию черных и белых квадратов, как найтипоследовательность ходов, которая завершает игру за минимальное количество ходов?

Answer 1

Один из способов просмотра этой проблемы - обход графика. Поскольку мы ищем кратчайший ход, мы можем использовать наши знания алгоритмов обхода графа и рассмотреть возможность использования обхода в ширину.

Нам понадобится сделать несколько вещей, чтобы достичь этого:

• Учитывая шахматную доску в некоторой конфигурации, вычисляет все допустимые ходы .
• Учитывая шахматную доску в некоторой конфигурации и допустимый ход, вычисляет конфигурацию шахматной доски после применения этого хода .
• Учитывая шахматную доску в некоторой конфигурации, проверьте, является ли эта конфигурация терминал (чтобы никакие другие ходы не могли быть сделаны из этой позиции, и игра окончена).

Теперь, когда у нас это есть, давайте посмотрим, как мы можем сопоставить эту проблему с проблемой обхода графа.

• Пусть исходной конфигурацией будет узел root вашего графа.
• ребер , выходящие из корневого узла, являются законными шагами, которые мы можем сделать из этой позиции.
• дочерних узлов , на которые указывают эти ребра, - это конфигурация, которая возникает в результате применения перемещения метки ребра к родительскому узлу.

Тогда процесс поиска кратчайшего пути к конечным позициям будет выглядеть так (начиная с корневого узла):

• Разверните дочерние узлы корневого узла, сгенерировав все допустимые ходы с учетом этой конфигурации.
• Проверьте каждого из детей, чтобы убедиться, что конфигурация терминала была достигнута.
• Если нет, разверните дочерние элементы в духе первого дыхания (эта ссылка от BU содержит более подробную информацию о реализации такого обхода)

Волшебство первого дыхания проходит здесь. Отсюда мы повторяем этот процесс расширения узла, проверки конфигурации терминала и понижения уровня на графике, если мы не найдем такую ​​конфигурацию.

Как только мы находим конфигурацию терминала, мы знаем, что путь (ребра, представляющие выполненные ходы) от нашего корневого узла (начальная конфигурация) до нашего терминального узла (игра закончена), является самым коротким . Все, что мы сейчас делаем, это подсчитываем количество ребер назад к корневому узлу, и мы знаем, каково минимальное количество ходов.