Всем привет, меня зовут Андрей, это снова я!
Хотя в заголовке игры и говорится про Эксель, информация, которая содержится в данной статье, пригодится всем, кто играет в Pusher, независимо от того, будет ли у читателя моего канала возможность и желание реализовывать все эти идеи на компьютере. Так, например. в статье содержится информация о том, как быстро найти "тупиковые" ситуации или постараться не допустить "тупиковых" ситуаций совсем.
Итак, давайте попробуем написать такой макрос, который научил бы эксель играть в Pusher. Для тех, кто не в курсе, что такое Pusher, скажу: это логическая игра, в которой надо передвигать ящики на определенные места в ограниченном пространстве, и приведу в качестве примера несколько картинок:
Часто сами элементы игры в разных версиях игры выглядят по-разному.
Так, например, иногда игровые картинки могут выглядеть так (в галерее приведено несколько примеров):
Но неизменным всегда остается одно: перечень основных элементов игры, а именно: стены (которые двигать нельзя и по которым (через которые) проходить нельзя, ящики (которые надо передвигать на свои места), персонаж (грузчик, который передвигает ящики), просто пустые места, а также такие места, на которые нужно передвинуть ящики. Если мы передвинули все ящики на свои места - то это значит, что данный уровень игры пройден.
В нашем конкретном примере:
ящики не на местах - это квадраты серого цвета;
ящики на местах - это квадраты оранжевого цвета;
пустые места для ящиков - это оранжевые крестики.
Итак, цель игры – передвинуть ящики на свои места. Нельзя сказать, что каждому ящику уготовано какое-то одно конкретное место, часто бывает так, что ящик, прежде, чем попасть на свое конечное место, может проходить не только через пустые клетки, но и через разные "места для ящика" - через те места, которые в конечной позиции будут заняты другими ящиками. В конечной позиции любой ящик может занимать любое место, предназначенное для ящика. В процессе игры можно сдвигать ящик с "места для ящика" как на пустые места, так и на другие "места для ящика". Главная проблема и главная сложность заключается в том, что игровое место (пространство) ограничено. Можно двигать ящик только тогда, когда за ящиком есть свободное место.
Самая короткая игра, которая может быть в принципе, состоит из одного-единственного хода:
Здесь всего один вариант: переместить ящик вправо, на крестик, и этот уровень будет пройден.
Но чаще всего в игре бывают более сложные ситуации, и не всегда удается быстро найти правильное решение уровня.
Если мы хотим привлечь макросы к решению задачи, то вначале нужно будет определиться, какие именно цифры будут обозначать те или иные элементы игры. К примеру:
1 – это стена (в основном бывает по периметру, но часто и внутри картинки тоже;
2 – это ящики не на месте, которые нужно двигать;
3 – это просто пустые места;
4 – это ящики на месте;
5 – это те пустые места, куда надо поставить ящик;
6 – это сам персонаж (грузчик), который толкает ящики.
Если персонаж оказывается на пустом месте "для ящика", то для этой ячейки будем применять шифр "6", потому что ситуации без персонажа быть не может, а главное в этой ситуации будет в том, что не все ящики находятся на своих местах (когда грузчик занимает "место для ящика", то это автоматически означает, что есть как минимум один ящик, который находится не на месте). То есть: при наложении цифр 3 и 6 [что означает "пустое место" и "грузчик"] (или 5 и 6 [место для ящика и грузчик]) всегда "побеждает" цифра 6, то есть "грузчик".
Итак, при ситуации, когда персонаж находится на месте для ящика, должен быть хотя бы один ящик, который не на месте (у него будет код 2). И, таким образом, вся игра будет сводиться к тому, что нам нужно избавиться от всех двоек (это ящики не на месте). Не надо ставить ситуацию "избавиться от всех пятерок" (занять все места для ящиков", потому что если останется один ящик на пустом месте, а на "место для ящика" встанет сам персонаж, тогда у нас не будет ни одной пятерки, но при этом ситуация будет не конечной, не решенной.
Таким образом, та ситуация, о который мы говорили ранее (та, которая решается в 1 ход), будет выглядеть так:
После того, как мы единственным возможным ходом подвинем ящик на свободное место, все три цифры (кроме единиц, которые символизируют стены), поменяют свои значения, и мы получим:
Можно даже применить условное форматирование, чтобы было более удобно оценивать ситуацию. Например, все стены (1) - это черный фон и черный текст; все пустые места (3) - это белый фон и белый текст; ящики не на месте (2) - это бледно-красный фон и такой же текст; ящики на месте (4) - это зеленый фон и текст; пустые места для ящиков (5) - это зеленый текст и бледно-желтый фон. Персонажа можно оставить "как есть".
Тогда две предыдущие картинки, которые мы недавно показали, будут выглядеть так (ниже представлена галерея из двух картинок):
Итак, уже на данном этапе можно определить основные правила игры, по которым макрос будет делать ходы или проверять, есть ли вообще ходы для персонажа в ту или иную сторону, и не сложилась ли просто тупиковая ситуация, при которой ходы для персонажа есть, но ящики стоят так, что подвинуть на нужные места их просто не получится никогда. Обозначим все возможные ситуации, применяя те самые цифры от 1 до 6, о которых мы уже говорили ранее:
Вначале рассмотрим ситуации, когда невозможно движение вправо, и те цифры, что стоят подряд в одной строке:
1) 61 (то есть: если правее персонажа стена), то это значит, что вправо идти нельзя (вправо хода нет);
2) 622, 624, 642, 644, 641 или 621 (то есть: справа от персонажа 2 ящика подряд, или ящик, а за ним стена), то это значит, что вправо хода нет;
Некоторые рисунки в приведенной выше галерее содержат тупиковые ситуации, но данные рисунки не про тупики, а про возможность или невозможность сделать один ход вправо.
Далее рассмотрим все основные ситуации, при которых ход вправо возможен (на всех рисунках приведена начальная позиция, до возможного хода):
1) 63 (то есть: справа от персонажа пустое место). Это значит, что ход возможен, сразу после хода 3 и 6 меняются местами (63…36). Но надо иметь ввиду: если до этого хода персонаж стоял не на пустом месте, а на "месте для ящика", тогда 63 превратится не в 36, а в 56. Итак, 63...36 (56).
2) 623 (то есть: справа от персонажа ящик, который не на месте, а за ним – пустое место). После того, как мы подвинем этот ящик вправо, ситуация изменится: 362 (пустое место, затем персонаж, затем ящик). Итак, 623…362.
Здесь тоже надо иметь ввиду: если персонаж до хода вправо стоял не на пустом месте, а на "месте для ящика", тогда 623 превратится в 562. Итак, 623...362 (562).
Далее все возможные ситуации будем приводить только в виде кодов. ситуации будут приводиться в скобках без комментариев, ведь мы уже разобрали подробно, что означает каждая из цифр.
3) 643...362 (562).
Эта ситуация интересна тем, что хотя вправо, в принципе, ход возможен, но он приведет к тупику (к ситуации, при которой нельзя получить конечный результат). О тупиках мы еще раз поговорим более подробно позже, пока лишь скажем только то, что при той ситуации, что изображена на рисунке, ход вправо возможен. Конечно же, если при построении алгоритма и программы для решения ситуаций мы сначала будем проверять не просто "возможен ли ход вообще", а "возможен ли такой ход, который не приведет к "тупику", тогда нам придется ввести как минимум еще одну цифру в наш алгоритм, например, цифру 7, и она будет означать такую пустую клетку, что при попадании ящика на нее точно образуется тупик. Но особенность тупиков в том, что не всегда можно увидеть такую клетку, бывает еще и так, что несколько ящиков подряд, расположенных не правильно, создают тупик на том месте, на котором при другом расположении ящиков тупика бы не было. Но есть, конечно, и такие места на поле, когда сразу видно, что нахождение одного ящика приводит к тупику. Поэтому не всегда можно определить полный перечень тех клеток, нахождение на которых ящика означает тупик, часто бывает и так, что создаются новые тупиковые ситуации, которые создаются неправильным расположением многих других ящиков. Но более подробно ситуации с тупиками мы рассмотрим позже.
6) 645...364 (564).
7) 65...36 (56).
В принципе, самые основные ситуации мы разобрали, других быть не должно.
Далее рассмотрим движение вниз. Ситуация аналогична той, что мы рассмотрели недавно, но все сочетания цифр, что мы рассмотрели, будут расположены не слева направо, а сверху вниз. Да и ситуации, будут в принципе, те же, но просто они будут повернуты на 90 градусов вправо. Например, ситуация, при которой те же цифры 6 и 1, будут рядом, но при этом, цифра 6 будет не левее единицы, а выше единицы, и это будет означать, что хода нет, но на этот раз хода нет не вправо, а вниз:
В предыдущем списке были числа 622, 624, 644, 641 и 621. При движении вниз шестерка будет вверху, все остальные цифры будут под шестеркой. В той же последовательности, что и при движении вправо, но в другом направлении. То, что было расположено слева направо, теперь будет сверху вниз.
Ситуации эти мы показывать не будем, потому что все они очень похожи на те, что мы уже рассмотрели, только картинки повернуты на 90 градусов вправо.
Далее аналогичным образом разберем все возможные и невозможные ходы влево, а затем и вверх. Они тоже будут похожи на те ситуации, что мы рассмотрели, только при движении влево те же цифры будут расположены справа налево, и при движении вверх - снизу вверх.
После того, как мы рассмотрели возможность или невозможность хода на каждом из этапов, а также подобно разобрали, как именно изменятся все цифры, характеризующие позицию на игровом поле после каждого возможного хода, нужно будет выяснить, при каких ситуациях складывается «тупик» - а именно: ситуация, при которой невозможно получить конечную позицию..
Варианты тупика:
1. Ящик в углу и не на месте.
Конечно же, ящик в любом другом углу, а не только в правом нижнем, представляет собой тупиковую ситуацию. Кроме, конечно, тех случаев, когда угол - это и есть та точка, куда нужно поставить ящик.
2. 4 ящика стоят рядом, (образуют квадратик 2 х 2), но при этом хотя бы один ящик находится не на конечном месте.
В приведенном примере - только частный случай, что касается других случаев, то четыре ящика, стоящих подряд квадратиком 2 х 2, могут представлять собой не тупик только тогда, когда все 4 ящика стоят на своих конечных местах.
3. Два ящика и два кирпичика стены образуют блок, аналогичный тому, о котором говорилось в предыдущем пункте.
В приведенном выше примере не только "нет хода вправо", а просто тупик, то есть: ситуация, при которой к конечному результату прийти невозможно вообще никак. Два ящика сразу подряд нельзя никуда двигать, между двумя стоящими подряд ящиками пройти нельзя, между стеной и ящиком пройти тоже нельзя.
Кроме того, здесь изображен только частный случай. В любой другой ситуации, при которой ящики и стены образуют квадратик 2*2, причем может быть как 3 стены (один кирпич), так и 2, 3, или 4 кирпича, если при этом хотя бы один кирпич стоит не на конечном месте, то это считается "тупиком".
4. Два ящика стоят почти в углу, если при этом хотя бы один из ящиков стоит не на месте для ящика,то это тупик:
Вариант 4 тупика - это только частный случай. У нас "в плену" оказалась правая нижняя клеточка. Если по такому же принципу "в плену" окажется целая группа пустых клеточек шириной (или высотой) в одну клетку, или группа пустых клеток 2 на 2, то это тоже будет тупик. Есть и несколько других вариантов, но их объединяет одно: "в плену", "взаперти" оказывается какое-то свободное поле, ограниченное со всех четырех сторон ящиками и стенами. При этом, если бы все ящики, которые входят в периметр того свободного пространства, стояли бы на нужных местах, то это не считалось бы тупиком. В нашем примере подобная ситуация сложилась в левом нижнем углу картинки под названием "Вариант 4 тупика".
Еще один вид "тупика" - два кубика и две стены-точки, например:
Возможны и другие вариации этой ситуации, если перебирать отражения и повороты, но принцип останется прежним. Главное в том, чтобы сами кубики-стены были по бокам и на разных уровнях, кубики-кирпичи должны быть только между ними, и хотя бы один из кубиков при этом должен быть не на месте.
Есть и еще один вид тупика. Мы про это уже говорили, когда рассматривали ситуацию "643", когда вправо ход был возможен, но он привел бы к "тупику". Если рядом со стенами только пустые клетки, то мы получим ближайший к стене проход. Если этот проход с трех сторон окружен стенами и в самом проходе нет ни одного конечного места для ящика, то любое нахождение ящика в этом проходе приведет к тупиковой ситуации. Можно привести ту же картинку, что у нас уже была раньше (вариант 3 тупика), но добавить пометки на те пустые клетки, в которых не должно быть ящиков, потому что ящики в этих клетках приведут к тупику:
Хотя в приведенной выше ситуации тупик, решений нет, но можно увидеть все те клетки (они выделены бордовым цветом), в которых не должно быть ящиков, но может быть сам персонаж. Попади ящик на любую из бордовых клеток, это будет означать тупик.
4. Два ящика (или больше двух) расположены так, что любое движение ящика приведет к тупику. Следовательно, уже на данном этапе можно сказать, что мы находимся в тупике. Вот пример такой ситуации:
В принципе, приведенный выше пример очень похож на "вариант 4 тупика", но "в плену" оказываются не одна, а несколько пустых клеток.
В общем, как-то так. Чтобы научить Эксель играть в пушер, нужно разработать алгоритм, согласно которому Эксель будет находить нужный конечный вариант расстановки ящиков.
Примерный алгоритм будет следующий:
1) Ввести в ячейки текущего листа цифры от 1 до 6, символизирующие разных персонажей.
2) Запросить (и ввести) исходные данные - количество ячеек в ширину и в длину.
3) Запомнить как исходную ситуацию в целом, так и конечные места для ящиков, независимо от того, они заняты ящиками или свободны в начальной позиции.
4) Уточнить, какие именно комбинации цифр означают возможность хода в ту или иную сторону, а какие комбинации означают невозможность хода в одну из сторон, а какие комбинации цифр означают тупиковую ситуацию.
5) Уточнить, как именно будут меняться все комбинации цифр при каждом ходе.
6) Найти первый возможный ход, в отдельном месте записывать все ходы; если какой-то ход невозможен или приводит к тупику, то сделать ход назад и искать новый ход, при этом стереть тот неверный ход из того массива, в котором ведется запись ходов.
7) Перебирать цепочки из нескольких ходов (например, ВЛНП, где В-верх; Н-низ; Л-лево; П-право) подряд, до тех пор, пока не получится ситуация, при которой все ящики стоят на месте.
8) Отобразить ту комбинацию ходов, которая приведет к победе.
А о том, как это всё реализовать в виде макроса, я расскажу в одной из следующих статей.
