Рассмотрим такую любимую задачу на понимание алгоритмов, как «Задача о восьми ферзях». Классическое определение: «расставить на шахматной доске 8 ферзей так, чтобы ни один из них не бил другого». Ок, задачка очень популярная на разных собеседованиях, и Википедия нам сразу дает решение на моем любимом Python"е .

И это наверняка правильное решение с точки зрения обычного человека, но абсолютно бессмысленное с точки зрения хакера, и вот я вам расскажу почему:

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

И как только алгоритм отработает мы получим все возможные решения.

Так в чем же проблема? В нашем случае, для доски 8х8, мы получим 92 различные решения, а представим, что, как это часто бывает в реальных задачах, мы не знаем размера доски. Если доска будет 25x25, как в тай сёги , тогда количество решений уже будет 275,986,683,743,434.

Таблица, зависимость количества решений от размера доски:

Что это будет значить для нашего скрипта? А то, что он уйдет в очень долгий поиск, и так-как все решения ему придется держать в уме, то уже через 15 мин Python будет съедать 300 мегабайтов памяти. Кто обладает мощным процессором и большим объемом оперативной памяти может проверить, завершиться ли этот процесс вообще...

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

А код был бы на много проще, и даже бы через 15 мин скрипт съедал бы ровно столько же памяти, как и через секунду после запуска. И вот бы как его реализация выглядела бы на Python"е:

Def rc_queens(n_col, width, sol): if len(sol) == width: print sol else: for n_row in range(width): if (safe_queen(n_row, n_col, sol)): rc_queens(n_col+1, width, sol+) def safe_queen(new_row, new_col, sol): for col in range(len(sol)): if (sol == new_row or abs(col - new_col) == abs(sol - new_row)): return 0 return 1 if __name__ == "__main__": for n in range(8): rc_queens(1, 8, [n])
P.S. Это всего лишь взгляд на проблему со стороны хакера, может кто-то предложит взгляд со стороны «theoretical computer science»?

Пару месяцев назад появилась с анализом классической задачи о расстановке ферзей на шахматной доске (см. детали и историю ниже). Задача невероятно известная и вся уже рассмотрена под микроскопом, поэтому было удивительно, что появилось что-то действительно новое.

(здесь максимальное число ферзей, причем на месте крестика можно поставить белого, а на месте точке черного - но не обоих сразу; взято из статьи)

Модели и сложность задач

Пришло время собственно обсудить: а как это вообще все решать и насколько быстро это вообще можно сделать?

Линейный поиск для классической задачи

Самый интересный момент, что даже специалисты иногда путаются и думают, что для решения N-ферзей нужен комбинаторный поиск и думают, что сложность задачи выше P. Про то, что такое P и NP, когда-то уже писал на Хабре: и . Однако, задача решается без перебора вариантов! Т.е., для доски любого размера можно всегда расставить ферзей один за одним лесенкой:

Отсюда вывод, для N = 1 и N > 3 решение всегда есть (см. алго), а для N = 2 или N = 3
всегда нет (тривиально следует из доски). Это значит, что задача разрешимости для N ферзей (где нужно сказать есть решение или нет) решается тривиально за константное время (ну ок, конструктивно за линейное - расставить/проверить).

Самое время перепроверить прочитанное, читаем типичный заголовок "задачу о N ферзях признали NP-полной задачей" - у вас замироточили глаза?

Как считать число решений на практике

Вот тут начинается самое интересное: у количества решений задачи о расстановке ферзей даже есть своё имя - "последовательность A000170 ". На этом хорошие новости заканчиваются. Сложность задачи: выше NP и P#, на практике это означает, что оптимальное решение - это скачать данные последовательности в словарь и возвращать нужное число. Так как для N=27 оно уже считалось на параллельном кластере сколько там недель.

Решение : выписываем табличку и по n, возвращаем а(n)
n a(n)
1: 1
2: 0
3: 0
4: 2
5: 10
6: 4
7: 40
8: 92
9: 352
10: 724
…
21: 314666222712
22: 2691008701644
23: 24233937684440
24: 227514171973736
25: 2207893435808352
26 22317699616364044
27: 234907967154122528

Однако, если у вас какая-то хитрая разновидность задачи и все-таки нужно посчитать решения (а их количество неизвестно и раньше их никто не посчитал), то лучший вариант прототипа обсуждается чуть ниже.

Дополнение до N и Answer Set Programming

Тут начинается самое интересное: в чём же состоит новый результат статьи? Задача о дополнении до N ферзей - NP-полна ! (Интересно, что про NP-полноту дополнения латинского квадрата было известно ещё в 1984-ом году.)

Что это означает на практике? Самый простой способ решишь эту задачу (или вдруг, если нам нужно её вариацию) - использовать SAT. Однако, мне больше нравится следующая аналогия:

SAT - это ассемблер для комбинаторных NP-задач, а Answer Set Programming (ASP) - это С++ (у ASP тоже загадочная русская душа: он временами запутан и непредсказуем для непосвященных; кстати, теория, лежащая в основе современного ASP , была придумана в 1988ом году Михаилом Гельфондом и Владимиром Лифшицем, работавших тогда в университетах Техаса и Стэнфорда соответственно).

Если говорить упрощенно: ASP - это декларативный язык программирования ограничений (constraints в англоязычной литературе) с синтаксисом Prolog. То есть мы записываем, каким ограничениям должно удовлетворять решение, а система сводит всё к варианту SAT и находит нам решение.

Детали решения здесь не столь важны, и Answer Set Programming достоин отдельного поста (который лежит у меня в черновике уже неприлично долго): поэтому разберем концептуальные моменты

% domain row(1..n). column(1..n). % alldifferent 1 { queen(X,Y) : column(Y) } 1:- row(X). 1 { queen(X,Y) : row(X) } 1:- column(Y). % remove conflicting answers:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 == Y2. :- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2. :- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.

Строка 1 { queen(X,Y) : column(Y) } 1:- row(X). - называется choice rule, и она определяет, что является допустимым пространством поиска.

Последние три строки называются integrity constraints: и они определяют каким ограничениям должно удовлетворять решение: не может быть ферзя в одном и том же ряду, не может быть ферзя в одной и той же колонке (опущено, в силу симметрии) и не может быть ферзя на одной и той же диагонали.

В качестве системы для экспериментов рекомендую Clingo .
И для начала стоит посмотреть их tutorial и попочитать блог на www.hakank.org .

Безусловно, если впервые писать на ASP, то первая модель не выйдет невероятно эффективной и быстрой, но скорее всего будет быстрее перебора с возвратом, написанным на скорую руку. Однако, если понять основные принципы работы системы, ASP может стать "regexp для NP-полных задач".

Проведем простой численный эксперимент с нашей ASP моделью. Я добавил 5 коварных ферзей в модель и запустил поиск решения для N от 1 до 150 и вот, что вышло (запущено на обычном домашнем ноутбуке):

Итого, наша ASP модель примерно в течении минуты может найти решения задачи о дополнении при N <= 150 (в обычном случае). Это показывает, что система отлично подходит для прототипирования моделей сложных комбинаторных задач.

Выводы

• Новый результат связан не с классической задачей о 8 ферзях, а дополнении обобщенной задачи о ферзях (что интересно, но в целом закономерно);
• Сложность существенно возрастает, так как, коварно поставив ферзей на доске, можно сбить алгоритм, ставящий ферзей по какой-то фиксированной закономерности;
• Эффективно посчитать число решений нельзя (ну совсем; пока не случится какой-то ужас и P не сравняется с NP итд);
• Возможно этот результат повлияет на работу современных SAT систем, так как некоторые эксперты считают, что эта задача в чем-то проще классических NP-полных задач (но это только мнение)
• Если вам вдруг зачем-то нужно решать подобную задачу - лучше всего воспользуйтесь системами аля Answer Set Programming, специально для этого предназначенных

Эта задача - одна из очень интересных шахматных головоломок.

Условие такое: можно ли поставить восемь ферзей на пустой доске таким образом, чтобы ни один из них не "атаковал" другого, т.е. так, чтобы ни какие два ферзя не стояли на одном и том же столбце, или на одной и той же строке, или на одной и той же диагонали шахматной доски. Решение этой задачи, как вы понимаете, существует, причем не одно. На рис.1 я показал один из возможных вариантов расстановки ферзей.

			Ф
Ф
				Ф
							Ф
	Ф
						Ф
		Ф
					Ф

Рисунок 1

Решение этой задачи на компьютере не представляет большой сложности. В принципе, можно тупо перебрать все возможные варианты расстановки ферзей на доске, а затем определить подходящие. Написать такую программу не сложно, но возникает вопрос: "Сколько существует вариантов и сколько времени нужно для их перебора?" Честно говоря, считать точное количество вариантов мне было лень, но, судя по всему, ждать придется долго.

Поэтому, нужно каким-то образом определить на какую клетку ставить следующего ферзя. Например, ставить несколько ферзей в одну линию бессмысленно (это противоречит условию). Если попробовать решить задача вручную, то становится понятно, что расставить 6 - 7 ферзей не сложно. Но после этого свободных клеток (которые не "бьются" ни одним из ферзей) нет. Следовательно, ферзей нужно расставлять так, чтобы они били как можно меньше клеток. Очень хорошо если несколько разных ферзей "бьют" одни и те же клетки, но при этом не "бьют" друг друга.

Подобные алгоритмы называются эвристическими и очень часто используются при разработке компьютерных игр. Эти алгоритмы обычно содержат условия, на основании которых компьютер может просчитать последствия того или иного хода (в данном случае, это количество клеток, которые будет "бить" ферзь), и выбрать лучший из них. Другие примеры программ, использующих эвристические алгоритмы вы можете посмотреть на сайте http://www.vova-prog.narod.ru/.

Для решения задачи нам понадобиться массив accessibility. В нем мы будем хранить информацию о том, свободна данная клетка или нет. Таким образом, для того чтобы определить сколько клеток будет "бить" ферзь из заданной, нам нужно перемещать ферзя по всем возможным направлениям (их 8) и считать свободные клетки. Для перемещения ферзя удобно использовать два одномерных массива, элементы которых указывают на сколько клеток нужно сместить ферзя при движении в выбранном направлении. Я определил их таким образом:

Const int vert = {0,-1,-1,-1,0,1,1,1}; const int hor = {1,1,0,-1,-1,-1,0,1};

Нулевой элемент соответствует перемещения вправо. Первый - по диагонали вправо и вверх, и т.д.

Для перемещения ферзя, например, на одну клетку вниз можно записать

X += hor; y += vert;

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

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

КУРСОВАЯ РАБОТА

«Решение задачи о 8 ферзях»

Харьков 2007

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

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

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

Задача звучит следующим образом:

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

Задача о восьми ферзях

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

Любопытно, что многие авторы ошибочно приписывали эту задачу и ее решение самому К. Гауссу. На самом деле, она была впервые поставлена в 1848 г. немецким шахматистом М. Беццелем. Доктор Ф. Наук нашел 60 решений и опубликовал их в газете «Illustrierte Zeitung» от 1 июня 1850 г. Лишь после этого Гаусс заинтересовался задачей и нашел 72 решения, которые он сообщил в письме к своему другу астроному Шумахеру от 2 сентября 1850 г. Полный же набор решений, состоящий из 92 позиций, получил все тот же Ф. Наук. Он привел их в упомянутой газете от 21 сентября 1850 г. Эта хронология установлена известным немецким исследователем математических развлечений В. Аренсом.

Строгое доказательство того, что 92 решения исчерпывают все возможности, было получено лишь в 1874 г. английским математиком Д. Глэшером (при помощи теории определителей). Забегая вперед, отметим, что существенных решений (не совпадающих при отражениях и поворотах доски) имеется только двенадцать.

Известно много способов организовать эффективный поиск расположения восьми мирных ферзей (методы Пермантье, Ла-Ное, Гюнтера, Глэшера, Лакьера и др.). Эти способы описаны в многочисленной литературе по занимательной математике. В наш век ЭВМ задача такого сорта не вызвала бы столь живой интерес. Ведь достаточно составить несложную программу, и уже через несколько минут после ее введения в машину все 92 необходимые позиции будут выданы на печать.

Из каждого решения задачи о ферзях можно получить ряд других при помощи поворотов (вращений) доски на 90, 180 и 270°, а также при ее зеркальном отражении относительно линий, разделяющих доску пополам. Например, из расстановки, показанной на рис. а, при повороте доски на 90° по часовой стрелке мы получаем расстановку на рис. в, а при отражении доски относительно линии, разделяющей королевский и ферзевый фланги, – на рис. г. При помощи других поворотов и отражений доски можно получить еще пять решений.

Итак, указанные операции с шахматной доской позволяют из одного расположения мирных ферзей получить, вообще говоря, семь новых. Доказано, что в общем случае на доске nхn (при n > 1) для любой расстановки n мирных ферзей возможны три ситуации:

1) при одном отражении доски возникает новая расстановка ферзей, а при поворотах и других отражениях новых решений не получается;

2) новое решение возникает при повороте доски на 90°, а ее отражения дают еще две расстановки;

3) три поворота доски и четыре отражения приводят к семи различным расстановкам (а если считать и исходную, то всего имеем восемь позиций).

В случае 1) исходное решение называется дважды симметрическим, в случае 2) – симметрическим, а в случае 3) – простым. Для обычной доски каждое решение является либо простым, либо симметрическим, а дважды симметрических не существует.

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

1) см. рис. а;

2) см. рис. б;

3) a4, b1, c5, d8, e6, f3, g7, h2;

4) a4, b2, c5, d8, e6, f1, g3, h7;

5) a4, b2, c7, d3, e6, f8, g1, h5;

6) a4, b2, c7, d3, e6, f8, g5, h1;

7) a3, b5, c2, d8, e6, f4, g7, h1;

8) a4, b1, c5, d8, e2, f7, g3, h6;

9) a4, b7, c3, d8, e2, f5, g1, h6;

10) a6, b4, c2, d8, e5, f7, g1, h3;

11) a4, b8, c1, d5, e7, f2, g6, h3;

12) a4, b2, c7, d5, e1, f8, g6, h3.

Остальные 80 расстановок получаются из этих двенадцати при помощи поворотов и отражений доски. Основная расстановка на рис. б является симметрической, другие одиннадцать основных расстановок – простыми. Итак, всего на доске имеем 11·8+1·4=92 расстановки восьми ферзей, не угрожающих друг другу.

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

Всякое решение задачи о восьми ферзях можно записать как набор (t1, t2, ј, t8), представляющий собой перестановку чисел 1, 2, ј, 8. Здесь ti – номер горизонтали, на которой стоит ферзь i-й вертикали. Так как ферзи не стоят на одной горизонтали, то все числа ti различны, а поскольку ферзи не стоят и на одной диагонали, то для любых i, j (i < j Ј 8) имеем: |tj-ti| № j-i.

Запишем числа 1, 2, ј, 8 сначала по возрастанию, а затем по убыванию. После этого сложим числа каждой из этих двух перестановок с числами произвольной перестановки восьми чисел, например такой – (3, 7, 2, 8, 5, 1, 4, 6): 1, 2, 3, 4, 5, 6, 7, 8

3, 7, 2, 8, 5, 1, 4, 6

4,9, 8, 7, 6, 5, 4, 3, 2, 1

3, 7, 2, 8, 5, 1, 4, 6

11,14,8,13,9,4, 6, 7.

Полученные суммы образуют два набора: (4, 9, 5, 12, 10, 7, 11, 14) и (11, 14, 8, 13, 9, 4, 6, 7). Рассмотрим следующую задачу.

Какие перестановки чисел от 1 до 8 дают в результате указанной операции сложения два таких набора, в каждом из которых все элементы различны?

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

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

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

На доске 1х1 один ферзь ставится на одно-единственное поле, и решение существует. На доске 2х2 один ферзь, где бы ни стоял, нападает на три других поля, и второго ферзя поставить некуда. На доске 3х3 умещаются только два мирных ферзя. Итак, для досок 2х2 и 3х3 задача не имеет решения. Эти два случая представляют собой исключение. Для всех n > 3 на доске nхn можно расставить n не угрожающих друг другу ферзей.

На доске 4ґ4 существует одна основная расстановка, причем дважды симметрическая: a2, b4, c1, d3, т.е. всего имеется два решения. На доске 5ґ5 основных расстановок две: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4. Общее число расстановок равно десяти, причем из них можно выбрать пять таких, при наложении которых друг на друга 25 ферзей заполняют все поля доски 5х5.

Заметим, что в общем случае n расстановок (решений задачи) могут заполнить при наложении всю доску nхn только при тех n, которые не кратны двум и трем. Из этого, в частности, следует, что для обычной доски подобрать восемь расстановок, накрывающих все 64 поля доски, невозможно.

Обобщая алгебраическое свойство решений задачи о восьми ферзях, получаем, что расстановка n ферзей (t1, t2, ј, tn) на доске nґn является искомой, если для любых i, j (i < j Ј n) имеет место: |tj-ti| № j-i. Таким образом, задача об n ферзях сводится к чисто математической задаче о нахождении перестановки чисел 1, 2, ј, n, удовлетворяющей указанному условию. Известно много решений этой задачи, некоторые из них опубликованы в серьезных математических журналах. Один из методов расстановки n ферзей, не угрожающих друг другу на произвольной доске nґn (n і 5), можно найти в книге «Математика на шахматной доске».

Описание алгоритма и структуры программы:

В данной программе реализован рекурсивный метод решения задачи о 8 ферзях.

У нас имеется функция (int put_queen (int x)), которая ставит очередного ферзя на поле и вызывает саму себя для, того чтобы поставить следующего, если очередного ферзя поставить нельзя, то она возвращает управление в функцию, из которой была вызвана, а та в свою очередь пробует поставить своего ферзя в другое место, и опять рекурсивно вызвать себя. Когда функция ставит последнего ферзя, то результат расстановки выводится пользователю.

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

Для сохранения положения ферзей используется массив из 8 элементов целочисленного типа (int queens). Порядок элемента в этом массиве означает номер ферзя и его x’овую координату, то есть столбец, а его значение – y’овую координату, или строку. Мы используем то свойство, что на одном столбце не могут находиться несколько ферзей.

В этой статье поговорим об известной логической головоломке под названием "восемь ферзей ". Суть задачи заключается в том, что нужно суметь расставить на шахматной доске (8 х 8) восемь ферзей так, чтобы они не находились под боем друг друга (напомню, что ферзь (королева) бьет по прямой и по диагонали). Скажу, что вариантов расстановки есть несколько, но найти их вручную не всегда легко, особенно тяжело поставить последнего ферзя. Один из вариантов расстановок ферзей смотрим ниже на рисунке 1

Рисунок 1

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

1. Шахматную доску представить в виде двумерного массива, размером 8 х 8.

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

Рисунок 2

Как видите, если поставить ферзя на позицию x = 2, y = 1, то под боем будет находиться 23 клетки. Такую процедуру нужно будет проделать для каждой клетки шахматной доски (двумерного массива). В итоге получим вот такую картину, показанную ниже на рисунке 3

Рисунок 3

3. После того, как приоритеты расставлены, нужно выбрать клетку с минимальным приоритетом (ту, с которой меньше бьется других клеток доски) и поставить на нее ферзя. Думаю, что тут понятно...т.к., если ставить ферзей на те клетки, с которых можно побить большее количество других клеток, то до расстановки восьми ферзей мы точно не дойдем. Продолжаем рассуждать...если клеток с минимальным приоритетом нашлось несколько (а в самом начале расстановки будет именно так), то выбирать подходящую будем случайным образом. Как это логически обоснованно организовать? Для этого мы должны сначала найти минимальный приоритет (допустим, 21 - именно оно будет самым маленьким в первой итерации - см. рисунок 3), затем сосчитать число клеток с этим приоритетом (в нашем случае с 21 этих одинаковых клеток будет аж 28), далее сгенерировать случайное число в интервале от 1 до числа одинаковых клеток (их 28) и, исходя из полученного при генерации числа, поставить ферзя на нужное место. Ту клетку, куда мы ставим ферзя, будем как-то помечать, допустим, присваивая ей значение 100. Можно брать абсолютно любое значение, только вот подбирайте так, чтобы оно не определялось как минимальное при определении приоритетов.

4. После постановки ферзя, нужно удалить побитые им клетки, пометив их каким-либо числом. Допустим, я буду помечать эти клетки для удобства числом 99.

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

5. Далее опять все повторяется с пункта 2 по 4, пока не расставим всех ферзей, которых должно быть восемь. Тут есть еще один момент: с первой попытки, даже используя так называемый "умный" подход к реализации задачи, приведенный выше алгоритм может не расставить всех восемь ферзей. Но тут есть выход из этого положения. После расстановки мы будем проверять: получилось ли поставить всех ферзей. Если нет, то повторяем расстановку заново.

На следующем четвертом рисунке я привожу в действие описанный выше алгоритм для наглядности. Он может выдавать различные варианты расстановок, но для этого вы должны перезагрузить вашу веб-страницу (кнопка "обновить" в браузере, либо F5) и тогда результат поменяется. К сожаления, web-технологию Ajax я пока что еще не знаю, поэтому для получения новой картинки нужно перезагружать страницу.

Рисунок 4

Вот вид программы (пока что привожу лишь ее основную часть - функцию main()), реализующей алгоритм

Const int SIZE = 8; int main() { int board; int x, y; int *ptrX = &x, *ptrY = &y; srand(time(NULL)); //пока не расставим все 8 ферзей do { resetBoard(board); //пробуем расставить ферзей for(int i = 1; i <= 8; i++) { updateBoard(board); choiseCell(board, ptrX, ptrY); board[x][y] = 100; deleteCell(board, x, y); } } while(!checkQueens(board)); printBoard(board); return 0; }

Как видите, в нем реализовано то, что я говорил выше

1) Объявляем двумерный массив board , размерностью 8 х 8 ячеек - это будет наша шахматная доска. Также нам будут нужны переменные для хранения координат точек (x и y ) и указатели на них (ptrX и ptrY ). Для инициализации массива нулями у нас будет служить функция resetBoard() .

2) Матрица объявлена, инициализирована. Теперь смотрим внутрь цикла for , который и будет у нас выполнять расстановку восьми ферзей. Как мы говорили выше в пункте 2, нам нужно задать для каждой ячейки матрицы свой приоритет. Это будет делать функция updateBoard() .

3) Приоритеты расставлены. Теперь, как мы говорили в пункте 3, нам нужно выбрать клетку с минимальным приоритетом. Если их будет несколько, то выбор сделать случайным образом. Выполняет это все функция choiseCell() , которая принимает в качестве аргументов матрицу и указатели на координаты x и y . Действуя через указатели, эта функция меняет значения координат x и y в основной программе. Т.к. координаты x и y изменились (во время объявления, как видите, они не были инициированы), то можно к матрице board обращаться по индексу. Задаем для выбранных координат значение 100 (здесь у нас стоит ферзь).

4) После постановки ферзя, помечаем убитые им клетки. Выполняет это функция deleteCell() .

Этот процесс повторяется ровно восемь раз, как задано в условиях цикла for . Если, как я писал выше, не получится с первой попытки расставить все восемь ферзей, то процесс расстановки обнуляется с помощью resetBoard() и цикл расстановки начинается заново. Для того, чтобы сообщить нам, расставлены ли все восемь ферзей или нет, служит функция checkQueens() , возвращающая ложь , если не получилось расставить, и истину , если расстановка удалась.

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

//Восемь ферзей //необходимые заголовочные файлы #include #include #include #include const int SIZE = 8; //прототипы функций void resetBoard(int); void updateBoard(int); int helpUpdateBoard(int, int, int, bool); void choiseCell(int, int*, int*); void deleteCell(int, int, int); bool checkQueens(int); void printBoard(int); using namespace std; int main() { int board; int x, y; int *ptrX = &x, *ptrY = &y; srand(time(NULL)); //пока не расставим все 8 ферзей do { resetBoard(board); //пробуем расставить ферзей for(int i = 1; i <= 8; i++) { updateBoard(board); choiseCell(board, ptrX, ptrY); board[x][y] = 100; deleteCell(board, x, y); } } while(!checkQueens(board)); printBoard(board); return 0; } //проверяем, расставлены ли все ферзи или нет bool checkQueens(int board) { int counter = 0; for(int i = 0; i < SIZE; i++) for(int j = 0; j < SIZE; j++) if(board[i][j] == 100) counter++; return (counter == 8 ? true: false); } //обнуляем все клетки доски void resetBoard(int board) { for(int i = 0; i < SIZE; i++) for(int j = 0; j < SIZE; j++) board[i][j] = 0; } //помечаем побитые клетки void deleteCell(int board, int x, int y) { helpUpdateBoard(board, x, y, true); } //ищем подходящую клетку для постановки ферзя void choiseCell(int board, int *ptrX, int *ptrY) { int counter = 0, rnd; int min = board; //находим значение минимального приоритета for(int i = 0; i < SIZE; i++) for(int j = 0; j < SIZE; j++) if(board[i][j] < min) min = board[i][j]; //узнаем сколько в матрице есть клеток в одинак.приоритетом for(int i = 0; i < SIZE; i++) for(int j = 0; j < SIZE; j++) if(board[i][j] == min) counter++; //генерируем случайное число rnd = 1 + rand() % counter; counter = 0; //выбираем одну клетку из одинаковых случайным образом //и запоминаем ее координаты for(int i = 0; i < SIZE; i++) for(int j = 0; j < SIZE; j++) if(board[i][j] == min) if(++counter == rnd) *ptrX = i, *ptrY = j; } //обновляем приоритеты клеток шахматной доски void updateBoard(int board) { for(int i = 0; i < SIZE; i++) for(int j = 0; j < SIZE; j++) if(board[i][j] != 100 && board[i][j] != 99) board[i][j] = helpUpdateBoard(board, i, j, false); } //вспомогательная ф-ция: делаем проходы по всем направлениям //для вычисления приоритетов клеток int helpUpdateBoard(int board, int x ,int y, bool label) { int counter = 0, xTemp = x, yTemp = y; //по диагонали вправо вниз while(xTemp < (SIZE - 1) && yTemp < (SIZE - 1)) { xTemp++; yTemp++; if(label) board = 99; //если клетка не занята ферзем и не побита if(board != 100 && board != 99) counter++; } xTemp = x, yTemp = y; //по диагонали влево вверх while(xTemp > 0 && yTemp > 0) { xTemp--; yTemp--; if(label) board = 99; if(board != 100 && board != 99) counter++; } xTemp = x, yTemp = y; //по диагонали вправо вверх while(xTemp < (SIZE - 1) && yTemp > 0) { xTemp++; yTemp--; if(label) board = 99; if(board != 100 && board != 99) counter++; } xTemp = x, yTemp = y; //по диагонали влево вниз while(xTemp > 0 && yTemp < (SIZE - 1)) { xTemp--; yTemp++; if(label) board = 99; if(board != 100 && board != 99) counter++; } xTemp = x, yTemp = y; //вверх while(yTemp > 0) { yTemp--; if(label) board = 99; if(board != 100 && board != 99) counter++; } xTemp = x, yTemp = y; //вниз while(yTemp < (SIZE - 1)) { yTemp++; if(label) board = 99; if(board != 100 && board != 99) counter++; } xTemp = x, yTemp = y; //вправо while(xTemp < (SIZE - 1)) { xTemp++; if(label) board = 99; if(board != 100 && board != 99) counter++; } xTemp = x, yTemp = y; //влево while(xTemp > 0) { xTemp--; if(label) board = 99; if(board != 100 && board != 99) counter++; } return counter; } //печать результатов void printBoard(int board) { for(int i = 0; i < SIZE; i++) { cout << endl; for(int j = 0; j < SIZE; j++) cout << setw(4) << (board[i][j] == 100 ? "#" : "."); cout << endl; } }

Результат работы программы

P.S. Также на сайте вы можете найти иную реализацию алгоритма "Восемь ферзей", реализованную программистом Алексеем и , за что ему большое спасибо.