Исходник программы, показывающей пример создания головоломки о том, как помочь фермеру безопасно переправить лису, утку и кукурузу через реку.
Фермер везет на рынок лису, утку и кукурузу. Но к сожалению, он застрял на левом берегу широкой реки. Хорошая новость состоит в том, что у него есть лодка. Однако, есть и плохая: она заключается в том, что лодка будет удерживать только его и еще один предмет для каждого перехода через реку.
Фермер не может оставить утку наедине с кукурузой (кукурузу съедят) или утку наедине с лисой (утку съедят). Кроме того, фермер знает из предыдущего опыта, что он не может оставить одну кукурузу на правом берегу реки, так как стая ворон ждет, чтобы ее съесть.
В игре необходимо помочь фермеру безопасно переправить всех через реку.
Описание алгоритма
Я решил представить состояние головоломки, используя четыре младших бита байтовой переменной состояния: 8 = лодка (и фермер), 4 = лиса, 2 = утка и 1 = кукуруза. Для каждого из них значение 0 означает левый берег, а 1 означает правый берег. Таким образом, мы сразу видим, что существует 16 возможных состояний 0 (двоичный 0000), представляющих начальную позицию со всем слева до выигрышной позиции, 15 (двоичная 1111), когда все находится на правом берегу.
С помощью этой системы мы можем идентифицировать допустимые переходы между состояниями, необходимые, когда компьютер ищет решение. Из нашего текущего состояния мы можем перевернуть только 8 бит (отправить лодку самостоятельно) или перевернуть 8 бит и один другой бит (отправить лодку на другой берег с одним объектом). Эти допустимые переходы хранятся в логическом массиве 16X16 Moves, где первый индекс представляет состояние «из», а второй индекс представляет состояние «в». Итак, если мы отправим лодку и утку из исходного состояния, State изменится с 0 на 10 (8 бит плюс 2 бита), а move [0,10] будет содержать значение «true», говорящее нам, что это действительный ход.
Логический массив Loser идентифицирует состояния с проигрышными позициями. Например, 6 (двоичный код 0110) представляет собой только лису и утку на правом берегу, определенно нет-нет. Для поиска программного решения мы просто никогда не переходим к состоянию N, если loser [N] истинно. В пользовательской игре мы сообщим игроку, что он проиграл и почему, если он переходит в проигрышную позицию.
Еще один логический массив из 16 записей, Visited, отслеживает состояния, которые мы посетили во время фазы программного решения, чтобы избежать зацикливания (человек-игрок может зацикливаться столько, сколько хочет).
Биты можно включить, добавив 1,2,4 или 8, если вы знаете, что бит не включен. Точно так же их можно отключить, вычтя 1,2,4 или 8, если вы уверены, что бит включен. Если бит необходимо установить в 1 независимо от его текущего состояния, можно использовать ИЛИ. N OR 8 включит 8 бит и оставит другие биты без изменений. Чтобы немного выключить, И поле с маской, имеющее 0 в битовых позициях, которые нужно выключить, и 1 везде. Так, например, N AND 7 отключит 8 бит. Чтобы немного перевернуть, операция «исключающее ИЛИ», XOR, сделает свое дело. Маске в этом случае нужно перевернуть единицы в битовых позициях. N XOR 8 перевернет 8 бит с 0 на 1 или с 1 на 0. Биты могут быть проверены в цикле, установив маску на 1 и используя SHL (сдвиг влево), чтобы переместить тестируемую позицию на одну позицию влево каждый раз через цикл.
Базы данных
