Sudoku problem (Hard) | Solve problems with Leetcode
Вставка
- Опубліковано 1 січ 2021
- Ура! Начинаем год с хардовой задачи, которую вы так долго просили. В сегодняшнем ролике мы с вами разберем, как решить судоку с помощью алгоритма 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собеседование
Спасибо большое за ваш труд! Простое и понятное объяснение с примерами сложной задачи. Объясняете очень интересно и доступно. Очень помогают ваши выпуски. Рубрики решения задач и интервью замечательные. Очень нравиться ваш канал.
Спасибо большое за добрые слова и поддержку! Успехов Вам!
Привет!
Какое же красивое решение!
Спасибо! Теперь разгадаю недорешённые судоку, десятилетней давности!)
Благодарю! Я на самом деле очень тянул с этой задачей, так как искал вариант решения, который будет легко понять. Рад, что понравилось!
Спасибо большое за оцень доходчивое пояснение алгоримта и задачи!
шикарная задача и объяснение 👍
Да, ты очень крут! :)
Спасибо вам большое за решение!
Класс! Рад, что понравилось) Спасибо, что смотрите.
Я в шоке, это красота
Рад, что понравилось
работаю пол года на позиции junior front-end смотря такие видосы хоть и понимаю что зачем нужно но не могу даже представить что смог бы сам такое решить
Это сложная задача. Ее вряд ли будут давать на джуниор или даже миддл позицию
@@frontendscience можете посоветовать способ прокачки навыка для решения задач подобных этой или проще.
заранее спасибо
Надо брать и решать задачи ) выбрать easy уровень на литкод и прорешать побольше. Потом перейти на медиум уровень и так далее
спасибо, что оставили свой комментарий, я бы тоже не решила, но думала, что задача простая и дело во мне)))))
высший пилотаж)
Рад, если оказалось полезно :)
ElbrusButcamp. Салам первая фаза.
ееее)))
Спасибо большое, интересно провел вечер :) Заметил, что в методе validate, похоже что не обязательно проверять сам ли это элемент, т.к. на момент валидации мы его еще не установили и на его месте будет '.'
Спасибо, мозг кипит :) мне легче наверное на бумаге такое решить
Дякую
Ну, это потрясающе. Сколько времени ушло на решение?
К сожалению уже не помню сколько времени ушло на решение. Я эту задачу очень давно решал.
Рад, что понравилось!
15:20 можно было ифы в один фор запихать :D
будь здоров 6:20
Блин, а это интересно. К слову время 2:38
смотрю в 01:48 :)
Где вы берете задачи? Очень хочется порешать)
Из разных мест беру. Что-то сам нахожу, что-то подписчики присылают. Сам обычно беру либо на leetcode либо на codewars. Рекомендую - там много всего интересного!
Объясните пожалуйста, в чем была опечатка? Что нам дало boxRow + внутри For'a (let i = boxRow; i < boxRow + boxSize; i++) ?
У нас вообще не работала проверка в секторах. Чтобы проверить сектор мы вычислили левую верхнюю ячейку сектора (boxRow, boxCell). Значит чтобы обойти все элементы этого сектора (если у нас поле 9х9 а сектор 3х3) надо сделать 2 цикла: от boxRow до boxRow + 3 и boxCell до boxCell + 3. Я опечатался и написать только boxSize - что в нашем случае только 3. Поэтому проверка сектора работала только для одного единственного верхнего левого сектора. В остальные мы даже не заходили. Например если у нас самый нижний правый сектор (его начало в (6,6)): цикл от 6 до i < 3. Мы в него даже не зайдем.
В результате вышло, что у нас работали проверки на строку и столбец, но не работала проверка на сектор (кроме верхнего левого). Как-то так.
Front-end Science c Сергеем Пузанковым очень интересно. Спасибо вам за подробное объяснение. Научиться бы так же понимать алгоритмы)))
@@vladislav23456 Для этого и выкладываю. :) Успехов!
24 минута)))
А какая сложность алгоритма? Мне кажется что O(n6) по времени и O(n4) по памяти, если n - размер сектора (внутреннего квадрата), но это не точно
Задачу решил частично. Такое решение подходит для судоку, которые можно решить не используя метод подстановки (пример из видео решается, но на 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
Круто!
Все - все задачи выполнены?
Можно сказать, что так. Посмотрел и попытался решить все, а сам решил около 25 из 29.
@@frontendscience
Теперь продолжу читать "Грокаем алгоритмы" (прочитал немного и стал задачи на бинарный поиск решать, а за ними и другие), а там, возможно, снова вернусь к задачам, с которыми у меня возникали трудности здесь.
Моя версия решения тем способом, который разобран в видео.
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
c 3-й не получилось давайте решать с 4-й прям как с девушками))
size и boxSize можно не передавать, если передается board, их легко вычислить. size = board[0].length, boxSize = Math.sqrt(size)
Да можно. А можно и не вычислять, а записать как константы.
Я кстати решаю судоку по тому же алгоритму если так подумать
Посмотрел видео часто останавливался и вникал в код, старался сам забегать на перед и писать код, вроде в теории принцип как работает алгоритм понял, единственное сложные участки для меня были Check box и с рекурсией, в остальном более менее. Но вот если мне даже эту же задачу дадут на собесе я думаю вряд ли смогу даже повторить что бы всё работало. Как быть?) :(
Ну это хардовая задача. Такую могут дать например на собеседовании в Google. Чтобы такое решать быстро надо много практиковаться на разных задачках. Кстати могу порекомендовать такой подход - в течении недели каждый день пробовать решить эту же задачу. Когда сложно - подглядывать по строчке чтобы продвинуться дальше. За неделю решение должно осесть в голове - и уже без подсказок можно будет написать его.
Часа 2 писал. У меня с рекурсиями туго. Сколько времени заняло вычисление 16*16 не пустого? У меня нода в серьёз и на долго задумалась. 4*4 и 9*9 решает в целом быстро. Пустой 16*16 тоже быстро. Т.е. алгоритм рабочий, но вероятно не сильно простой. Есть что оптимизировать ))) За видео спасибо!
Ну тут много же зависит от компа - уже сейчас не помню сколько именно - но ощущениям, секунды 3. И да - оптимизировать его можно и нужно.
а я сейчас решаю судоку в газетах )))
смотрю ролик в 1:40 ночи )) Начинал решать задачу пару лет назад, решил, но такой ужасный был код, что забросил его до лучших времен. И ВОТ увидел "Задача Судоку (Hard) | Решаем... " и решил глянуть решение, а потом спатки пойти.
PS: заснул, и только сейчас отправил )))
Один человек не решет судоку в газетах)
Жесть, я то в двух циклах начинаю теряться, а тут...
Не боись! Все приходит с практикой)
Интересно, а можно ли написать алгоритм, который решал бы Судоку действительно по правилам?. Ведь вызов рекурсии и откат назад - это одно и тоже, что стирать цифры "ластиком", т.е. дается бесконечное число прав на ошибку. В настоящих Судоку - ошибок быть не должно, они ведь решаются однозначно.
да для этого нужно сделать 3 числа по 27 бит которые будут отображать соответственно по 3 строки в виде "1" - заполнено, "0" - незаполнено. 10 наборов по 3 числа отображают состояние заполненности основной матрицы и 9 матриц с числами. Вводим маски "111000000111000000111" в двоичном виде и "111111111" и *100000000010000000001" это маски заполнения чисел для столбцов, строк и квадратов в матрице числа при нахождении соотвественного числа, далее находим в числах матриц наборы строк, столбцов, квадратов 3x3 с 1 "0" заполняем их 1 во всех матрицах. Для более сложных судоку нужно вводить много масок для нахождения по 2 нуля в одном столбце внутри квадрата, по 3 нуля в соответственных матрицах. И да некоторые самые сложные судоку в середине решения решаются выбором среди 2 возможных чисел как ни ищи возможные комбинации
не понял за размер сектора(boxSize),подскажите плиз
в судоку 9х9 есть 9 секторов 3х3 внутри которых тоже уникальные числа. Для этого вынес boxSize в отдельную переменную, чтобы можно было решать разного размера судоку.
@@frontendscience понял,спасибо,не обращал раньше внимание на это)
20:55
Прикольно. А что там? :)
@@frontendscience вы же в начале ролика просили указать время, в какое мы решаем)
@@user-gp5jm1je8f АААА )) Благодарю! Ютюб просто сделал из него тайм метку - я открываю видео на 20:55 и не понимаю что там ))))
Смотрю в 6 утра
Прикольно. А это где сейчас столько? Откуда смотрите?
@@frontendscience Владивосток. Кстати после вашей рекомендации дочитываю Цель.
@@JenechekDv класс! Понравилась?
@@frontendscience ага, некоторые моменты как будто с меня писались) Жене теперь вручил.
В каком часу я решаю эту задачу? 4 утра хахап
Оказалось, задачка-то несложная совсем
какой вы молодец
Слишком замудрил
Судоку Онлайн - xn--d1amlkkd.xn--80asehdb - ТРИ уровня сложности. Не каждый сможет решить !