Задача о восьми ферзях
Поделись знанием:
– Да, я… я… хочу обновления, – с трудом выговорил Пьер.
– Хорошо, – сказал Смольянинов, и тотчас же продолжал: – Имеете ли вы понятие о средствах, которыми наш святой орден поможет вам в достижении вашей цели?… – сказал ритор спокойно и быстро.
– Я… надеюсь… руководства… помощи… в обновлении, – сказал Пьер с дрожанием голоса и с затруднением в речи, происходящим и от волнения, и от непривычки говорить по русски об отвлеченных предметах.
– Какое понятие вы имеете о франк масонстве?
– Я подразумеваю, что франк масонство есть fraterienité [братство]; и равенство людей с добродетельными целями, – сказал Пьер, стыдясь по мере того, как он говорил, несоответственности своих слов с торжественностью минуты. Я подразумеваю…
– Хорошо, – сказал ритор поспешно, видимо вполне удовлетворенный этим ответом. – Искали ли вы средств к достижению своей цели в религии?
– Нет, я считал ее несправедливою, и не следовал ей, – сказал Пьер так тихо, что ритор не расслышал его и спросил, что он говорит. – Я был атеистом, – отвечал Пьер.
– Вы ищете истины для того, чтобы следовать в жизни ее законам; следовательно, вы ищете премудрости и добродетели, не так ли? – сказал ритор после минутного молчания.
– Да, да, – подтвердил Пьер.
Ритор прокашлялся, сложил на груди руки в перчатках и начал говорить:
– Теперь я должен открыть вам главную цель нашего ордена, – сказал он, – и ежели цель эта совпадает с вашею, то вы с пользою вступите в наше братство. Первая главнейшая цель и купно основание нашего ордена, на котором он утвержден, и которого никакая сила человеческая не может низвергнуть, есть сохранение и предание потомству некоего важного таинства… от самых древнейших веков и даже от первого человека до нас дошедшего, от которого таинства, может быть, зависит судьба рода человеческого. Но так как сие таинство такого свойства, что никто не может его знать и им пользоваться, если долговременным и прилежным очищением самого себя не приуготовлен, то не всяк может надеяться скоро обрести его. Поэтому мы имеем вторую цель, которая состоит в том, чтобы приуготовлять наших членов, сколько возможно, исправлять их сердце, очищать и просвещать их разум теми средствами, которые нам преданием открыты от мужей, потрудившихся в искании сего таинства, и тем учинять их способными к восприятию оного. Очищая и исправляя наших членов, мы стараемся в третьих исправлять и весь человеческий род, предлагая ему в членах наших пример благочестия и добродетели, и тем стараемся всеми силами противоборствовать злу, царствующему в мире. Подумайте об этом, и я опять приду к вам, – сказал он и вышел из комнаты.
– Противоборствовать злу, царствующему в мире… – повторил Пьер, и ему представилась его будущая деятельность на этом поприще. Ему представлялись такие же люди, каким он был сам две недели тому назад, и он мысленно обращал к ним поучительно наставническую речь. Он представлял себе порочных и несчастных людей, которым он помогал словом и делом; представлял себе угнетателей, от которых он спасал их жертвы. Из трех поименованных ритором целей, эта последняя – исправление рода человеческого, особенно близка была Пьеру. Некое важное таинство, о котором упомянул ритор, хотя и подстрекало его любопытство, не представлялось ему существенным; а вторая цель, очищение и исправление себя, мало занимала его, потому что он в эту минуту с наслаждением чувствовал себя уже вполне исправленным от прежних пороков и готовым только на одно доброе.
Через полчаса вернулся ритор передать ищущему те семь добродетелей, соответствующие семи ступеням храма Соломона, которые должен был воспитывать в себе каждый масон. Добродетели эти были: 1) скромность , соблюдение тайны ордена, 2) повиновение высшим чинам ордена, 3) добронравие, 4) любовь к человечеству, 5) мужество, 6) щедрость и 7) любовь к смерти.
– В седьмых старайтесь, – сказал ритор, – частым помышлением о смерти довести себя до того, чтобы она не казалась вам более страшным врагом, но другом… который освобождает от бедственной сей жизни в трудах добродетели томившуюся душу, для введения ее в место награды и успокоения.
«Да, это должно быть так», – думал Пьер, когда после этих слов ритор снова ушел от него, оставляя его уединенному размышлению. «Это должно быть так, но я еще так слаб, что люблю свою жизнь, которой смысл только теперь по немногу открывается мне». Но остальные пять добродетелей, которые перебирая по пальцам вспомнил Пьер, он чувствовал в душе своей: и мужество , и щедрость , и добронравие , и любовь к человечеству , и в особенности повиновение , которое даже не представлялось ему добродетелью, а счастьем. (Ему так радостно было теперь избавиться от своего произвола и подчинить свою волю тому и тем, которые знали несомненную истину.) Седьмую добродетель Пьер забыл и никак не мог вспомнить ее.
В третий раз ритор вернулся скорее и спросил Пьера, всё ли он тверд в своем намерении, и решается ли подвергнуть себя всему, что от него потребуется.
– Я готов на всё, – сказал Пьер.
– Еще должен вам сообщить, – сказал ритор, – что орден наш учение свое преподает не словами токмо, но иными средствами, которые на истинного искателя мудрости и добродетели действуют, может быть, сильнее, нежели словесные токмо объяснения. Сия храмина убранством своим, которое вы видите, уже должна была изъяснить вашему сердцу, ежели оно искренно, более нежели слова; вы увидите, может быть, и при дальнейшем вашем принятии подобный образ изъяснения. Орден наш подражает древним обществам, которые открывали свое учение иероглифами. Иероглиф, – сказал ритор, – есть наименование какой нибудь неподверженной чувствам вещи, которая содержит в себе качества, подобные изобразуемой.
Пьер знал очень хорошо, что такое иероглиф, но не смел говорить. Он молча слушал ритора, по всему чувствуя, что тотчас начнутся испытанья.
– Ежели вы тверды, то я должен приступить к введению вас, – говорил ритор, ближе подходя к Пьеру. – В знак щедрости прошу вас отдать мне все драгоценные вещи.
– Но я с собою ничего не имею, – сказал Пьер, полагавший, что от него требуют выдачи всего, что он имеет.
– То, что на вас есть: часы, деньги, кольца…
Пьер поспешно достал кошелек, часы, и долго не мог снять с жирного пальца обручальное кольцо. Когда это было сделано, масон сказал:
– В знак повиновенья прошу вас раздеться. – Пьер снял фрак, жилет и левый сапог по указанию ритора. Масон открыл рубашку на его левой груди, и, нагнувшись, поднял его штанину на левой ноге выше колена. Пьер поспешно хотел снять и правый сапог и засучить панталоны, чтобы избавить от этого труда незнакомого ему человека, но масон сказал ему, что этого не нужно – и подал ему туфлю на левую ногу. С детской улыбкой стыдливости, сомнения и насмешки над самим собою, которая против его воли выступала на лицо, Пьер стоял, опустив руки и расставив ноги, перед братом ритором, ожидая его новых приказаний.
– И наконец, в знак чистосердечия, я прошу вас открыть мне главное ваше пристрастие, – сказал он.
– Мое пристрастие! У меня их было так много, – сказал Пьер.
– То пристрастие, которое более всех других заставляло вас колебаться на пути добродетели, – сказал масон.
Пьер помолчал, отыскивая.
«Вино? Объедение? Праздность? Леность? Горячность? Злоба? Женщины?» Перебирал он свои пороки, мысленно взвешивая их и не зная которому отдать преимущество.
– Женщины, – сказал тихим, чуть слышным голосом Пьер. Масон не шевелился и не говорил долго после этого ответа. Наконец он подвинулся к Пьеру, взял лежавший на столе платок и опять завязал ему глаза.
– Последний раз говорю вам: обратите всё ваше внимание на самого себя, наложите цепи на свои чувства и ищите блаженства не в страстях, а в своем сердце. Источник блаженства не вне, а внутри нас…
Пьер уже чувствовал в себе этот освежающий источник блаженства, теперь радостью и умилением переполнявший его душу.
Скоро после этого в темную храмину пришел за Пьером уже не прежний ритор, а поручитель Вилларский, которого он узнал по голосу. На новые вопросы о твердости его намерения, Пьер отвечал: «Да, да, согласен», – и с сияющею детскою улыбкой, с открытой, жирной грудью, неровно и робко шагая одной разутой и одной обутой ногой, пошел вперед с приставленной Вилларским к его обнаженной груди шпагой. Из комнаты его повели по коридорам, поворачивая взад и вперед, и наконец привели к дверям ложи. Вилларский кашлянул, ему ответили масонскими стуками молотков, дверь отворилась перед ними. Чей то басистый голос (глаза Пьера всё были завязаны) сделал ему вопросы о том, кто он, где, когда родился? и т. п. Потом его опять повели куда то, не развязывая ему глаз, и во время ходьбы его говорили ему аллегории о трудах его путешествия, о священной дружбе, о предвечном Строителе мира, о мужестве, с которым он должен переносить труды и опасности. Во время этого путешествия Пьер заметил, что его называли то ищущим, то страждущим, то требующим, и различно стучали при этом молотками и шпагами. В то время как его подводили к какому то предмету, он заметил, что произошло замешательство и смятение между его руководителями. Он слышал, как шопотом заспорили между собой окружающие люди и как один настаивал на том, чтобы он был проведен по какому то ковру. После этого взяли его правую руку, положили на что то, а левою велели ему приставить циркуль к левой груди, и заставили его, повторяя слова, которые читал другой, прочесть клятву верности законам ордена. Потом потушили свечи, зажгли спирт, как это слышал по запаху Пьер, и сказали, что он увидит малый свет. С него сняли повязку, и Пьер как во сне увидал, в слабом свете спиртового огня, несколько людей, которые в таких же фартуках, как и ритор, стояли против него и держали шпаги, направленные в его грудь. Между ними стоял человек в белой окровавленной рубашке. Увидав это, Пьер грудью надвинулся вперед на шпаги, желая, чтобы они вонзились в него. Но шпаги отстранились от него и ему тотчас же опять надели повязку. – Теперь ты видел малый свет, – сказал ему чей то голос. Потом опять зажгли свечи, сказали, что ему надо видеть полный свет, и опять сняли повязку и более десяти голосов вдруг сказали: sic transit gloria mundi. [так проходит мирская слава.]
Пьер понемногу стал приходить в себя и оглядывать комнату, где он был, и находившихся в ней людей. Вокруг длинного стола, покрытого черным, сидело человек двенадцать, всё в тех же одеяниях, как и те, которых он прежде видел. Некоторых Пьер знал по петербургскому обществу. На председательском месте сидел незнакомый молодой человек, в особом кресте на шее. По правую руку сидел итальянец аббат, которого Пьер видел два года тому назад у Анны Павловны. Еще был тут один весьма важный сановник и один швейцарец гувернер, живший прежде у Курагиных. Все торжественно молчали, слушая слова председателя, державшего в руке молоток. В стене была вделана горящая звезда; с одной стороны стола был небольшой ковер с различными изображениями, с другой было что то в роде алтаря с Евангелием и черепом. Кругом стола было 7 больших, в роде церковных, подсвечников. Двое из братьев подвели Пьера к алтарю, поставили ему ноги в прямоугольное положение и приказали ему лечь, говоря, что он повергается к вратам храма.
– Он прежде должен получить лопату, – сказал шопотом один из братьев.
– А! полноте пожалуйста, – сказал другой.
Пьер, растерянными, близорукими глазами, не повинуясь, оглянулся вокруг себя, и вдруг на него нашло сомнение. «Где я? Что я делаю? Не смеются ли надо мной? Не будет ли мне стыдно вспоминать это?» Но сомнение это продолжалось только одно мгновение. Пьер оглянулся на серьезные лица окружавших его людей, вспомнил всё, что он уже прошел, и понял, что нельзя остановиться на половине дороги. Он ужаснулся своему сомнению и, стараясь вызвать в себе прежнее чувство умиления, повергся к вратам храма. И действительно чувство умиления, еще сильнейшего, чем прежде, нашло на него. Когда он пролежал несколько времени, ему велели встать и надели на него такой же белый кожаный фартук, какие были на других, дали ему в руки лопату и три пары перчаток, и тогда великий мастер обратился к нему. Он сказал ему, чтобы он старался ничем не запятнать белизну этого фартука, представляющего крепость и непорочность; потом о невыясненной лопате сказал, чтобы он трудился ею очищать свое сердце от пороков и снисходительно заглаживать ею сердце ближнего. Потом про первые перчатки мужские сказал, что значения их он не может знать, но должен хранить их, про другие перчатки мужские сказал, что он должен надевать их в собраниях и наконец про третьи женские перчатки сказал: «Любезный брат, и сии женские перчатки вам определены суть. Отдайте их той женщине, которую вы будете почитать больше всех. Сим даром уверите в непорочности сердца вашего ту, которую изберете вы себе в достойную каменьщицу». И помолчав несколько времени, прибавил: – «Но соблюди, любезный брат, да не украшают перчатки сии рук нечистых». В то время как великий мастер произносил эти последние слова, Пьеру показалось, что председатель смутился. Пьер смутился еще больше, покраснел до слез, как краснеют дети, беспокойно стал оглядываться и произошло неловкое молчание.
Молчание это было прервано одним из братьев, который, подведя Пьера к ковру, начал из тетради читать ему объяснение всех изображенных на нем фигур: солнца, луны, молотка. отвеса, лопаты, дикого и кубического камня, столба, трех окон и т. д. Потом Пьеру назначили его место, показали ему знаки ложи, сказали входное слово и наконец позволили сесть. Великий мастер начал читать устав. Устав был очень длинен, и Пьер от радости, волнения и стыда не был в состоянии понимать того, что читали. Он вслушался только в последние слова устава, которые запомнились ему.
«В наших храмах мы не знаем других степеней, – читал „великий мастер, – кроме тех, которые находятся между добродетелью и пороком. Берегись делать какое нибудь различие, могущее нарушить равенство. Лети на помощь к брату, кто бы он ни был, настави заблуждающегося, подними упадающего и не питай никогда злобы или вражды на брата. Будь ласков и приветлив. Возбуждай во всех сердцах огнь добродетели. Дели счастье с ближним твоим, и да не возмутит никогда зависть чистого сего наслаждения. Прощай врагу твоему, не мсти ему, разве только деланием ему добра. Исполнив таким образом высший закон, ты обрящешь следы древнего, утраченного тобой величества“.
Кончил он и привстав обнял Пьера и поцеловал его. Пьер, с слезами радости на глазах, смотрел вокруг себя, не зная, что отвечать на поздравления и возобновления знакомств, с которыми окружили его. Он не признавал никаких знакомств; во всех людях этих он видел только братьев, с которыми сгорал нетерпением приняться за дело.
Великий мастер стукнул молотком, все сели по местам, и один прочел поучение о необходимости смирения.
Великий мастер предложил исполнить последнюю обязанность, и важный сановник, который носил звание собирателя милостыни, стал обходить братьев. Пьеру хотелось записать в лист милостыни все деньги, которые у него были, но он боялся этим выказать гордость, и записал столько же, сколько записывали другие.
Заседание было кончено, и по возвращении домой, Пьеру казалось, что он приехал из какого то дальнего путешествия, где он провел десятки лет, совершенно изменился и отстал от прежнего порядка и привычек жизни.
На другой день после приема в ложу, Пьер сидел дома, читая книгу и стараясь вникнуть в значение квадрата, изображавшего одной своей стороною Бога, другою нравственное, третьею физическое и четвертою смешанное. Изредка он отрывался от книги и квадрата и в воображении своем составлял себе новый план жизни. Вчера в ложе ему сказали, что до сведения государя дошел слух о дуэли, и что Пьеру благоразумнее бы было удалиться из Петербурга. Пьер предполагал ехать в свои южные имения и заняться там своими крестьянами. Он радостно обдумывал эту новую жизнь, когда неожиданно в комнату вошел князь Василий.
– Мой друг, что ты наделал в Москве? За что ты поссорился с Лёлей, mon сher? [дорогой мoй?] Ты в заблуждении, – сказал князь Василий, входя в комнату. – Я всё узнал, я могу тебе сказать верно, что Элен невинна перед тобой, как Христос перед жидами. – Пьер хотел отвечать, но он перебил его. – И зачем ты не обратился прямо и просто ко мне, как к другу? Я всё знаю, я всё понимаю, – сказал он, – ты вел себя, как прилично человеку, дорожащему своей честью; может быть слишком поспешно, но об этом мы не будем судить. Одно ты помни, в какое положение ты ставишь ее и меня в глазах всего общества и даже двора, – прибавил он, понизив голос. – Она живет в Москве, ты здесь. Помни, мой милый, – он потянул его вниз за руку, – здесь одно недоразуменье; ты сам, я думаю, чувствуешь. Напиши сейчас со мною письмо, и она приедет сюда, всё объяснится, а то я тебе скажу, ты очень легко можешь пострадать, мой милый.
Князь Василий внушительно взглянул на Пьера. – Мне из хороших источников известно, что вдовствующая императрица принимает живой интерес во всем этом деле. Ты знаешь, она очень милостива к Элен.
Несколько раз Пьер собирался говорить, но с одной стороны князь Василий не допускал его до этого, с другой стороны сам Пьер боялся начать говорить в том тоне решительного отказа и несогласия, в котором он твердо решился отвечать своему тестю. Кроме того слова масонского устава: «буди ласков и приветлив» вспоминались ему. Он морщился, краснел, вставал и опускался, работая над собою в самом трудном для него в жизни деле – сказать неприятное в глаза человеку, сказать не то, чего ожидал этот человек, кто бы он ни был. Он так привык повиноваться этому тону небрежной самоуверенности князя Василия, что и теперь он чувствовал, что не в силах будет противостоять ей; но он чувствовал, что от того, что он скажет сейчас, будет зависеть вся дальнейшая судьба его: пойдет ли он по старой, прежней дороге, или по той новой, которая так привлекательно была указана ему масонами, и на которой он твердо верил, что найдет возрождение к новой жизни.
– Ну, мой милый, – шутливо сказал князь Василий, – скажи же мне: «да», и я от себя напишу ей, и мы убьем жирного тельца. – Но князь Василий не успел договорить своей шутки, как Пьер с бешенством в лице, которое напоминало его отца, не глядя в глаза собеседнику, проговорил шопотом:
Зада́ча о восьми́ фе́рзя́х — широко известная задача по расстановке фигур на шахматной доске. Исходная формулировка: «Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого». Подразумевается, что ферзь бьёт все клетки, расположенные по вертикалям, горизонталям и обеим диагоналям. Обобщение задачи — расставить максимальное количество взаимно не бьющих друг друга ферзей на прямоугольном поле, в частности, квадратном поле, со стороной n.
Содержание
- 1 Формулировка
- 2 Особенности решения
- 3 Вариант решения для доски произвольного размера на C#
- 4 Вариант решения для доски произвольного размера на C
- 5 Вариант решения для доски размера до 10-11 на Oracle 11 SQL
- 6 Рекурсивное решение для доски произвольного размера на C++
- 7 Альтернативный подход
- 8 Примечания
- 9 Ссылки
Формулировка
В более «математическом» виде задача может быть сформулирована несколькими способами, например, так: «Заполнить матрицу размером 8×8 нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна 8, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы».
Конечная цель, поставленная перед решающим задачу, может формулироваться в нескольких вариантах:
- Построить одно, любое решение задачи.
- Аналитически доказать, что решение существует.
- Определить количество решений.
- Построить все возможные решения.
- Одна из типовых задач по программированию алгоритмов перебора: создать компьютерную программу, находящую все возможные решения задачи.
Иногда постановка задачи требует нахождения способов расстановки N ферзей на доске N×N клеток (при этом при 1<N<4 задача не имеет решения).
Мы же подробнее рассмотрим классический “шахматный” случай для доски 8*8.
Особенности решения
Общее число возможных расположений 8 ферзей на 64-клеточной доске равно 4 426 165 368 (= 64!/(8!(64-8)!)). Общее число возможных расположений, удовлетворяющих условию задачи, равно 92. Современные компьютеры уже позволяют произвести решение задачи (нахождение любого или всех решений) путём прямого перебора всех возможных вариантов расстановки, но обычно такое решение считается некорректным, и от решающего задачу требуется найти алгоритм, который позволял бы существенно сократить объём перебора. Например, очевидно, что на одной горизонтали или вертикали доски не может находиться больше одного ферзя, поэтому алгоритм решения изначально не должен включать в перебор позиции, где два ферзя стоят на одной горизонтали или вертикали. Даже такое простое правило способно существенно уменьшить число возможных расположений: 16 777 216 (то есть 88) вместо 4 426 165 368. Генерируя перестановки, которые являются решениями задачи о восьми ладьях и затем проверяя атаки по диагоналям, можно сократить число возможных расположений всего до 40 320 (то есть 8!). Однако, если условие нападения по диагонали учитывать при генерации позиций, скорость счёта возрастает на порядок.
Один из типовых алгоритмов решения задачи — использование поиска с возвратом: первый ферзь ставится на первую горизонталь, затем каждый следующий пытаются поставить на следующую так, чтобы его не били ранее установленные ферзи. Если на очередном этапе постановки свободных полей не оказывается, происходит возврат на шаг назад — переставляется ранее установленный ферзь (такой алгоритм использован в приведённых ниже программах).
Программа, реализующая этот алгоритм на QBasic.
Алгоритм на QBasic
CLS
DEFINT A-I
OPEN "ferz" FOR OUTPUT AS #1
FOR a = 1 TO 8
FOR b = 1 TO 8
IF b = a THEN 8
IF ABS(b - a) = 1 THEN 8
FOR c = 1 TO 8
IF c = a OR c = b THEN 7
IF ABS(c - b) = 1 OR ABS(c - a) = 2 THEN 7
FOR d = 1 TO 8
IF d = a OR d = b OR d = c THEN 6
IF ABS(d - c) = 1 OR ABS(d - b) = 2 OR ABS(d - a) = 3 THEN 6
FOR e = 1 TO 8
IF e = a OR e = b OR e = c OR e = d THEN 5
IF ABS(e - d) = 1 OR ABS(e - c) = 2 OR ABS(e - b) = 3 OR ABS(e - a) = 4 THEN 5
FOR f = 1 TO 8
IF f = a OR f = b OR f = c OR f = d OR f = e THEN 4
IF ABS(f - e) = 1 OR ABS(f - d) = 2 OR ABS(f - c) = 3 OR ABS(f - b) = 4 >
OR ABS(f - a) = 5 THEN 4
FOR g = 1 TO 8
IF g = a OR g = b OR g = c OR g = d OR g = e OR g = f THEN 3
IF ABS(g - f) = 1 OR ABS(g - e) = 2 OR ABS(g - d) = 3 OR ABS(g - c) = 4 >
OR ABS(g - b) = 5 OR ABS(g - a) = 6 THEN 3
FOR h = 1 TO 8
IF h = a OR h = b OR h = c OR h = d OR h = e OR h = f OR h = g THEN 2
IF ABS(h-g) = 1 OR ABS(h-f) = 2 OR ABS(h-e) = 3 OR ABS(h-d) = 4 OR ABS(h-c) = 5 >
OR ABS(h-b) = 6 OR ABS(h-a) = 7 THEN 2
i = i + 1
PRINT i; " "; "a"; a; " "; "b"; b; " "; "c"; c; " "; "d"; d;
PRINT " "; "e"; e; " "; "f"; f; " "; "g"; g; " "; "h"; h
PRINT #1, i; " "; "a"; a; " "; "b"; b; " "; "c"; c; " "; "d";
PRINT #1, d; " "; "e"; e; " "; "f"; f; " "; "g"; g; " "; "h"; h
2 NEXT h
3 NEXT g
4 NEXT f
5 NEXT e
6 NEXT d
7 NEXT c
8 NEXT b
NEXT a
ENDРезультаты работы программы (вывод)
Список позиций, выдаваемый программой, является списком решений исходной задачи:
1 a 1 b 5 c 8 d 6 e 3 f 7 g 2 h 4 2 a 1 b 6 c 8 d 3 e 7 f 4 g 2 h 5 3 a 1 b 7 c 4 d 6 e 8 f 2 g 5 h 3 4 a 1 b 7 c 5 d 8 e 2 f 4 g 6 h 3 5 a 2 b 4 c 6 d 8 e 3 f 1 g 7 h 5 6 a 2 b 5 c 7 d 1 e 3 f 8 g 6 h 4 7 a 2 b 5 c 7 d 4 e 1 f 8 g 6 h 3 8 a 2 b 6 c 1 d 7 e 4 f 8 g 3 h 5 9 a 2 b 6 c 8 d 3 e 1 f 4 g 7 h 5 10 a 2 b 7 c 3 d 6 e 8 f 5 g 1 h 4 11 a 2 b 7 c 5 d 8 e 1 f 4 g 6 h 3 12 a 2 b 8 c 6 d 1 e 3 f 5 g 7 h 4 13 a 3 b 1 c 7 d 5 e 8 f 2 g 4 h 6 14 a 3 b 5 c 2 d 8 e 1 f 7 g 4 h 6 15 a 3 b 5 c 2 d 8 e 6 f 4 g 7 h 1 16 a 3 b 5 c 7 d 1 e 4 f 2 g 8 h 6 17 a 3 b 5 c 8 d 4 e 1 f 7 g 2 h 6 18 a 3 b 6 c 2 d 5 e 8 f 1 g 7 h 4 19 a 3 b 6 c 2 d 7 e 1 f 4 g 8 h 5 20 a 3 b 6 c 2 d 7 e 5 f 1 g 8 h 4 21 a 3 b 6 c 4 d 1 e 8 f 5 g 7 h 2 22 a 3 b 6 c 4 d 2 e 8 f 5 g 7 h 1 23 a 3 b 6 c 8 d 1 e 4 f 7 g 5 h 2 24 a 3 b 6 c 8 d 1 e 5 f 7 g 2 h 4 25 a 3 b 6 c 8 d 2 e 4 f 1 g 7 h 5 26 a 3 b 7 c 2 d 8 e 5 f 1 g 4 h 6 27 a 3 b 7 c 2 d 8 e 6 f 4 g 1 h 5 28 a 3 b 8 c 4 d 7 e 1 f 6 g 2 h 5 29 a 4 b 1 c 5 d 8 e 2 f 7 g 3 h 6 30 a 4 b 1 c 5 d 8 e 6 f 3 g 7 h 2 31 a 4 b 2 c 5 d 8 e 6 f 1 g 3 h 7 32 a 4 b 2 c 7 d 3 e 6 f 8 g 1 h 5 33 a 4 b 2 c 7 d 3 e 6 f 8 g 5 h 1 34 a 4 b 2 c 7 d 5 e 1 f 8 g 6 h 3 35 a 4 b 2 c 8 d 5 e 7 f 1 g 3 h 6 36 a 4 b 2 c 8 d 6 e 1 f 3 g 5 h 7 37 a 4 b 6 c 1 d 5 e 2 f 8 g 3 h 7 38 a 4 b 6 c 8 d 2 e 7 f 1 g 3 h 5 39 a 4 b 6 c 8 d 3 e 1 f 7 g 5 h 2 40 a 4 b 7 c 1 d 8 e 5 f 2 g 6 h 3 41 a 4 b 7 c 3 d 8 e 2 f 5 g 1 h 6 42 a 4 b 7 c 5 d 2 e 6 f 1 g 3 h 8 43 a 4 b 7 c 5 d 3 e 1 f 6 g 8 h 2 44 a 4 b 8 c 1 d 3 e 6 f 2 g 7 h 5 45 a 4 b 8 c 1 d 5 e 7 f 2 g 6 h 3 46 a 4 b 8 c 5 d 3 e 1 f 7 g 2 h 6 47 a 5 b 1 c 4 d 6 e 8 f 2 g 7 h 3 48 a 5 b 1 c 8 d 4 e 2 f 7 g 3 h 6 49 a 5 b 1 c 8 d 6 e 3 f 7 g 2 h 4 50 a 5 b 2 c 4 d 6 e 8 f 3 g 1 h 7 51 a 5 b 2 c 4 d 7 e 3 f 8 g 6 h 1 52 a 5 b 2 c 6 d 1 e 7 f 4 g 8 h 3 53 a 5 b 2 c 8 d 1 e 4 f 7 g 3 h 6 54 a 5 b 3 c 1 d 6 e 8 f 2 g 4 h 7 55 a 5 b 3 c 1 d 7 e 2 f 8 g 6 h 4 56 a 5 b 3 c 8 d 4 e 7 f 1 g 6 h 2 57 a 5 b 7 c 1 d 3 e 8 f 6 g 4 h 2 58 a 5 b 7 c 1 d 4 e 2 f 8 g 6 h 3 59 a 5 b 7 c 2 d 4 e 8 f 1 g 3 h 6 60 a 5 b 7 c 2 d 6 e 3 f 1 g 4 h 8 61 a 5 b 7 c 2 d 6 e 3 f 1 g 8 h 4 62 a 5 b 7 c 4 d 1 e 3 f 8 g 6 h 2 63 a 5 b 8 c 4 d 1 e 3 f 6 g 2 h 7 64 a 5 b 8 c 4 d 1 e 7 f 2 g 6 h 3 65 a 6 b 1 c 5 d 2 e 8 f 3 g 7 h 4 66 a 6 b 2 c 7 d 1 e 3 f 5 g 8 h 4 67 a 6 b 2 c 7 d 1 e 4 f 8 g 5 h 3 68 a 6 b 3 c 1 d 7 e 5 f 8 g 2 h 4 69 a 6 b 3 c 1 d 8 e 4 f 2 g 7 h 5 70 a 6 b 3 c 1 d 8 e 5 f 2 g 4 h 7 71 a 6 b 3 c 5 d 7 e 1 f 4 g 2 h 8 72 a 6 b 3 c 5 d 8 e 1 f 4 g 2 h 7 73 a 6 b 3 c 7 d 2 e 4 f 8 g 1 h 5 74 a 6 b 3 c 7 d 2 e 8 f 5 g 1 h 4 75 a 6 b 3 c 7 d 4 e 1 f 8 g 2 h 5 76 a 6 b 4 c 1 d 5 e 8 f 2 g 7 h 3 77 a 6 b 4 c 2 d 8 e 5 f 7 g 1 h 3 78 a 6 b 4 c 7 d 1 e 3 f 5 g 2 h 8 79 a 6 b 4 c 7 d 1 e 8 f 2 g 5 h 3 80 a 6 b 8 c 2 d 4 e 1 f 7 g 5 h 3 81 a 7 b 1 c 3 d 8 e 6 f 4 g 2 h 5 82 a 7 b 2 c 4 d 1 e 8 f 5 g 3 h 6 83 a 7 b 2 c 6 d 3 e 1 f 4 g 8 h 5 84 a 7 b 3 c 1 d 6 e 8 f 5 g 2 h 4 85 a 7 b 3 c 8 d 2 e 5 f 1 g 6 h 4 86 a 7 b 4 c 2 d 5 e 8 f 1 g 3 h 6 87 a 7 b 4 c 2 d 8 e 6 f 1 g 3 h 5 88 a 7 b 5 c 3 d 1 e 6 f 8 g 2 h 4 89 a 8 b 2 c 4 d 1 e 7 f 5 g 3 h 6 90 a 8 b 2 c 5 d 3 e 1 f 7 g 4 h 6 91 a 8 b 3 c 1 d 6 e 2 f 5 g 7 h 4 92 a 8 b 4 c 1 d 3 e 6 f 2 g 7 h 5
Интересно отметить, что эти 92 расположения разбиваются на 12 групп: 11 групп по 8 и одну из 4 расположений. Положения внутри групп получаются из одного положения путём преобразований симметрии: отражения от вертикальной и горизонтальной осей, отражения от диагоналей доски и поворотов на 90, 180 и 270 градусов. Пары расположений, симметричные относительно горизонтальной оси, имеют сумму номеров равную 93, то есть для каждой группы эта сумма равна 93×4.
1
a 1 b 5 c 8 d 6 e 3 f 7 g 2 h 4 :1 a 4 b 2 c 7 d 3 e 6 f 8 g 5 h 1 :33 a 8 b 4 c 1 d 3 e 6 f 2 g 7 h 5 :92 a 1 b 7 c 5 d 8 e 2 f 4 g 6 h 3 :4 +(3) a 6 b 3 c 5 d 7 e 1 f 4 g 2 h 8 :71 a 8 b 2 c 4 d 1 e 7 f 5 g 3 h 6 :89 a 5 b 7 c 2 d 6 e 3 f 1 g 4 h 8 :60 a 3 b 6 c 4 d 2 e 8 f 5 g 7 h 1 :22
2
a 1 b 6 c 8 d 3 e 7 f 4 g 2 h 5 :2 a 5 b 2 c 4 d 7 e 3 f 8 g 6 h 1 :51 a 8 b 3 c 1 d 6 e 2 f 5 g 7 h 4 :91 a 1 b 7 c 4 d 6 e 8 f 2 g 5 h 3 :3 +(2) a 6 b 4 c 7 d 1 e 3 f 5 g 2 h 8 :78 a 8 b 2 c 5 d 3 e 1 f 7 g 4 h 6 :90 a 4 b 7 c 5 d 2 e 6 f 1 g 3 h 8 :42 a 3 b 5 c 2 d 8 e 6 f 4 g 7 h 1 :15
3
a 2 b 4 c 6 d 8 e 3 f 1 g 7 h 5 :5 +(1) a 5 b 7 c 1 d 3 e 8 f 6 g 4 h 2 :57 a 7 b 5 c 3 d 1 e 6 f 8 g 2 h 4 :88 a 6 b 1 c 5 d 2 e 8 f 3 g 7 h 4 :65 a 5 b 2 c 6 d 1 e 7 f 4 g 8 h 3 :52 a 3 b 8 c 4 d 7 e 1 f 6 g 2 h 5 :28 a 4 b 2 c 8 d 6 e 1 f 3 g 5 h 7 :36 a 4 b 7 c 3 d 8 e 2 f 5 g 1 h 6 :41
4
a 2 b 5 c 7 d 1 e 3 f 8 g 6 h 4:6 a 4 b 6 c 8 d 3 e 1 f 7 g 5 h 2:39 a 7 b 4 c 2 d 8 e 6 f 1 g 3 h 5:87 a 4 b 1 c 5 d 8 e 2 f 7 g 3 h 6:29 +(4) a 3 b 6 c 2 d 7 e 1 f 4 g 8 h 5:19 a 5 b 8 c 4 d 1 e 7 f 2 g 6 h 3:64 a 5 b 3 c 1 d 6 e 8 f 2 g 4 h 7:54 a 6 b 3 c 7 d 2 e 8 f 5 g 1 h 4:74
5
a 2 b 5 c 7 d 4 e 1 f 8 g 6 h 3 :7 a 3 b 6 c 8 d 1 e 4 f 7 g 5 h 2 :23 a 7 b 4 c 2 d 5 e 8 f 1 g 3 h 6 :86 a 5 b 1 c 8 d 4 e 2 f 7 g 3 h 6 :48 +(5) a 3 b 6 c 2 d 7 e 5 f 1 g 8 h 4 :20 a 4 b 8 c 1 d 5 e 7 f 2 g 6 h 3 :45 a 6 b 3 c 1 d 8 e 5 f 2 g 4 h 7 :70 a 6 b 3 c 7 d 2 e 4 f 8 g 1 h 5 :73
6
a 2 b 6 c 1 d 7 e 4 f 8 g 3 h 5 :8 a 5 b 3 c 8 d 4 e 7 f 1 g 6 h 2 :56 a 7 b 3 c 8 d 2 e 5 f 1 g 6 h 4 :85 a 3 b 1 c 7 d 5 e 8 f 2 g 4 h 6 :13 +(6) a 3 b 5 c 7 d 1 e 4 f 2 g 8 h 6 :16 a 6 b 8 c 2 d 4 e 1 f 7 g 5 h 3 :80 a 4 b 6 c 1 d 5 e 2 f 8 g 3 h 7 :37 a 6 b 4 c 2 d 8 e 5 f 7 g 1 h 3 :77
7
a 2 b 6 c 8 d 3 e 1 f 4 g 7 h 5 :9 a 5 b 7 c 4 d 1 e 3 f 8 g 6 h 2 :62 a 7 b 3 c 1 d 6 e 8 f 5 g 2 h 4 :84 a 5 b 1 c 4 d 6 e 8 f 2 g 7 h 3 :47 +(7) a 6 b 2 c 7 d 1 e 3 f 5 g 8 h 4 :66 a 4 b 8 c 5 d 3 e 1 f 7 g 2 h 6 :46 a 4 b 2 c 5 d 8 e 6 f 1 g 3 h 7 :31 a 3 b 7 c 2 d 8 e 6 f 4 g 1 h 5 :27
8
a 2 b 7 c 3 d 6 e 8 f 5 g 1 h 4 :10 a 4 b 1 c 5 d 8 e 6 f 3 g 7 h 2 :30 a 7 b 2 c 6 d 3 e 1 f 4 g 8 h 5 :83 a 7 b 1 c 3 d 8 e 6 f 4 g 2 h 5 :81 +(8) a 4 b 7 c 5 d 3 e 1 f 6 g 8 h 2 :43 a 2 b 8 c 6 d 1 e 3 f 5 g 7 h 4 :12 a 5 b 8 c 4 d 1 e 3 f 6 g 2 h 7 :63 a 5 b 2 c 4 d 6 e 8 f 3 g 1 h 7 :50
9
a 2 b 7 c 5 d 8 e 1 f 4 g 6 h 3 :11 a 3 b 6 c 4 d 1 e 8 f 5 g 7 h 2 :21 a 7 b 2 c 4 d 1 e 8 f 5 g 3 h 6 :82 a 5 b 1 c 8 d 6 e 3 f 7 g 2 h 4 :49 +(9) a 5 b 7 c 2 d 6 e 3 f 1 g 8 h 4 :61 a 4 b 8 c 1 d 3 e 6 f 2 g 7 h 5 :44 a 6 b 3 c 5 d 8 e 1 f 4 g 2 h 7 :72 a 4 b 2 c 7 d 3 e 6 f 8 g 1 h 5 :32
10
a 3 b 5 c 2 d 8 e 1 f 7 g 4 h 6 :14 a 6 b 4 c 7 d 1 e 8 f 2 g 5 h 3 :79 a 6 b 4 c 7 d 1 e 8 f 2 g 5 h 3 :79 a 5 b 3 c 1 d 7 e 2 f 8 g 6 h 4 :55 +(12) a 5 b 3 c 1 d 7 e 2 f 8 g 6 h 4 :55 a 4 b 6 c 8 d 2 e 7 f 1 g 3 h 5 :38 a 3 b 5 c 2 d 8 e 1 f 7 g 4 h 6 :14 a 4 b 6 c 8 d 2 e 7 f 1 g 3 h 5 :38
11
a 3 b 5 c 8 d 4 e 1 f 7 g 2 h 6 :17 a 6 b 2 c 7 d 1 e 4 f 8 g 5 h 3 :67 a 6 b 4 c 1 d 5 e 8 f 2 g 7 h 3 :76 a 5 b 7 c 1 d 4 e 2 f 8 g 6 h 3 :58 +(10) a 6 b 3 c 1 d 7 e 5 f 8 g 2 h 4 :68 a 4 b 2 c 8 d 5 e 7 f 1 g 3 h 6 :35 a 3 b 7 c 2 d 8 e 5 f 1 g 4 h 6 :26 a 3 b 6 c 8 d 2 e 4 f 1 g 7 h 5 :25
12
a 3 b 6 c 2 d 5 e 8 f 1 g 7 h 4 :18
a 4 b 7 c 1 d 8 e 5 f 2 g 6 h 3 :40
a 6 b 3 c 7 d 4 e 1 f 8 g 2 h 5 :75
a 6 b 3 c 1 d 8 e 4 f 2 g 7 h 5 :69 +(11)
a 4 b 2 c 7 d 5 e 1 f 8 g 6 h 3 :34
a 3 b 6 c 8 d 1 e 5 f 7 g 2 h 4 :24
a 5 b 2 c 8 d 1 e 4 f 7 g 3 h 6 :53
a 5 b 7 c 2 d 4 e 8 f 1 g 3 h 6 :59
Вот как выглядит это разделение. Причём сумма номеров позиций в каждой группе равна 372. Группа номер 10 — симметрическая.
В этой группе при повороте на 180 градусов позиции переходят сами в себя. Характерной особенностью симметрических положений является пустой квадрат 4×4 в середине доски и пустые диагонали. Таким образом, имея 12 расположений — по одному из каждой группы, можно получить все остальные, что, впрочем, известно из шахматной литературы[1]. В списке знаком «плюс» отмечены позиции, которые выбраны в качестве базовых (то есть тех, с которыми производятся преобразования симметрии) в английской и украинской версии данной статьи в Википедии и указаны номера, под которыми они в ней фигурируют. Здесь же базовые позиции (первые позиции в каждой группе) выбраны по признаку минимального номера в группе. Очевидно, что наборов базовых позиций можно составить 4×811.
Вариант решения для доски произвольного размера на C#
Ниже приведен только класс, непосредственно реализующий алгоритм решения.
Вариант решения на C#
class QueensProblem : IProblem {
private int size;
private int[] positions;
private List<int[]> saved;
private IProblemCallback cb;
public void Init(int size, IProblemCallback cb) {
this.size = size;
this.cb = cb;
positions = new int[size];
saved = new List<int[]>();
}
private void Save() {
saved.Add((int[]) positions.Clone());
}
private bool Step() {
int s = size;
for (int i = 1; i < s; i++) {
int pos = positions[i];
while (true) {
bool found = false;
for (int j = 0; j < i; j++) {
int epos = positions[j];
if (epos == pos || pos - i == epos - j || pos + i == epos + j) {
if (++pos >= s) {
if (!Next(i)) return false;
while (++i < s) positions[i] = 0;
return true;
}
positions[i] = pos;
found = true;
break;
}
}
if (!found) break;
}
}
Save();
return Next(s - 1);
}
private bool Next(int pos) {
int s = size;
if (++positions[pos] < s) return true;
do {
positions[pos] = 0;
if (++positions[--pos] < s) return true;
} while (pos > 0);
return false;
}
public int Solve() {
float prev = 0;
int sq = size * size;
while (Step()) {
int part = positions[0] * size + positions[1];
if (part != prev) cb.Progress((float) (prev = part) / sq);
}
return saved.Count;
}
public List<int[]> GetResults() {
return saved;
}
public int Size {
get { return size; }
}
}Время выполнения алгоритма
Ниже представлена зависимость времени выполнения программы от размера доски (время приведено для компьютера с процессором Intel Core2 Q6600 @ 2.4 ГГц):
| Размер | Решений | Время (мс) |
|---|---|---|
| 4 | 2 | 1 |
| 5 | 10 | 2 |
| 6 | 4 | 2 |
| 7 | 40 | 2 |
| 8 | 92 | 3 |
| 9 | 352 | 6 |
| 10 | 724 | 16 |
| 11 | 2 680 | 69 |
| 12 | 14 200 | 376 |
| 13 | 73 712 | 2 311 |
| 14 | 365 596 | 15 411 |
| 15 | 2 279 184 | 108 587 |
| 16 | 14 772 512 | 812 945 |
Характер зависимости времени выполнения от размера доски — экспоненциальный (как показано на графике).
Вариант решения для доски произвольного размера на C
Здесь приведена программа, решающая задачу для размеров доски от 1 до 17. Программа измеряет и выводит время работы алгоритма.
Вариант решения на C
#include <time.h>
#include <stdio.h>
#include <string.h>
#define SIZE 20
int size,
sol_num,
a[ SIZE ];
struct _board {
unsigned int a[ SIZE ];
} board[ SIZE+1 ];
void dfs(register int ind)
{
register int i, j;
if (ind >= size)
{
++sol_num;
return;
}
for (a[ind] = 0; a[ind] < size; ++a[ind])
{
if (!(board[ind].a[ ind ] & (1<<a[ind])))
{
memcpy(board[ind+1].a, &board[ind].a , SIZE*sizeof(int));
for (i = ind, j = a[ind]; i<size && j<size; ++i, ++j)
board[ind+1].a[i] |= (1<<j);
for (i = ind, j = a[ind]; i<size && j>=0; ++i, --j)
board[ind+1].a[i] |= (1<<j);
board[ind+1].a[ind] = 65535u;
for (i = ind; i < size; ++i)
board[ind+1].a[i] |= 1<<a[ind];
dfs(ind+1);
}
}
}
int main()
{
double start, end;
int i;
for (size = 1; size < 20; ++size)
{
start = clock();
sol_num = 0;
memset(a, 0, sizeof(int)*SIZE);
for (i = 0; i < SIZE+1; ++i)
memset(board[i].a, 0, sizeof(int)*SIZE);
dfs(0);
end = clock();
printf("%20d%20d\ttime: %.2lf\n", size, sol_num, (end-start)/CLOCKS_PER_SEC);
}
return 0;
}Время выполнения алгоритма
Ниже представлена зависимость времени выполнения программы от размера доски (время приведено для компьютера с процессором Intel Core i5-2410M @ 2.3 ГГц):
| Размер | Решений | Время (с) |
|---|---|---|
| 1 | 1 | 0.000 003 |
| 2 | 0 | 0.000 001 |
| 3 | 0 | 0.000 001 |
| 4 | 2 | 0.000 004 |
| 5 | 10 | 0.000 008 |
| 6 | 4 | 0.000 025 |
| 7 | 40 | 0.000 091 |
| 8 | 92 | 0.000 347 |
| 9 | 352 | 0.001 508 |
| 10 | 724 | 0.008 023 |
| 11 | 2 680 | 0.031 750 |
| 12 | 14 200 | 0.114 120 |
| 13 | 73 712 | 0.538 676 |
| 14 | 365 596 | 3.267 996 |
| 15 | 2 279 184 | 21.486 720 |
| 16 | 14 772 512 | 147.388 255 |
| 17 | 95 815 104 | 1 088.978 601 |
| 18 | 666 090 624 | 8 776.579 792 |
Вариант решения для доски размера до 10-11 на Oracle 11 SQL
В Oracle SQL возможно решение одним рекурсивным оператором. Время выполнения — секунды для доски 8*8, до 1 минуты для доски 9*9.
Использован усовершенствованный метод поиска с возвратом:
На доске есть четыре типа ресурсов: вертикали, горизонтали, левые и правые диагонали. Каждая поставленная фигура на доску «потребляет» одну горизонталь, одну вертикаль, и две диагонали. Соответственно, следующего ферзя мы будем пробовать ставить на ту клетку, для которого есть оставшиеся незанятые горизонталь, вертикаль и диагонали. Этим существенно сокращаем время перебора.
Вариант решения на SQL
with
T1 as (select level - 1 as K from dual connect by level <= &&D)
, T2 (N, L, X, Y, D1, D2, NL)
as (select a.K * &D + b.K, 0
, power (2, a.K), power (2, b.K), power (2, a.K - b.K + &D - 1)
, power (2, a.K + b.K), chr (a.K + 97) || to_char (b.K + 1)
from T1 a, T1 b)
, T3 (RN, RL, RX, RY, RD1, RD2, RNL)
as (select * from T2 union all
select N, RL + 1, RX + X, RY + Y, RD1 + D1, RD2 + D2, RNL || ' ' || NL
from T2, T3
where bitand (RX , X ) = 0 and bitand (RY , Y ) = 0
and bitand (RD1, D1) = 0 and bitand (RD2, D2) = 0 and N > RN
)
select RNL from T3 where RL = &D - 1;Рекурсивное решение для доски произвольного размера на C++
Вариант решения на C++
// Backtracking method. "Поиск с возвратом" на примере
// задачи о восьми ферзях.
#include <iostream>
const int SIZE = 8; // Размер.
int board[SIZE][SIZE];
int results_count = 0; // Количество решений.
// Функция showBoard() - отображает доску.
void showBoard()
{
for(int a = 0; a < SIZE; ++a)
{
for(int b = 0; b < SIZE; ++b)
{
std::cout << ((board[a][b]) ? "Q " : ". ");
}
std::cout << '\n';
}
}
// Функция tryQueen() - проверяет нет ли уже установленных ферзей,
// по вертикали, диагоналям.
bool tryQueen(int a, int b)
{
for(int i = 0; i < a; ++i)
{
if(board[i][b])
{
return false;
}
}
for(int i = 1; i <= a && b-i >= 0; ++i)
{
if(board[a-i][b-i])
{
return false;
}
}
for(int i = 1; i <= a && b+i < SIZE; i++)
{
if(board[a-i][b+i])
{
return false;
}
}
return true;
}
// Функция setQueen() - пробует найти результаты решений.
void setQueen(int a) // a - номер очередной строки в которую нужно поставить очередного ферзя.
{
if(a == SIZE)
{
showBoard();
std::cout << "Result #" << ++results_count << "\n\n";
return; // Опционально.
}
for(int i = 0; i < SIZE; ++i)
{
// Здесь проверяем, что если поставим в board[a][i] ферзя (единицу),
// то он будет единственным в этой строке, столбце и диагоналях.
if(tryQueen(a, i))
{
board[a][i] = 1;
setQueen(a+1);
board[a][i] = 0;
}
}
return; // Опционально.
}
int main()
{
setQueen(0);
return 0;
}Альтернативный подход
Если решать более общую задачу об N ферзях при помощи описанного выше алгоритма, то такой перебор вариантов даже с использованием описанных выше сокращений будет весьма долго работать уже при N = 20, так как 20! = 2.433·1018. Поэтому представляет особенный интерес следующий эвристический алгоритм, решающий задачу об N ферзях на поле размером N x N. Он работает для всех N ≥ 4 или N = 1:
- Разделить N на 12 и запомнить остаток (N будет равно 8 для задачи о восьми ферзях).
- Занести в список все четные числа от 2 до N по порядку.
- Если остаток равен 3 или 9, перенести 2 в конец списка.
- Добавить в список все нечетные числа от 1 до N по порядку, но, если остаток равен 8, перевернуть пары соседних чисел (например: 3, 1, 7, 5, 11, 9, …).
- Если остаток равен 2 и N ≥ 3, поменять местами 1 и 3, затем, если N ≥ 5, перенести 5 в конец списка.
- Если остаток равен 3 или 9, переместить 1 и 3 (именно в этом порядке, а не в котором они сейчас) в конец списка.
- Разместить ферзя в первом столбце и в строке с номером, равным первому элементу списка, затем поместить следующего ферзя во втором столбце и в строке с номером, равным второму элементу списка, и т. д.
Для N = 8 результат работы этого алгоритма показан на картинке.
| a | b | c | d | e | f | g | h | ||
| 8 |   | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
Решение, полученное с помощью эвристики.(5)
Ещё несколько примеров:
- 14 ферзей (остаток 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
- 15 ферзей (остаток 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
- 20 ферзей (остаток 8): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17.
Реализация на C++
Реализация на C++
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
int N, Mod;
std::vector < int > L;
std::cin >> N;
Mod = N % 12;
for ( int x = 2; x <= N; x += 2 )
L.push_back( x );
if ( Mod == 3 || Mod == 9 )
{
L.push_back( 2 );
L.erase( L.begin() );
}
if ( Mod == 8 )
{
std::vector < int > V;
for ( int x = 1; x <= N; x += 2 )
V.push_back( x );
for ( int i = 1; i < V.size(); i += 2 )
std::swap( V.at( i ), V.at( i - 1 ) );
for ( int i = 0; i < V.size(); ++i )
L.push_back( V.at( i ) );
}
else
for ( int x = 1; x <= N; x += 2 )
L.push_back( x );
if ( Mod == 2 && N >= 3 )
{
std::swap( *std::find( L.begin(), L.end(), 1 ), *std::find( L.begin(), L.end(), 3 ) );
if ( N >= 5 )
{
L.erase( std::find( L.begin(), L.end(), 5 ) );
L.push_back( 5 );
}
}
if ( Mod == 3 || Mod == 9 )
{
L.erase( std::find( L.begin(), L.end(), 1 ) );
L.push_back( 1 );
L.erase( std::find( L.begin(), L.end(), 3 ) );
L.push_back( 3 );
}
for ( int i = 0; i < L.size(); ++i )
std::cout << L.at( i ) << " ";
return 0;
}Реализация на Haskell
Реализация на Haskell
position n = evenPosition ++ oddPosition where
modN = n `mod` 12
evenPosition
| modN == 3 || modN == 9 = [4,6..n] ++ [2]
| otherwise = [2,4..n]
oddPosition = oneThree $ fiveSeven others where
others
| modN == 8 = swapPairs [9,11..n]
| otherwise = [9,11..n]
where
swapPairs [] = []
swapPairs [x] = [x]
swapPairs (y:x:xs) = x:y:swapPairs xs
fiveSeven
| modN == 2 && n >= 5 = ([7] ++) . (++ [5])
| modN == 8 = ([7,5] ++)
| n < 7 = ([5,7..n] ++)
| otherwise = ([5,7] ++)
oneThree
| modN == 3 || modN == 9 = (++ [1,3])
| modN == 8 || (modN == 2 && n >= 3) = ([3,1] ++)
| n < 3 = ([1] ++)
| otherwise = ([1,3] ++)
main = print $ map position [8,14,15,20]
-- [[2,4,6,8,3,1,7,5],
-- [2,4,6,8,10,12,14,3,1,7,9,11,13,5],
-- [4,6,8,10,12,14,2,5,7,9,11,13,15,1,3],
-- [2,4,6,8,10,12,14,16,18,20,3,1,7,5,11,9,15,13,19,17]]Реализация на Erlang
Реализация на Erlang
-module(queens).
-export([start/0]).
pmut([])->
[[]];
pmut(A) ->
[[H|T] || H <- A, T <- pmut(A--[H])].
start() ->
N = 8, % size of board / num of queens (N>=4)
ListP = pmut(lists:seq(1,N)),
[Q || Q <- ListP, length(lists:usort([lists:nth(X,Q)+X || X <- Q])) == N,
length(lists:usort([lists:nth(X,Q)-X || X <- Q])) == N].
---
$ erl
Erlang R16B03 (erts-5.10.4) [source] [64-bit] [smp:4:4] [async-threads:10] [hipe] [kernel-poll:false]
Eshell V5.10.4 (abort with ^G)
1> queens:start().
[[1,5,8,6,3,7,2,4],
[1,6,8,3,7,4,2,5],
[1,7,4,6,8,2,5,3],
[1,7,5,8,2,4,6,3],
[2,4,6,8,3,1,7,5],
[2,5,7,1,3,8,6,4],
[2,5,7,4,1,8,6,3],
[2,6,1,7,4,8,3,5],
[2,6,8,3,1,4,7,5],
[2,7,3,6,8,5,1,4],
[2,7,5,8,1,4,6,3],
[2,8,6,1,3,5,7,4],
[3,1,7,5,8,2,4,6],
[3,5,2,8,1,7,4,6],
[3,5,2,8,6,4,7,1],
[3,5,7,1,4,2,8,6],
[3,5,8,4,1,7,2,6],
[3,6,2,5,8,1,7,4],
[3,6,2,7,1,4,8,5],
[3,6,2,7,5,1,8,4],
[3,6,4,1,8,5,7,2],
[3,6,4,2,8,5,7|...],
[3,6,8,1,4,7|...],
[3,6,8,1,5|...],
[3,6,8,2|...],
[3,7,2|...],
[3,7|...],
[3|...],
[...]|...]Напишите отзыв о статье "Задача о восьми ферзях"
Примечания
- ↑ Гик Е. Я. Шахматы и математика. — М.: Наука, 1983. — 176 с.
Ссылки
- [loveorigami.info/forum/viewtopic.php?f=21&t=564&start=30 Фрактальное решение] задачи для досок N-N, если N=(a1)•(a2)•…•(an), где а1 ≥ 4 и а2,…,аn > 4 (А.Ермаков, 2011)
Отрывок, характеризующий Задача о восьми ферзях
В ту минуту как дверь отворилась и вошел неизвестный человек, Пьер испытал чувство страха и благоговения, подобное тому, которое он в детстве испытывал на исповеди: он почувствовал себя с глазу на глаз с совершенно чужим по условиям жизни и с близким, по братству людей, человеком. Пьер с захватывающим дыханье биением сердца подвинулся к ритору (так назывался в масонстве брат, приготовляющий ищущего к вступлению в братство). Пьер, подойдя ближе, узнал в риторе знакомого человека, Смольянинова, но ему оскорбительно было думать, что вошедший был знакомый человек: вошедший был только брат и добродетельный наставник. Пьер долго не мог выговорить слова, так что ритор должен был повторить свой вопрос.– Да, я… я… хочу обновления, – с трудом выговорил Пьер.
– Хорошо, – сказал Смольянинов, и тотчас же продолжал: – Имеете ли вы понятие о средствах, которыми наш святой орден поможет вам в достижении вашей цели?… – сказал ритор спокойно и быстро.
– Я… надеюсь… руководства… помощи… в обновлении, – сказал Пьер с дрожанием голоса и с затруднением в речи, происходящим и от волнения, и от непривычки говорить по русски об отвлеченных предметах.
– Какое понятие вы имеете о франк масонстве?
– Я подразумеваю, что франк масонство есть fraterienité [братство]; и равенство людей с добродетельными целями, – сказал Пьер, стыдясь по мере того, как он говорил, несоответственности своих слов с торжественностью минуты. Я подразумеваю…
– Хорошо, – сказал ритор поспешно, видимо вполне удовлетворенный этим ответом. – Искали ли вы средств к достижению своей цели в религии?
– Нет, я считал ее несправедливою, и не следовал ей, – сказал Пьер так тихо, что ритор не расслышал его и спросил, что он говорит. – Я был атеистом, – отвечал Пьер.
– Вы ищете истины для того, чтобы следовать в жизни ее законам; следовательно, вы ищете премудрости и добродетели, не так ли? – сказал ритор после минутного молчания.
– Да, да, – подтвердил Пьер.
Ритор прокашлялся, сложил на груди руки в перчатках и начал говорить:
– Теперь я должен открыть вам главную цель нашего ордена, – сказал он, – и ежели цель эта совпадает с вашею, то вы с пользою вступите в наше братство. Первая главнейшая цель и купно основание нашего ордена, на котором он утвержден, и которого никакая сила человеческая не может низвергнуть, есть сохранение и предание потомству некоего важного таинства… от самых древнейших веков и даже от первого человека до нас дошедшего, от которого таинства, может быть, зависит судьба рода человеческого. Но так как сие таинство такого свойства, что никто не может его знать и им пользоваться, если долговременным и прилежным очищением самого себя не приуготовлен, то не всяк может надеяться скоро обрести его. Поэтому мы имеем вторую цель, которая состоит в том, чтобы приуготовлять наших членов, сколько возможно, исправлять их сердце, очищать и просвещать их разум теми средствами, которые нам преданием открыты от мужей, потрудившихся в искании сего таинства, и тем учинять их способными к восприятию оного. Очищая и исправляя наших членов, мы стараемся в третьих исправлять и весь человеческий род, предлагая ему в членах наших пример благочестия и добродетели, и тем стараемся всеми силами противоборствовать злу, царствующему в мире. Подумайте об этом, и я опять приду к вам, – сказал он и вышел из комнаты.
– Противоборствовать злу, царствующему в мире… – повторил Пьер, и ему представилась его будущая деятельность на этом поприще. Ему представлялись такие же люди, каким он был сам две недели тому назад, и он мысленно обращал к ним поучительно наставническую речь. Он представлял себе порочных и несчастных людей, которым он помогал словом и делом; представлял себе угнетателей, от которых он спасал их жертвы. Из трех поименованных ритором целей, эта последняя – исправление рода человеческого, особенно близка была Пьеру. Некое важное таинство, о котором упомянул ритор, хотя и подстрекало его любопытство, не представлялось ему существенным; а вторая цель, очищение и исправление себя, мало занимала его, потому что он в эту минуту с наслаждением чувствовал себя уже вполне исправленным от прежних пороков и готовым только на одно доброе.
Через полчаса вернулся ритор передать ищущему те семь добродетелей, соответствующие семи ступеням храма Соломона, которые должен был воспитывать в себе каждый масон. Добродетели эти были: 1) скромность , соблюдение тайны ордена, 2) повиновение высшим чинам ордена, 3) добронравие, 4) любовь к человечеству, 5) мужество, 6) щедрость и 7) любовь к смерти.
– В седьмых старайтесь, – сказал ритор, – частым помышлением о смерти довести себя до того, чтобы она не казалась вам более страшным врагом, но другом… который освобождает от бедственной сей жизни в трудах добродетели томившуюся душу, для введения ее в место награды и успокоения.
«Да, это должно быть так», – думал Пьер, когда после этих слов ритор снова ушел от него, оставляя его уединенному размышлению. «Это должно быть так, но я еще так слаб, что люблю свою жизнь, которой смысл только теперь по немногу открывается мне». Но остальные пять добродетелей, которые перебирая по пальцам вспомнил Пьер, он чувствовал в душе своей: и мужество , и щедрость , и добронравие , и любовь к человечеству , и в особенности повиновение , которое даже не представлялось ему добродетелью, а счастьем. (Ему так радостно было теперь избавиться от своего произвола и подчинить свою волю тому и тем, которые знали несомненную истину.) Седьмую добродетель Пьер забыл и никак не мог вспомнить ее.
В третий раз ритор вернулся скорее и спросил Пьера, всё ли он тверд в своем намерении, и решается ли подвергнуть себя всему, что от него потребуется.
– Я готов на всё, – сказал Пьер.
– Еще должен вам сообщить, – сказал ритор, – что орден наш учение свое преподает не словами токмо, но иными средствами, которые на истинного искателя мудрости и добродетели действуют, может быть, сильнее, нежели словесные токмо объяснения. Сия храмина убранством своим, которое вы видите, уже должна была изъяснить вашему сердцу, ежели оно искренно, более нежели слова; вы увидите, может быть, и при дальнейшем вашем принятии подобный образ изъяснения. Орден наш подражает древним обществам, которые открывали свое учение иероглифами. Иероглиф, – сказал ритор, – есть наименование какой нибудь неподверженной чувствам вещи, которая содержит в себе качества, подобные изобразуемой.
Пьер знал очень хорошо, что такое иероглиф, но не смел говорить. Он молча слушал ритора, по всему чувствуя, что тотчас начнутся испытанья.
– Ежели вы тверды, то я должен приступить к введению вас, – говорил ритор, ближе подходя к Пьеру. – В знак щедрости прошу вас отдать мне все драгоценные вещи.
– Но я с собою ничего не имею, – сказал Пьер, полагавший, что от него требуют выдачи всего, что он имеет.
– То, что на вас есть: часы, деньги, кольца…
Пьер поспешно достал кошелек, часы, и долго не мог снять с жирного пальца обручальное кольцо. Когда это было сделано, масон сказал:
– В знак повиновенья прошу вас раздеться. – Пьер снял фрак, жилет и левый сапог по указанию ритора. Масон открыл рубашку на его левой груди, и, нагнувшись, поднял его штанину на левой ноге выше колена. Пьер поспешно хотел снять и правый сапог и засучить панталоны, чтобы избавить от этого труда незнакомого ему человека, но масон сказал ему, что этого не нужно – и подал ему туфлю на левую ногу. С детской улыбкой стыдливости, сомнения и насмешки над самим собою, которая против его воли выступала на лицо, Пьер стоял, опустив руки и расставив ноги, перед братом ритором, ожидая его новых приказаний.
– И наконец, в знак чистосердечия, я прошу вас открыть мне главное ваше пристрастие, – сказал он.
– Мое пристрастие! У меня их было так много, – сказал Пьер.
– То пристрастие, которое более всех других заставляло вас колебаться на пути добродетели, – сказал масон.
Пьер помолчал, отыскивая.
«Вино? Объедение? Праздность? Леность? Горячность? Злоба? Женщины?» Перебирал он свои пороки, мысленно взвешивая их и не зная которому отдать преимущество.
– Женщины, – сказал тихим, чуть слышным голосом Пьер. Масон не шевелился и не говорил долго после этого ответа. Наконец он подвинулся к Пьеру, взял лежавший на столе платок и опять завязал ему глаза.
– Последний раз говорю вам: обратите всё ваше внимание на самого себя, наложите цепи на свои чувства и ищите блаженства не в страстях, а в своем сердце. Источник блаженства не вне, а внутри нас…
Пьер уже чувствовал в себе этот освежающий источник блаженства, теперь радостью и умилением переполнявший его душу.
Скоро после этого в темную храмину пришел за Пьером уже не прежний ритор, а поручитель Вилларский, которого он узнал по голосу. На новые вопросы о твердости его намерения, Пьер отвечал: «Да, да, согласен», – и с сияющею детскою улыбкой, с открытой, жирной грудью, неровно и робко шагая одной разутой и одной обутой ногой, пошел вперед с приставленной Вилларским к его обнаженной груди шпагой. Из комнаты его повели по коридорам, поворачивая взад и вперед, и наконец привели к дверям ложи. Вилларский кашлянул, ему ответили масонскими стуками молотков, дверь отворилась перед ними. Чей то басистый голос (глаза Пьера всё были завязаны) сделал ему вопросы о том, кто он, где, когда родился? и т. п. Потом его опять повели куда то, не развязывая ему глаз, и во время ходьбы его говорили ему аллегории о трудах его путешествия, о священной дружбе, о предвечном Строителе мира, о мужестве, с которым он должен переносить труды и опасности. Во время этого путешествия Пьер заметил, что его называли то ищущим, то страждущим, то требующим, и различно стучали при этом молотками и шпагами. В то время как его подводили к какому то предмету, он заметил, что произошло замешательство и смятение между его руководителями. Он слышал, как шопотом заспорили между собой окружающие люди и как один настаивал на том, чтобы он был проведен по какому то ковру. После этого взяли его правую руку, положили на что то, а левою велели ему приставить циркуль к левой груди, и заставили его, повторяя слова, которые читал другой, прочесть клятву верности законам ордена. Потом потушили свечи, зажгли спирт, как это слышал по запаху Пьер, и сказали, что он увидит малый свет. С него сняли повязку, и Пьер как во сне увидал, в слабом свете спиртового огня, несколько людей, которые в таких же фартуках, как и ритор, стояли против него и держали шпаги, направленные в его грудь. Между ними стоял человек в белой окровавленной рубашке. Увидав это, Пьер грудью надвинулся вперед на шпаги, желая, чтобы они вонзились в него. Но шпаги отстранились от него и ему тотчас же опять надели повязку. – Теперь ты видел малый свет, – сказал ему чей то голос. Потом опять зажгли свечи, сказали, что ему надо видеть полный свет, и опять сняли повязку и более десяти голосов вдруг сказали: sic transit gloria mundi. [так проходит мирская слава.]
Пьер понемногу стал приходить в себя и оглядывать комнату, где он был, и находившихся в ней людей. Вокруг длинного стола, покрытого черным, сидело человек двенадцать, всё в тех же одеяниях, как и те, которых он прежде видел. Некоторых Пьер знал по петербургскому обществу. На председательском месте сидел незнакомый молодой человек, в особом кресте на шее. По правую руку сидел итальянец аббат, которого Пьер видел два года тому назад у Анны Павловны. Еще был тут один весьма важный сановник и один швейцарец гувернер, живший прежде у Курагиных. Все торжественно молчали, слушая слова председателя, державшего в руке молоток. В стене была вделана горящая звезда; с одной стороны стола был небольшой ковер с различными изображениями, с другой было что то в роде алтаря с Евангелием и черепом. Кругом стола было 7 больших, в роде церковных, подсвечников. Двое из братьев подвели Пьера к алтарю, поставили ему ноги в прямоугольное положение и приказали ему лечь, говоря, что он повергается к вратам храма.
– Он прежде должен получить лопату, – сказал шопотом один из братьев.
– А! полноте пожалуйста, – сказал другой.
Пьер, растерянными, близорукими глазами, не повинуясь, оглянулся вокруг себя, и вдруг на него нашло сомнение. «Где я? Что я делаю? Не смеются ли надо мной? Не будет ли мне стыдно вспоминать это?» Но сомнение это продолжалось только одно мгновение. Пьер оглянулся на серьезные лица окружавших его людей, вспомнил всё, что он уже прошел, и понял, что нельзя остановиться на половине дороги. Он ужаснулся своему сомнению и, стараясь вызвать в себе прежнее чувство умиления, повергся к вратам храма. И действительно чувство умиления, еще сильнейшего, чем прежде, нашло на него. Когда он пролежал несколько времени, ему велели встать и надели на него такой же белый кожаный фартук, какие были на других, дали ему в руки лопату и три пары перчаток, и тогда великий мастер обратился к нему. Он сказал ему, чтобы он старался ничем не запятнать белизну этого фартука, представляющего крепость и непорочность; потом о невыясненной лопате сказал, чтобы он трудился ею очищать свое сердце от пороков и снисходительно заглаживать ею сердце ближнего. Потом про первые перчатки мужские сказал, что значения их он не может знать, но должен хранить их, про другие перчатки мужские сказал, что он должен надевать их в собраниях и наконец про третьи женские перчатки сказал: «Любезный брат, и сии женские перчатки вам определены суть. Отдайте их той женщине, которую вы будете почитать больше всех. Сим даром уверите в непорочности сердца вашего ту, которую изберете вы себе в достойную каменьщицу». И помолчав несколько времени, прибавил: – «Но соблюди, любезный брат, да не украшают перчатки сии рук нечистых». В то время как великий мастер произносил эти последние слова, Пьеру показалось, что председатель смутился. Пьер смутился еще больше, покраснел до слез, как краснеют дети, беспокойно стал оглядываться и произошло неловкое молчание.
Молчание это было прервано одним из братьев, который, подведя Пьера к ковру, начал из тетради читать ему объяснение всех изображенных на нем фигур: солнца, луны, молотка. отвеса, лопаты, дикого и кубического камня, столба, трех окон и т. д. Потом Пьеру назначили его место, показали ему знаки ложи, сказали входное слово и наконец позволили сесть. Великий мастер начал читать устав. Устав был очень длинен, и Пьер от радости, волнения и стыда не был в состоянии понимать того, что читали. Он вслушался только в последние слова устава, которые запомнились ему.
«В наших храмах мы не знаем других степеней, – читал „великий мастер, – кроме тех, которые находятся между добродетелью и пороком. Берегись делать какое нибудь различие, могущее нарушить равенство. Лети на помощь к брату, кто бы он ни был, настави заблуждающегося, подними упадающего и не питай никогда злобы или вражды на брата. Будь ласков и приветлив. Возбуждай во всех сердцах огнь добродетели. Дели счастье с ближним твоим, и да не возмутит никогда зависть чистого сего наслаждения. Прощай врагу твоему, не мсти ему, разве только деланием ему добра. Исполнив таким образом высший закон, ты обрящешь следы древнего, утраченного тобой величества“.
Кончил он и привстав обнял Пьера и поцеловал его. Пьер, с слезами радости на глазах, смотрел вокруг себя, не зная, что отвечать на поздравления и возобновления знакомств, с которыми окружили его. Он не признавал никаких знакомств; во всех людях этих он видел только братьев, с которыми сгорал нетерпением приняться за дело.
Великий мастер стукнул молотком, все сели по местам, и один прочел поучение о необходимости смирения.
Великий мастер предложил исполнить последнюю обязанность, и важный сановник, который носил звание собирателя милостыни, стал обходить братьев. Пьеру хотелось записать в лист милостыни все деньги, которые у него были, но он боялся этим выказать гордость, и записал столько же, сколько записывали другие.
Заседание было кончено, и по возвращении домой, Пьеру казалось, что он приехал из какого то дальнего путешествия, где он провел десятки лет, совершенно изменился и отстал от прежнего порядка и привычек жизни.
На другой день после приема в ложу, Пьер сидел дома, читая книгу и стараясь вникнуть в значение квадрата, изображавшего одной своей стороною Бога, другою нравственное, третьею физическое и четвертою смешанное. Изредка он отрывался от книги и квадрата и в воображении своем составлял себе новый план жизни. Вчера в ложе ему сказали, что до сведения государя дошел слух о дуэли, и что Пьеру благоразумнее бы было удалиться из Петербурга. Пьер предполагал ехать в свои южные имения и заняться там своими крестьянами. Он радостно обдумывал эту новую жизнь, когда неожиданно в комнату вошел князь Василий.
– Мой друг, что ты наделал в Москве? За что ты поссорился с Лёлей, mon сher? [дорогой мoй?] Ты в заблуждении, – сказал князь Василий, входя в комнату. – Я всё узнал, я могу тебе сказать верно, что Элен невинна перед тобой, как Христос перед жидами. – Пьер хотел отвечать, но он перебил его. – И зачем ты не обратился прямо и просто ко мне, как к другу? Я всё знаю, я всё понимаю, – сказал он, – ты вел себя, как прилично человеку, дорожащему своей честью; может быть слишком поспешно, но об этом мы не будем судить. Одно ты помни, в какое положение ты ставишь ее и меня в глазах всего общества и даже двора, – прибавил он, понизив голос. – Она живет в Москве, ты здесь. Помни, мой милый, – он потянул его вниз за руку, – здесь одно недоразуменье; ты сам, я думаю, чувствуешь. Напиши сейчас со мною письмо, и она приедет сюда, всё объяснится, а то я тебе скажу, ты очень легко можешь пострадать, мой милый.
Князь Василий внушительно взглянул на Пьера. – Мне из хороших источников известно, что вдовствующая императрица принимает живой интерес во всем этом деле. Ты знаешь, она очень милостива к Элен.
Несколько раз Пьер собирался говорить, но с одной стороны князь Василий не допускал его до этого, с другой стороны сам Пьер боялся начать говорить в том тоне решительного отказа и несогласия, в котором он твердо решился отвечать своему тестю. Кроме того слова масонского устава: «буди ласков и приветлив» вспоминались ему. Он морщился, краснел, вставал и опускался, работая над собою в самом трудном для него в жизни деле – сказать неприятное в глаза человеку, сказать не то, чего ожидал этот человек, кто бы он ни был. Он так привык повиноваться этому тону небрежной самоуверенности князя Василия, что и теперь он чувствовал, что не в силах будет противостоять ей; но он чувствовал, что от того, что он скажет сейчас, будет зависеть вся дальнейшая судьба его: пойдет ли он по старой, прежней дороге, или по той новой, которая так привлекательно была указана ему масонами, и на которой он твердо верил, что найдет возрождение к новой жизни.
– Ну, мой милый, – шутливо сказал князь Василий, – скажи же мне: «да», и я от себя напишу ей, и мы убьем жирного тельца. – Но князь Василий не успел договорить своей шутки, как Пьер с бешенством в лице, которое напоминало его отца, не глядя в глаза собеседнику, проговорил шопотом:
