КОМПЬЮТЕРРА

"Облака" (HELP) 

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

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

Головоломка "Облака", на первый взгляд, является очень вольной вариацией "морского боя". На чемпионатах мира по пазлспорту она появилась в 1996-м году, но в голландских журналах встречалась гораздо раньше. Как и в морском бое, в таблицу нужно расставить прямоугольники, не касающиеся друг друга даже углом (только это уже не "корабли эскадры", а "облака"), а числа по краям таблицы означают количество клеток, занятых ими. На этом сходство с морским боем и кончается. Количество и размер облаков не заданы, известно лишь, что стороны прямоугольников имеют длину не меньше двух.

	Задача не имеет жесткого формата: размер таблицы может быть любым. При решении "облаков" нередко возникают удивительные по своей красоте и логике рассуждения, именно поэтому ее так любят многие опытные головоломщики. Одна из немногих головоломок, при решении которой опыт и "владение техникой" могут существенно пригодиться. Рассмотрим процесс решения на примере головоломки, которая была на отборе команды России для поездки на Чемпионат мира в 1998-м году.
На самый первый взгляд, начать решение не с чего: ни про одну клетку нельзя точно сказать, принадлежит она облаку или небу. Поэтому попробуем выяснить разбиение заполненных клеток по облакам в строках, и будем записывать его справа от от строк синим цветом. (Аналогичную работу можно было проделать и для столбцов). В верхней десятой строке все три клетки могут быть заняты лишь одним облаком (так как длина стороны облака не меньше двух). Это облако продолжается и на строку 9, из чего делаем вывод, что в ней должно появиться еще одно облако длины три.
	Аналогично в строке 7 два облака, одно из которых продолжается вниз, а другое - вверх. В строке 5 встречаются облака длины 2 и 3. В строке 1 сумма длин облаков - 6, они продолжаются до строки 2, и еще появляется облако длины 2 (продолжающееся по крайней мере до строки 3). А облако длины 3 из строки 3 продолжается вниз до строки 2. То есть в строке 2 есть облака и длины 2, и длины 3, 8=2+3+3. Оба облака длины три опускаются вниз до первой строки. То есть мы получили "разбивку по облакам" ключевых чисел строк.
	Тут мы уже можем отметить некоторые фрагменты: в строке ?2 фрагменты расположены максимально возможно плотно друг к другу, выделим те 6 клеток, которые будут заняты независимо от взаимного расположения облаков длины 2, 3 и 3. Будем отмечать "облака - облачно-серым цветом, а небо - небесно-голубым. В столбце а облако длины три обязательно займет строку 3, и никак не займет строки, номера которых больше 4.
Аналогично, в столбце f облако длины два займет еще не более одной строки. Облако, занимающее клетки аb23, продолжится по горизонтали и до столбца с (иначе в нем не наберется восьми заполненных клеток), и там закончится (так как имеет длину 2 или 3). Вверх оно продолжаться не может (так как в четвертой строке - 2, значит, оно опускается вниз. Таким образом, положение одного облака мы нашли.
	Тут мы уже можем отметить некоторые фрагменты: в строке 2 фрагменты расположены максимально возможно плотно друг к другу, выделим те 6 клеток, которые будут заняты независимо от взаимного расположения облаков длины 2, 3 и 3. Будем отмечать "облака" облачно-серым цветом, а небо - небесно-голубым. В столбце a облако длины три обязательно займет строку 3, и никак не займет строки, номера которых больше 4.
Аналогично, в столбце f облако длины два займет еще не более одной строки. Облако, занимающее клетки ab23, продолжится по горизонтали и до столбца c (иначе в нем не наберется восьми заполненных клеток), и там закончится (так как имеет длину 2 или 3). Вверх оно продолжаться не может (так как в четвертой строке - 2), значит, оно опускается вниз. Таким образом, положение одного облака мы нашли. Строки 7 и 9 разбились на две части, в каждой из которых находится по облаку длины три, причем столбцы c, d, h и i заняты в них облаками.
	Рассмотрим строку 8. Если в клетках сd8 - облака, то в столбце e никак не получаются 4 заполненные клетки, то есть их в нем либо две, либо по крайней мере 5. Значит, в с8 и d8 - небо, а облака - в h8 и i8 . Тут же получаем разбивку столбца c (а заодно и d) на облака. Облако ширины 2 продолжается от них вправо до столбца e, а облако ширины 3 - влево до b. Отмечаем новые "небесные" клетки.
	Облако hi-789 вправо продолжаться не может (это "переполнит" столбец j), продолжаем его влево до столбца g. Отмечаем небо во всем столбце h, а также в g-45. Дозаполняем строку 2, и продолжаем из нее облака длины 3 - вниз до первой строки, а длины 2 - вверх до пятой. Проверим, не ошиблись ли мы где-нибудь? Нет, не ошиблись.

Ну, вот и все!

Ваши Ольга Леонтьева и Константин Кноп