Юный техник 1958-03, страница 52

Любое беспорядочное расположение шашек в игре в «Пятнадцать» можно передвижением привести либ в нормальный порядок, либо к позиции, в которой шьшки 14 и 15 поменяются местами В первом случае мы имеем дело с разрешимыми задачами, во втором — с неразрешимыми.

Исход игры в «Пятнадцать» rte зависит от находчивости игрока Он точно предопределен алгоритмом, и по нему машина може^т играть с таким же успехом, как и человек

Как ни по :ажется странным, но межд" игрою в «Пятнадцать» и лабиринтом имеется большое сходство. И тут и там своеобразная игра в слова.

В самом деле, буквы, которыми мы обозначили площад-чи нашего лабиринта, образуют слово «гипотенуза». Напишем эти буквы на фишках и условимся, что при перехо ie с площадки на площадку бу-.пем менять фишки. При этом изменится и первоначальное слово «гипотенуза».

Путь в лабиринте будет отмечен такими совершенно бессмысленными словами: «игпо-тенуза», «итпогенуза», «иепогт-нуза» и так далее.

Когда наше путешествие окончится, буква Г перекочует на место буквы А, и начальное слово «гипотенуза» пре-5ратится в набор букв ИПТЕ-ОЗНУАГ.

Теперь ясно, что можно было даже не рисовать плача лабиринта, а проверить умение

находить из него выход так: написать слово «гипотенуза» и указать допустимый порядок перемены местами буКЕ Менять можно буквы площадок, соединенных коридорами. Например, Г на И и О. Букву И на П и Т и так далее.

Выход из лабиринта будет найден, когда, соблюдая э^-от порядок, буква Г окажется на месте буквл! А. Задачу можно решить с помощью того же алгоритма, по которому мы искали путь в лабиринте. А по указаниям руководства к действию это сделает и машина.

Меняя буквы в словах, она искала бы путь в лабиринте и в конце концов получила бь, «слово», оканчивающееся буквой Г, — нашла бы выход из лабиринта.

Теперь превратим игру в «Пя ,-надцать» в лабиринт слов. Напишите на шашках вместо цифр буквы и расставьте их так, чтобы образовались следующее слова: «февраль», «быт», «жди», «ус». Как видите, пятнадцать буки и при этом все разные. Попробуйте передвижением шашек получить из них слова «фестиваль дружбы». В них тоже пятнадцать буке Но сделать вам это никогда не удастся, ибо здесь потребуется нечетное число пересано-вок шашек с буквами — одиннадцать. Передвижкой преобразовать одну комбинацию слов в другую невозможно.

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

42