Комментарии 20
Не уверен, что сложность решения оценена правильно.
Мы ведь для каждой клетки рассматриваем случай когда мы ее берем и когда не берем
получаем (2^N) как минимум для первой строки.
Кажется если решения не будет, то перебирать будем 2^82^7262^52^42^3*2 = 3221225472 варианта
Мы не проверяем каждую клетку с каждой клеткой.
Переход на следующую строку только если успешно поставили ферзя, поэтому сложность проверки первой строки - просто число ячеек.
Тот факт, что мы для каждой ячейки куда смогли ставим а потом убираем (если не прокатило) ферзя - это просто накладные расходы, спрятаны в не показанной константе при О-большом
Неправильно делается вывод о сложности алгоритма. В худшем случае для первой строки придется N раз перебирать вторую строку, в которой в худшем случае N раз перебирать третью и т.д..
Итого получаем N^M где M число строк, ну или N^N для квадратной доски.
Эта верхняя оценка сильно сокращается проверками горизонталей, вертикалей и диагоналей (до N!). Дальше сокращается проверками цветов.
И вот на этапе проверки цветов (при условии что цветов тоже N), сложность должна радикально сокращаться, возможно до полинома, но посчитать конкретно мне способностей уже не хватает. Возможно следующий комментатор сможет раскрыть мою мысль.
Можно ещё отметить, что для областей цвета из 1 ячейки, в случае когда цветов столько сколько ферзей, известно что во всех таких ячейках будет стоять ферзь (на верхнюю оценку не влияет, но на практике такая оптимизация могла бы сильно ускорить решение)
Хм. Чет я и правда затупил. У нас не дерево, а матрица.
Разверну чуть больше.
Рекурсия используется в качестве программного "цикла циклов", соответственно, эквивалентная схема:
for( i1 in range(N)):
for( i2 in range(N)):
for( i3 in range(N)):
..
for( iN in range(N)):
то есть таки да, это цикл на N^N итераций.
Проверки вертикалей (проверки горизонталей всегда true так как циклы работают каждый на своей выделенной горизонтали) превращают в факториал, так как мы заменяем вызов следующих циклов на константную проверку массива.
Проверок диагоналей у нас нет. Проверка соседей меняет выкидывание одной клетки в строке на выкидывание почти трёх:
0 1 0 0 => 0 1 0 0 => 0 1 0 0
? ? ? ? ? x ? ? x x x 0
Но это только в прямо последующей строке. Фактически, снижает с полного факториала до факториала N-2 что не влияет.
Проверка цветовой области не сильно влияет на оценку, так как в худшем случае у нас каждая строка -- отдельный цвет, и не влияет на все другие строки.
Таким образом, фактическая сложность получается факториал, а не квадрат.
... что только подтверждает, что решение "в лоб" обычно далеко от эффективности;
... что не меняет того факта, что решатель справляется за практически невидимое для глаза время, так как решение точно существует всегда; задача предполагает решение человеком; и максимальный размер я пока за ~150 дней видел только 15*15.
С проверкой цветов нюанс в том, что в худшем случае она вообще не влияет, а в лучшем упрощает решение до полинома (количество валидных расстановок может упасть пропорционально ~N-1!), но вот что там в среднем - вопрос хороший. Но я согласен - на верхнюю оценку действительно не влияет и она будет в районе N!
Ну нас интересует не количество валидных расстановок, а поиск какого-либо решения. Мы же не ищем количество решений, ни пытаемся найти какое-то особое решение -- нам устроит любое.
С этой точки зрения, "каждая строка -- отдельный цвет" это лучший, а не худший случай, мы найдём решение практически с первой попытки.
p.s.: ради интересу добавил вывод числа найденных решений в скрипт; сегодня только одно решение. в задаче от 28го (та что в статье) тоже только одно решение. интересно...
Я не поняла Вашу оценку, поэтому давайте зайду с примера. Пусть есть всего одна область - первая клетка последней строки.
У нас в задаче N строк, N столбцов и N разных цветов. То есть если есть только одна область -- задача представляет собой одну единственную клетку 1*1
А, пардон, не увидела, что в одном из предыдущих комментариев все-таки сошлись на n!. Давайте немного модифицирую пример, чисто чтобы был: все остальные области это просто строки. То есть подходит любая перестановка, где последний элемент переходит в первый. Но чтобы дойти до такой, надо перебрать как минимум (n-2)! тех, где первый остается на месте, и ещё некоторые.
Не понимаю примера. Можно в цифрах?...
[0,0,0,0,0
,1,1,1,1,1
,2,2,2,2,2
,3,3,3,3,3
,4,4,4,4,4]
вот это -- каждая строка свой цвет. Данная раскладка имеет 14 решений, но первое находится буквально сразу, как первая же возможная расстановка:
W....
..W..
....W
.W...
...W.
Hidden text
((field)=>{
var N=Math.sqrt(field.length);
var rw=Array(N);
var cl=Array(N);
var cr=Array(N);
var sol=Array(N*N);
var psol=()=>{var k=0;var s='';for(var i=0;i<N;++i){for(var j=0;j<N;++j,++k){s+=sol[k]?'W':'.';}s+='\n';}console.log(s)};
var id=(r,c)=>r*N+c;
var nei=(r,c)=>(r>0&&c>0&&sol[id(r-1,c-1)])||
(r>0&& sol[id(r-1,c)])||
(r>0&& sol[id(r-1,c+1)])||
( c>0&&sol[id(r ,c-1)])||
( sol[id(r ,c)])||
( sol[id(r ,c+1)])||
( c>0&&sol[id(r+1,c-1)])||
( sol[id(r+1,c)])||
( sol[id(r+1,c+1)]);
var ok=(r,c)=>!rw[r]&&!cl[c]&&!cr[field[id(r,c)]]&&!nei(r,c);
var set=(r,c,v)=>{
sol[id(r,c)]=v;
rw[r]=v;
cl[c]=v;
cr[field[id(r,c)]]=v;
};
var solve=(r)=>{
var sols = 0;
for(var c=0;c<N;c++) {
if(ok(r,c)) {
set(r,c,true);
if(r==N-1) { sols ++; psol(); }
else sols += solve(r+1);
set(r,c,false);
}
}
return sols;
};
console.log("Total count of solutions: ", solve(0));
})([0,0,0,0,0
,1,1,1,1,1
,2,2,2,2,2
,3,3,3,3,3
,4,4,4,4,4])
Заранее прошу прощения, если опять в какое-то условие не попала. С учётом запрета соседей там все-таки не (n-2)!, но что-то похожее.
00000
11111
22222
33333
43333
У каждой клетки есть цвет, и число цветов равно числу столбцов и рядов. Цвета еще и связные области, но для имеющегося решения это не важно.
Да, я перечитала статью и отредактировала).
Там откусывается не сверху, а снизу от факториала несколько строк. С практической точки зрения -- это всё мелкая константа, которой можно пренебречь и считать что оно факториальное.
Total count of solutions: 2 checked: 100
При такой задаче, для поиска всех надо перебрать 100 вариантов. От полного факториала (5!=120) недалеко ушли :)
Первое решение найдено на 56м варианте, второе -- на 81м.
Уменьшение числа валидных расстановок означает, что у нас реже будет возможность поставить ферзя и зайти в рекурсию (что уменьшает и глубину рекурсии как следствие).
При этом если мы имеем N цветов/ферзей и допустим что клеток каждого цвета поровну, то получим (для N = 8) что из исходных 64! / (56!*8!) расстановок ферзей только 8^8 (расстановок по 1 ферзю внутри N областей по N ячеек) будут подходить под условие цвета (без прочих условий). То есть уменьшение числа расстановок схоже с эффектом от проверки (только) горизонталей.
Неравномерная раскраска же уменьшает количество расстановок ещё больше. Крайний случай = если возьмем 7 областей по 1 ячейке и одну область на 57, то расстановок вообще останется 57 без прочих проверок.
Поэтому я и предположил, что в среднем время поиска должно падать.
В случае когда мы ищем только первое решение из многих конечно получается что поиск может наоборот удлиняться (как и от остальных проверок), но в случае, когда решение всего одно (или их крайне мало относительно числа исходных перестановок) - нам нет большой разницы, ищем ли мы все решения или первое.
Зачем это всё?
Для каждого цвета у нас только 
решений, причём, каждый последующий цвет полностью зависим от предыдущего условиями задачи - ни в строках, ни в столбцах не может находиться больше одной фигуры. То есть для каждого 
ячеек другого цвета будет всегда меньше начального значения.
Рассмотрим на примере из статьи
или
[0,0,0,0,1,1,1,0,
0,2,0,0,1,1,1,0,
3,3,3,0,1,1,1,0,
3,3,3,0,0,0,0,0,
3,3,3,0,0,0,4,4,
5,5,0,0,0,0,4,4,
5,5,0,6,6,0,7,0,
0,0,0,6,6,0,0,0]у нас получится такое распределение по цветам и по количеству занятых ячеек:
c(0) = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }
c(1) = { 1,1,1,1,1,1,1,1,1 }
c(2) = { 2 }
c(3) = { 3,3,3,3,3,3,3,3,3 }
c(4) = { 4,4,4,4 }
c(5) = { 5,5,5,5 }
c(6) = { 6,6,6,6 }
c(7) = { 7 }ну и после сортировки получаем
c(2) = { 2 }
c(7) = { 7 }
c(4) = { 4,4,4,4 }
c(5) = { 5,5,5,5 }
c(6) = { 6,6,6,6 }
c(1) = { 1,1,1,1,1,1,1,1,1 }
c(3) = { 3,3,3,3,3,3,3,3,3 }
c(0) = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }как мы видим два цвета представлены всего одной ячейкой и после исключения тех клеток где другие фигуры находиться не могут, у нас будет такая ситуация на поле
и по данным
c(4) = { 4 }
c(5) = { 5 }
c(6) = { 6,6 }
c(1) = { 1,1,1,1 }
c(3) = { 3,3,3,3 }
c(0) = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }как видно исключение ячеек дало нам еще две безальтернативные позиции
c(3) = { 3 }
c(6) = { 6,6 }
c(1) = { 1,1,1,1 }
c(0) = { 0,0,0,0,0,0 }и так далее, пока
c(1) = { 1 }Мы полностью решили задачу, но нужно понимать, что это частный случай, но сам принцип позволяет сильно сократить число ячеек, которые потребуется выбирать для решения, так как оно сразу исключает необходимость любых проверок.
То есть по сути эти исключения идут до вашего решения, тогда ваше решение или вообще не потребуется как с этой задачей или ему нужно будет проверять меньше данных.
Так же в какой-то момент в нижней части доски была такая ситуация
Я подсветил три ячейки. Дело в том, что ячейки жёлтого цвета находятся в одной линии и на 100% гарантируют что одна из фигур будет стоять там, но эта ситуация так же исключает свободную ячейку слева от них из рассмотрения - там точно не может быть ни одной фигуры.
Не уверен что проверка на такое даст что-то решающее, но всё же.
Совершенно верно! Оптимизация перебора -- мастхэв для ускорения решения с ростом размерности задачи. Это не меняет худший случай, зато сильно улучшает средний случай.
Но реализация интеллектуального перебора требует значитнельно больше времени, чем экономится. Сейчас типичное поле решается на 0.05-0.1 сек, практически равно дисперсии времени наведения на кнопку и нажатия на неё. Как быстро окупится 30 минут дополнительного кодинга и усложнение когда при сокращении этого времени даже в 10 раз?
В случае же, если этот код болтается в продакшене, при загрузке проца в полку -- уже интереснее расклад. До тех пор -- только как развлечение.
Литкод изи — это просто