Может ли в шахматах быть 2 ферзя?
Но таким образом может быть и больше, чем только 2 ферзя на доске!
По правилам, пешка дошедшая до последней горизонтали может стать любой фигурой, в том числе и ферзём. В шахматной литературе описаны задачи и композиции в которых на шахматной доске находятся и два, и три ферзя.
Вообще-то в начальной позиции на доске всегда два ферзя- белый и черный).
Теоретически же на шахматной доске может быть одновременно 9 белых ферзей и 9 черных ферзей. Поскольку все из 16-ти пешек могут превратиться в ферзей (при достижении пешками последней горизонтали) + ещё 2 ферзя изначально-вот и всего 18 ферзей).
В реальных партиях такое чудо, конечно, не встречается). Но в турнирных партиях (на высоком уровне) бывало, и по 4 ферзя имелось(по 2 штуки у каждого игрока), ничего удивительного).
Если исходить из начальной позиции, то каждый шахматист имеет в наличии 1-го ферзя. Т.е. их изначально 2. Один белый и один чёрный.
По правилам шахматной игры пешка, дошедшая до последней горизонтали, может превратиться в любую из фигур, исключая короля. Следовательно, в ферзя она тоже может превратиться. Если к тому моменту ферзь из начального комплекта фигур ещё находится на доске, то получится 2 ферзя одного цвета.
В первой диаграмме мат чёрному королю ставится в четырнадцать ходов. Первый ход здесь такой: Фb4-c5. Во второй позиции мат ставится тоже в четырнадцать ходов. Первый ход за белых будет: Фe4-f5. В третьей позиции белые ставят мат в одиннадцать ходов. Первый ход: Кре3-f3. Есть такие Таблицы Налимова, где на шахматной доске все варианты просчитаны до самого конца, при условии, что на доске не более шести фигур.
К сожалению для черных, имеющих большой материальный перевес, добиться победы здесь, при правильной игре белых, нельзя. Почему? Просто белые имеют все шансы построить «крепость», то есть такое положение, при котором черному королю никак не подойти на помощь ферзю).
А для построения крепости белым, например, нужно всего-то попасть ладьей на с3. Если бы сейчас был ход белых, то просто 1.Лс3+, и всё. Король черных к углу не попадет, и белые далее просто ходят королем туда-сюда, не оставляя пешку b2 без зашиты, конечно. И по истечению 50-ти ходов фиксируется ничья).
И при ходе черных нет никакой возможности воспрепятствовать попаданию ладьи на с3. «Вилки» нет, и с помощью шахов падью не выиграть.
Вот так наличие одной дополнительной пешки позволяет слабейшей стороне легко защитится в таких позициях).
В спортивных шахматах две ладьи всегда лучше и сильнее. Почему так?
Недаром есть в шахматах понятие «ценность», и вот эта ценность любой шахматной фигурки исходит не просто так. Поставьте в центр доски любую фигуру и посчитайте сколько она контролирует полей одновременно, излучая свои «усики» — все поля на которые она может попасть.
Так вот, две ладьи будут всегда «захватывать» 28 полей, где бы они не были на пустой доске! Когда как ферзь будет, в лучшем случае — 27, а в худшем на пустой доске 21.
Поэтому ценность одной ладья — 5, а ценность ферзя около 9. И математически 10 будет больше 9, и по маневренности две ладьи лучше, чем ферзь и. по взаимодействию друг друга — две ладьи (за счет универсальности*) опаснее, чем один ферзь!
Две ладьи могут контролировать и оказывать давление на разных участках в партии больше по возможностям, чем один ферзь.
«Универсальность» (в сравнение однопольных слонов) попадание на любое поле, черное или белое. Поэтому, конь с малым маневром, равен слону
Да, такая расстановка вполне возможна, и даже не так уж сложна — вариантов далеко не один. Полный набор решений задачи про расстановку восьми ферзей на стандартной шахматной доске насчитывает аж 92 варианта, и исчерпывается ими, что доказал в 1874 году Глэшер. А привел этот полный набор решений (часть из них была получена им же, часть — другими математиками) Ф. Наук в 1850 году.
Вот один из вариантов расстановки:
В приведённой позиции материальное преимущество белых незначительно, и уж никак не скажешь, что чёрные играют без ферзя.По шахматной арифметике, без учёта конкретной позиции, ферзь равен двум ладьям.Следовательно у белых материальное преимущество — качество + пешка.Данный перевес не может быть решающим для этой позиции.Вероятно предыдущий ход белых был слишком «атакующим» -ладья белых пошла на 7-ю линию, забыв о защите короля. Но даже беглый взгляд на доску,без серьёзного анализа, показывает, что у чёрных позиция не хуже, а из-за плохого положения белого короля, у чёрных есть все шансы на победу.Здесь Вы немного лукавите относительно везения: на мой взгляд партия развивалась динамично, а разница в материале есть результат каких-либо тактических замыслов.
Не думаю, что просто подарив ферзя, можно надеяться на выигрыш с шахматистом уровня приведённой позиции;саму позицию можно рассматривать как ответ на поставленный вопрос.
Может ли быть несколько ферзей на шахматной доске?
Дабы не наводить тень на плетень и сразу внести ясность, скажу, что ответ на вопрос: может ли быть несколько ферзей на доске, — положительный.
Никаких ограничений в правилах на этот счет нет. Это означает, что теоретически ферзей может быть столько, сколько пешек. Ибо каждая из них может превратиться в ферзя.
Практически ситуация с 16 ферзями разумеется невозможна. Более того, на практике позиции с тремя ферзями встречаются редко, с четырьмя – еще реже. Более 4 ферзей автору в практических партиях наблюдать не доводилось.
Стереотипы восприятия, или ферзь – фигура конкретная
Ферзь – фигура, обладающая почти неограниченными возможностями. В позициях «ферзь против ферзя» и особенно в ситуациях когда на доске появляется несколько ферзей, — оценка позиции из общих соображений неприемлема.
«У меня два ферзя и у него два ферзя и по 4 пешки, — значит на доске равенство».
Такая оценка слишком абстрактна . Ферзь, а тем более два ферзя обычно с легкостью опровергнут столь поверхностные суждения.
Давайте рассмотрим примеры, подтверждающие это правило.
Бульдозер
Иногда в партиях возникает ситуация, когда проходные пешки проходят в ферзи одновременно. При этом «первозданные» ферзи еще на доске.
В таких ситуациях чаще всего выигрывает та сторона, у кого право хода. Два ферзя способны запросто все смести на своем пути словно бульдозер.
1.с8Ф d1Ф
Казалось бы черным до победы рукой подать – 2. Фf1X
Однако ход белых. И это меняет все.
2.Фf5+!
На 1…Крh6 следует 2.Фbf4+ и мат следующим ходом. Другие отступления короля также не спасают черных от мата в два хода. В этом вы можете легко убедиться сами.
Один на один
Еще один пример стереотипа восприятия.
Как бы вы оценили эту позицию?:
Ну что здесь может быть кроме ничьей? Оказывается может…
1.Фс4+ Кра3 2.Фа6+ Крb2 3.Фb5+ Кра3 4.Фа5+ Крb2 5.Фb4+ и 6.Крс2
И мат следующим ходом.
Один ферзь в поле воин
Еще пример, подтверждающий важность таких факторов, как очередь хода и конкретное расположение фигур.
1.h8Ф? А как удержаться от такой возможности?
1… Фе2+! С ничьей.
На 2.Крb3 Фе6+! (но не 2. Фе3+?? 3.Фс3!)
Ферзь черных шахует так, чтобы не дать защититься ферзем с поля h8 и не дает выйти королю белых из клетки.
Иногда можно воспользоваться сопутствующими возможностями. Например, залезть в пат.
У белых грозная позиция и материальный перевес. Однако.
1. Фс7!!
Холодный душ. Теперь на 2.Ф:с7 пат, а на 2.Кра6 Фс8+ 3.Кра5 Фс7 Ничья.
Еще похожий пример, но уже с другим, еще более неожиданным результатом:
1. Фg1+
Что делать белым? На 2.Крf4 Фd4+ c вечным шахом. А что если избежать ничейной перспективы? Две пешки как никак.
2.Крh4??
3. Фе1+ 4.Фg3 Фе7+ 5.Крg4 Фg5Х
Белые избежали ничьей. Правда слишком дорогой ценой:)
На это оптимистичной ноте позвольте откланяться. Сегодня обойдемся без пространных эпилогов. Играйте в шахматы!
Разбираемся, что же там нового открыли в задаче о ферзях
Пару месяцев назад появилась занятная статья с анализом классической задачи о расстановке ферзей на шахматной доске (см. детали и историю ниже). Задача невероятно известная и вся уже рассмотрена под микроскопом, поэтому было удивительно, что появилось что-то действительно новое.
Сможете поставить ещё шесть? А найти все решения?
(картинка из статьи)
Далее, к сожалению, произошла какая-то совершенно невразумительная история из цепочки вот таких вот превращений:
- Отличная статья —пресс служба университета—>невразумительный пресс-релиз.
- Пресс релиз —занятный перевод—>непонятная статья на гиктаймс
Стоит отметить, что пять наугад открытых ссылок на русском ещё меньше проясняли картину происходящего.
Я тут подумал — надо бы кому-то эту странную цепочку прервать и нормальным языком изложить суть событий.
О чём пойдёт речь:
История задачи
Латинский квадрат
Задача известна еще с древности (
средних веков), необходимо расставить буквы таким образом, чтобы ни в одной строке и ни в одной колонке не было одинаковых, как например здесь:
Само название Латинский Квадрат получило из-за привычки использовать буквы латинского Леонардом Эйлером для данной задачи. Из латинского квадрата (и ряда похожих задач) естественным образом появлялись новые, такие как задача о ферзях, где добавляется дополнительное ограничение на диагонали.
Задача о восьми ферзях
Задачу придумал в 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 достоин отдельного поста (который лежит у меня в черновике уже неприлично долго): поэтому разберем концептуальные моменты
Строка 1 < queen(X,Y) : column(Y) >1 :- row(X). — называется choice rule, и она определяет, что является допустимым пространством поиска.
Последние три строки называются integrity constraints: и они определяют каким ограничениям должно удовлетворять решение: не может быть ферзя в одном и том же ряду, не может быть ферзя в одной и той же колонке (опущено, в силу симметрии) и не может быть ферзя на одной и той же диагонали.
В качестве системы для экспериментов рекомендую Clingo.
И для начала стоит посмотреть их tutorial и попочитать блог на www.hakank.org.
Безусловно, если впервые писать на ASP, то первая модель не выйдет невероятно эффективной и быстрой, но скорее всего будет быстрее перебора с возвратом, написанным на скорую руку. Однако, если понять основные принципы работы системы, ASP может стать «regexp для NP-полных задач».
Проведем простой численный эксперимент с нашей ASP моделью. Я добавил 5 коварных ферзей в модель и запустил поиск решения для N от 1 до 150 и вот, что вышло (запущено на обычном домашнем ноутбуке):
Итого, наша ASP модель примерно в течении минуты может найти решения задачи о дополнении при N <= 150 (в обычном случае). Это показывает, что система отлично подходит для прототипирования моделей сложных комбинаторных задач.
8 ферзей на шахматной доске
Восемь ферзей на шахматной доске — головоломка, которая адресована начинающим игрокам для развития пространственного мышления и аналитических способностей. Автором задачи стал теоретик шахмат Макс Беззель (1824-1871). Условия головоломки были сформулированы в 1848 году: игроку предстояло расположить на классической шахматной доске восемь ферзей так, чтобы ни одна из фигур не находилась под боем любой другой. Задача усложняется геометрией ферзевых ходов, которые осуществляются не только по вертикали или горизонтали, но и в диагональном направлении.
Классическая версия головоломки может формулироваться в нескольких вариантах:
- найти любое допустимое решение;
- выявить все возможные варианты решений;
- доказать возможность решения задачи.
Модифицированная версия головоломки Беззеля используется при обучении школьников основам программирования и математического анализа. Ученикам предлагается расставить N фигур на доске N×N клеток. В качестве N выступает любое целое число. Многочисленные исследования показали, что при значениях переменной, равным 2, 3 или 4, задача становится нерешаемой.
Допустимые варианты решения
За 170 лет шахматистам удалось найти 12 базовых решений для головоломки Беззеля. Они рассматриваются в качестве основных во всех учебниках по шахматной теории. Учет правил симметрии позволит расширить число доступных решений до 92: расположение фигур относительно друг друга будет неизменным, варьируются только координаты клеток с ферзями.
Карл Гаусс, известный математик и любитель шахмат, смог выявить 72 варианта расстановки. Ученый использовал своеобразный подход: при обнаружении подходящего решения он последовательно разворачивал доску вокруг оси с шагом в девяносто градусов. Так появлялись «дополнительные» варианты расстановки без длительных изысканий.
Как расставить 8 ферзей на доске
Головоломка Беззеля рассматривается тренерами как задача средней сложности: подходящее решение могут обнаружить новички за несколько минут. Наиболее известная расстановка фигур отражена в таблице.
| Номер ферзя | Координаты |
| Первый | h5 |
| Второй | f1 |
| Третий | d8 |
| Четвертый | b4 |
| Пятый | g7 |
| Шестой | e3 |
| Седьмой | c6 |
| Восьмой | a2 |
Три дополнительных варианта можно получить с помощью последовательного поворота доски по предложенному Гауссом принципу. Аналогичным образом действует зеркальное отражение расстановки фигур.
Решение задачи о восьми ферзях полезно для формирования навыков счета ходов, анализа текущей позиции на доске и поиска быстрого ответа на комбинацию соперника. Новичкам рекомендуется искать варианты расстановки фигур без использования ухищрений в виде поворотов игрового поля. В этом случае все обнаруженные решения станут результатом интеллектуальных усилий игрока.
Модифицированные условия задачи Беззеля часто используются в математических секциях или на уроках информатики. Так, осваивающие основы программирования ученики могут создать скрипт для поиска решений при фиксированном или произвольном значении переменной N, обозначающей количество расставляемых на доске фигур и размеры игрового поля.