Одно из решений для данной задачи можно построить следующим образом: | | A | B | C | D | E | F | | --- | --- | --- | --- | --- | --- | --- | | 6 | R | | R | | R | | | 5 | | R | | R | | R | | 4 | R | | R | | R | | | 3 | | R | | R | | R | | 2 | R | | R | | R | | | 1 | | R | | R | | R | Для того, чтобы побить все клетки и все незанятые внутренние узлы, в данном решении было использовано 9 сторожевых башен. Поясним, как было найдено это решение. Каждая сторожевая башня бьёт клетки обеих диагоналей, пересекающихся в этой башне, а также узлы вертикали и горизонтали, пересекающихся в этой башне. В данном случае, в каждом столбце и каждой строке используется по три башни, чтобы побить все незанятые узлы. Узлы на границе не нужно бить, поэтому нижний левый и верхний правый узлы остаются пустыми. Чтобы решить эту задачу, мы можем следовать следующему алгоритму: 1. Поставим по одной башне на каждое из полей на диагоналях, исключая верхний левый и нижний правый узлы. 2. Добавим по одной башне в каждый угол таблицы (A6, F1, F6, A1). 3. Расставим оставшиеся 4 башни в таблице по следующему принципу: - Оставшиеся башни будем расставлять по очереди в каждую строку, начиная с верхней. - Сначала расставим башни на черные клетки каждой строки, затем на белые клетки. - В каждой строке также будем придерживаться следующего принципа: если башня уже стоит в столбце, пропускаем его, иначе ставим башню. Один из вариантов решения, полученный при использовании этого алгоритма, описан в таблице выше. Таким образом, мы можем побить все клетки и все незанятые внутренние узлы, используя 9 сторожевых башен. Это минимально возможное количество башен, которое достигает все условия задачи.