Привет! Все мы слышали об очень известной логической головоломке под названием «Судоку». Сегодня я расскажу вам об этой головоломке, одном из способов ее решения и о том, на какой платформе вы можете ее решить. Итак, начнем.
Итак, по сути судоку - это логическая головоломка, которая представлена сеткой 9x9, и мы должны заполнить диапазон чисел от 1 до 9 в каждой ячейке, но есть некоторое правило для заполнения чисел.
- Заполните число в ячейке так, чтобы никакая другая ячейка не содержала это число в той же строке, а также в том же столбце.
- Заполните число в ячейке так, чтобы каждый из девяти блоков 3x3 содержал все числа от 1 до 9.
Это два правила, которым мы должны следовать, чтобы решить головоломку судоку. Это очень известная головоломка, основанная на логике высказываний в дискретной математике.
Теперь приходит в голову вопрос, как решить эту головоломку?
Итак, для решения этого вопроса один из приемов, используемых в программировании, называется откат. Отслеживание с возвратом - это в основном рекурсивный способ решения любой проблемы, но он отличается от рекурсии. Итак, во-первых, вам нужно знать об обратном отслеживании.
В общем, если я вам скажу, идея решения этой головоломки состоит в том, что всего имеется 9x9 = 81 ячеек. Вы просто пробуете каждую ячейку (которая пуста) и помещаете все числа от 1 до 9 в эту ячейку и проверяете, действительно ли помещать номер в эту ячейку, если он действителен, затем введите номер в ячейку, в противном случае найдите какое-то другое число, попробуйте этот подход для каждой клетки.
Позвольте мне показать вам математические шаги для решения этой головоломки, которые я нашел в Книге дискретной математики, написанной Кеннетом Х. Розеном. Ниже приведено изображение этого ограничения, и вы также можете проверить его в Книге. (на странице 53 pdf). (Ссылка предоставляется.)
Итак, на картинке выше дана математическая форма для решения головоломки судоку. Позвольте мне рассказать вам все шаги простым языком.
Шаги:
- Отметьте первое пустое место в данной сетке. (на изображении выше пункт 1)
- Если вы не найдете ни одной пустой ячейки, дальше идти не нужно, все ячейки в сетке заполнены действительными числами.
- Теперь начните цикл от чисел от 1 до 9 в каждой ячейке, и число, которое удовлетворяет, заполняет это число.
3. а. Возьмите номер и проверьте, находится ли он уже в той же строке или нет. (на изображении выше пункт 2.)
3. б. Возьмите номер и проверьте, находится ли он уже в том же столбце или нет. (на изображении выше пункт 3).
3.c. Возьмите число, затем проверьте, находится ли оно уже в той же сетке 3x3. (На изображении выше, пункт 4).
4. Теперь последняя точка на изображении выше говорит о том, что если все вышеперечисленные условия (3.a, 3.b, 3.c) удовлетворяют, то число не присутствует в той же строке, том же столбце и той же сетке. затем мы присваиваем этот номер этой ячейке и переходим к следующей пустой ячейке.
5. Если где-то наша предыдущая заполненная ячейка не заполнена действительным числом, удалите это число из этой ячейки и снова вернитесь к другому числу.
Все это основные шаги для решения головоломки судоку. Вышеупомянутый алгоритм требует экспоненциального времени для решения головоломки судоку, но вы можете дополнительно оптимизировать это. Я не могу предоставить здесь свой код для этой головоломки, вы просто решаете ее с заданными шагами.
Чтобы узнать больше об этой головоломке, воспользуйтесь указанными ниже ресурсами.
- Книга по дискретной математике, написанная Кенетом Х. Розеном.
- Лекция MIT по судоку. (здесь вы можете найти более оптимальный способ решения этой головоломки)
- Для решения этой головоломки вы можете перейти на Leetcode.
Спасибо вам всем. Если вы найдете что-то не так в этой статье. Скажи пожалуйста.
