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

Обновлено: 04.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 — поля на которых не должно быть других.)

image

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

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

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

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

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

image


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

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

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

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

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

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

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

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

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



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

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

Задачу придумал в 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 фигур – ферзей, (или королев, если угодно), таким образом, чтоб ни одна из них не была под боем другой.

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