Sudoku problem (Hard) | Solve problems with Leetcode

Ура! Начинаем год с хардовой задачи, которую вы так долго просили. В сегодняшнем ролике мы с вами разберем, как решить судоку с помощью алгоритма DFS (Depth-First-Search).
Будем идти по решению поэтапно - начнем с разбора судоку 4х4, а далее в наш алгоритм скормим судоку 9х9. И на десерт решим судоку 16х16. Уляля!
Приятного просмотра!
Код Решения Задачи: codepen.io/puzankov/pen/eYZyZ...
Задача про банкомат (Часть 2) - • Задача про банкомат. В...
Задача про лабиринт - • Решаем задачу с собесе...
Как всегда, Ваши лайки и решения ждем под видео!
И поделитесь видео с друзьями, если они еще не видели.
---
Если видео было для вас полезным, ставьте лайк и поделитесь им с друзьями.
Подписывайтесь на наш канал: bit.ly/fs-ytb
---
Присоединяйтесь к нам в соцсетях:
FB: / frontendscience
Instagram Сергея Пузанкова: / puzankovcom
Заходите на наш сайт: frontend-science.com/
Music by -
Blue Wednesday - 90s kid
Blue Wednesday - Murmuration
Blue Wednesday - Suede
#javascript #задачи #leetcode #itсобеседование

[@user-hq9yi9ep6q]

Спасибо большое за ваш труд! Простое и понятное объяснение с примерами сложной задачи. Объясняете очень интересно и доступно. Очень помогают ваши выпуски. Рубрики решения задач и интервью замечательные. Очень нравиться ваш канал.

[@frontendscience]

Спасибо большое за добрые слова и поддержку! Успехов Вам!

[@vangog63]

Спасибо большое за оцень доходчивое пояснение алгоримта и задачи!

[@andreyzhukov2821]

Привет! Какое же красивое решение! Спасибо! Теперь разгадаю недорешённые судоку, десятилетней давности!)

[@frontendscience]

Благодарю! Я на самом деле очень тянул с этой задачей, так как искал вариант решения, который будет легко понять. Рад, что понравилось!

[@anton-vr5xw]

шикарная задача и объяснение 👍

[@user-il3xh5di2i]

Да, ты очень крут! :)

[@uliakarahmazli7766]

Спасибо вам большое за решение!

[@frontendscience]

Класс! Рад, что понравилось) Спасибо, что смотрите.

[@user-iz7fk4eu5t]

работаю пол года на позиции junior front-end смотря такие видосы хоть и понимаю что зачем нужно но не могу даже представить что смог бы сам такое решить

[@frontendscience]

Это сложная задача. Ее вряд ли будут давать на джуниор или даже миддл позицию

[@user-iz7fk4eu5t]

@@frontendscience можете посоветовать способ прокачки навыка для решения задач подобных этой или проще. заранее спасибо

[@frontendscience]

Надо брать и решать задачи ) выбрать easy уровень на литкод и прорешать побольше. Потом перейти на медиум уровень и так далее

[@Sha-Kate]

спасибо, что оставили свой комментарий, я бы тоже не решила, но думала, что задача простая и дело во мне)))))

[@lovikuanyshev]

Я в шоке, это красота

[@frontendscience]

Рад, что понравилось

[@mtb-love-belarus]

Спасибо большое, интересно провел вечер :) Заметил, что в методе validate, похоже что не обязательно проверять сам ли это элемент, т.к. на момент валидации мы его еще не установили и на его месте будет '.'

[@samano4619]

ElbrusButcamp. Салам первая фаза.

[@kennymccormick9103]

ееее)))

[@xoxo2880808]

Спасибо, мозг кипит :) мне легче наверное на бумаге такое решить

[@multiply87]

высший пилотаж)

[@frontendscience]

Рад, если оказалось полезно :)

[@wisarty]

Дякую

[@yazanworck5017]

будь здоров 6:20

[@user-fp7dd3po3s]

Блин, а это интересно. К слову время 2:38

[@FanTopRU]

15:20 можно было ифы в один фор запихать :D

[@galinaturubarova33]

смотрю в 01:48 :)

[@user-ss7qk6bm8t]

Ну, это потрясающе. Сколько времени ушло на решение?

[@frontendscience]

К сожалению уже не помню сколько времени ушло на решение. Я эту задачу очень давно решал.

[@frontendscience]

Рад, что понравилось!

[@ded_zamay]

а я сейчас решаю судоку в газетах ))) смотрю ролик в 1:40 ночи )) Начинал решать задачу пару лет назад, решил, но такой ужасный был код, что забросил его до лучших времен. И ВОТ увидел "Задача Судоку (Hard) | Решаем... " и решил глянуть решение, а потом спатки пойти. PS: заснул, и только сейчас отправил )))

[@eugeneromanenko5960]

size и boxSize можно не передавать, если передается board, их легко вычислить. size = board[0].length, boxSize = Math.sqrt(size)

[@frontendscience]

Да можно. А можно и не вычислять, а записать как константы.

[@vladislav23456]

Объясните пожалуйста, в чем была опечатка? Что нам дало boxRow + внутри For'a (let i = boxRow; i < boxRow + boxSize; i++) ?

[@frontendscience]

У нас вообще не работала проверка в секторах. Чтобы проверить сектор мы вычислили левую верхнюю ячейку сектора (boxRow, boxCell). Значит чтобы обойти все элементы этого сектора (если у нас поле 9х9 а сектор 3х3) надо сделать 2 цикла: от boxRow до boxRow + 3 и boxCell до boxCell + 3. Я опечатался и написать только boxSize - что в нашем случае только 3. Поэтому проверка сектора работала только для одного единственного верхнего левого сектора. В остальные мы даже не заходили. Например если у нас самый нижний правый сектор (его начало в (6,6)): цикл от 6 до i < 3. Мы в него даже не зайдем. В результате вышло, что у нас работали проверки на строку и столбец, но не работала проверка на сектор (кроме верхнего левого). Как-то так.

[@vladislav23456]

Front-end Science c Сергеем Пузанковым очень интересно. Спасибо вам за подробное объяснение. Научиться бы так же понимать алгоритмы)))

[@frontendscience]

@@vladislav23456 Для этого и выкладываю. :) Успехов!

[@murcha5899]

24 минута)))

[@user-xt9nl7no8e]

c 3-й не получилось давайте решать с 4-й прям как с девушками))

[@alicenNorwood]

Я кстати решаю судоку по тому же алгоритму если так подумать

[@arttema950]

А какая сложность алгоритма? Мне кажется что O(n6) по времени и O(n4) по памяти, если n - размер сектора (внутреннего квадрата), но это не точно

[@denisoleksyuk5346]

Посмотрел видео часто останавливался и вникал в код, старался сам забегать на перед и писать код, вроде в теории принцип как работает алгоритм понял, единственное сложные участки для меня были Check box и с рекурсией, в остальном более менее. Но вот если мне даже эту же задачу дадут на собесе я думаю вряд ли смогу даже повторить что бы всё работало. Как быть?) :(

[@frontendscience]

Ну это хардовая задача. Такую могут дать например на собеседовании в Google. Чтобы такое решать быстро надо много практиковаться на разных задачках. Кстати могу порекомендовать такой подход - в течении недели каждый день пробовать решить эту же задачу. Когда сложно - подглядывать по строчке чтобы продвинуться дальше. За неделю решение должно осесть в голове - и уже без подсказок можно будет написать его.

[@chess5821]

Судоку Онлайн - xn--d1amlkkd.xn--80asehdb - ТРИ уровня сложности. Не каждый сможет решить !

[@pavelm.2402]

Один человек не решет судоку в газетах)

[@nazar6408]

Часа 2 писал. У меня с рекурсиями туго. Сколько времени заняло вычисление 16*16 не пустого? У меня нода в серьёз и на долго задумалась. 4*4 и 9*9 решает в целом быстро. Пустой 16*16 тоже быстро. Т.е. алгоритм рабочий, но вероятно не сильно простой. Есть что оптимизировать ))) За видео спасибо!

[@frontendscience]

Ну тут много же зависит от компа - уже сейчас не помню сколько именно - но ощущениям, секунды 3. И да - оптимизировать его можно и нужно.

[@EvilYou]

Задачу решил частично. Такое решение подходит для судоку, которые можно решить не используя метод подстановки (пример из видео решается, но на leetcode алгоритм не прошел): function solveSudoku(board) { let rowNum = 9; let colNum = 9; let emptyCells = 0; for (let i = 0; i < rowNum; i++) { for (let j = 0; j < colNum; j++) { if (board[i][j] === '.') emptyCells++; } } let nums = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]; while (emptyCells > 0) { for (let i = 0; i < rowNum; i++) { for (let j = 0; j < colNum; j++) { if (board[i][j] !== '.') continue; let possibleNums = nums.concat(); function checkForPossibleNum(current) { if (current === '.') return; let index = possibleNums.indexOf(current); if (index === -1) return; possibleNums.splice(index, 1); } // Проверяю по горизонтали for (let k = 0; k < 9; k++) { let current = board[i][k]; checkForPossibleNum(current); } // Проверяю по вертикали for (let m = 0; m < 9; m++) { let current = board[m][j]; checkForPossibleNum(current); } // Проверяю в квадрате let squareI = Math.floor( i / 3 ) * 3; let squareJ = Math.floor( j / 3 ) * 3; for (let y = squareI; y

[@frontendscience]

Круто!

[@frontendscience]

Все - все задачи выполнены?

[@EvilYou]

Можно сказать, что так. Посмотрел и попытался решить все, а сам решил около 25 из 29.

[@EvilYou]

@@frontendscience Теперь продолжу читать "Грокаем алгоритмы" (прочитал немного и стал задачи на бинарный поиск решать, а за ними и другие), а там, возможно, снова вернусь к задачам, с которыми у меня возникали трудности здесь.

[@EvilYou]

Моя версия решения тем способом, который разобран в видео. function solveSudoku(board) { if ( !solve() ) throw Error('invalid board'); function solve() { let [i, j] = getFirstEmpty() || []; if (i === undefined) return true; for (let k = 1; k

[@user-vv3gg6xm1b]

Где вы берете задачи? Очень хочется порешать)

[@frontendscience]

Из разных мест беру. Что-то сам нахожу, что-то подписчики присылают. Сам обычно беру либо на leetcode либо на codewars. Рекомендую - там много всего интересного!

[@mega.pe4enka147]

Жесть, я то в двух циклах начинаю теряться, а тут...

[@frontendscience]

Не боись! Все приходит с практикой)

[@1987Raziell]

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

[@fam4699]

да для этого нужно сделать 3 числа по 27 бит которые будут отображать соответственно по 3 строки в виде "1" - заполнено, "0" - незаполнено. 10 наборов по 3 числа отображают состояние заполненности основной матрицы и 9 матриц с числами. Вводим маски "111000000111000000111" в двоичном виде и "111111111" и *100000000010000000001" это маски заполнения чисел для столбцов, строк и квадратов в матрице числа при нахождении соотвественного числа, далее находим в числах матриц наборы строк, столбцов, квадратов 3x3 с 1 "0" заполняем их 1 во всех матрицах. Для более сложных судоку нужно вводить много масок для нахождения по 2 нуля в одном столбце внутри квадрата, по 3 нуля в соответственных матрицах. И да некоторые самые сложные судоку в середине решения решаются выбором среди 2 возможных чисел как ни ищи возможные комбинации

[@JenechekDv]

Смотрю в 6 утра

[@frontendscience]

Прикольно. А это где сейчас столько? Откуда смотрите?

[@JenechekDv]

@@frontendscience Владивосток. Кстати после вашей рекомендации дочитываю Цель.

[@frontendscience]

@@JenechekDv класс! Понравилась?

[@JenechekDv]

@@frontendscience ага, некоторые моменты как будто с меня писались) Жене теперь вручил.

[@maxlight9258]

В каком часу я решаю эту задачу? 4 утра хахап

[@IntresNO]

20:55

[@frontendscience]

Прикольно. А что там? :)

[@user-gp5jm1je8f]

@@frontendscience вы же в начале ролика просили указать время, в какое мы решаем)

[@frontendscience]

@@user-gp5jm1je8f АААА )) Благодарю! Ютюб просто сделал из него тайм метку - я открываю видео на 20:55 и не понимаю что там ))))

[@danielnedefo]

не понял за размер сектора(boxSize),подскажите плиз

[@frontendscience]

в судоку 9х9 есть 9 секторов 3х3 внутри которых тоже уникальные числа. Для этого вынес boxSize в отдельную переменную, чтобы можно было решать разного размера судоку.

[@danielnedefo]

@@frontendscience понял,спасибо,не обращал раньше внимание на это)

[@romanryaboshtan9270]

Оказалось, задачка-то несложная совсем

[@user-xt9nl7no8e]

какой вы молодец

[@Ted_K.]

Слишком замудрил