Загадка 8 ферзей на одной доске
Обновлено: 20.09.2024
Исследователи Сент-Эндрюсского университета в Великобритании предложили миллион долларов тому, кто разгадает старинную шахматную головоломку.
Ученые предложили всем желающим попробовать себя в решении сложной задачи или доказать, что ее решения нет. Исследователи подчеркнули, что тот, кто сумеет написать программу, будет способен адаптировать ее для решения значимых проблем.
Дубликаты не найдены
4 года назадБлин, так может, мне проще эту задачу решить, чем забеременеть пытаться? Деньги, вроде, те же.
текущая задача БАЗИРУЕТСЯ на ОРИГИНАЛЬНОЙ задаче 1850 года о 64 клетках и 8 ферзях, но текущая задача это "написать алгоритм" решающий эту задачу для любого количества клеток (в частности 1000 на 1000 с 1000 ферзями) в разумно приемлимые сроки
по моим ощущениям проблемы тут особой нет, т.к. хотя ученые и предполагают что задача решается перебором, по мне так она решается алгоритмически
раскрыть ветку 3 4 года назад На степик.орг эта задача встречается в курсе обучения с++. Именно в такой формулировке - NxN c N ферзями.раскрыть ветку 2 DELETED 4 года назад
еще давно решил там же, чота нету у меня миллиона от британских ученых.
так бомжем и помру(
на степике нет условия "в разумные сроки".
и хотя я не согласен с тем, что 1000х1000 представляет из себя какую-то проблему (если надо найти одну любую расстановку, а не все), но в задаче на степике речь идет о решении в принципе, а не об оптимальном. при этом необходимость (на степике) решать это через рекурсивные функции оптимальной явно не будет (они жрут память и ресурсы дай боже как).
DELETED 4 года назад а забеременеть давно пытаешься?С одним партнером, или меняешь?)
Блят. У меня после вчерашнего башка болит пипец, думать вообще влом. А ты тут со схемами своими. Можь, ну их нах, те шахматы? Мы ещё не все способы мужской беременности попробовали.
Коньюктурщик! Наше общество "Лям за пузо" осуждает ваше стремление к лёгким деньгам!
- мой песик Альберт пишет картины.
- ну если кормить маслом, то маслом!
4 года назадОшибка в переводе статьи. На доске 8х8 даже ребенок решит. У меня 10 секунд ушло. Имеется ввиду программа, способная на основе вводных (размера доски и количества ферзей) решить эту задачку.
4 года назад Хм, расставил на доске. Могу в пару действий доказать, что данный метод (алгоритм) расстановки работает для любой доски N*N с N ферзями, при N>=5. Может все таки требуется алгоритм находящий все возможные варианты расстановки? 4 года назадрасставил фигуры за 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 фигур – ферзей, (или королев, если угодно), таким образом, чтоб ни одна из них не была под боем другой.
Читайте также: