Загадка 8 ферзей на одной доске

Обновлено: 22.11.2024

Исследователи Сент-Эндрюсского университета в Великобритании предложили миллион долларов тому, кто разгадает старинную шахматную головоломку.

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

Дубликаты не найдены
4 года назад

Блин, так может, мне проще эту задачу решить, чем забеременеть пытаться? Деньги, вроде, те же.

раскрыть ветку 8 4 года назад

текущая задача БАЗИРУЕТСЯ на ОРИГИНАЛЬНОЙ задаче 1850 года о 64 клетках и 8 ферзях, но текущая задача это "написать алгоритм" решающий эту задачу для любого количества клеток (в частности 1000 на 1000 с 1000 ферзями) в разумно приемлимые сроки

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

раскрыть ветку 3 4 года назад На степик.орг эта задача встречается в курсе обучения с++. Именно в такой формулировке - NxN c N ферзями.
раскрыть ветку 2 DELETED 4 года назад

еще давно решил там же, чота нету у меня миллиона от британских ученых.

так бомжем и помру(

4 года назад

на степике нет условия "в разумные сроки".

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

DELETED 4 года назад а забеременеть давно пытаешься?

С одним партнером, или меняешь?)

раскрыть ветку 1 4 года назад Наши лаборантки будут рады ответить на ваши вопросы! :) Оставьте, пожалуйста, свои контактные данные, и мы свяжемся с вами!:) Мы попробуем найти ответы на ваши вопросы вместе! Медикаментозная поддержка, психологическая перестройка и поиск партнёра для вас берём на себя! 4 года назад А ты уже пытался беременеть. раскрыть ветку 1 4 года назад Последние результаты вынашивания - 17 недель. Плод крепкий, пропорция мышечной ткани к скелету - 2.6. Не ахти, конечно, результат, учитывая смертность родительского материала. Мои инженеры ведут долгую и кропотливую работу ради удешевления производства рабочих юнитов. Наши экспериментальные лаборатории уже начали изыскания на предмет производства рабочих юнитов четвёртой категории на основе родительского материала второй очереди. Это значит, что в будущем каждый юнит категории "4+" сможет самовоспроизводиться каждые 3 цикла сам, причём не покидая своей рабочей капсулы. Мы заботимся о вас! 4 года назад

раскрыть ветку 1 4 года назад

Блят. У меня после вчерашнего башка болит пипец, думать вообще влом. А ты тут со схемами своими. Можь, ну их нах, те шахматы? Мы ещё не все способы мужской беременности попробовали.

4 года назад Щас я за кофе сбегаю, готовьте миллион к завтрашнему вечеру. раскрыть ветку 3 4 года назад

Коньюктурщик! Наше общество "Лям за пузо" осуждает ваше стремление к лёгким деньгам!

раскрыть ветку 2 4 года назад Ничем не могу помочь. Я уже начал кодить, и не остановить меня. раскрыть ветку 1 DELETED 4 года назад

- мой песик Альберт пишет картины.

- ну если кормить маслом, то маслом!

4 года назад

Ошибка в переводе статьи. На доске 8х8 даже ребенок решит. У меня 10 секунд ушло. Имеется ввиду программа, способная на основе вводных (размера доски и количества ферзей) решить эту задачку.

4 года назад Хм, расставил на доске. Могу в пару действий доказать, что данный метод (алгоритм) расстановки работает для любой доски N*N с N ферзями, при N>=5. Может все таки требуется алгоритм находящий все возможные варианты расстановки? 4 года назад

расставил фигуры за 4мин.. а алгоритмы писать не умею((

4 года назад раскрыть ветку 2 4 года назад

Ну и действительно, в чём прикол?

4 года назад

Беги за миллионом

показать ещё 0 комментариев Похожие посты 4 месяца назад

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

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

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

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

Следующая загадка

Каждый, наверное, сталкивался с задачей расстановки 8 ферзей на шахматной доске.
Рассмотрим решение данной задачи с использованием массива.

Итак, имеем одномерный массив состоящий из 8 элементов. Индексные значения — это строки, а значения в архиве по соответствующим индексам — это столбец шахматной доски соответственно.

Для того, чтобы мы оставили Ферзя в покое и начали перемещать следующего, должны отсутствовать иные Ферзи:
1. по вертикали
2. по диагоналям
3. по горизонтали

Третий пункт в данном методе решения этой задачи можно исключить сразу, так как два Ферзя в одной строке мы изначально не рассматриваем.

На рисунке показано, какие поля попадают под «бой» (Q — устанавливаемый Ферзь, q — поля на которых не должно быть других.)

Из чего получаем, что нам необходимо для исключения вертикали сравнить равенство номер столбцов, а для исключения диагоналей сравнить модуль разницы столбцов с разницей строк у устанавливаемого и проверяемого Ферзей.

Вот что мы в итоге получаем:

public class Ferzi2 < static int[] chessboard = ; static int index = 0; static int version = 0; public static void main(String[] args)

Следующая загадка

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


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

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

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

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

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

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

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

Задача известна еще с древности (

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


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

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

Задачу придумал в 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 ферзей

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


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

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

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


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

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

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

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


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

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

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

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

Решение: выписываем табличку и по 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: и они определяют каким ограничениям должно удовлетворять решение: не может быть ферзя в одном и том же ряду, не может быть ферзя в одной и той же колонке (опущено, в силу симметрии) и не может быть ферзя на одной и той же диагонали.

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

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


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

Нярн шинж — национальная калмыцкая головоломка. Описание. История. Полная сборка и разборка. Классическая и альтернативная начальные позиции

Название игры переводится как "тонкое соображение" или "мудрое решение"[1].

Другое распространённое название — 12 роговых колец.

Элементы головоломки — железный прут, а также дощечка, к которой прикреплены кольца, которые также особым образом скреплены между собой.

Число колец обычно составляет 8 или 12, хотя иногда встречаются другое исполнение.

На фото представлена классическая начальная позиция, которая чаще всего даётся для решения головоломки, здесь вариант из 8 колец.

А так выглядит освобождённая от прута планка с кольцами.

Как утверждается, игра была известна ещё в древности, а во время праздников проводились состязания по её решению. Находятся свидетельства, что решить головоломку "предлагали сватам на сватовстве девушки", а несправившимся иногда отказывали, а ещё "в порядке выигрыша" могли "требовать оседлого коня"[2].

Тому же автору приписывается стихотворение про эту головоломку[3]:

Не зря народ оставил нам в наследство
Так много игр, влекущих издали:
Играло человеческое детство —
И улетали к звездам корабли.

В некоторых источниках более обобщённо рассказывают о предрасположенности калмыков в целом к математике, некой склонности к созданию и решению головоломок и загадок, а также о распространённости шахмат[4]. Возможно, также неспроста Международную ассоциацию по шахматам с 1995 по 2018 гг. возглавлял К.Н.Илюмжимов, который также долгое время являлся главой Калмыкии.

В настоящее время, как кажется, игра вновь набирает некоторую национальную популярность, на неё обращают внимание в школах, она является предметом изучения[1, 2, 3, 4], головоломку разгадывают в качестве состязания[5], в том числе во время праздников / мероприятий, наряду с другим распространённым народным развлечением — игрой в альчики[6]. Но это уже другая тема. :)

Часть 2. Бонус: Кстати, вот так выглядит альтернативная стартовая позиция. В отличие от классической расстановки, приведённой выше, здесь остаётся только одно последнее неснятое кольцо.

Только вот чтобы решить головоломку, теперь понадобится почти в два раза больше действий!

И первый этап — надеть все кольца обратно, с первого до последнего (о ужас!). А уже только потом их снимать!

(Иногда ещё дополнительно надевают первое кольцо. Тогда путь решения станет официально самым длинным из возможных!)

Собственно .. на этом бы можно было и закончить?

Но нет. Хорошо бы ещё знать, как это разбирать и собрать. Правильно?

Если кратко, то, там несложно, особенно если знать (хе-хе):

- чтобы снять чётное кольцо (например, кольцо 12) нужно сначала снять 1 + 2 кольца, потом сразу снимается 4 кольцо, а потом можно идти за другими (будут сняты кольца 1-10, следующим шагом снимается кольцо 12!),

- а чтобы снять нечётное кольцо (например, кольцо 11) нужно сначала снять 1 кольцо, потом сразу снимается 3 кольцо, а потом можно идти за другими (будут сняты кольца 1-9, следующим шагом снимается кольцо 11!).

Вот ценный совет. А ещё в Интернете есть видео. Вот второй ценный совет. Но и на этом не закончим.

Выкладываю собственные полные пособия по сборке и разборке нярн жинж. :)

1. Текстовая инструкция. Полная разборка нярн шинж (12 колец) из классической стартовой позиции, а также его сборка обратно + там же описание разборки и сборки этой головоломки из альтернативной стартовой позиции:

- текстовый вариант (текст того же, в новой вкладке),

- зеркало (.doc, когда перестанет грузиться),

- зеркало-2 (.txt, тот же текстовый вариант).

2. Иллюстрированная инструкция. Полная разборка нярн шижн (8 колец) из классической стартовой позиции. Для сборки — смотреть в обратном порядке (ну, разумеется):

- зеркало (.pdf, когда перестанет грузиться).

UPDATE: 2.1. Иллюстрированная инструкция в виде gif (141 кадр, 6,6мб) (по просьбам):

Текст (кроме цитирования), фотографии и все пособия мои, можете свободно использовать: CC0.

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

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

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

При поиске ответа на задачу тренируются следующие навыки:

    – способность находить нестандартные решения интеллектуальных задач, действовать не на основе изобретенного алгоритма, адаптивно ведя поиск ответа; – вид умственной деятельности и избирательное направление восприятия, без которых концентрация на предмете невозможна;
  • логическое мышление – вид мыслительного процесса, при котором знание достигается путем применения в рассуждении понятий и логических конструкций.

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

Следующая загадка

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

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

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

Читайте также: