КОМПЬЮТЕРРА


"Палатки" (HELP) 

Автор: Ольга Леонтьева, 9360.g23@g23.relcom.ru
Дата публикации:18.09.2000

Соавторство: Константин Кноп


1767.gif (376 bytes)

Эта головоломка придумана в Голландии и в последние годы также частенько встречалась на разных соревнованиях. Как правило, ее условия достаточно стандартны: таблица 10х10 представляет собой план леса, в котором указано положение 20 деревьев. К каждому дереву надо привязать свою палатку (в клетку, касающуюся клетки дерева стороной), всего ровно 20 палаток. Клетки с палатками не должны касаться (даже углом), а числа, как и в других аналогичных пазлах, обозначают количество клеток, занятых искомыми объектами (в данном случае, палатками), в соответствующей строке или столбце.

1767.gif (376 bytes)
Рассмотрим, как обычно, решение головоломки на конкретном примере.

1761.gif (6002 bytes)

На рисунке слева изображено условие задачи. Занумеруем строки и столбцы. Будем в дальнейшем обозначать темно-зеленым цветом те клетки, в которых палатки находиться не могут.

В ''палатках'', как, пожалуй, ни в какой другой головоломке, следует проявлять внимание и аккуратность при каждом шаге. Ошибки могут возникать по самым разным причинам. Возможно неполное логическое исследование: кажется, что для имеющихся данных существуют возможности А или Б, но Б исключается по таким-то соображениям, значит, возможно только А. Но при этом не замечается, что для имеющихся данных есть возможности и В, и Г. Или из-за невнимательного взгляда информация представляется искаженной - остаются незамеченными некоторые пустые (или заполненные) клетки, упускаются из виду касания, и т.д. Разумеется, то же самое можно сказать и про другие пазлы, просто в палатках такие ошибки, вынуждающие начинать решение сначала, наиболее часты.

1762.gif (6520 bytes)

Можно сразу отметить темно-зеленым клетки, которые не имеют общей стороны с клетками деревьев - в них палатки отсутствуют. Рассмотрим столбец j: в нем две палатки. При этом в j6 и j4 палатки одновременно быть не могут (так как они принадлежали бы одному дереву на j5). Поэтому палатка точно стоит на j2, и относится она к дереву на i2. Отмечаем темно-зеленым все клетки вокруг этой палатки. В столбце i должно быть две палатки, по одной в блоке из двух возможных клеток. В нижнем блоке в i5 палатка быть не может (так как от j5 палатка должна отходить вертикально), значит, отмечаем палатку в i4, отмечаем темно-зеленым клетки вокруг нее, и убеждаемся, что около дерева j5 палатка может стоять только сверху.

1763.gif (6886 bytes)

Рассмотрим строку 1. В ней три свободных места - как раз для трех палаток. Палатка в столбце е может быть привязана только к дереву d1, значит, палатка на с1 связана с деревом с2, а палатка g1 может относиться лишь к h1 (иначе этому дереву не соответствует ничего). В строке 2 вторая палатка может быть лишь на а2 и связыватьяс с деревом а3. Отметим также на g3 палатку, принадлежащую дереву на g2 (единственно возможное место для палатки).

1764.gif (7072 bytes)

Заполняем темно-зеленым строку 3 (единственная палатка в ней уже найдена). Присоединяем к дереву d3 палатку сверху (больше неоткуда), и отмечаем темно-зеленым остальные клетки столбца d. Этот столбец разделил ''лес'' на две вертикальные части. В трех левых столбцах (a, b и c) шесть деревьев, но палаток должно быть семь. Поэтому для дерева d10 палатка должна стоять на с10. Отмечаем клетки вокруг этой палатки, и ставим на а10 единственно возможную палатку, связанную с деревом b10.

1765.gif (7191 bytes)

Кстати, у нас уже давным-давно заполнен столбец g (в нем поставлены обе его палатки). В таких задачах это - естественное явление, когда следующий ход может делаться многими способами.

От дерева на b6 палатка не может быть ни снизу (тогда у дерева на а5 нет палатки), ни слева (тогда от дерева на а5 палатка может идти лишь вниз, и в столбце а будет перебор - четыре палатки), ни сверху (тогда палатки нет для дерева на с8). То есть палатка может идти лишь вправо на с6, а от дерева на с8 - тогда только влево на b8. Отмечаем новые темно-зеленые клетки. Ставим на f5 единственную возможную палатку в строке 5.

1766.gif (7313 bytes)

Осталось сделать последний рывок в решении. Из дерева на а5 строим палатку вниз (третью в строке 4), из дерева на g6 - единственным возможным способом вправо, а из g7 - влево. Оставшиеся палатки расставляем также единственным возможным способом: от дерева на h8 - вправо на i8, от дерева на h9 - вверх на h10, и от дерева на f9 - влево на е9. Все сошлось, задача решена.