Лабораторная работа №3 Рекурсия. Графы. Деревья.

 

Задача 1. Дано N-дерево. Удалить самый высокий лист в дереве.

 

Задача 2. Дано N-дерево. Удалить все самые нижние поддеревья с нечётным числом листьев.

 

Задача 3. Дано N-дерево. Удалить все самые нижние поддеревья с чётным числом не – листьев.

 

Задача 4. Дано N-дерево. Удалить самый низкий лист(листья).

 

Задача 5. Дано N-дерево. Найти поддеревья с максимальным и минимальным соотношением (высота / число листьев).

 

Задача 6. Дано N-дерево. Найти самый длинный от корня путь, проходящий только по вершинам с нечётными номерами.

 

Задача 7. Дано N-дерево. Заданы веса вершин. Найти поддерево с мах отношением (сумма весов / число вершин).

 

Задача 8. Дано N-дерево. Удалить поддерево с мин отношением (число листьев / число не листьев).

 

Задача 9. Дано N-дерево. Найти в дереве длиннейший путь (пути), вдоль которого номера вершин упорядочены по возрастанию.

 

Задача 10. Дано бинарное дерево. Каждую вершину с чётным номером поменять местами с сыном, имеющим чётный номер.

 

Задача 11. Дано N-дерево. Найти все вершины с одинаковыми номерами.

 

Задача 12. Дано N-дерево. Найти все вершины равноудалённые от корня и от ближайшего своего листа.

 

Задача 13. Дано N-дерево. Найти ветви с мах числом ветвлений.

 

Задача 14. Дано бинарное дерево. Выполнить вращение для самого разбалансированого поддерева.

 

Задача 15. Дано бинарное дерево. Определить какие поддеревья являются пирамидами.

 

Задача 16. Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

 

Задача 17. Дано N-дерево. Найти в дереве самый длинный путь без ветвлений.

 

Задача 18. Дано N-дерево. Найти в дереве самое высокое (низкое) поддерево, имеющее заданное число листьев.

 

Задача 19. Дано N-дерево. Найти в дереве самое широкое (узкое) поддерево имеющее заданную высоту.

 

Задача 20. Дано N-дерево. Найти поддерево не включающее ни одну из заданных вершин.

 

Задача 21. Дано N-дерево. Найти поддерево, для всех вершин которого выполняется правило, если – (i) – k – ый сын (j), то (i) не имеет k – ого сына.

 

Задача 22. Дано N-дерево. Найти все поддеревья, структура которых совпадает с заданной.

 

Задача 23. Дано N-дерево. Найти все поддеревья, листья которых находятся в заданном диапазоне высот от корня поддерева.

 

Задача 24. Дано N-дерево. Найти все поддеревья, вершины которых имеют номера: нечётные, если вершина находится на нечётном расстоянии от корня, и чётные в противном случае.

 

Задача 25. Задан граф, проверить является ли он деревом.

 

Задача 26. Задан граф. Удалить минимальное количество дуг так, чтобы он стал деревом.

 

Задача 27. Задан орграф. Найти все вершины, достижимые из заданной вершины за указанное число шагов.

 

Задача 28. Задан орграф. Найти все циклы длинны N.

 

Задача 29. Задан орграф. Найти все вершины не достижимые из заданной.

 

Задача 30. Задан орграф. Найти все пути из вершины i в вершину j.

 

Задача 31. Задан орграф. Найти кратчайший путь из вершины i в вершину j.

 

Задача 32. Задан орграф. Найти все пути из вершины i в вершину j за заданное число шагов.

 

Задача 33. Задан орграф. Разорвать все циклы чётной длинны.

 

Задача 34. Задан орграф. Известны веса рёбер. Найти путь из i в j с min суммой весов рёбер.

 

Задача 35. Задан орграф. Найти цикл, содержащий каждую вершину из заданного множества М ровно один раз.

 

Задача 36. Задан орграф. Проверить является ли он деревом.

 

Задача 37. Задан орграф. Найти путь из i в j не содержащий вершин из некоторого множества M.

 

Задача 38. Задан орграф. Найти путь, содержащий каждую вершину из заданного множества M.

 

Задача 39. Задан орграф. Найти наидлиннейший цикл.

 

Задача 40. Задан орграф. Найти все вершины взаимно недостижимые друг от друга.

 

Задача 41. Задан орграф. Найти все пути N не имеющие ветвлений.

 

Задача 42. Дано N-дерево. Удалить все самые верхние поддеревья с нечётным числом листьев.

 

Задача 43. Дано N-дерево. Удалить все самые верхние поддеревья с чётным числом не – листьев.

 

Задача 44. Дано N-дерево. Найти самый длинный в дереве путь, проходящий только по вершинам с нечётными номерами.

 

Задача 45. Дано бинарное дерево. Найти все поддеревья, структура которых совпадает с заданной.

 

 

1.4.

Лабораторная работа №4 Рекурсия и головоломки.

 

Какуро

Хитори

Китайская стена

Филиппинский кроссворд

Японская мозаика

Морской бой

Мосты

Ожерелье

Фонари

Филломино

Неравенство

Куромасу

Нурикабе

Лагерь

Кен-кен

Хидато

Нумератор

Квадраты

Галактики

Небоскрёбы

Волновой эффект

Гранд тур

Первые встречные

Облако

Бумеранг

Сапёр

27. Сапёр + Морской бой

Комнаты

Числобус

Сто

Стрелки

Матракс

Стрейтс

Линейщик

Двоичный код

Стены

Домино-пасьянс

Лоскутки

Особняки

Рекуто

Соседи

Роза ветров

Шака-шака

Какурасу

Мочикоро

Двери

Маяки

Тапа

Четвёртый лишний

 

 

Какуро ("Kakuro") - это числовая головоломка, математический эквивалент кроссворда. Необходимо вставить в клетки цифры от 1 до 9, причем некоторые клетки неактивны (такие клетки помечены черным цветом). В клетках с заданными числовыми значениями правое верхнее значение означает сумму цифр в ряду, а значение снизу слева равно сумме цифр столбца ниже клетки. Например, число 6 можно представить как сумму 1 и 5, 2 и 4; одинаковые цифры (3 и 3) использовать запрещено.

 

 

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

 

 

Китайская стена ("Slitherlink", "Fences", "Loop the Loop", "Dotty Dilemma", "Sli-Lin"; еще одно название - Скользящие линии) - это логическая головоломка, напоминающая лабиринт. Необходимо соединить точки вертикальными и горизонтальными прямыми отрезками так, чтобы получилась единая замкнутая цепь, не пересекающая саму себя. Каждая цифра указывает, сколько отрезков должно расположиться вокруг нее по периметру. Если в ячейке нет цифры, то вокруг нее может быть любое количество линий.

 

 

 

Филиппинский кроссворд ("Link-a-Pix", "Paint by Pairs") - это головоломка с числами. Все числа, расположенные в сетке, кроме единицы, имеют свою пару. Необходимо найти каждую пару чисел и соединить их линиями. Количество клеток в ней должно равняться числам на ее концах. Линии, соединяющие пары, могут преломляться и идти в горизонтальном или вертикальном направлениях (но не по диагоналям). Линии не могут пересекаться друг с другом или проходить через одни и те же клетки.

 

 

 

 

Японская мозаика ("Fill-a-Pix", "Mosaik", "Nurie Puzzle", "Nampre Puzzle") - это логическая головоломка, в которой с помощью цифр зашифрована картинка. Каждое из чисел означает, сколько примыкающих клеток (считая ту, что с цифрой) должно быть закрашено. Например, если в клетке стоит ноль, то ни эта клетка, ни соседствующие с ней закрашены не будут.

 

 

 

Морской бой ("Battleships", "Solitaire Battleships", "Battleship Solitaire") - это головоломка, правила которой похожи на известную игру. Необходимо расположить "корабли" так, чтобы они не соприкасались даже углами. Цифры сбоку и снизу означают, сколько всего фрагментов кораблей попало в эту строку или столбец.

Стандартные размеры поля - 10 x 10. Имеются один корабль, занимающий 4 клетки, два корабля, занимающие 3 клетки, три корабля из 2 клеток и четыре корабль размером в 1 клетку. Иногда некоторые из фрагментов кораблей уже открыты.

 

Мосты ("Hashiwokakero", "Hashi", "Bridges", "Chopsticks", "Ai-Ki-Ai") - головоломка, в которой необходимо соединить кружки с цифрами ("острова") прямыми линиями ("мостами"). Цифра на острове показывает, сколько мостов должно быть к нему проложено. Изолированных островов быть не должно; линии должны быть проведены таким образом, чтобы с любого острова по построенным мостам можно было попасть на любой остров.

Между двумя островами разрешается строить не больше двух мостов. Линии могут проходить по горизонтали и вертикали, но не по диагонали. Они не должны преломляться, пересекаться или проходить сквозь острова.

 

 

Ожерелье ("Masyu", "Shiroshinju Kuroshinju", "White pearls and black pearls") - это логическая головоломка, в которой необходимо соединить белые и черные круги вертикальными и горизонтальными прямыми отрезками так, чтобы получилась единая замкнутая линия, не пересекающая саму себя. Через белые круги линия проходит прямо, но должна повернуть в предыдущей или следующей клетке (или в обеих этих клетках). Когда линия пересекает черный круг, она должна повернуть на 90 градусов, при этом в предыдущей и следующей клетке повороты запрещены.

 

Фонари ("Light Up", "Akari", "Bijutsukan") - это логическая головоломка. Игровое поле состоит из белых и черных клеток; в некоторых черных клетках расположены числа. Необходимо разместить "светильники" в белых клетках таким образом, чтобы все игровое поле было освещено, но фонари не "светили" бы друг на друга.

Свет фонаря распространяется по горизонтали и по вертикали, но может быть заблокирован черной клеткой. В черной клетке может находиться число от 0 до 4, указывая, сколько фонарей должно быть размещено рядом с ней (не учитываются фонари, помещенные по диагонали от этой черной клетки). Если клетка не содержит числа, около нее может быть размещено любое количество фонарей.

 

 

 

Филломино ("Fillomino") представляет собой прямоугольную сетку произвольного размера; в некоторых клетках находятся числа. Необходимо разбить игровое поле на блоки; блок должен содержать столько клеток, сколько обозначено числом в клетках блока. Блоки, имеющие одинаковый размер, не должны соприкасаться по горизонтали или по вертикали. Клетки, которые изначально не содержали чисел, также могут быть объединены в блоки, необходимые для решения головоломки.

 

 

Неравенство ("Futoshiki", "Hutoshiki", "Unequal") - это логическая головоломка с числами. Игровое поле представляет собой квадратную сетку; в некоторых клетках могут стоять цифры; между клетками могут присутствовать знаки "<" и ">", которые показывают соотношения, установленные между соседними цифрами. Необходимо заполнить свободные клетки цифрами так, чтобы в каждой строке и в каждом столбце каждая цифра встречалась бы только один раз.

 

Куромасу ("Kuromasu", "Kurodoko", "Where is black cells?") представляет собой прямоугольную сетку, в некоторых клетках которой могут стоять числа. Необходимо закрасить черным цветом клетки, соблюдая следующие условия:

• каждое число означает, сколько белых клеток "видно" из данной клетки по вертикали и по горизонтали; "взгляд" простирается до тех пор, пока не достигнет края поля или на пути не встретится клетка черного цвета;
• клетки с числами всегда остаются белыми;
• черные клетки не могут соприкасаться по вертикали или по горизонтали;
• все белые клетки составляют единое белое поле, то есть соприкасаются по вертикали или по горизонтали.

 

 

Нурикабе ("Nurikabe", "Cell Structure", "Islands in the Stream") - логическая головоломка с числами. В японской мифологии "нурикабе" - это чудовище в виде большой невидимой стены, загораживающей проход.

Необходимо восстановить карту, на которой изображено расположение островов, соблюдая следующие правила:

• информация о каждом острове представлена в виде числа, показывающего количество клеток, которые занимает этот остров;
• любые два острова могут соприкасаться только углами;
• все острова содержат в своем описании только одно число;
• между островами протекает река;
• все клетки реки должны быть соединены между собой;
• на карте не должно присутствовать ни одного квадрата размерами 2 x 2, все клетки которого содержат реку.

 

 

 

Лагерь ("Tents", "Tents and Trees") представляет собой прямоугольную сетку, некоторые клетки которой содержат "деревья". Необходимо разместить рядом с деревьями "палатки", соблюдая следующие правила:

• Число палаток равняется числу деревьев.
• Каждая палатка располагается рядом со "своим" деревом по горизонтали или вертикали, но не по диагонали. Если это условие выполнено, расположение по отношению к "чужим" деревьям значения не имеет.
• Две палатки не могут располагаться в соседних клетках, в том числе и по диагонали.
• Числа сбоку и сверху означают, сколько палаток находится в этой строке или столбце.

 

Кен-кен ("KenKen", "KENKEN", "KenDoku", "CalcuDoku", "Square Wisdom") - это математическая и логическая головоломка. Необходимо заполнить сетку цифрами так, чтобы в каждой строке и в каждом столбце они не повторялись. Число в углу каждого выделенного блока является результатом арифметической операции над цифрами в этом блоке. В отличие от судоку-убийцы (сум-до-ку), цифры внутри блока могут повторяться.

 

 

Хидато ("Hidato"; в переводе с идиш: "моя головоломка"; еще одно название - "Hidoku") была изобретена израильским математиком Гиором Бенедеком (Gyora Benedek). Головоломка представляет собой поле произвольной формы (чаще всего прямоугольное или квадратное), состоящее из клеток. Необходимо заполнить все клетки последовательными числами, которые соединены горизонтально, вертикально или по диагонали. В каждой головоломке уже присутствуют наименьшее и наибольшее числа. Также на поле могут стоять и другие числа, чтобы облегчить игроку процесс разгадывания и обеспечить единственность решения задачи.

В России головоломку еще называют "Путь короля", так как движение от одного числа к другому напоминает перемещение шахматного короля по доске.

 

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

 

 

Квадраты ("Shikaku", "Divide by Squares", "Divide by Box", "Number Area") - это логическая головоломка. Она представляет собой прямоугольную сетку без стандартного размера. Некоторые клетки сетки содержат числа. Необходимо прочертить линии, разделяющие сетку на прямоугольные и квадратные регионы таким образом, чтобы каждый регион содержал только одно число, равное площади этого региона.

 

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

 

 

 

 

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

 

Волновой эффект ("Ripple Effect", "Hakyuu", "Seismic") - вид логической головоломки. Задание состоит из прямоугольной сетки, разделенной на блоки ("комнаты"); в некоторых клетках могут стоять числа. Необходимо заполнить все клетки числами так, чтобы каждый блок содержал числа от 1 до количества клеток в блоке. Если ряд клеток или столбец содержат два одинаковых числа, количество клеток между ними больше или равно этим числам. Например, если столбец содержит две клетки с числом 5, между ними должно быть по крайней мере пять клеток с другими числами.

 

Гранд тур ("Grand Tour"; еще одно название - Петля с фрагментами) - логическая головоломка, в которой требуется провести не касающуюся и не пересекающую себя замкнутую линию через все точки прямоугольной или квадратной сетки. Для того, чтобы обеспечить единственность решения головоломки, несколько точек уже соединены отрезками.

 

Первые встречные ("Easy as ABC", "ABC End View", "Last Man Standing"; еще одно название - Букварики) - логическая головоломка с буквами. Необходимо заполнить квадратную сетку латинскими буквами (например, от A до E), так чтобы каждый символ встречался в каждой строке и в каждом столбце ровно один раз. Некоторые клетки сетки могут быть пустыми. Буква, стоящая на границе сетки, показывает - какая буква встретится первой в данной строке (столбце).

 

 

 

Облака ("Clouds", "Radar"; еще одно название - Синоптик) - это разновидность головоломки "Морской бой". В сетке произвольной формы необходимо расставить прямоугольники ("облака") так, чтобы они не касались друг друга даже углами. Числа по краям сетки означают количество клеток, занятых облаками. Количество и размер облаков не заданы; известно лишь, что стороны прямоугольников имеют длину не меньше двух.

 

 

Бумеранг ("Yajilin", "Arrow Ring", "Straight and Arrow") - логическая головоломка квадратной или прямоугольной формы. Задание содержит клетки со стрелками и числами; эта информация необходима для расстановки клеток черного цвета на поле. Цель - нарисовать замкнутую, не пересекающую себя петлю, которая не должна проходить через клетки со стрелками или черные клетки.

• Числа в клетках указывают, сколько именно черных клеток находится в том ряду или том столбце и в том направлении, в котором указывает стрелка. Сами клетки со стрелками не считаются за черные клетки.
• Если клетка не содержит стрелку и не является черной, то она должна содержать сегмент петли.
• Числа в клетках указывают точное число черных клеток. То есть, если ячейка сетки содержит число "3" и стрелку, указывающую влево, это означает, что в ряду слева от такой ячейки располагаются три черных клетки.
• Черные клетки не должны соприкасаться по горизонтали или по вертикали.
• На поле могут быть черные клетки, на которые не указывает ни одна стрелка.

 

 

Сапёр ("Minesweeper") известен всем пользователям операционной системы Microsoft Windows. Необходимо расставить "мины" в свободных клетках, используя ключевые числа. Каждое ключевое число показывает, сколько соседних с ним клеток занято минами. Мины расположены по одной в каждой клетке, а в клетке с числом мин не бывает.

 

Сапёр + Морской бой ("Minesweeper Battleships") объединяет в себе черты двух популярных головоломок. Необходимо расставить на поле корабли таким образом, чтобы они не касались даже углами. В некоторых клетках сетки стоят цифры. Эти цифры показывают, сколько фрагментов кораблей находится вокруг данной клетки (включая диагонали).

 

 

 

Комнаты ("Heyawake") - логическая головоломка. Она представляет собой прямоугольную сетку, разделенную на блоки ("комнаты"). Некоторые блоки могут содержать числа; число показывает, сколько именно черных клеток должен содержать блок. Если число в блоке отсутствует, такой блок может содержать любое количество черных клеток.

• Черные клетки не должны соприкасаться по горизонтали или по вертикали (только по диагонали).
• Все белые клетки соединены друг с другом по горизонтали или по вертикали.
• Непрерывная линия из белых клеток не должна пересекать более двух "комнат".

Числобус ("Tenner Grid", "From 1 to 10", "Zehnergitter") представляет собой прямоугольную сетку шириной десять клеток. Необходимо заполнить сетку таким образом, чтобы каждый ряд содержал цифры от 0 до 9. В столбцах числа могут повторяться. Число внизу сетки означает сумму всех цифр в столбце. Числа, находящиеся в смежных клетках (даже если клетки соприкасаются лишь по диагонали), должны быть разными.

 

 

 

Сто ("Hundred") состоит из квадратной сетки, в каждой клетке которой проставлены цифры. Требуется поставить дополнительные цифры таким образом, чтобы сумма чисел в каждом ряду и каждом столбце была равна 100.

 

Стрелки ("Arrows") - это разновидность логической головоломки. Она состоит из сетки прямоугольной или квадратной формы, заполненной числами. Цель головоломки - расставить стрелки за пределами сетки. Каждая стрелка указывает хотя бы на одну клетку с числом. Число означает количество стрелок, указывающих на данную клетку.

 

 

Матракс ("Mathrax") - разновидность логической головоломки. Необходимо заполнить числами квадрат так, чтобы в каждой строке и в каждом столбце каждое число использовалось лишь единожды. Некоторые из чисел уже могут присутствовать в сетке. На пересечениях линий сетки могут располагаться кружки с дополнительными условиями:

• Число и знак арифметического действия (сложение, вычитание, умножение, деление) - число в кружке означает результат выполнения арифметического действия над парами чисел в клетках, примыкающих к кружку и соприкасающихся друг с другом по диагонали.
• Латинская буква " E " - в клетках, примыкающих к кружку, все четыре числа являются чётными ("E" - от английского слова "even", чётный).
• Латинская буква " O " - в клетках вокруг кружка все четыре числа являются нечётными ("O" - от английского слова "odd", нечётный).

 

Стрейтс ("Str8ts", "Straights"; от термина в карточной игре покер, обозначающего пять карт по порядку) - логическая головоломка, придуманная Джеффом Виддеричем (Jeff Widderich) из Канады. Сетка квадратной формы содержит черные и белые клетки. Необходимо расставить числа в белых клетках таким образом, чтобы в промежутках между черными клетками образовывались наборы последовательных чисел, но не обязательно в порядке возрастания или убывания (например: 2-1-3-4). В каждой строке и в каждом столбце числа, стоящие в белых и черных клетках, не должны повторяться. Числа в черных клетках не входят в наборы последовательных чисел.

Линейщик ("Linesweeper") - логическая головоломка, правила которой похожи на правила головоломки "Сапёр". Задание представляет собой квадратную или прямоугольную сетку; в некоторых клетках сетки стоят числа (возможны значения от 0 до 8). Необходимо провести замкнутую линию через клетки; линия не должна пересекать саму себя или проходить через клетки с числами. Цифра в клетке показывает, через какое количество клеток, расположенных вокруг клетки с числом, проходит линия.

 

 

 

 

Двоичный код ("Binairo", "Binary Puzzle", "Takuzu", "Tohu wa Vohu") - логическая головоломка с использованием цифр "0" и "1". Прямоугольную или квадратную сетку необходимо заполнить цифрами в соответствии со следующими правилами:

• Каждая строка и каждый столбец содержат столько же цифр "1", как и цифр "0" (или на одну больше для сеток с нечётными размерами).
• Одна и та же цифра может стоять лишь в двух ячейках подряд.
• Каждая строка должна быть уникальной, и каждый столбец должен быть уникальным.

 

Стены ("Walls") - логическая головоломка; её изобрёл Наоки Инаба (Naoki Inaba) из Японии. Необходимо расставить в белых клетках горизонтальные и вертикальные линии так, чтобы суммарная длина всех "лучей", исходящих из клетки чёрного цвета, совпадала с числом, стоящим в этой клетке.

 

 

Домино-пасьянс ("Dominosa", "Dominosa Omnibus", "Solitaire Dominoes", "Domino Hunt") - логическая головоломка, в которой используются костяшки домино. На поле показаны только числа; необходимо восстановить границы между костяшками домино.

 

Лоскутки ("Patchwork", "Tatami"; еще одно название - Магические полоски) - головоломка, которая представляет собой квадратную сетку, поделенную на регионы одинакового размера ("комнаты"). Необходимо заполнить каждую комнату цифрами от 1 до числа, равного количеству клеток в регионе. Каждый ряд и каждая колонка должны содержать одинаковые количества каждого вида цифр. Соседние клетки, соприкасающиеся по горизонтали или вертикали, не должны содержать одинаковые цифры.

В некоторых заданиях этой разновидности головоломок используются буквы вместо цифр. Cross+A может решать головоломки как с цифрами, так и с буквами в задании.

 

 

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

 

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

 

 

Соседи ("Neighbours") - это логическая головоломка, представляющая собой сетку произвольной формы. В некоторых клетках сетки проставлены числа или знаки вопроса. Необходимо поделить сетку на регионы с равным количеством клеток. Каждый регион должен содержать только одну клетку с числом (или со знаком вопроса); это число показывает, сколько именно "соседей" должно быть у данного региона. Два региона считаются соседними, если у них есть общая граница. Если регион содержит клетку со знаком вопроса, у такого региона может быть любое количество "соседей".

 

Роза ветров ("Four Winds") - логическая головоломка, которая представляет собой квадратную или прямоугольную сетку с черными и белыми клетками. Необходимо нарисовать прямые линии, исходящие из черных клеток и проходящие через все белые клетки. Число в черной клетке показывает, сколько белых клеток занимают линии, соединенные с этой черной клеткой. Линии не должны пересекаться.

 

 

Шака-шака ("Shakashaka", "Proof of Quilt") - логическая головоломка квадратной или прямоугольной формы. Задание содержит белые и черные клетки; в некоторых черных клетках могут стоять цифры (от 0 до 4). Необходимо расставить в белых клетках черные треугольники таким образом, чтобы сформировать прямоугольные и квадратные области белого цвета. Некоторые белые клетки могут оставаться пустыми. Области могут быть ориентированы горизонтально, вертикально или по диагонали. Соседние области белого цвета не должны иметь общих сторон. Цифра в черной клетке показывает, сколько треугольников соприкасаются с этой клеткой.

 

Какурасу ("Kakurasu") - головоломка квадратной или прямоугольной формы, в которой необходимо расставить черные и белые клетки. Числа слева и сверху от сетки обозначают суммы "весов" черных клеток в рядах и столбцах. Числа справа и снизу от сетки определяют "вес" черных клеток в соответствующих рядах и столбцах ("вес" черного квадрата в первом ряду или первом столбце равен 1, во втором ряду или втором столбце - 2 и т.д.).

 

 

 

Мочикоро ("Mochikoro", "Mochinuri") представляет собой прямоугольную или квадратную сетку, в некоторых ячейках которой стоят числа. Необходимо разместить белые и черные клетки таким образом, чтобы образовались прямоугольные или квадратные «острова» из белых клеток.

• Один белый «остров» может содержать не более одной клетки с числом; число означает количество белых клеток, принадлежащих этой области.
• Некоторые «острова» не содержат клеток с числами.
• Регионы белого цвета не могут соприкасаться сторонами, но все белые «острова» касаются друг с друга по диагонали.
• В сетке не должно быть ни одного квадрата 2 x 2, состоящего только лишь из черных клеток.

 

 

Двери ("Seethrough", "Doors", "Open Office") - логическая головоломка квадратной или прямоугольной формы, где каждая ячейка обозначает "комнату". Требуется закрыть или открыть "двери" между комнатами. Открытые двери позволяют смотреть из комнаты в комнату или сквозь несколько комнат. Число обозначает, сколько комнат видно из данной комнаты, за исключением самой этой комнаты. Не должно быть изолированных друг от друга частей сетки, то есть из любой комнаты можно попасть в любую комнату.

 

Маяки ("Lighthouses") - логическая головоломка, содержащая черные клетки с числами ("маяки"). Число означает количество кораблей, которые освещены данным маяком. Маяк освещает корабль, если они находятся в одном ряду или колонке, даже если между маяком и кораблем расположены другие корабли или маяки. Каждый корабль освещен по крайней мере одним маяком. Корабли располагаются таким образом, что не соприкасаются с маяками или друг с другом, в том числе и по диагонали.

 

 

Тапа ("Tapa") была изобретена Серканом Юрекли (Serkan Yürekli) из Турции. Головоломка представляет собой квадратную или прямоугольную сетку, состоящую из белых клеток. Необходимо закрасить некоторые клетки черным цветом таким образом, чтобы выполнялись следующие правила:

• Все черные клетки должны соприкасаться друг с другом по вертикали или по горизонтали.
• Не должно быть группы клеток размером 2 x 2, состоящей из одних лишь черных клеток.
• Некоторые из клеток содержат числа или знаки вопроса; такие клетки всегда остаются белыми.
• Каждое число обозначает непрерывную группу черных клеток вокруг белой клетки с этим числом; две такие группы черных клеток обязательно должны быть разделены хотя бы одной белой клеткой.
• Знак вопроса обозначает любое число больше нуля.
• Позиции чисел или порядок их размещения внутри клетки не имеют значения.

 

Четвёртый лишний ("Forbidden Four") - логическая головоломка, изобретенная Наоки Инаба (Naoki Inaba) из Японии. Головоломка представляет собой прямоугольную или квадратную сетку, в некоторых ячейках которой стоят круги. Необходимо расставить в пустых клетках круги таким образом, чтобы все они соприкасались друг с другом по горизонтали или по вертикали. Не должно быть четырех подряд кругов по горизонтали или по вертикали.