КОМПЬЮТЕРРА


"Числовые ломаные" (HELP) 

Автор: Константин Кноп, Konstantin@Knop.com
Дата публикации:09.09.2000


Числовые ломаные

Эта головоломка (как и многие другие подобные занимательные задачки) пришла к нам из Японии. Ее английское название - Number Lines, то есть "числовые линии". Ну, а я предпочитаю называть эти задачки "числовыми ломаными", потому что это лучше отражает суть.

Итак, что же это за фрукт? Общие правила для всех таких головоломок следующие:

В некоторых клетках таблички (а размеры у табличек бывают разные - 10x10, 12x16, 15x20 или даже больше) стоят числа от 0 до 3. Требуется провести по границам клеток одну несамопересекающуюся замкнутую ломаную так, чтобы с каждой клеткой ломаная граничила ровно столько раз, какое число стоит внутри клетки.

Ниже мы очень подробно на небольшом примере (5x5) разберем некоторые базовые приемы, помогающие в решении таких головоломок. Разумеется, есть и другие полезные приемы и "правила" - но всех таких правил не знает никто, так что почему бы не предоставить читателям возможность переоткрыть часть таких правил самостоятельно?

Пример

1373.gif (1907 bytes)

Условие задачи изображено на рисунке слева. Проведенные линии мы будем помечать черным цветом.

1374.gif (1985 bytes)

Те места, где линий быть не может, мы тоже будем выделять цветом - например, желтым. Для начала отметим желтым все границы вокруг клетки "0": ведь 0 по условию означает, что линий вокруг клетки нет.

1375.gif (2054 bytes)

Теперь обратим внимание на цифру 3 рядом с нулем. "3" означает, что только по одной стороне (из четырех) не проходит линия. Поскольку эту сторону мы уже знаем, то около каждой из трех остальных сторон можем нарисовать линию (давайте договоримся свежепроведенные линии рисовать красным цветом, а на следующих рисунках изображать их уже черными).

1376.gif (2098 bytes)

Подумаем, как можно продолжить уже нарисованные черные отрезочки. Очевидно, что один из них должен быть продлен вверх, а другой - вниз: других вариантов нет.

1377.gif (2165 bytes)

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

1378.gif (2247 bytes)

Что мы можем сказать о тех местах, которые выделены синим цветом? Линии через них проводить некуда! Поэтому около единиц, стоящих в левых углах, линии не слева, не сверху и не снизу, а справа (а потом заворачивают по горизонтали - см. рисунок слева)

1379.gif (2231 bytes)

Внимание! Следующее используемое правило уже сложнее. Оно требует более подробного разбора и даже небольшого доказательства. (Проведите его самостоятельно.) В результате у вас должно получиться то, что изображено на этом рисунке: около двух соседних цифр 3 обязательно должны быть три горизонтальных отрезка - между цифрами, выше и ниже. А отрезки слева и справа от среднего можно смело красить желтым. (Почему?)

1380.gif (2291 bytes)

Рассмотрим синие границы вокруг красной цифры 1. Эти два отрезка сходятся в одном "узле" с двумя желтыми отрезками. Поэтому в этом узле ситуация аналогична той, которую мы видели в углу головоломки на шаге 3. Следовательно, и здесь на синих границах линии нет. Поэтому линия должна проходить справа от красной единицы. Кстати, после этого легко определяется и направление продолжения этой ломаной возле второй цифры 3.

1381.gif (2276 bytes)

Теперь посмотрим на левый верхний угол возле красной тройки. Ломаная, пришедшая в него слева, затем должна обойти вокруг цифры 3. Это может быть сделано двумя способами - в результате непроведенной окажется либо линия на левой границе этой цифры, либо линия на верхней ее границе. В обоих случаях две других границы должны быть. Нарисуем там линии прямо сейчас!

1382.gif (2329 bytes)

Пришел черед двух красных двоек. Сначала взглянем на верхнюю. Ломаная, огибающая цифру 3 выше и левее ее, не может "ветвиться" и проходить около нее. Поэтому выше и левее двойки границы желтые. Тогда ниже и правее мы вынуждены нарисовать два отрезка ломаной - больше им быть негде. Совершенно аналогично теперь можно разобраться и со следующей двойкой.

1383.gif (2302 bytes)

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

1384.gif (2280 bytes)

Осталось провести четыре красных отрезка, причем проводятся они единственным образом.

1385.gif (2000 bytes)

Ответ:

Не правда ли, все не так уж сложно?

Ваш Константин Кноп