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

Разбираемся, что же там нового открыли в задаче о ферзях

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

Сможете поставить ещё шесть? А найти все решения?
(картинка из статьи)

Далее, к сожалению, произошла какая-то совершенно невразумительная история из цепочки вот таких вот превращений:

Отличная статья —пресс служба университета—>невразумительный пресс-релиз.
Пресс релиз —занятный перевод—>непонятная статья на гиктаймс

Стоит отметить, что пять наугад открытых ссылок на русском ещё меньше проясняли картину происходящего.

Я тут подумал — надо бы кому-то эту странную цепочку прервать и нормальным языком изложить суть событий.

О чём пойдёт речь:

История задачи
- Латинский квадрат
- Задача о восьми ферзях
- Расстановка N ферзей
- Подсчет числа решений
- Дополнение до N ферзей
- Вариации задачи
- Линейный поиск для N ферзей
- Как считать число решений на практике
- Дополнение до N
История задачи

Латинский квадрат

Задача известна еще с древности (~ средних веков), необходимо расставить буквы таким образом, чтобы ни в одной строке и ни в одной колонке не было одинаковых, как например здесь:

Само название Латинский Квадрат получило из-за привычки использовать буквы латинского Леонардом Эйлером для данной задачи. Из латинского квадрата (и ряда похожих задач) естественным образом появлялись новые, такие как задача о ферзях, где добавляется дополнительное ограничение на диагонали.

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

Задачу придумал в 1848 году шахматный композитор Макс Беззель: суть задачи в том, чтобы расставить 8 ферзей на шахматной доске так, чтобы они не атаковали друг друга. С тех пор многие математики, например Гаусс, работали над задачей, а алгоритмисты и программисты, такие как Дейкстра, придумали множество подходов к поиску и подсчету решений.

В задаче, о которой мы будем говорить, не 8 ферзей, а N и доска, соответственно, не обычная шахматная, а NxN.

Три типа задачи «о ферзях»

Есть три наиболее популярных постановки задачи о ферзях

Расстановка N ферзей

Задача формулируется очень прямолинейно.

Дано: пустая доска NxN, например 8х8

(в принципе понятно, что достаточно просто указать N, но так наглядней)

Найти: расстановку максимально возможного числа ферзей

Т.е. на вход число — размер доски, а на выход позиции ферзей (одного решения).

Подсчет числа решений

Задача ставится тоже достаточно просто:

Дано: размер пустой доски N
Найти: H число возможных расстановок N ферзей на доске

Например, размер доски N = 1, тогда число возможных расстановок H = 1.
N = 8 => H = 92.

Дополнение до N ферзей

Вот тут формулировка чуть-чуть коварней:

Дано: размер доски N и M позиций уже установленных ферзей
Найти: позиции оставшихся N — M ферзей

Визуально все как на КПДВ:

(картинка также из оригинальной статьи)

Вариации задачи

Вообще говоря, вариаций задачи больше: см. например: расстановку белых и черных ферзей
http://www.csplib.org/Problems/prob110
однако здесь мы рассматриваем только основной классический вариант.

В подобной вариации решения существенно отличаются (белые не бьют белых, а черные черных: в случае путаницы — см. комментарии тут):

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

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

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

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

Самый интересный момент, что даже специалисты иногда путаются и думают, что для решения N-ферзей нужен комбинаторный поиск и думают, что сложность задачи выше P. Про то, что такое P и NP, когда-то уже писал на Хабре: Зачем нам всем нужен SAT и все эти 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 и вот, что вышло (запущено на обычном домашнем ноутбуке):

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

Хотите улучшить этот вопрос? Переформулируйте вопрос так, чтобы он был сосредоточен только на одной проблеме.

Закрыт 2 года назад .

Есть задача с расстановкой на шахматной доске 8х8, 8 ферзей так, чтобы ни один из них не мог быть атакован другим. Решить нужно простой проверкой элементов доски по горизонтали, вертикали и диагоналям соответственно текущей позиции вставки на доске. 0 на доске соответствуют пустой позиции, 1-установленному ферзю. Есть код:
```
#include using namespace std; bool SVert(int arr[8][8], int i, int j) < bool inf = true; for (int i = 0; i < 8; i++) < if (arr[j][i] == 1) < inf = false; return inf; >> return inf; > bool SHor(int arr[8][8], int i, int j) < bool inf = true; for (int j = 0; j < 8; j++) < if (arr[i][j] == 1) < inf = false; return inf; >> return inf; > bool SDiag(int arr[8][8], int i, int j) < bool d1 = true, d2 = true, inf = true; return inf; >void Nulification(int arr[8][8]) < for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) arr[i][j] = 0; >void Show(int arr[8][8]) < for (int i = 0; i < 8; i++) < for (int j = 0; j < 8; j++) cout cout void Ferzification(int arr[8][8]) < int counter = 0; while (counter < 8) < for(int i=0;i<8;i++) for(int j=0; j<8; j++) if (SVert(arr,i,j) && (SHor(arr, i, j)) && (SDiag(arr, i, j))) < arr[i][j] = 1; counter++; >> cout int main()
```
Нужно дописать функцию проверки на 2 горизонтали, которая вернет True, если на обеих горизонталях, относительно позиции вставки нет ферзя, но что-то совсем мысли в голову не идут, хотя дело элементарно.

Задача «Ферзи»

Известно, что на доске 8×8 можно расставить 8 ферзей так, чтобы они не били друг друга. Вам дана расстановка 8 ферзей на доске, определите, есть ли среди них пара бьющих друг друга.

Программа получает на вход восемь пар чисел, каждое число от 1 до 8 — координаты 8 ферзей. Если ферзи не бьют друг друга, выведите слово NO , иначе выведите YES .

Решение задачи от разработчиков на Python:

Copy to Clipboard

Другая реализация задачи на Python:

Copy to Clipboard

Смотреть видео — Задача «Ферзи» решение на Python

Делитесь с друзьями ссылкой на ответ и задавайте вопросы в комментариях! ��

Related Posts

Задача «Родословная: LCA»

Задача «Родословная: предки и потомки»

Задача «Родословная: подсчет уровней»

Задача «Продажи»

5 2 голоса
Рейтинг статьи
Подписаться
2 комментариев
Новые Популярные
Межтекстовые Отзывы
Посмотреть все комментарии
1 год назад
10 месяцев назад

Сделал без необходимости перебора всех элементов, если будет найдены пересекающиеся ферзи цикл будет прерван сразу.
k = 8
coord_list = []
answer = «»

for _ in range(k):
p = [int(s) for s in input().split()]

for elem in coord_list:
if (elem[0] == p[0] or elem[1] == p[1]): #checking for horizontal & vertical crossing
answer = ‘YES’
break
elif (elem[0] — p[0] == elem[1] — p[1]) or (elem[0] + elem[1] == p[0] + p[1]): #checking for diagonal crossing
answer = ‘YES’
break

if answer == ‘YES’:
break
else:
answer = ‘NO’
coord_list.append(p) #appending element after loop for not cheching element itself
continue

Задача «8 ферзей»

«8 ферзей» – отличная задача-головоломка для развития логического мышления. Эта online флеш-игра является своеобразной современной формулировкой известной шахматной задачи, придуманной шахматистом Максом Базелем в 1848 г.

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

Правила. Задача о 8 ферзях имеет своим единственным условием задание расставить на стандартной шахматной доске (64 клетки, 8х8) 8 фигур – ферзей, (или королев, если угодно), таким образом, чтоб ни одна из них не была под боем другой.

Вспоминается фраза из «Трех мушкетеров» Дюма, отпущенная Ришелье во время игры в шахматы с д’Артаньяном: «Это королева, она ходит как угодно». Эта цитата хоть в конкретном случае и была двойственной, но все же она для тех, кто незнаком с правилами игры в шахматы. Уточним, что ферзь ходит на любое поле по вертикали, горизонтали и диагонали, на любые расстояния.

Полезные советы или в поисках решения

Всего оригинальных решений 12. Общее количество возможных (с учетом применения операции симметрии) вариантов – 92. Первым опубликовал ответ на эту задачу в 1850 г. Франц Нак. С тех пор многие ученые решали и исследовали эту задачу, предлагая собственные варианты решения. Так, известный немецкий математик, механик и физик Карл Гаусс очень любил эту головоломку и находил 72 варианта возможной расстановки. Он творчески подошел к процессу поиска ответа – разные комбинации 8 ферзей достигались с помощью интересного приёма… поворота доски на 90, 180 и 270 градусов соответственно. Такое вот нетривиальное решение этой головоломки.

Задача достаточно сложная, но как минимум один вариант как правильно расставить ферзей находится довольно быстро и называется явным. Самое популярное правильное расположение достигается следующей расстановкой ферзей: a2, b4, c6, d8, e3, f1, g7, h5. Схема данной расстановки изображена на первом рисунке, оставшиеся три способа расставить ферзей были найдены при вращении шахматной доски.

Другие комбинации постарайтесь найти самостоятельно. Успехов!

Тренируемые навыки

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

Отзывы и комментарии

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

Советуем также прочитать:
- Сторителлинг
- Сколько вариантов одеться?
- Задача коммивояжера
- Сегодня задача Ферми
- Как и зачем развивать мышление
- Задача «Сколько весит стакан?»
- Как организовать свои дела с помощью Agile
- Как и зачем развивать логику?
- Техники мышления
- Шахматы для начинающих
- Задача про 2 монеты
Похожие публикации: