Пример задачи
Давайте рассмотрим другой пример, чтобы проиллюстрировать, как выбор соответствующего представления может упростить поиск решений более сложной задачи.
Как и в игре крестики-нолики, задача здесь начинается с матрицы 3х3, но в этой задаче, клетки занимают квадратные яблоки.
Давайте назовем это задачей квадратных яблок.
Люди на самом деле могут вырастить квадратные яблоки или даже квадратные арбузы.
Предположим, что в исходном состоянии этой задачи существует червь в средней ячейке.
Вопрос в том, может ли червь съесть все яблоки, выполнив следующие два правила.
Во-первых, после того, как червь закончил целое яблоко в текущей ячейке, он может двигаться только в другую ячейку, которую разделяет общая сторона, так что эти стрелки показывают 4 возможных хода и 2-е правило состоит в том, что вы не можете переместиться в ту ячейку, которую посещали прежде.
То есть, червь может двигаться только в ячейку, где есть еще несъеденное яблоко внутри.
Рисунок показывает, что червь начинает с середины. После того, как заканчивается среднее яблоко, он может двигаться в одну из четырех клеток на стороне, но не в углу. Таким образом, червь может двигаться вправо, двигаться вниз, двигаться влево и двигаться вверх.
Я хочу, чтобы вы подумали, есть ли решение этой задачи.
То есть, может ли червь съесть все 9 яблок.
Это должно быть совершенно очевидно.
Здесь часть пространства состояний графа и это возможный путь, который может привести к решению.
На самом деле, вы обнаружите, что есть 7 других пути для решения, пробуя другие ходы.
Можно написать программу Java, которая была бы создана для решения этой задачи.
И после прочтения этой книги, вы должны быть в состоянии написать собственную программу для решения таких задач, как эта.
Это демо-программа, которая была написана для вас, чтобы проиллюстрировать решение задачи квадратного яблока.
Задача будет начинаться с червем в середине. Червь настигает яблоко, перемещаясь в другую ячейку.
Отображая условие – не посещать клетки, которые были захвачены ранее, цифры показывают последовательность шагов.
Программа также отображает последовательность шагов в другом окне.
Таким образом, вы можете видеть, что есть в общей сложности 8 решений, как обсуждалось ранее.
Давайте теперь посмотрим на 3D-версию задачи. Задача в основном такая же, как и раньше, за исключением того, что у вас есть 3x3x3 куб как кубик Рубика и с квадратным яблоком в каждой ячейке.
То есть, есть в общей сложности, есть 27 яблок. Чтобы помочь вам визуализировать проблему, диаграмма здесь отображает куб в три слоя.
Подобно тому, что у нас было раньше, червь прячется в середине, и мы должны следовать тем же правилам.
То есть, в начале, есть 6 возможных ходов, вместо 4, как в случае 2D, потому что в дополнение к 4 ячейкам на сторонах в среднем слое, червь также может перейти к средней ячейке на переднем плане и средней ячейке на заднем плане.
И теперь вопрос в том, может ли червь по-прежнему съесть все 27 яблок.
Помните, что червь не может вернуться к любым тем ячейкам, которые были захвачены ранее.
Давайте теперь вернемся и посмотрим на 2D-задачу немного по-другому. Некоторые из красных яблок заменены на зеленые яблоки, и они расположены по такой схеме.
Если червь опять должен начать с середины, следуя тем же правилам, это та же задача, как и раньше, независимо от цвета яблок, и у нас есть те же 8 решений, как и в предыдущем случае 2D.
Теперь рассмотрим, что, если вместо того, чтобы начать с середины, червь начинает с одной из ячеек на стороне, а все другие правила те же самые.
Подсказка в том, что надо посмотреть, как меняется цвет, когда червь переходит из одного яблока в другое.
Давайте теперь вернемся к задаче квадратных яблок 3D и будем чередовать цвета яблок, как мы сделали это в 2D случае.
Как и в предыдущем 3D случае червь прячется в середине.
Так что это все та же 3D задача, как и раньше, хотя цвета некоторых из яблок были изменены.
Теперь используйте то, что вы наблюдали в случае 2D, и попытайтесь придумать быстрое решение этой задачи.