Решение задачи о ферзях на доске 5x5

Какое минимальное количество ферзей нужно поставить на клетчатую доску 5 на 5 так, чтобы все клетки были под боем?

Ответ: 3

Решение поставить ферзей в угол навеяно ответом на задачу о ферзях-часовых, где на шахматной доске надо расставить 5 ферзей, чтобы они держали под боем все клетки доски.

Расстановка показана на картинке.

Возможна также расстановка двух ферзей как показано ниже и третьего на любую из клеток главной диагонали.

Остается только доказать, что двух ферзей недостаточно.

Допустим, двух достаточно. Чтобы побить все клетки с цифрами, одного надо поставить на клетку 14. Чтобы побить оставшиеся 16 клеток (даже за вычетом уже бьющихся 6ти), еще одного не достаточно. Об этом говорит элементарный перебор двух позиций по диагонали (чтобы бить горизонталь и вертикаль, он должен быть на диагонали, а бить нужно то и другое, т. к. при ферзе в клетке 14 по две крайние клетки a1, a2, e4, e5 остаются не под ударом). А если поставить первого в любую клетку кроме 14, для покрытия 9ти оцифрованных клеток нужен второй плюс остается сколько-то непобитых из оставшихся 16ти.

Для решения шахматных задач удобно использовать файл с доской и фигурами в разных слоях, может кому пригодится: chess.psd

Еще удобнее использовать Паскаль или C++ для большого числа клеток, но это уже другая история.