4. Пояснения к задачам

   1. «Игра «Судоку»: генератор поля»

Судоку - логическая головоломка, квадрат 9x9, который нужно заполнить цифрами по следующим правилам: в свободных клетках надо расставить цифры от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3x3 каждая цифра встречалась бы только один раз.

Необходимо сгенерировать полное поле цифр для игры Судоку, удовлетворяющее правилам игры.

Входные данные для программы не требуются.

Выходными данными будет сгенерированное поле в виде матрицы 9х9.

2. «Игра «Судоку»: решатель задач»

Судоку - логическая головоломка, квадрат 9x9, который нужно заполнить цифрами по следующим правилам: в свободных клетках надо расставить цифры от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3x3 каждая цифра встречалась бы только один раз.

Необходимо найти решения задаваемой головоломки: одно, если оно однозначно, несколько, если возможны различные корректные решения или сделать вывод, что конкретная задача не имеет решений.

Входными данными будет начальное поле размером 9х9, в котором 0 обозначаются пустые клетки, цифрами от 1 до 9 открытые клетки.

Выходными данными будут одно или несколько полей в виде матрицы 9х9 с решениями задачи либо сообщение об отсутствии решений.

3. «Японский кроссворд»

В клетках японского кроссворда скрываются не слова, а картинки. Задача - нарисовать картинку по числам, которые проставлены слева от строк и над колонками. Числа показывают, сколько групп закрашенных клеток находится в соответствующей линии и сколько закрашенных клеток содержит каждая группа. Например (рис. 1), числа 2, 1 и 1 во второй строке означают, что в этой строке есть три группы, состоящие: первая - из двух, вторая - из одной, третья - также из одной закрашенной клетки. Группы разделены, как минимум, одной пустой клеткой. Пустые клетки могут быть и по краям рядов.

Необходимо найти решения задаваемого кроссворда: одно, если оно однозначно, несколько, если возможны различные корректные решения или сделать вывод, что конкретный кроссворд не имеет решений.

Входными данными будут размеры поля M и N, а также наборы длин закрашенных групп по координатам X и Y.

Выходными данными будут одно или несколько полей в виде матрицы MхN с решениями кроссворда, где пустое поле будет обозначать не закрашенную клетку, а поле с цифрой/буквой/символом закрашенное, либо сообщение об отсутствии решений.

4. «Расстановка ферзей»

Разработать программу поиска всех возможных способов расстановки восьми шахматных ферзей на пустой доске размером x*y таким образом, чтобы ни один из них не "бил" другого. Т.е. так, чтобы ни какие два ферзя не стояли на одном и том же столбце, или на одной и той же строке, или на одной и той же диагонали шахматной доски.

Входными данными для программы будет являться размер доски.

Выходными данными будут количество найденных расстановок и сами расстановки.

5. «Путешествие коня»

Разработать программу для обхода шахматным конем, находящимся на произвольной клетке доски размером x*y, всех остальные клеток доски. При этом на одну клетку можно походить только один раз.

Входными данными для программы будет являться размер доски.

Выходными данными будет последовательность обхода доски.