Если проиграть ситуацию (возможно мысленно) на модели доски (например, размером
4 х 4), появляются следующие заключения:
1. Если дважды подряд заменяют цвет у одного и того же ряда, позиция не меняется.
2. Пусть мы хотим сделать два хода (а и b). От того, какой ход мы сделаем первым, а какой - вторым, результат не зависит. Это определяется тем, что разные строки, как и столбцы, не имеют между собой общих шашек. У пересекающихся строки и столбца - только одна общая шашка, которая при любом порядке ходов в результате вернется к исходному цвету.
3. На основании двух первых заключений можно сделать вывод, что порядок ходов не является существенным и, кроме того, результирующее состояние ряда то же при 2n+k ходах, что и при к ходах. Таким образом, пространство перебора сокращается: надо перебирать всевозможные множества строк и столбцов с которыми будет проведена замена цвета. Таких множеств уже конечное число, хотя всё же ещё очень много -
4. После того, как сделан ход, номер ряда не является существенным, так как в задаче важным является лишь число шашек белого цвета, но не место их расположения.
5. На основании предыдущего вывода можно строки, у которых был изменён цвет один раз, перенести в верхнюю часть доски, а столбцы соответственно - в левую часть. Таким образом доска окажется разбитой на четыре части:
Число строк L в верхних и число столбцов С в левых прямоугольниках соответствуют рядам шашек, модифицированных один раз.
Таким образом, пространство перебора ещё более сокращается: надо перебирать всевозможные пары (L,С). Объем пространства перебора уже вполне приемлемый -10000.
6. Представленная на доске позиция обладает симметрией относительно строк и столбцов. Если (L, С) - решение задачи, то и (C,L) также будет решением.
7. Рассматриваемая позиция обладает ещё и центральной симметрией. Если (L, С) -решение задачи, то и (100-С, 100-L) также будет решением. Теперь пространство перебора можно задать как пары (L,C), в которых и его объём -2100.
Однако на этом мы не остановимся, а продолжим изучение задачи. Запишем замкнутую формулировку. Число белых шашек составляет: вверху - L х (100-С) и внизу - С х (100-L). В результате условие, которой должна удовлетворять искомая пара можно записать в виде: 100(L+C)-2LC=1990.
Становится очевидным, что достаточно перебирать только первый элемент пары - L, а С вычислять по формуле C=(1990-100L)/(100-2L) и проверять на приемлемость. Таким образом, пространство перебора сокращается до 50 элементов.
На данном этапе задачу целесообразно немного обобщить. Мы сведём эту задачу к решению простого уравнения в целых числах. Пусть р - половина длины доски и n -число, равное половине заданного числа белых шашек. Тогда можно записать p(L+C)-LC=n Сделаем замену переменных L =l+p, С=с+р. Получим уравнение 1с=р2 - n. Целое число, стоящее справа, известно. Это 50х50 - 1990/2=1505. Для существования решения необходимо, чтобы число 1505 было разложимо на множители, сопоставимые с размерами доски. 1505=5х7х43, а так как р=50, то -50< l < 50, -50< с < 50. В данном случае имеется решение, удовлетворяющие этим условиям: /=5х 7, с=43, L=85, С=93 (или симметричное ему l=-5х 7, с=-43, L=15, С=7). Таким образом, имеется вариант получения на доске 1990 белых шашек.
Задачи
Задача 1. В длинную деревянную рейку вбили несколько гвоздей. Некоторые пары гвоздей связываются верёвочками так, чтобы выполнялись следующие условия:
1. к каждому гвоздю была привязана хотя бы одна верёвочка;
2. суммарная длина верёвочек была бы минимальной.
Написать программу, которая связывает пары гвоздей верёвочками как описано выше.
Технические требования: Входными данными являются число гвоздей и их координаты, выходными - минимальная суммарная длина и пары соединений гвоздей.
Замечание. Задача решается без перебора.
Задача 2. Квадрат размером 5x5 вдоль линий сетки разбили на несколько фигурок. Написать программу, которая определяет, можно ли переложить часть фигурок так, чтобы снова образовался квадрат размером 5х5. При перекладывании не разрешается поворачивать и переворачивать фигурки.
Технические требования: Входные данные - символьная матрица размером 5x5. Каждая буква в матрице означает идентификатор фигурки, содержащей соответствующую клетку. Идентификаторами являются большие буквы латинского алфавита. Программа должна выдать другой способ составления квадрата размером 5х5, либо сообщение, что это невозможно.
Замечание. Это стандартная переборная задача. Решается с помощью перебора с возвратом (можно использовать распространение ограничений).
Задача 3. В океане расположен архипелаг из N островов, каждый из которых имеет форму многоугольника. Острова не соприкасаются и не пересекаются. Эти острова необходимо соединить между собой мостами так, чтобы от любого острова архипелага можно было добраться до любого другого. Каждый мост должен соединять пару островов, при этом суммарная длина мостов должна быть минимальной.
Технические требования: Входными данными являются число островов в архипелаге (N) и описаний островов. Каждый остров задаётся числом вершин и их координатами в порядке обхода по часовой стрелке. Программа должна вывести два числа - количество мостов и их суммарную длину.
Замечание. Задача решается без перебора.
Задача 4. Разбиение. Массив натуральных чисел А (А1,...,Аn) разбить на два непересекающиеся массива В и С (то есть каждый элемент массива А должен попасть точно в один из двух массивов: В или С), так, чтобы сумма чисел в В равнялась сумме чисел в С.
Технические требования: Входными данными являются количество чисел (п) и последовательность из п чисел. Программа должна вывести два массива чисел В и С.
Замечание. Задача схожа с задачей о рюкзаке и решается перебором с возвратом. Можно использовать распространение ограничений. Перед перебором имеет смысл упорядочить массив А по невозрастанию.
