Алгоритм нахождения 1000 ферзей на шахматной доске

[TheGodfather]

Алгоритмическая сложность, О-большое? Не, не слышали?

[AlexSchur]

Здравствуйте.
Извините не понял)

[TheGodfather]

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

А время должно лишь дополнять эту картинку, но никак не служить основой сравнения.

[AlexSchur]

Понял, спасибо)

[drai3]

Есть довольно простой и более быстрый способ решения этой задач — анализировать левые и правые диагонали поля по количеству ферзей на них.

1. Расставить сразу всех ферзей по 1 на ряд, стараясь учитывать свободные диагонали. Если нет возможности ставить на свободную диагональ, то ставить на как можно менее занятой.
2. Последовательно переставлять ряды с занятых диагоналей, пока не будет найдено решение, при котором на всех диагоналях поля находится только один ферзь.

С данным алгоритмом мой код на js расставляет поле 1000х1000 за 300мс на i7-8700. Вот тут есть более подробное описание и примерный код алгоритма:

https://www.geeksforgeeks.org/n-queen-problem-using-branch-and-bound/

[AlexSchur]

Здравствуйте.
Попробовал код(java) который вы скинули и он не работает(выдаёт ошибку в

slashCode[r] = r + c;

и следующей строке)
Нет ли рабочего скрипта чтобы проверить решение?
Заранее спасибо)

[drai3]

Вот моё немного кривое, но работающее решение на js:
https://gist.github.com/EugeneDraitsev/3d19c6ba3ed5770492128e393514047c

Это решение к https://www.codewars.com/kata/5985ea20695be6079e000003/train/javascript/5fa6dea279a15500171a2920 этой кате, поэтому там присутствует один ферзь с заданным начальным положением (2й аргумент в функции solveNQueens)

[AlexSchur]

Спасибо.
Рабочее и быстрое решение)

[qpwoei]

эта задача решается за микросекунды, хотя если оптимизировать, то за сотни наносекунд.

[qpwoei]

1. расставить всех верзей по диагонали — массив [1,2,4,8,16,32,64,128], где позиция единички в числе — номер строки
2. Перебор комбинайций делать перестановками, всего 8! = 40320 комбинаций
3. горизонтальные и вертикальные проверки не нужны, только диагональные проверки, которые можно проверять через логические операции в двоичной системев которых проверка диагоналей для одного верзя всегда будет O(7)
4. Если голову поднапрячь можно довести до O(8!*/4), т.к. каждая уникальная комбинация повторяется 3 раза если доску поворачивать.

[jin_x]

Почему у вас везде функция возвращает false (кроме «Что вернул метод» -> true -> «Вернуть true»)? Полагаю, в правых нижних эллипсах должно быть «Вернуть true» (в обоих схемах).

[AlexSchur]

Здравствуйте, спасибо за вопрос)).
В правые нижние выходы мы попадаем только если мы проверили все клетки этого ряда(то есть дошли до конца) и если к этому моменту мы не нашли ничего то это означает что проверка провалилась и надо вернуться на шаг назад к предыдущему ряду.
То что у нас только один true это так и должно быть так как мы полностью полагаемся на проверку метода который вызывает сам себя и если он вернул true то значит что во время N-го вызова дошёл до конца.

[jin_x]

А где она возвращает true? Я не вижу ни одного такого места в блок-схемах, кроме того места, где она возвращает true после того, как получила true от вызова самой себя (а поскольку во всех остальных местах она возвращает false, то такое событие наступить не может).

У вас функция получается что-то вроде такого (если выкинуть все места с расчётами):

bool some(int x)
{
  if (some(x)) { return true; }
  return false;
}

Такая функция никогда не завершится и не вернёт true :)