Не атакующие друг друга слоны, угроза всех полей

Всем здравствуйте, столкнулся с такой проблемой, что непонимаю условия задачи, может кто-то поймет, что здесь происходит? Сама задачу звучит так:
Не атакующие друг друга слоны, угроза всех полей
Найти все способы расстановки минимального числа не атакующих друг друга слонов на
шахматной доске размером n х n так, чтобы они держали под угрозой все поля доски.
Исследовать асимптотическую временную сложность решения задачи в зависимости от n.
Подсказка: число фигур = n; для n = 8, число фигур = 8, число расстановок = 5184.

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

0

Но ответ для примера не сходится, получается 22522960 вариантов расстановки при n = 8.
Либо я что-то не так сделал с исходным кодом, чтобы его запустить (маловероятно, но всё может быть), либо задача по ссылке выше отличается (там не указано, что должны быть "под угрозой" все поля доски, и это, судя по всему, влияет на результат).

0

Сообщение от gunslinger и это, судя по всему, влияет на результат

Например, мы не должны учитывать подобные ситуации (тут не все поля "под ударом"):

Для n = 3 ответ должен быть 2 (вроде как), а не 26 (судя по коду).
Дальше правильный ответ не считал (вручную), но суть (расхождения) должна быть ясна.
Короче, нужно как-то отбрасывать "лишнее". Либо подход "изначальный" менять (ибо это другая задача).

0

Проблема в том, что ТС не понимает условие, следовательно, он не в состоянии объяснить, что подразумевается под "не атакующие друг друга слоны"? Тут некоторые в теме начали активно рассуждать задачу, что мне показалось, что они поняли условие. Однако, на мой вопрос никто так и не ответил, что говорит о том, что никто не понял условие. Если же условие никому не понятно, то смысл вообще делать вид, мол пытаетесь что-то решить?

0

Сообщение от TheCalligrapher О каких "в 1 ряду таких 64 варианта" вы ведете речь? Откуда взялось 64?

64 - это количество комбинаций в 1 ряду, если менять между собой этих слонов. Вот первая уникальная комбинация, где каждым цветом указан единственный слон - https://kappa.lol/1wsi-. Далее, мы ищем еще 1 комбинацию, можем поменять местами 2 слона между собой - это и будет еще уникальная комбинация - уже нашли 2 таких комбинаций - https://kappa.lol/TQi81. чтобы не сидеть и не менять местами вот так каждую, можно умножить 8 на 8 = 64. в первом ряду будет 64 такие комбинации, где можно переставлять местами. каждый такой ряд одинаковый между собой, следовательно, можно просто 64*8 = 512 комбинаций - это все 8 рядов по горизонтали. также можно сделать и по вертикали. еще 512 комбинаций. 512+512 = 1024. но есть еще комбинации.

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

не понимаю вообще, как писать код для этой задачи, помогите пожалуйста

Вложения

a000899_1.pdf (2.30 Мб, 4 просмотров)

0

Сообщение от Royal_X Проблема в том, что ТС не понимает условие, следовательно, он не в состоянии объяснить, что подразумевается под "не атакующие друг друга слоны"

у слонов ход - это диангональ, следовательно, на жтой диагонали не должен стоять другой слон. пример - когда все слоны стоят в 1 ряду, она не угрожают друг другу, но угрожают всему полю. ПОКА ПИСАЛ ЭТОТ ТЕКСТ, ПОНЯЛ, ЧТО Я ДУРАК. ЕСЛИ ПОСТАВИТЬ В 1 ЛИНИЮ, ТО НЕ ПОЛУЧИТСЯ ЗАКРЫТЬ ВСЕ ПОЛЕ. ВСЕ, ЭТО ЖОПА, А НЕ ЗАДАЧА(извините за капс) https://kappa.lol/65aPv

Добавлено через 33 секунды
прошу прощения, способ где все в ряд - не работает

0

Сообщение от Judie dkkd не угрожают друг другу, но угрожают всему полю.

Это ж как они бьют всё поле стоя на первом ряду ???
Там где О, кто будет бдить ?

Сообщение от Royal_X Однако, на мой вопрос никто так и не ответил, что говорит о том, что никто не понял условие.

Все поняли, только я не понял что ты не понял.
Ну чё, понял ?

Добавлено через 2 минуты

Сообщение от Judie dkkd прошу прощения, способ где все в ряд - не работает

Работает, если стоят ближе к центру.

0

Сообщение от SmallEvil Работает, если стоят ближе к центру.

а как написать программу, которая будет выводить количество комбинаций? это невозможно(

0

Прямым перебором даже 8*8 не вытянет.
Нужно искать закономерности.

0

SmallEvil, ну если ты понял, то объясни, как ты понял, слоны одного цвета или там есть и белые и черные, соответственно, если свой слон атакует своего, то это не считается атакой?

0

Royal_X,
- считай что все слоны свои
- могут стоять на любых клетках (чёрных и белых)
- расставить что бы ни один слон не "смотрел" стоял на линии боя у другого
- расставить их так, что бы все свободные поля были под боем
- количество слонов равно N (где N - размер доски).

Я так понял, если ТС не сильно исковеркал текст ТЗ.

Добавлено через 2 минуты
ЗЫ : В любом случае, задача-однодневка для гиков.

1

Сообщение от SmallEvil - считай что все слоны свои - могут стоять на любых клетках (чёрных и белых) - расставить что бы ни один слон не "смотрел" стоял на линии боя у другого - расставить их так, что бы все свободные поля были под боем - количество слонов равно N (где N - размер доски).

все правильно

0

SmallEvil, типа так

1

Сообщение от Royal_X типа так

да, теперь эти слоны в этой позиции менять можно местами между собой, каждая смена +1 комбинация

0

Сообщение от Judie dkkd еперь эти слоны в этой позиции менять можно местами между собой

зачем их менять местами ?
что это за фишка и где она в условии ?

0

Number of arrangements of n non-attacking bishops on an n X n board such that every square of the board is controlled by at least one bishop: https://oeis.org/A122749

FORMULA From Andy Huchala, Mar 22 2024 (based on Mathematica code): (Start) a(4*n) = (n+1)^2*((2*n)!)^2. a(4*n+1) = (1/3)*(n+2)*(1+4*n+6*n^2)*((2*n)!)^2. a(4*n+2) = 4*(n+1)^4*((2*n)!)^2. a(4*n+3) = (1/3)*(3+17*n+22*n^2+6*n^3)*(2*n)!*(2*n+2)! . (End)

n a(n) 2 4 3 2 4 16 5 44 6 256 7 768 8 5184 9 25344 10 186624 11 996480 12 8294400 13 57888000 14 530841600 15 4006195200 16 40642560000 17 367408742400 18 4064256000000 19 39358255104000 20 474054819840000 21 5254107586560000 22 68263894056960000 23 804207665479680000 24 11242684107325440000

1

gunslinger, спасибо, под это программу попробую написать

0

Сообщение от gunslinger FORMULA

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

1

SmallEvil, как дойти: https://link.springer.com/chap... BFb0097382 или ссылка от ТС-а.
Меня это ничему не учит (если только гуглить), так как мозгов не хватает. Насчет других не знаю.
И, как по мне, задача далеко не тривиальная.

Добавлено через 27 минут
"Неэквивалентный" (inequivalent) случай (частный?): https://oeis.org/A005635
В указанной ситуации, видимо, отбрасываются случаи, которые можно получить "симметричным отображением".
То есть учитываются только "оригинальные" (в своей конфигурации) расположения фигур.

Оригинал ссылки от ТС-а: https://oeis.org/A000899/a000899_1.pdf

0

Сообщение от gunslinger Тут, видимо, отбрасываются случаи, которые можно получить "симметричным отображением"

Нет! Тут ты ошибаешься.
Я писал методом в лоб, все перестановки, то есть все варианты, и на малых значения совпадают (ну а на больших, нужно стареть и умирать, пока перестановки продолжаются).
То есть зеркальные тоже учитываются.

Добавлено через 3 минуты

Сообщение от gunslinger "Неэквивалентный" (inequivalent) случай (частный?)

По ссылке, ну да, видимо что так.
Вообщем, задачка опередила знания ТС.
Тут нужно грызть и грызть "гранит науки" ))

Добавлено через 1 минуту
Никто не хочет спросить у ЧатоЖопыти, как оно видит решение ? ))

0

SmallEvil, подправил текст (чтобы было понятнее). Он относится к "частному" случаю.
Но ты это, видимо, уже понял.

Добавлено через 5 минут
А с жпт стараюсь не общаться. Баловство это (но другие могут считать иначе).

Добавлено через 1 час 33 минуты
На основе

MAPLE E:=proc(n) local k; if n mod 2 = 0 then k := n/2; if k mod 2 = 0 then RETURN( (k!*(k+2)/2)^2 ); else RETURN( ((k-1)!*(k+1)^2/2)^2 ); fi; else k := (n-1)/2; if k mod 2 = 0 then RETURN( ((k!)^2/12)*(3*k^3+16*k^2+18*k+8) ); else RETURN( ((k-1)!*(k+1)!/12)*(3*k^3+13*k^2-k-3) ); fi; fi; end;

получился код
Результат:

0