На доске NxN расставить N ферзей так, чтобы они не били друг друга.
N- большое, времени мало.

Здравствуйте, Трурль, Вы писали:

Т>На доске NxN расставить N ферзей так, чтобы они не били друг друга.
Т>N- большое, времени мало.

За исключением случаев, когда это не возможно? — 2х2, 3х3..

Здравствуйте, ZevS, Вы писали:

ZS>За исключением случаев, когда это не возможно? — 2х2, 3х3..
Естественно. Вряд ли 2 и 3 можно считать большими

Здравствуйте, Трурль, Вы писали:

Т>Здравствуйте, ZevS, Вы писали:

ZS>>За исключением случаев, когда это не возможно? — 2х2, 3х3..
Т>Естественно. Вряд ли 2 и 3 можно считать большими

если это миллиарды долларов, то можно))

Здравствуйте, Трурль, Вы писали:

Т>На доске NxN расставить N ферзей так, чтобы они не били друг друга.
Т>N- большое, времени мало.

Похоже, что ничего, кроме перебора, в общем случае применить нельзя.

Есть решение для N=4

-*--
---*
*---
--*-

Его можно продолжить для случая N=16=4^2.
Разобьём доску 16x16 на 4 "больших клетки" (размера 4x4). Будем расставлять ферзей в "больших клетках", соответствующих тем, что были ранее (в решении для N=4).
Каждая "большая клетка" — это клетка 4x4. Внутри неё расставим ферзей так же, как и в случае для N=4.
1) Ферзи, стоящие в одной "большой клетке", не бьют друг друга. Очевидно.
2) Ферзи, стоящие в разных "больших клетках", тоже не бьют друг друга. Покажем это.
Пусть у нас есть "большие ферзи" — ферзи, размера 4x4. Если мы их поставим в наши "большие клетки", то они не будут бить друг друга (это просто задача для N=4). Вернёмся к "маленьким" ферзям. Каждый из них бьёт ещё меньше, чем "большой ферзь", в состав которого он входит. Поэтому ни один из маленьких ферзей не будет стоять на линии, которую бьёт какой-либо другой ферзь. Всё.

Это решение продолжается аналогично на случай N=64, 256, ..., 4^k, ...

Аналогично, если мы построим решение для любого N=p, его можно будет продолжить для любого N=p^k.

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

Имеет смысл располагать только по одному ферзю в столбце, т. е. искать решение в виде f(i), i = 1..N, 1<=f<=N.

Создадим матрицу a[i, j], значением элемента которой будет количество ферзей, под ударом которых находится поле (i, j). Тогда при выборе строки для i-го столбца мы будем выбирать только ту, для которой a[i, j] = 0. Инкрементируем значения a[i,j] "ферзевым паттерном". Если на каком-то шаге в текущем столбце нечего выбрать -- приехали, отматываем алгоритм назад, декрементируем матрицу Есть гипотеза, что в связи с быстрым "забиванием" матрицы ненулевыми элементами, такой алгоритм сойдется за малое (не экспоненциально зависящее от N) время.

Здравствуйте, Пономарёв Иван, Вы писали:

ПИ>Создадим матрицу a[i, j], значением элемента которой будет количество ферзей, под ударом которых находится поле (i, j). Тогда при выборе строки для i-го столбца мы будем выбирать только ту, для которой a[i, j] = 0. Инкрементируем значения a[i,j] "ферзевым паттерном". Если на каком-то шаге в текущем столбце нечего выбрать -- приехали, отматываем алгоритм назад, декрементируем матрицу Есть гипотеза, что в связи с быстрым "забиванием" матрицы ненулевыми элементами, такой алгоритм сойдется за малое (не экспоненциально зависящее от N) время.

Не нужна двумерная матрица. Очевидно, что все ферзи будут стоять на различных строках или столбцах (как приятнее смотреть). Работа с двумерной матрицей технически усложнит решение.
А если еще немного подумать, можно понять, что тут не перебор, а перестановки все по тем же причинам. А перестановки N из N — это очень быстро.

Здравствуйте, Пономарёв Иван, Вы писали:

ПИ>Имеет смысл располагать только по одному ферзю в столбце, т. е. искать решение в виде f(i), i = 1..N, 1<=f<=N.

ПИ>Создадим матрицу a[i, j], значением элемента которой будет количество ферзей, под ударом которых находится поле (i, j). Тогда при выборе строки для i-го столбца мы будем выбирать только ту, для которой a[i, j] = 0. Инкрементируем значения a[i,j] "ферзевым паттерном". Если на каком-то шаге в текущем столбце нечего выбрать -- приехали, отматываем алгоритм назад, декрементируем матрицу Есть гипотеза, что в связи с быстрым "забиванием" матрицы ненулевыми элементами, такой алгоритм сойдется за малое (не экспоненциально зависящее от N) время.

Блин, невнимательно прочитал сообщение. Мое сообщение про двумерную матрицу прошу считать недействительным.
И бэктрекинг хорошо подходит в данном случае.

Здравствуйте, Laurel, Вы писали:

L>А если еще немного подумать, можно понять, что тут не перебор, а перестановки все по тем же причинам. А перестановки N из N — это очень быстро.

N! — это не так уж и быстро.

Т>>Естественно. Вряд ли 2 и 3 можно считать большими

ZS>если это миллиарды долларов, то можно))

А если миллионы — то, конечно, нельзя...

Здравствуйте, Пономарёв Иван, Вы писали:

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

То, что Вы предожили называется forward checking. Это действительно сильно сокращает перебор, но время остается экспоненциальным.

Здравствуйте, Eugene Sh, Вы писали:

L>>А если еще немного подумать, можно понять, что тут не перебор, а перестановки все по тем же причинам. А перестановки N из N — это очень быстро.

ES>N! — это не так уж и быстро.

По сравнению с N^N — быстро.
Я уже сказал, что читал поперек

Здравствуйте, Eugene Sh, Вы писали:

ES>Аналогично, если мы построим решение для любого N=p, его можно будет продолжить для любого N=p^k.

И более того, если у нас есть решение для {p,q,...r}, то мы можем построить решения для N=(p^k)*(q^l)*...*(r^m)

Здравствуйте, Трурль, Вы писали:

Т>То, что Вы предожили называется forward checking. Это действительно сильно сокращает перебор, но время остается экспоненциальным.

Факториал круче экспоненты, N! ~ (N/e)^N

Здравствуйте, Кодт, Вы писали:

К>И более того, если у нас есть решение для {p,q,...r}, то мы можем построить решения для N=(p^k)*(q^l)*...*(r^m)

Точно!
Таким образом, осталось решить задачу для простых N. Т.к. для N=2 и N=3 задача не решается, то её надо решить ещё для некоторых N: 4, 8, 9, 27, 6, 2*p (для простых p), 3*p (для простых p).

Тогда алгоритм такой. Раскладываем N на простые множители. Если 2 и 3 не входят в это разложение, то задача решена.
Если 2 входит в степени, большей чем 1, то при помощи нескольких 4-к и, может быть, одной 8-ки "съедаем" этот множитель.
Аналогично для 3.
Если 2 входит в степени 1, то объединяем её с каким-нибудь простым множителем.
То же самое для 3-ки.
Если и 2, и 3 входят в степени 1, то им может не хватить простых множителей для объединения (каждому надо по одному множителю), то объединим их между собой (решение для N=6).
Всё.

Таким образом, если N допускает разложение хотя бы на несколько множителей, скорость решения значительно увеличивается.
Для больших простых N, возможно, тоже есть быстрое решение. Надо подумать, можно ли использовать простоту N.

Здравствуйте, Кодт, Вы писали:

К>Факториал круче экспоненты, N! ~ (N/e)^N
Да один черт EXPTYME.

Здравствуйте, Трурль, Вы писали:

Т>На доске NxN расставить N ферзей так, чтобы они не били друг друга.
Т>N- большое, времени мало.

Довольно простенький алгоритм. Сперва алгоритм для четных N.
Начальная позиция (1, 0). с шагом по абциссе 2, а по ординате 1 выставляешь ферзей. Дойдя до конца доски по абциссе остается еще половина по ордиате. Осуществляется переход в точку (0, N/2) и с тем же шагом ставится остальные ферзи. Это все можно сделать и в цикле с интервалом от 0 до N/2

Далее алгоритм, если N — нечетно
Пусть доска — это матрица. Делается минор, без самых крайних ряда и столбца. На пересечении этих строки и столбца ставиться ферзь. В миноре по алгоритму, где N — четно расставляются ферзи.

P.S. нумерации строк и столбцов начинал с 0

Здравствуйте, dony, Вы писали:

D>Довольно простенький алгоритм. Сперва алгоритм для четных N.
D>Начальная позиция (1, 0). с шагом по абциссе 2, а по ординате 1 выставляешь ферзей. Дойдя до конца доски по абциссе остается еще половина по ордиате. Осуществляется переход в точку (0, N/2) и с тем же шагом ставится остальные ферзи. Это все можно сделать и в цикле с интервалом от 0 до N/2

Попробуем:

  0 1 2 3 4 5 6 7
0 - Q \ | / | - /
1 / | - Q - | / |
2 - | / | \ Q - |
3 - / - | / \ - Q
4 X | · / · | \ |
5 · | / | · / · \
6 · / · | / | · |
7 / | · / · | · |

Облом!

Здравствуйте, Кодт, Вы писали:

К>Облом!
Угу. Но идея делить на четные и нечетные весьма здравая.

Здравствуйте, Кодт, Вы писали:
К>Попробуем:
К>Облом!

Да не такой уж и облом. Учитывая, что приведенный алгоритм не работает только для N=2^(2k+1) и N=2^(2k+1)+1, то это не плохой результат. Код не писал, для более точной оценки чисел, для которых алгоритм не пригоден. Увидел закономерность при N=4,5,6,7,10,11 и предложил , ну перепрыгнул 8 и 9 , каюсь.
Для N=2^(2k+1), вроде присутствует закономерность расположения ферзей на доске. Проверил для N=8,N=32. Расположение идет по тому же алгоритму, но добавиться еще один пункт: для второй диагонали небольшое преобразование. Каждую пару ферзей зеркально отобразить относитель оси абцисс это пары.

  0 1 2 3 4 5 6 7
0 - Q \ | / | - /
1 / | - Q - | / |
2 - | / | \ Q - |
3 - / - | / \ - Q
4 / | Q / - | \ |
5 Q | / | - / - \
6 - / - | / | Q |
7 / | - / Q | - |

Нашел расположение ферзей на доске при N=9, не проверял для других N=2^(2k+1)+1.

  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
0   |   |   |   |   |   |   | + |
1   |   |   |   |   | + |   |   |
2 + |   |   |   |   |   |   |   |
3   |   | + |   |   |   |   |   |                        
4   |   |   |   | + |   |   |   |
5   |   |   |   |   |   | + |   |
6   |   |   |   |   |   |   |   | +
7   |   |   | + |   |   |   |   |
8   | + |   |   |   |   |   |   |

В любых "правильных" комбинациях расположений ферзей присутствует закономерность: пара, рядом стоящих ферзей, находят в пределе одного хода коня

<offtop>А вообщем рассположение ферзей наглядно видно в табличном редакторе, особенно при использовании возможностей заливки ячеек </offtop>