Решаем задачу о 8ми ферзях на языке скала, функциональное программирование

В данном видео мы решаем очень популярную задачу о 8ми ферзях при помощи функционального программирования на языке скала
#программирование #scala #фп #функциональное_программирование #алгоритмы #шахматы

[@a.khakimov]

Хорошо, что подписался на канал

[@Khashimova_wellness]

Невероятно! Мой мозг порой взрывается от того что программирование может решить. Отличное видео, чувствую как автор/спикер улучшает свои навыки в блогерстве. Удачи!

[@TGrod]

Недавно наткнулся на этот ЗАМЕЧАТЕЛЬНЕЙШИЙ канал и мне дико нравятся ролики! Очень интересно смотреть. Решил ради интереса попробовать реализовать код из урока, но на c++, и, вроде, получилось. Надо будет так сделать с каждым уроком)

[@wolf_code]

Это круто! Если что кидайте код потом в комментариях (как бывший плюсист буду рад взглянуть)

[@TGrod]

@@wolf_code (я не совсем понимаю, но похоже мой комент удаляет Ютуб, так как в нём есть ссылка на код (я не хотел его сюда вставлять из-за объёма). Уже раза 3 отправил или 4)

[@wolf_code]

@@TGrod да - к сожалению ютуб не любит чужие ссылки, можно скинуть ссылку в наш телеграм чатик t.me/wolfcode0

[@0rkhan.d]

Блиин, очень крутое решение, но так как я не особо шарю, но очень влиться, я долго пытался понять алгоритм

[@user-mr1ii2wn2w]

Как всегда топ) Двигаешь меня и мой лит код вперёд)

[@denisluke7191]

Спасибо за видео. Есть вопрос к функции. Почему ты используешь case, если и так внутри только default (_)? Не проще написать if(условие первого кейса) первый кейс else второй кейс?

[@wolf_code]

Спасибо за коммент! По поводу использования паттерн матчинга вместо ифки - тут чисто субъективщина, мне хотелось говорить о кейсах и писать тоже case Конечно можно и ифку заюзать без проблем

[@user-kj7fo3bd9y]

сейчас сижу и пытаюсь реализовать данное решение на плюсах. Очень нужное видео для понятия алгоритма решения. Если будет возможность, можно ли будет записать решение на С++? Думаю не будет лишним) Удачи во всем)))))

[@wolf_code]

Спасибо за коммент Да можно попробовать на плюсах - тряхнуть стариной - почему бы нет)) Постараюсь

[@user-kj7fo3bd9y]

@@wolf_code можно ли будет реализовать это при помощи классов и наследования?

[@wolf_code]

тут по сути классы нужны чисто чтобы понятие Queen (ферзь) определить дальше уже надо чисто написать функцию решения

[@user-kj7fo3bd9y]

@@wolf_code у меня по заданию наследование классов просто и хотелось бы глянуть как это можно реализовать в таком виде. Но не могу не согласиться с Вашими словами

[@TGrod]

@@user-kj7fo3bd9y Ну наследование, я бы сказал, не нужно

[@tym32167]

Раз рассказываете о алгоритме, почему бы не рассказать про его время работы в том числе? (O(n)) Ну и раз речь о рекурсивном алгоритме, какие у него минусы и есть ли смысл задачу решать итеративным алгоритмом? Ну или хотя бы какие оптимизации можно применить и есть ли в этом смысл? (Например, если не рассматривать столбцы, где стоят уже ферзи, то можно ускорить алгоритм до 2 раз). Ну или решить задачу для не-квадратной доски, просто прямоугольной? Также упомянуть, что задача именно для расстановки ферзей, для расстановки других фигур будет уже другой алгоритм. Просто идеи накидываю, если вам интерсно это все читать :)

[@wolf_code]

Спасибо за предложения Артём! Согласен, многие вещи я опустил, дело в том что длинные видео люди менее охотно смотрят. Я не хотел превращать видео в нудную лекцию, поэтому оставил лишь самое интересное) Если Вы имели ввиду О(n) что это время работы, то это не совсем верно, у алгоритма поиска с возвратом экспоненциальная сложность для задачи определения всех расстановок. По поводу оптимизаций, при экспоненциальной сложности решения, ускорение его в два раза не даст сильного эффекта. При задаче расстановки других фигур алгоритм будет такой же, т к поиск с возвратом это универсальный подход, надо будет лишь переопределитб функции выбора кандидата и атаки

[@tym32167]

@@wolf_code я просто накинул идей :) У меня у самого неплохой опыт с алгоритмами уже есть. Да, O(n) я написал только, чтобы обозначить о чем речь, в ваш алгоритм явно нелинейный и не может быть линейным. Оптимизации не дадут эффекта при расчете O(n), но дадут на практике при измерении производительности. Ну и про алгоритм для ферзей - я это и имел ввиду, что все, что касается идеи рекурсивного поиска останется, все, что касается выбора кандидата-клетки изменится. Вы уже не сможете просто пропустить строчку на доске, вам придется рассматривать всю доску с начала до конца каждый раз либо добавлять какую то эвристику типа "ячеек, которые ещё не под ударом". Ну и я, конечно, не ради спора пришел, просто увидел видео, подумал можно ещё идей накидать автору, вдруг чего полезное скажу :)

[@wolf_code]

@@tym32167 спор тоже хорошо)) Идеи отличные! Тоже размышлял о том чтобы реализовать универсальный алгоритм для любых видов фигур) Кстати вроде доказали что задача подсчета расстановок N ферзей NP полная, поэтому как узнал - решил что игра не стоит свеч))

[@tym32167]

@@wolf_code ну, задача, что вы решили в видео, очень похожа на расстановку N ферзей (в некотором смысле к ней сводится, с допущениями), да и решили вы её по сути также, перебором, и сложность такая же - полиномиальная. Алгоритм для любых видов фигур придумать очень просто, но он будет оочень медленный (по сути тоже полиномиальный, но больше фигур - больше вариантов, больше разных фигур - больше вариантов * сочетания (или размещения, не помню)). Но я согласен, это можно чисто из эксперимента закодить, но практической пользы в такой задаче нет, её и на собесе навряд ли спросят в таком виде, так как NP полная требует перебора, а на собесах обычно задачки, которые решаются быстрее, чем за перебор.

[@wolf_code]

@@tym32167 ах если бы сложность была полиномиальная, я бы сразу пошел за призом в миллион долларов, в моем решении сложность экспоненциальная, допустип для N=28, мой алгоритм будет работать больше 1000 лет (Еще раз подчеркну, что мы решаем задачу нахождения всех расстановок) blogs.cs.st-andrews.ac.uk/csblog/2017/08/31/n-queens-completion-is-np-complete/

[@inf10k]

За какое время вычисляется для доски 8х8?

[@wolf_code]

Точно не измерял - но точно меньше секунды

[@user-xb7uu2ne8i]

12×12 на питоне за 15 минут

[@TGrod]

@@user-xb7uu2ne8i Неужели так много... Просто я на плюсы переписал, как смог, и получилось чуть менее, чем 2.7 секунды (если не выводить доски, так как это слишком долго выйдет) Кому интересно - 14200 вариантов расстановки (если правильно написал программу) P.S. Очень удивился, когда проверил, за сколько вычисляется 8x8. Менее 0.004 секунды... Это ж моментально!

[@ilias3624]

А слабо решить эту задачу для поля 2х2 или 3х3 ?))

[@wolf_code]

2х2 нет решений 3х3 тоже

[@georgeyarish3439]

а где здесь backtracking? те возврат

[@wolf_code]

Когда у нас не остается кандидатов после фильтрации (откинули всех), дальше рекурсивный вызов не происходит следовально текущая функция завершается - происходит возврат

[@georgeyarish3439]

@@wolf_code понял, спасибо

[@KrassRome]

Бросается в глаза симметрия расположения.

[@wolf_code]

ага - с помощью нее можно ускорить алгоритм