Sudoku problem (Hard) | Solve problems with Leetcode
Вставка
- Опубліковано 17 гру 2024
- Ура! Начинаем год с хардовой задачи, которую вы так долго просили. В сегодняшнем ролике мы с вами разберем, как решить судоку с помощью алгоритма DFS (Depth-First-Search).
Будем идти по решению поэтапно - начнем с разбора судоку 4х4, а далее в наш алгоритм скормим судоку 9х9. И на десерт решим судоку 16х16. Уляля!
Приятного просмотра!
Код Решения Задачи: codepen.io/puz...
Задача про банкомат (Часть 2) - • Задача про банкомат. В...
Задача про лабиринт - • Решаем задачу с собесе...
Как всегда, Ваши лайки и решения ждем под видео!
И поделитесь видео с друзьями, если они еще не видели.
---
Если видео было для вас полезным, ставьте лайк и поделитесь им с друзьями.
Подписывайтесь на наш канал: bit.ly/fs-ytb
---
Присоединяйтесь к нам в соцсетях:
FB: / frontendscience
Instagram Сергея Пузанкова: / puzankovcom
Заходите на наш сайт: frontend-scienc...
Music by -
Blue Wednesday - 90s kid
Blue Wednesday - Murmuration
Blue Wednesday - Suede
#javascript #задачи #leetcode #itсобеседование
Спасибо большое за ваш труд! Простое и понятное объяснение с примерами сложной задачи. Объясняете очень интересно и доступно. Очень помогают ваши выпуски. Рубрики решения задач и интервью замечательные. Очень нравиться ваш канал.
Спасибо большое за добрые слова и поддержку! Успехов Вам!
Привет!
Какое же красивое решение!
Спасибо! Теперь разгадаю недорешённые судоку, десятилетней давности!)
Благодарю! Я на самом деле очень тянул с этой задачей, так как искал вариант решения, который будет легко понять. Рад, что понравилось!
шикарная задача и объяснение 👍
работаю пол года на позиции junior front-end смотря такие видосы хоть и понимаю что зачем нужно но не могу даже представить что смог бы сам такое решить
Это сложная задача. Ее вряд ли будут давать на джуниор или даже миддл позицию
@@frontendscience можете посоветовать способ прокачки навыка для решения задач подобных этой или проще.
заранее спасибо
Надо брать и решать задачи ) выбрать easy уровень на литкод и прорешать побольше. Потом перейти на медиум уровень и так далее
спасибо, что оставили свой комментарий, я бы тоже не решила, но думала, что задача простая и дело во мне)))))
Я в шоке, это красота
Рад, что понравилось
Спасибо большое за оцень доходчивое пояснение алгоримта и задачи!
Спасибо вам большое за решение!
Класс! Рад, что понравилось) Спасибо, что смотрите.
Да, ты очень крут! :)
Задачу решил частично. Такое решение подходит для судоку, которые можно решить не используя метод подстановки (пример из видео решается, но на 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
ElbrusButcamp. Салам первая фаза.
ееее)))
Спасибо большое, интересно провел вечер :) Заметил, что в методе validate, похоже что не обязательно проверять сам ли это элемент, т.к. на момент валидации мы его еще не установили и на его месте будет '.'
Объясните пожалуйста, в чем была опечатка? Что нам дало 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 Для этого и выкладываю. :) Успехов!
высший пилотаж)
Рад, если оказалось полезно :)
Блин, а это интересно. К слову время 2:38
Спасибо, мозг кипит :) мне легче наверное на бумаге такое решить
Ну, это потрясающе. Сколько времени ушло на решение?
К сожалению уже не помню сколько времени ушло на решение. Я эту задачу очень давно решал.
Рад, что понравилось!
смотрю в 01:48 :)
size и boxSize можно не передавать, если передается board, их легко вычислить. size = board[0].length, boxSize = Math.sqrt(size)
Да можно. А можно и не вычислять, а записать как константы.
а я сейчас решаю судоку в газетах )))
смотрю ролик в 1:40 ночи )) Начинал решать задачу пару лет назад, решил, но такой ужасный был код, что забросил его до лучших времен. И ВОТ увидел "Задача Судоку (Hard) | Решаем... " и решил глянуть решение, а потом спатки пойти.
PS: заснул, и только сейчас отправил )))
Где вы берете задачи? Очень хочется порешать)
Из разных мест беру. Что-то сам нахожу, что-то подписчики присылают. Сам обычно беру либо на leetcode либо на codewars. Рекомендую - там много всего интересного!
Дякую
А какая сложность алгоритма? Мне кажется что O(n6) по времени и O(n4) по памяти, если n - размер сектора (внутреннего квадрата), но это не точно
будь здоров 6:20
Посмотрел видео часто останавливался и вникал в код, старался сам забегать на перед и писать код, вроде в теории принцип как работает алгоритм понял, единственное сложные участки для меня были Check box и с рекурсией, в остальном более менее. Но вот если мне даже эту же задачу дадут на собесе я думаю вряд ли смогу даже повторить что бы всё работало. Как быть?) :(
Ну это хардовая задача. Такую могут дать например на собеседовании в Google. Чтобы такое решать быстро надо много практиковаться на разных задачках. Кстати могу порекомендовать такой подход - в течении недели каждый день пробовать решить эту же задачу. Когда сложно - подглядывать по строчке чтобы продвинуться дальше. За неделю решение должно осесть в голове - и уже без подсказок можно будет написать его.
15:20 можно было ифы в один фор запихать :D
Я кстати решаю судоку по тому же алгоритму если так подумать
Часа 2 писал. У меня с рекурсиями туго. Сколько времени заняло вычисление 16*16 не пустого? У меня нода в серьёз и на долго задумалась. 4*4 и 9*9 решает в целом быстро. Пустой 16*16 тоже быстро. Т.е. алгоритм рабочий, но вероятно не сильно простой. Есть что оптимизировать ))) За видео спасибо!
Ну тут много же зависит от компа - уже сейчас не помню сколько именно - но ощущениям, секунды 3. И да - оптимизировать его можно и нужно.
c 3-й не получилось давайте решать с 4-й прям как с девушками))
20:55
Прикольно. А что там? :)
@@frontendscience вы же в начале ролика просили указать время, в какое мы решаем)
@@СергейКозлов-н1л АААА )) Благодарю! Ютюб просто сделал из него тайм метку - я открываю видео на 20:55 и не понимаю что там ))))
Интересно, а можно ли написать алгоритм, который решал бы Судоку действительно по правилам?. Ведь вызов рекурсии и откат назад - это одно и тоже, что стирать цифры "ластиком", т.е. дается бесконечное число прав на ошибку. В настоящих Судоку - ошибок быть не должно, они ведь решаются однозначно.
да для этого нужно сделать 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 понял,спасибо,не обращал раньше внимание на это)
24 минута)))
Один человек не решет судоку в газетах)
Жесть, я то в двух циклах начинаю теряться, а тут...
Не боись! Все приходит с практикой)
Смотрю в 6 утра
Прикольно. А это где сейчас столько? Откуда смотрите?
@@frontendscience Владивосток. Кстати после вашей рекомендации дочитываю Цель.
@@JenechekDv класс! Понравилась?
@@frontendscience ага, некоторые моменты как будто с меня писались) Жене теперь вручил.
В каком часу я решаю эту задачу? 4 утра хахап
Оказалось, задачка-то несложная совсем
какой вы молодец
Слишком замудрил
Судоку Онлайн - xn--d1amlkkd.xn--80asehdb - ТРИ уровня сложности. Не каждый сможет решить !