July 28th, 2018

Ферзи и множества



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

Иными словами, никакие два ферзя не должны находиться на одной горизонтали, вертикали или диагонали — именно так ведь ходит ферзь.

Несмотря на простоту постановки, в решении задачи есть некоторые сложности. Аналитический способ её решения, увы, неизвестен, поэтому остаётся, фактически, только решение перебором.

Но и с перебором тоже не всё так очевидно. Особенно если обобщить задачу до «найти все способы размещения любого количества ферзей на доске» — ну, так, чтобы размещения одного ферзя, двух ферзей и даже ста ферзей, если такое каким-то чудом получится, тоже вошло бы в ответ.

Казалось бы, а чего тут такого? 1 — есть на этом поле ферзь, 0 — нет ферзя. Переберём все варианты, для каждого проверим, не бьют ли какие-то ферзи друг друга…


Читать целиком