Задумывались ли вы, где можно применить навык решения задачек а-ля литкод изи? Я встречаюсь с ними частенько, главное просто присмотреться.
Например, на Linked.in недавно ввели "игры". Я как-то глянул на них на послеобеденном кофе.
"Ферзи" (queens)
Задача проста: расставить ферзей на доске так, чтоб в каждой строке, столбце и связной цветовой области было ровно по одному ферзю, и ферзи не должны касаться друг друга.
Например, ферзи за 28 октября:
Я решил её раз. Решил другой день. На третий стало понятно, что задачка сама по себе ничего не даёт. Но! Можно развлечься созданием её решателя!
Всё, что нужно, чтобы решать такие задачи -- минимальное знание javascript на уровне синтаксиса, знание, что страница -- это дерево элементов, у которых есть классы, айдишники, и прочие параметры.
И умение формализовать свои мысли: то есть умение решать "литкод изи".
Получение данных
Чтобы решить задачу, надо её сначала получить. Открываем по Ctrl+Shift+J консоль в хроме, наводимся, разворачиваем дерево элементов:
Видим, что ячейки перечислены в форме div элементов с классом queens-cell, и вторым классом cell-color-X, где X -- цвет ячейки. Проверяем, находим их все через document.getElementByClassName('queens-cell'):
Превратим все ячейки в просто номера цветов:
field=Array.from(document.getElementsByClassName('queens-cell')).map((x)=>x.classList[1].split('-')[2]|0);
[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]Литкодим
Отлично, задача сведена к следующей. Дан одномерный массив размера N^2 элементов, где каждый элемент -- номер цвета. Выдать массив размера N^2 элементов, где 1 стоит в позициях ферзей. В каждой строке, столбце и области цвета должен быть ровно один ферзь. Ферзи не должны касаться друг друга.
Решаем буквально в лоб:
Для каждой позиции в первой строке пробуем поставить ферзя.
Если ферзя поставили -- переходим к размещению во второй строке.
Если не смогли найти решение -- убираем ферзя и переходим к следующей ячейке в строке.
Если дошли до конца строки -- возвращаем ошибку.
Получается рекурсивное жадное решение в лоб:
var solve=(r)=>{
for(var c=0;c<N;c++) {
if(ok(r,c)) {
set(r,c,true);
if(r==N-1) return true;
if(solve(r+1)) return true;
set(r,c,false);
}
}
return false;
};
solve(0);Всё, что осталось, это дополнить требуемыми проверками:
Вычислим размер поля
var N=Math.sqrt(field.length)"В каждой строке": заводим массивчик "в строке есть ферзь":
var rw=Array(N)."В каждом столбце":
var cl=Array(N)."В каждом цвете":
var cr=Array(N)."Не должны касаться": так, тут чуток сложнее, надо проверить, что вокруг заданной точки нет ферзя.
var sol=Array(N*N); // Массив с положением ферзей
var id=(r,c)=>r*N+c; // для удобства, конвертер пары row/col в индекс
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)]);Теперь мы можем проверить, можно ли поставить ферзя в клетку r,c, то есть проверки на "нет в ряду, нет в столбце, нет в поле цвета и нет соседа":
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;
};Проверяем:
Сложность решения? Для каждой строки до N вариантов, так что O(N^2). (см в комментарии)
Для раз-в-день -- нет смысла даже думать над решением лучше!
Выводим решение
Осталось вывести решение на экран:
fld = Array.from(document.getElementsByClassName("queens-cell"));
for(var i=0;i<fld.length;i++) {
if (sol[i]) { fld[i].style = 'border: 3px solid red'; }
}
Всё, прокликиваем квадратики и задача решена. Да, можно еще найти кто и как слушает клики, как вызвать их программно (вместо подсветки клетки)... Оставлю это как упражнение для читателя :)
Сливаем всё вместе
Заворачиваем скрипт в готовый для копипасты:
Полный скрипт
((fld)=>{
var field = fld.map((x)=>x.classList[1].split('-')[2]|0);
var N=Math.sqrt(field.length);
var rw=Array(N);
var cl=Array(N);
var cr=Array(N);
var sol=Array(N*N);
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)=>{
for(var c=0;c<N;c++) {
if(ok(r,c)) {
set(r,c,true);
if(r==N-1) return true;
if(solve(r+1)) return true;
set(r,c,false);
}
}
return false;
};
solve(0);
for(var i=0;i<fld.length;i++) {
if (sol[i]) { fld[i].style = 'border: 3px solid red'; }
}
})(Array.from(document.getElementsByClassName("queens-cell")))Для удобства, засунем скрипт в любой минификатор:
Минискрипт
(_=>{var e=_.map(_=>0|_.classList[1].split("-")[2]),r=Math.sqrt(e.length),$=Array(r),s=Array(r),l=Array(r),t=Array(r*r),a=(_,e)=>_*r+e,n=(_,e)=>_>0&&e>0&&t[a(_-1,e-1)]||_>0&&t[a(_-1,e)]||_>0&&t[a(_-1,e+1)]||e>0&&t[a(_,e-1)]||t[a(_,e)]||t[a(_,e+1)]||e>0&&t[a(_+1,e-1)]||t[a(_+1,e)]||t[a(_+1,e+1)],f=(_,r)=>!$[_]&&!s[r]&&!l[e[a(_,r)]]&&!n(_,r),i=(_,r,n)=>{t[a(_,r)]=n,$[_]=n,s[r]=n,l[e[a(_,r)]]=n},o=_=>{for(var e=0;e<r;e++)if(f(_,e)){if(i(_,e,!0),_==r-1||o(_+1))return!0;i(_,e,!1)}return!1};o(0);for(var m=0;m<_.length;m++)t[m]&&(_[m].style="border: 3px solid red")})(Array.from(document.getElementsByClassName("queens-cell")));Теперь откроем вкладку закладок (Ctrl+Shift+B), правой кнопкой => add page => название "Queens Solver", в поле URL пишем javascript: и затем вставляем минимизированный код:
И всё, можем решать в один клик:
p.s.: Если не смогли сделать решатель для Tango, возьмите тут.
p.p.s.:
Кто заметил, что "в ряду" проверка излишняя? :)
Комментарии (18)
killyself
30.10.2024 08:25Неправильно делается вывод о сложности алгоритма. В худшем случае для первой строки придется N раз перебирать вторую строку, в которой в худшем случае N раз перебирать третью и т.д..
Итого получаем N^M где M число строк, ну или N^N для квадратной доски.
Эта верхняя оценка сильно сокращается проверками горизонталей, вертикалей и диагоналей (до N!). Дальше сокращается проверками цветов.
И вот на этапе проверки цветов (при условии что цветов тоже N), сложность должна радикально сокращаться, возможно до полинома, но посчитать конкретно мне способностей уже не хватает. Возможно следующий комментатор сможет раскрыть мою мысль.
Можно ещё отметить, что для областей цвета из 1 ячейки, в случае когда цветов столько сколько ферзей, известно что во всех таких ячейках будет стоять ферзь (на верхнюю оценку не влияет, но на практике такая оптимизация могла бы сильно ускорить решение)
datacompboy Автор
30.10.2024 08:25Хм. Чет я и правда затупил. У нас не дерево, а матрица.
Разверну чуть больше.
Рекурсия используется в качестве программного "цикла циклов", соответственно, эквивалентная схема:
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.killyself
30.10.2024 08:25С проверкой цветов нюанс в том, что в худшем случае она вообще не влияет, а в лучшем упрощает решение до полинома (количество валидных расстановок может упасть пропорционально ~N-1!), но вот что там в среднем - вопрос хороший. Но я согласен - на верхнюю оценку действительно не влияет и она будет в районе N!
datacompboy Автор
30.10.2024 08:25Ну нас интересует не количество валидных расстановок, а поиск какого-либо решения. Мы же не ищем количество решений, ни пытаемся найти какое-то особое решение -- нам устроит любое.
С этой точки зрения, "каждая строка -- отдельный цвет" это лучший, а не худший случай, мы найдём решение практически с первой попытки.
p.s.: ради интересу добавил вывод числа найденных решений в скрипт; сегодня только одно решение. в задаче от 28го (та что в статье) тоже только одно решение. интересно...
Sanechka_nocopy
30.10.2024 08:25Я не поняла Вашу оценку, поэтому давайте зайду с примера. Пусть есть всего одна область - первая клетка последней строки.
datacompboy Автор
30.10.2024 08:25У нас в задаче N строк, N столбцов и N разных цветов. То есть если есть только одна область -- задача представляет собой одну единственную клетку 1*1
Sanechka_nocopy
30.10.2024 08:25А, пардон, не увидела, что в одном из предыдущих комментариев все-таки сошлись на n!. Давайте немного модифицирую пример, чисто чтобы был: все остальные области это просто строки. То есть подходит любая перестановка, где последний элемент переходит в первый. Но чтобы дойти до такой, надо перебрать как минимум (n-2)! тех, где первый остается на месте, и ещё некоторые.
datacompboy Автор
30.10.2024 08:25Не понимаю примера. Можно в цифрах?...
[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])Sanechka_nocopy
30.10.2024 08:25Заранее прошу прощения, если опять в какое-то условие не попала. С учётом запрета соседей там все-таки не (n-2)!, но что-то похожее.
00000 11111 22222 33333 43333datacompboy Автор
30.10.2024 08:25У каждой клетки есть цвет, и число цветов равно числу столбцов и рядов. Цвета еще и связные области, но для имеющегося решения это не важно.
datacompboy Автор
30.10.2024 08:25Там откусывается не сверху, а снизу от факториала несколько строк. С практической точки зрения -- это всё мелкая константа, которой можно пренебречь и считать что оно факториальное.
Total count of solutions: 2 checked: 100
При такой задаче, для поиска всех надо перебрать 100 вариантов. От полного факториала (5!=120) недалеко ушли :)
Первое решение найдено на 56м варианте, второе -- на 81м.
killyself
30.10.2024 08:25Уменьшение числа валидных расстановок означает, что у нас реже будет возможность поставить ферзя и зайти в рекурсию (что уменьшает и глубину рекурсии как следствие).
При этом если мы имеем N цветов/ферзей и допустим что клеток каждого цвета поровну, то получим (для N = 8) что из исходных 64! / (56!*8!) расстановок ферзей только 8^8 (расстановок по 1 ферзю внутри N областей по N ячеек) будут подходить под условие цвета (без прочих условий). То есть уменьшение числа расстановок схоже с эффектом от проверки (только) горизонталей.
Неравномерная раскраска же уменьшает количество расстановок ещё больше. Крайний случай = если возьмем 7 областей по 1 ячейке и одну область на 57, то расстановок вообще останется 57 без прочих проверок.Поэтому я и предположил, что в среднем время поиска должно падать.
В случае когда мы ищем только первое решение из многих конечно получается что поиск может наоборот удлиняться (как и от остальных проверок), но в случае, когда решение всего одно (или их крайне мало относительно числа исходных перестановок) - нам нет большой разницы, ищем ли мы все решения или первое.
asavan
Не уверен, что сложность решения оценена правильно.
Мы ведь для каждой клетки рассматриваем случай когда мы ее берем и когда не берем
получаем (2^N) как минимум для первой строки.
Кажется если решения не будет, то перебирать будем 2^82^7262^52^42^3*2 = 3221225472 варианта
datacompboy Автор
Мы не проверяем каждую клетку с каждой клеткой.
Переход на следующую строку только если успешно поставили ферзя, поэтому сложность проверки первой строки - просто число ячеек.
Тот факт, что мы для каждой ячейки куда смогли ставим а потом убираем (если не прокатило) ферзя - это просто накладные расходы, спрятаны в не показанной константе при О-большом