Загорается игровой алгоритм

Это домашнее задание. Я должен разработать и выключить игру, используя описание обратного отслеживания ниже.

Игра состоит из сетки 5-на-5; при запуске игры включается набор этих огней (случайный или один из набора сохраненных паттернов головоломки). Нажатие одного из огней приведет к включению и выключению четырех огней рядом с ним. (Диагональные соседи не затронуты.) Игра представляет собой загадку: если у вас есть какая-то первоначальная конфигурация, в которой некоторые огни включены, а некоторые выключены, цель состоит в том, чтобы выключить все световые сигналы, желательно как можно меньше кнопок.

Мой подход идет от 1 до 25 и проверяет, выключены ли все огни или нет. Если нет, то я проверю от 1 до 24 и так далее, пока не дойду до 1 или не найду решение. Нет, если нет решения, тогда я начну с 2 до 24 и следую описанному выше процессу до достижения 2 или найденного решения.

Но через это я не получаю результат? например, свет в (0,0) (1,1) (2,2) (3,3) (4,4) включен?

Если кому-то нужен код, я могу его опубликовать.

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

Благодарю.

    Существует стандартный алгоритм решения этой проблемы, основанный на гауссовском исключении над GF (2). Идея состоит в том, чтобы настроить матрицу, представляющую кнопку, нажимающую вектор-столбец, представляющий свет, а затем использовать стандартные методы упрощения матрицы, чтобы определить, какие кнопки нажать. Он работает в полиномиальное время и не требует никакого возврата.

    У меня есть реализация этого алгоритма, который включает в себя математическое описание того, как он работает на моем личном сайте. Надеюсь, вы сочтете это полезным!

    Изменить : если вы вынуждены использовать обратную трассировку, вы можете использовать следующие факты:

    • Любое решение никогда не будет нажимать одну и ту же кнопку дважды, так как это приведет к отмене предыдущего шага.
    • Любое решение либо нажимает первую кнопку, либо нет.

    Учитывая этот подход, вы можете решить это с помощью обратного трассировки с использованием простого рекурсивного алгоритма, который отслеживает текущее состояние платы и какие кнопки вы уже принимали решения:

    • Если вы решили о каждой кнопке, то верните, разрешена ли доска или нет.
    • В противном случае:
      • Попробуйте нажать следующую кнопку и посмотреть, разрешена ли recursion.
      • Если да, верните успех.
      • В противном случае попробуйте не нажимать следующую кнопку и видеть, разрешена ли репликация платы там.
      • Если да, верните успех. Если нет, верните сбой.

    Это позволит исследовать пространство поиска размером 2 25 , что составляет около 32 миллионов. Это большой, но не непреодолимо большой.

    Надеюсь это поможет!

    Возврат:

    Incrementally build a solution, throwing away impossible solutions. 

    Вот один из подходов, основанный на том, что существует локальность входов и выходов (нажатие кнопки влияет на квадрат вокруг него).

     problem = GIVEN solutions = [[0],[1]] // array of binary matrix answers (two entries, a zero and a one) for (problemSize = 1; problemSize <= 5; problemSize++) { newSolutions = []; foreach (solutions as oldSolution) { candidateSolutions = arrayOfNByNMatriciesWithMatrixAtTopLeft(min(5,problemSize+1), oldSolution); // size of candidateSolutions is 2^((problemSize+1)^2 - problemSize^2) // except last round candidateSolutions == solutions foreach (candidateSolutions as candidateSolution) { candidateProblem = boardFromPressingButtonsInSolution(candidateSolution); if (compareMatrix(problem, candidateProblem, 0, 0, problemSize, problemSize)==0) newSolutions[] = candidateSolution; } } solutions = newSolutions; } return solutions; 

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

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

     Let Aij = Light ij Toggled { Aij = 0 or 1 } 

    Должно быть 25 таких переменных.

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

     summation (Amn) = 0. { Amn = 5 light buttons that toggle the light mn } 

    Таким образом, у вас будет 25 переменных и 25 неизвестных. Вы можете решить эти уравнения одновременно.

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

    Наивное решение

    Во-первых, вам понадобится способ представления состояния платы и стека для хранения всех состояний. На каждом шаге сделайте копию доски, измененную на новое состояние. Сравните это состояние со всеми состояниями доски, с которыми вы столкнулись. Если вы его не видели, нажмите это состояние поверх стека и перейдите к следующему шагу. Если вы его видели, попробуйте следующий шаг. Каждый уровень должен будет попробовать все возможные 64 хода перед тем, как вытащить состояние из стека (backtracking). Вы захотите использовать рекурсию для управления состоянием следующего перехода для проверки.

    Существует не более 2 64 возможных конфигураций плат, а это значит, что вы можете пойти на очень длинную цепочку уникальных состояний и по-прежнему исчерпать память. (Для справки, 1 ГБ составляет 2 30 байт, и для хранения конфигурации платы требуется минимум 8 байтов). Этот алгоритм вряд ли завершится в течение жизни известного юниверса.

    Вам нужно сделать что-то умное, чтобы сократить пространство поиска …

    Жадный первый поиск

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

    Не все загадки головоломки разрешаются

    Независимо от того, какой алгоритм вы используете, может не быть решения, то есть вы можете искать навсегда (или, по крайней мере, несколько триллионов лет), не найдя решения.

    Вы захотите проверить плату за разрешимость (что намного быстрее, чем выясняется), прежде чем тратить время на поиск решения.

    Interesting Posts

    Как настроить прокси-сервер на XP для тестирования программного обеспечения?

    Страница непрерывной петли (не бесконечный свиток)

    В C #, почему String является ссылочным типом, который ведет себя как тип значения?

    VPN-соединение с VirtualBox

    Сохранение любого файла в базе данных, просто преобразование его в массив байтов?

    Java lib или приложение для преобразования CSV в XML-файл?

    Где на моем компьютере Wget загрузил это изображение?

    WPF привязка к локальной переменной

    Нужно ли закрывать каждый вложенный OutputStream и Writer отдельно?

    Требует ли JSONP модификации сервера?

    Наибольшее и наименьшее число в массиве

    Время и время анализа в нескольких форматах

    Каково максимальное количество разделов, которые можно сделать на жестком диске?

    Деление плавающей запятой в пакетном файле

    Как добавить самозаверяющий сертификат в качестве исключения в Chrome?

    Давайте будем гением компьютера.