Задача о расстановке ферзей. Перебор с возвратом.

Задача о расстановке ферзей.

Небольшая подсказка к решению задачи о расстановке 8 ферзей.

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

Стоит сразу заметить, что перебирать все возможные варианты расстановок мы не в состоянии.  Точнее можно конечно написать такую программу, но мы поступим иначе, более оптимально.

Некоторые замечания о способе хранения расстановки.

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

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

Имеет смысл хранить лишь одномерный массив из восьми элементов, каждый из которых будет соответствовать одной из вертикалей. А значение каждого элемента будет соответствовать той строке, в которой установлен ферзь. Следующий рисунок отлично поясняет этот принцип.

О проверке, находится ли поле «под боем» или нет.

Опишем математически, какие клетки шахматной доски находятся «под боем» ферзя,  установленного в клетке [i][j].

Посмотрите на следующий рисунок.

 

Пусть [i][j] – позиция ферзя, а [k][m] – координаты проверяемой клетки. 

k=I – горизонталь,

m=j – вертикаль,

k+m =i+j – восходящая диагональ,

k–m = i–j – нисходящая диагональ.

Эти условия легко переделать под наш способ хранения расстановки ферзей.

Допустим, что уже имеется несколько установленных ферзей, которые не бьют друг друга. Какие условия налагаются на следующего ферзя?

Понятно, что нужно последовательно обработать каждую из предыдущих элементов. Пусть мы хотим поставить ферзя на позицию k.

Начинаем проверку, с первого элемента, в нём у нас записано значение восемь. Следовательно, k не должно равняться восьми, иначе оба ферзя окажутся на одной горизонтали. Кроме того, k+4 != 8+1 (условие зеленой линии), иначе мы пытаемся поставить ферзя на занятую диагональ. И наконец, k-4 != 8-1 (условие синей линии), иначе мы снова попадаем на диагональ, которая бьётся другим ферзем. Проверку условия красной линии осуществлять не нужно, так как способ представления расстановок в памяти не позволит на одну горизонталь поставить двух ферзей.

Аналогичные проверки необходимо будем произвести для всех ферзей, которые к этому моменту уже установлены на доске. Логично будет выделить эти проверки в функцию, которая принимает два аргумента – строку и столбик клетки, в которую мы хотим установить ферзя.

Основной алгоритм решения. Перебор с возвратом.

Теперь обсудим основной алгоритм реализующий расстановку ферзей. Действовать будем так, как мы действовали бы, если у нас была бы реальная доска перед глазами. 

 

Поставим первого ферзя в первую клетку первой вертикали. Соответственно в первый элемент нашего массива сохраним единичку. Хорошо, первый ферзь установлен. Самое время попытаться установить второго ферзя.

Он должен стоять на второй горизонтали.

Поставим его в первую клетку второй вертикали. Вызов функцию проверки, даст отрицательный результат на первом же условии, так как это строка бьется ранее установленным ферзем.

Проверим вторую клетку, второй вертикали. Результат проверки неудовлетворительный, это поле тоже бьется ранее установленным ферзем.

Теперь проверим третью клетку второй вертикали, может быть она нам подойдет? Действительно подходит. Устанавливаем туда ферзя.    Переходим к установке третьего ферзя на третью вертикаль. 

 

Проверку начинаем осуществлять с 1 клетки третей вертикали.

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

Аналогичным способом заполняем четвертую, пятую, шестую и седьмую вертикали.  Пока что это всё можно реализовать стандартным перебором в два цикла. Внешний цикл двигается по вертикалям от 1 до 8, а внутренний по горизонталям.

Отдельно рассмотрим установку ферзя на последней вертикали.

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

Что же делать? Нужно вернуться на шаг назад и попытаться установить седьмого ферзя в другое место. 

Это операция называется возврат.

Нет необходимости, снова проверять для седьмого ферзя клетки с 1 по 6, так как они уже были проверены ранее, и первые шесть ферзей остались на своих местах. Проверив седьмую и восьмую клетки, убеждаемся, что установить в них седьмого ферзя не получится, а поэтому снова делаем возврат, и теперь уже пробуем поставить на другое место шестого ферзя. 

 Будем проверять лишь клетки с 5 по 8. Нетрудно убедиться, что ни одна из них не подходит. А значит, выполняем еще один возврат и пытаемся установить пятого ферзя на новое место.

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

Продолжая в таком духе (чередуя установки с возвратами), рано или поздно мы наткнемся на такую расстановку ферзей, которая удовлетворяет всем нашим требованиям. Другими словами на доске будет размещено 8 ферзей, которые не будут бить друг друга. Наткнувшись на такую расстановку, мы сохраним её в отдельный массив, или же сразу можем вывести на экран. После чего, нам необходимо будет продолжить выполнение перебора.

Такая вот огромная подсказка. Используя полученные знания, попытайтесь теперь написать соответствующую программу.