Поиск оригинальных комбинаций четверок ферзей.

Gennadiy Usov
Дата: 23.02.2018 19:31:06
В сообщении 22 21156343 говорится об «оригинальных комбинациях четверок ферзей», то есть должны быть специальные комбинации четверок, чтобы они не повторялись.
Есть предложение обсудить возможность построения алгоритма выбора таких комбинаций (конечно, если такой алгоритм возможен).

Исходные данные:
Допустим, имеется множество точек, сформированных на плоскости в виде прямоугольника А на В точек, т.е. всего точек N = А х В.
Каждые 4 рядом стоящие точки (пока рассматриваем только такие) образуют квадрат (четверку) точек. Всего таких квадратов будет М = (А-1) х (В-1).
Каждая комбинация квадратов включает в себя перечень разных квадратов из М квадратов на плоскости. В комбинации может быть любое количество квадратов, отвечающих следующим условиям:
- нельзя в одну комбинацию включать рядом стоящие квадраты, то есть точки нового квадрата комбинации уже использованы в одном из квадратов этой комбинации.
- комбинация из одного квадрата может быть только одна, и комбинация из одного другого квадрата уже не оригинальна.
- новая комбинация квадратов не должна быть похожа на предыдущие комбинации квадратов с учетом сбвигов, симметрии и поворотов.
Требуется найти все оригинальные комбинации квадратов из М квадратов.

Ниже приведен пример нескольких оригинальных комбинаций квадратов для 16 квадратов, образованных 25 точками (5х5).
+

О О О О
О К О О
О О О О
О О О О

К О О О
О О О О
О К О О
О О О О

К О О О
О О О О
К О О О
О О О О

К О О О
О О О О
О О К О
О О О О

К О О О
О О О О
К О К О
О О О О

К О К О
О О О О
К О К О
О О О О

О О К О
К О О О
О О О К
О К О О
Мудроглюков
Дата: 24.03.2018 16:45:19
вообще-то на шахматной доске каждая клетка имеет свои "координаты" и
вот повороты и смметрии на доске - это другие позиции => другие положения ферзей

И в задаче нужно ПОДСЧИТАТЬ, а не выдать все положения.

_____
И если "мы" глуповато просто проверяем все возможные позиции, оценивая атакуют ли
какие-нибудь ферзи друг друга, то это и есть NP-полнота такого решения = ресурсозатркты
на такое решение равны ресурсозатратам на прямую проверку всех возможных позиций (то
есть, по-пацански говоря, алгоритма нет).
Gennadiy Usov
Дата: 25.03.2018 07:11:46
Мудроглюков
И если "мы" глуповато просто проверяем все возможные позиции, оценивая атакуют ли
какие-нибудь ферзи друг друга, то это и есть NP-полнота такого решения = ресурсозатркты
на такое решение равны ресурсозатратам на прямую проверку всех возможных позиций (то
есть, по-пацански говоря, алгоритма нет).

Никто не говорит, что алгоритм охватит все возможные решения, хотя к этому надо стремиться.
Если имеется множество комбинаций "четверок", которые можно применить в задаче, то нахождение алгоритма, который определяет часть этих комбинаций - это уже неплохо.

В выше указанной постановке задачи - только "малые "четверки" - внутри "четверок" точек нет. И эти "четверки" применяются по-парно. А ведь могут быть тройки "четверок", четверки "четверок" и т.д.
В выше указанной постановке задачи - только "малые "четверки" - внутри "четверок" точек нет. А ведь есть еще "четверки", которые имеют внутри 1 точку, 4 точки и т.д.
А есть еще комбинации "малых", "побольше", "еще побольше" и т. д. "четверок".
Так что курочка по зернышку.
tip78
Дата: 25.03.2018 09:37:47
зачем комбинации с пустыми клетками?
и зачем такие, неразрешённые по условию задачи (ферзи на одной линии):
К	О	К	О
О	О	О	О
К	О	К	О
О	О	О	О
tip78
Дата: 25.03.2018 09:39:38
в поле 10Х10 эти квадраты не сработают
а вообще это уже по-моему рассматривали в теме про ферзи
Gennadiy Usov
Дата: 25.03.2018 12:49:38
tip78
зачем комбинации с пустыми клетками?
и зачем такие, неразрешённые по условию задачи (ферзи на одной линии):
К	О	К	О
О	О	О	О
К	О	К	О
О	О	О	О

В сообщении 21214450 рассматривается пример, который может помочь в определении «оригинальных комбинаций четверок ферзей».
Под точками подразумеваются те ферзи, которые можно перемещать (небольшой поворот).
А в примерах, приведенные в том же сообщении, показаны уже квадраты, которые располагаются на сетке точек 26х25. Об этом написано перед примерами.
Буквой К показаны квадраты, которые перемещаются для данного варианта комбинации.
Буквой О показаны квадраты, которые не перемещаются для данного варианта комбинации.
Соседние по сторонам квадраты имеют две общие точки.
Соседние по углам квадраты имеют одну общую точку.
Gennadiy Usov
Дата: 25.03.2018 12:53:12
tip78
в поле 10Х10 эти квадраты не сработают
а вообще это уже по-моему рассматривали в теме про ферзи

Проработки показали, что квадраты "работают" на досках 6хК+К1, где К1 = 0,1,4,5. 21272629
Мудроглюков
Дата: 27.03.2018 04:31:17
tip78
в поле 10Х10 эти квадраты не сработают
а вообще это уже по-моему рассматривали в теме про ферзи


в отдельный топег не лишне - абстрагировать алоритмику от прочего
Мудроглюков
Дата: 27.03.2018 04:51:50
Мудроглюков
вообще-то на шахматной доске каждая клетка имеет свои "координаты" и
вот повороты и смметрии на доске - это другие позиции => другие положения ферзей

И в задаче нужно ПОДСЧИТАТЬ, а не выдать все положения.

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


вот проникнуться глубже и по-существу в чем вопрос: NP =? P

имхо, это как вот если богатый и прекрасный принц искал бы себе жену = он мог бы просто
опробовать на роль жены всех имеющихся женщин планеты Земля, и каждую бы
конкретно проверил "является ли она решением его задачи?" (NP-полнота, если о
любой женщине нет никакой информации) - и верифицируя отмечал бы: одна блудлива,
другая скандальна, третья старовата "душой", четвертая занудлива, ... и попробовав
всех выбрал бы, но это когда у него нет критериев,
а в жизни всегда есть какая-то информация об объектах задачи и всегда
есть какие-то критерии, что является решением, и т.д. = то есть всгеда
есть возможность решить задачу на имеющихся ресурсах (P-трудность),
причем принципиально == вот если бы женщины были бы все одинаковые (то есть
не важно - есть или нет, знаем или не знаем, ... ещ какую-то информацию про женщин),
то принц просто взял бы любую (решал задачу как не более, чем P-трудную),
НО рассматриваются практически всегда конкретные объекты с какой-то всегда ненулевой
основной и дополнтельной и контекстной и т.д. информацией ...

вот и "NP =? P"

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

имхо
Мудроглюков
Дата: 27.03.2018 08:07:19
Gennadiy Usov,

вот типа-встал на путь создания алгоритма на основе некоторых вращающихся и симметрично-отображающихся
подквадратов -> так и давай алгоритм

имхо, здесь не столько сочетания полезны, сколько перестановки,
а в теории щаз
выделяют ЧЕТЫРЕ класса алгоритмов:
- на основе лексикографического упорядочение
- на сонове векторов инверсий
- на сонове транспозиции смежных элементов
- на основе вложенных циклов
ЗЫ и для разных задач - разные типы по-разному пригодны оказываются с кучей деталей, в связи с конкретикой задач,
где перестановки "зашиваются" в алгоритм
ый давай 5-ый тип, если можешь! :^)