Как поставить 8 ферзей чтобы они не пересекались?

14 ответов на вопрос “Как поставить 8 ферзей чтобы они не пересекались?”

  1. omg Ответить


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

    И как только алгоритм отработает мы получим все возможные решения.
    Так в чем же проблема? В нашем случае, для доски 8х8, мы получим 92 различные решения, а представим, что, как это часто бывает в реальных задачах, мы не знаем размера доски. Если доска будет 25×25, как в тай сёги, тогда количество решений уже будет 275,986,683,743,434.
    Таблица, зависимость количества решений от размера доски:
    n:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    ..
    24
    25
    26
    уникальных:
    1
    1
    2
    1
    6
    12
    46
    92
    341
    1,787
    9,233
    45,752
    ..
    28,439,272,956,934
    275,986,683,743,434
    2,789,712,466,510,289
    различных:
    1
    2
    10
    4
    40
    92
    352
    724
    2,680
    14,200
    73,712
    365,596
    ..
    227,514,171,973,736
    2,207,893,435,808,352
    22,317,699,616,364,044
    Что это будет значить для нашего скрипта? А то, что он уйдет в очень долгий поиск, и так-как все решения ему придется держать в уме, то уже через 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+[n_row])
    def safe_queen(new_row, new_col, sol):
    for col in range(len(sol)):
    if (sol[col] == new_row or
    abs(col – new_col) == abs(sol[col] – new_row)):
    return 0
    return 1
    if __name__ == “__main__”:
    for n in range(8):
    rc_queens(1, 8, [n])
    P.S. Это всего лишь взгляд на проблему со стороны хакера, может кто-то предложит взгляд со стороны «theoretical computer science»?

  2. Direforge Ответить


    Задача о восьми ферзях
    Очевидно, больше восьми мирных ферзей (как и ладей) на обычной доске расставить невозможно. Найти какое-нибудь расположение восьми ферзей, не угрожающих друг другу, легко (на рисунке представлены четыре искомые расстановки). Значительно труднее подсчитать общее число расстановок и вывести их, в чем, собственно, и состоит задача.
    Любопытно, что многие авторы ошибочно приписывали эту задачу и ее решение самому К. Гауссу. На самом деле, она была впервые поставлена в 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[8]). Порядок элемента в этом массиве означает номер ферзя и его x’овую координату, то есть столбец, а его значение – y’овую координату, или строку. Мы используем то свойство, что на одном столбце не могут находиться несколько ферзей.

  3. Drela Ответить

    Пробовали ли вы когда-нибудь расставить 8 ферзей на шахматной доске так, чтобы ни один из них не находился под ударом? Зная, что ферзь бьет по вертикали, горизонтали и диагонали, довольно непросто подобрать такую позицию. Но не для С. Небольшая программа за считанные минуты выдаст вам около 90 таких позиций, например, вот такую:

    int col[8], up_free[15], dn_free[15], coln[8] ;
    main( )
    {
    int i ;
    for ( i = 0 ; i < = 7 ; i++ ) col[i] = 1 ; for ( i = 0 ; i <= 14 ; i++ ) up_free[i] = dn_free[i] = 1 ; clrscr( ) ; addqueen( ) ; } addqueen( ) { int i, c, r ; static int comb, row = -1 ; row++ ; /* Проверяем колонки */ for ( i = 0 ; i <= 7 ; i++ ) { /* если клетка не находится под ударом */ if ( col[i] && up_free[i+row] && dn_free[row-i+7]) { /* запоминаем, что в строке находится ферзь */ coln[row] = i ; /* маркируем колонку и диагональ */ col[i] = 0 ; up_free[i+row] = 0 ; dn_free[row-i+7] = 0 ; /* если заполнены все строки */ if ( row>= 7 )
    {
    comb++ ;
    printf ( “\n\n\ncombination no. %d”, comb ) ;
    for ( r = 0 ; r <= 7 ; r++ ) { printf ( "\n" ) ; for ( c = 0 ; c <= 7 ; c++ ) { if ( c == coln[r] ) printf ( " Q " ) ; else printf ( " . " ) ; } } } else addqueen( ) ; /* снимаем пометку с колонки и диагонали */ col[ coln[row] ] = 1 ; up_free[ row + coln[row] ] = 1 ; dn_free[ row - coln[ row ] + 7 ] = 1 ; } } row-- ; /* уменьшаем счетчик строк, пробуем следующую комбинацию */ }

  4. Aigul Avon Ответить

    “8 ферзей” – это интересная игра для любителей головоломок. Идея для игры была подсказана известной логической задачей о расстановке фигур на шахматной доске. По условию задачи требуется расставить на самой обычной 64-клеточной шахматной доске 8 ферзей. Фигуры должны находится таким образом, чтобы ни одна из них не находилась под атакой другой фигуры. Каждый игрок знает, что ферзь или королева – самая сильная шахматная фигура. И не так-то просто разойтись на доске даже двумя ферзями, а в игре предстоит разместить целых восемь фигур! Игроку дана трехмерная доска, на которой с помощью мышки, он может устанавливать фигуры. Нажатием левой кнопки мыши можно установить королеву на любую клеточку поля. Теперь нужно внимательно следить, чтобы после второй установки следующей фигуры, ее линии атаки по горизонтали, вертикали и диагонали не пересекались с предыдущей фигурой. Все очень просто, но и одновременно достаточно сложно, ведь чем больше ферзей появляется на шахматном поле сражений, тем меньше свободного места остается. Если фигура попадет под влияние другого ферзя, то она будет считаться “убитой”. Потренируйте логическое мышление в этой увлекательной и бесплатной головоломке.

  5. LoRd # Ответить

    Одной из самых знаменитых математических задач на шахматной доске, является задача о восьми ферзях.
    Задача о восьми ферзях привлекала внимание великого математика – Карла Гаусса.
    Сколькими способами можно расставить на доске восемь ферзей так, чтобы они не угрожали друг другу?
    Очевидно, больше восьми мирных ферзей
    на обычной шахматной доске расставить невозможно.
    Найти мирное расположение восьми ферзей, не угрожающих друг другу, достаточно легко, например 10 видов расстановок ферзей:
    a4, b1, c5, d8, e6, f3, g7, h2
    a4, b7, c3, d8, e2, f5, g1, h6
    a6, b4, c2, d8, e5, f7, g1, h3
    a4, b2, c5, d8, e6, f1, g3, h7
    a4, b2, c7, d3, e6, f8, g1, h5
    a4, b2, c7, d3, e6, f8, g5, h1
    a3, b5, c2, d8, e6, f4, g7, h1
    a4, b1, c5, d8, e2, f7, g3, h6
    a4, b8, c1, d5, e7, f2, g6, h3
    a4, b2, c7, d5, e1, f8, g6, h3
    Более трудной задачей является подсчет общего числа расстановок, в этом и состоит задача о восьми ферзях.
    Многие авторы ошибочно приписывали эту задачу и ее решение самому К. Гауссу.
    На самом же деле, она была впервые поставлена в 1848 г. немецким шахматистом М. Беццелем.
    Гаусс же нашел 72 решения, которые и сообщил в письме к другу астроному Шумахеру в сентябре 1850 года.
    Полный набор решений состоит из 92 позиций.
    Существенных решений (не совпадающих при отражениях и поворотах доски) имеется только двенадцать.
    Остальные 80 расстановок получаются из этих двенадцати при помощи поворотов и отражений доски.
    Различные способы расположения 8-ми мирных ферзей описаны в литературе по занимательной математике,
    методы Гюнтера, Глэшера, Пермантье, Ла-Ное.
    Но в 21 веке задача о 8-ми ферзях не вызывала такой же большой интерес, как в прошлом, так как
    компьютерная программа, разработанная студентом первокурсником матфака, позволяет напечатать на бумаге все искомые 92 позиций.
    Из каждого решения задачи о ферзях можно получить ряд других при помощи поворотов
    (вращений) доски на 90, 180 и 270°, а также при ее зеркальном отражении относительно линий,
    разделяющих доску пополам.
    Набор расстановок восьми мирных ферзей называется основным, если,
    эти расстановки не переходят друг в друга при поворотах и отражениях доски,
    и любая другая расстановка получается из какой-нибудь основной
    при помощи данных преобразований доски.
    Второй вариант этой задачи: 8-korolev.html.
    Нескучной вам логической игры! Сам великий Карл Гаусс с ней развлекался.

    Ссылки на другие браузерные онлайн игры в шахматы:
    Шахматы игра с компьютером – играть бесплатно и без регистрации
    на флеш на уровне 1-ого разряда.
    FlashChess III шахматы с компьютером онлайн – флеш игра в шахматы.
    Шахматы Barack Obama – политические шахматы.
    SparkChess – красивые бесплатные флеш шахматы на русском языке.
    Простые 2D флеш шахматы – Easy Chess онлайн, играть бесплатно
    Все шахматы – ссылки на все браузерные онлайн флеш игры в шахматы

Добавить ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *