Как сделать судоку
Добавил пользователь Alex Обновлено: 05.10.2024
Судоку, или магический квадрат, — это цифровая головоломка, решать которую надо на специальном игровом поле.
Классическое поле представляет собой расчерченный квадрат размерами 9 на 9 клеток. Большая фигура, в свою очередь, состоит из девяти малых, размерами 3 на 3 клетки каждая.
Иллюстрация: Анна Гуридова / Лайфхакер
В каждой строке и столбце цифрами заполнены лишь несколько клеточек. Задача играющего — выяснить, каких цифр не хватает, и правильно расположить их во всех пустых ячейках квадрата.
Эксперты утверждают What is Sudoku? / Sudoku Space , что существует 6 670 903 752 021 072 936 960 вариантов расположения цифр. Таким образом, в новые и новые судоку можно играть бесконечно.
Какие правила судоку надо учесть
- Игровое поле можно заполнять только цифрами от 1 до 9. Существуют виды судоку, которые решают буквами или символами, но это совершенно отдельные игры со своими правилами и стратегией.
- Цифру можно записывать лишь в том случае, если она не будет повторяться в строке, столбце и малом квадрате 3 х 3, в которых расположена пустая ячейка.
Также помните о том, что судоку — расслабляющая игра, которая помогает не только потренировать мозг, но и снять стресс. Поэтому не торопитесь и старайтесь получить удовольствие.
Как решать судоку классическим способом с перебором
Он подходит для решения судоку любой сложности. Но всё же лучше всего сработает на простых игровых полях, где изначально цифрами заполнена минимум половина ячеек. Например, на таком:
Иллюстрация: Анна Гуридова / Лайфхакер
Для начала выберите максимально заполненный цифрами малый квадрат. В данном случае этот:
Иллюстрация: Анна Гуридова / Лайфхакер
На других полях вариантов может быть несколько. Среди равносильных остановитесь на том, который вам больше нравится.
Теперь выберите ячейку, расположенную на пересечении максимально заполненных цифрами строки и столбца.
Иллюстрация: Анна Гуридова / Лайфхакер
Чтобы вычислить ответ, надо провести несложный анализ. В теории цифра может быть любой — от 1 до 9. Но мы знаем, что она не должна повторяться в пределах малого квадрата.
Итого из возможных девяти вариантов мы вычёркиваем те, что уже присутствуют в малом квадрате: 7, 2, 8, 1, 6, 4. Значит, искомая цифра — это 3, 5 или 9.
Теперь анализируем строку, в которой расположена наша пустая ячейка. В ней, помимо прочих, присутствует цифра 3. Это значит, что мы можем вычеркнуть этот вариант.
Таким образом, остаются лишь две цифры, которые можно вписать в ячейку, — это 9 или 5. Но если мы впишем 9, то для цифры 5 останется место лишь в столбце, где уже есть своя пятёрка:
Иллюстрация: Анна Гуридова / Лайфхакер
Поскольку это противоречит правилам, приходим к однозначному выводу: в анализируемой ячейке может находиться только цифра 5:
Иллюстрация: Анна Гуридова / Лайфхакер
Теперь надо выяснить, какие цифры располагаются в двух оставшихся пустыми клетках. Это совсем просто. Мы знаем, что варианта всего два — это 3 и 9.
Тройка не может находиться в средней строке малого квадрата, поскольку она уже есть в той же строке большого. По той же причине в нижней строке малого квадрата не может находиться девятка. Значит, возможно лишь такое расположение цифр:
Иллюстрация: Анна Гуридова / Лайфхакер
Заполнив первый малый квадрат, переходим к следующему. Выбираем его по той же схеме — чтобы в нём и пересекающих его строках и столбцах большого квадрата было как можно больше заполненных ячеек. В данном случае это нижний правый квадрат.
Начинаем заполнять его с левой верхней клетки, поскольку она расположена на пересечении самых заполненных строки и столбца.
Поскольку в малом квадрате уже известны четыре цифры, искомой может быть только 1, 2, 6, 7 или 9.
Но 1, 7 и 6 уже есть в общей строке. Значит, остаются всего два варианта: 2 и 9. Однако 2 присутствует в общем столбце, поэтому итог перебора выглядит так:
Иллюстрация: Анна Гуридова / Лайфхакер
Переходим к следующей пустой клетке, расположенной на пересечении наиболее заполненных строчки и столбца, — это средняя ячейка в нижнем ряду. Сразу же выясняем, что цифрой в этой клетке не могут быть 1, 2, 3, 4 (поскольку они есть в соответствующем столбце), а также 5, 7, 8 и 9, указанные в соответствующей строке. Итого вариант один:
Иллюстрация: Анна Гуридова / Лайфхакер
Продолжайте заполнять пустые ячейки по тому же алгоритму, пока не решите головоломку.
Как решать судоку последовательным способом
Схема решения головоломки в данном случае та же. Только вместо мысленного подбора подходящих цифр используется документальный.
В каждую пустую ячейку впишите все цифры от 1 до 9, а затем просто вычёркивайте неподходящие. Переходите от одной клетки к другой.
Уже при первом проходе большого квадрата вы обнаружите как минимум одну ячейку с однозначным вариантом решения. Впишите найденную цифру в клетку.
Пример — цифра 3:
Иллюстрация: Анна Гуридова / Лайфхакер
Никакую другую цифру вписать в конкретную ячейку невозможно, это будет нарушением правил.
Далее проанализируйте оставшиеся пустыми клетки в том же малом квадрате, вычеркнув из возможных вариантов только что вписанную цифру. Скорее всего, вы тут же обнаружите ещё как минимум одно однозначное решение для незаполненной ячейки.
Продолжайте вычёркивать неподходящие варианты по тому же принципу. Процесс пойдёт лавинообразно.
Как решать судоку методом исключения
Этот способ позволяет очень быстро заполнять пустые клетки, но подойдёт только самым внимательным. Заключается он в том, что мы сканируем сразу несколько расположенных в одном столбце или строке малых квадрата.
В этом примере легко заметить, что в среднем и нижнем квадратах уже есть цифра 3, причём в разных столбцах. А в квадрате слева тройка стоит в средней строке. Это значит, что в верхнем правом квадрате есть лишь одна ячейка, куда можно вставить 3, — правая в нижней строке:
Иллюстрация: Анна Гуридова / Лайфхакер
По тому же принципу можно быстро вписать в ячейку другого малого квадрата цифру 6:
Иллюстрация: Анна Гуридова / Лайфхакер
Продолжайте анализировать другие рядом стоящие фигуры: есть ещё много ячеек, которые можно заполнить буквально за пару секунд, не перебирая варианты.
Как решать судоку с помощью анализа малых квадратов
Рассмотрите каждый малый квадрат и выпишите рядом с ним все цифры, которых в нём не хватает.
Иллюстрация: Анна Гуридова / Лайфхакер
Выберите одну из фигур, в которой не заполнено меньше всего ячеек. Положим, левый центральный квадрат. Там нет цифр 1, 2 и 8.
Сразу заметно, что 2 не может стоять ни в одной из свободных ячеек в верхней строке: ведь там уже есть двойка. Значит, расположение этой цифры однозначно.
Остаются только две клетки в верхней строке малого квадрата. Но 1 не может находиться в правой ячейке, поскольку уже есть во всём столбце. Поэтому ставим туда 8. Получается, для единицы доступно только одно место:
Иллюстрация: Анна Гуридова / Лайфхакер
Рассмотрите следующую фигуру. Например, левую нижнюю, где не хватает трёх цифр — 7, 8 и 9. Теперь расставляем цифры в допустимые для них ячейки.
Берём 7: она не должна стоять ни в первом, ни во втором столбце, поскольку в каждом из них уже есть семёрка. Значит, эту цифру можно вписать только в третий столбец.
Переходим к 8. Она не может находиться во втором столбце, потому что уже стоит в нём. Соответственно, единственное допустимое для этой цифры место — первый столбец.
Цифру 9 по остаточному принципу ставим в единственную свободную ячейку — в центральном, втором столбце:
Иллюстрация: Анна Гуридова / Лайфхакер
Затем переключитесь на следующий малый квадрат с небольшим количеством незаполненных ячеек.
Автор и редактор статей о здоровье, психологии, сексологии. Работаю в медицинской журналистике более 15 лет. Опираюсь на принципы докмеда, люблю и умею искать и анализировать релевантные исследования в мировых научных журналах. Стараюсь просто и доступно писать о самых сложных заболеваниях. Верю, что понять механизм развития болезни — значит сделать первый шаг к выздоровлению.
Формулировка задания: “Написать программу для решения судоку”
Выбранный язык программирования: С++.
Поле судоку представляет собой таблицу 9х9 клеток. В каждую клетку заносится цифра от 1 до 9. Цель игры: расположить цифры таким образом, чтобы в каждой строке, в каждом столбце и в каждом блоке 3х3 не было повторений. Другими словами, в каждом столбце, строке и блоке должны быть все цифры от 1 до 9.
Существует множество подходов к решению задачи судоку.
Как решать простые судоку?
Рассмотрим на конкретном примере как разгадывать судоку. Игровое поле на картинке представляет собой относительно простой вариант игры. Правила игры судоку для простых сводятся к выявлению зависимостей в горизонтальной и вертикальной плоскости и в отдельных квадратах.
Например, в центральной вертикали не хватает цифр 3, 4, 5. Четверка не может находиться в нижнем квадрате, так как в нем уже присутствует. Также можно исключить пустую центральную клетку, так как мы видим 4 в горизонтальной линии. Из этого делаем вывод, что она располагается в верхнем квадрате. Аналогично можем проставить 3 и 5 и получить следующий результат.
Проведя линии в верхнем среднем малом квадрате 3х3 можно исключить ячейки, в которых не может находиться цифра 3.
Продолжая разгадывать подобным образом, необходимо заполнить оставшиеся ячейки. В результате получается единственно верное решение.
Как решать сложные судоку?
В первую очередь необходимо заполнить пустые ячейки возможными вариантами, чтобы максимально облегчить решение и иметь перед глазами полную картину.
Ответ, как решить судоку сложные для каждого свой. Кому-то удобнее использовать разные цвета для окрашивания ячеек или цифр, кто то предпочитает черно-белый вариант. На рисунке видно, что нет ни одной ячейки, в которой бы стояла единственная цифра, однако, это не говорит о том, что в данном задании нет одиночек. Вооружившись правилами судоку и внимательным взглядом, можно увидеть, что в верхней строке среднего малого блока стоит цифра 5, которая встречается единожды в своей линии. В связи с этим можно смело проставить ее и исключить из ячеек, окрашенных в зеленый цвет. Данное действие повлечет за собой возможность проставить цифру 3 в оранжевой клетке и смело вычеркнуть ее из соответствующик фиолетовых по вертикали и малом блоке 3х3.
Таким же образом проверяем остальные клеточки и проставляем единицы в обведенных клетках, так как они также являются единственными в своих строках. Чтобы разобраться, как решать судоку сложные, необходимо вооружиться несколькими простыми методами.
Чтобы очистить поле дальше, необходимо найти открытые пары, которые позволяют исключить имеющиеся в них цифры из других ячеек в блоке и строках. В примере такими парочками являются 4 и 9 из третьей строки. Они наглядно показывают, как разгадывать сложные судоку. Их комбинация говорит о том, что в данных клетках могут быть проставлены исключительно 4 или 9. Этот вывод делается на основании правил судоку.
Подобно действует система сопряжения, когда можно исключить из ячеек блока/строки/столбца значения, несколько раз встречающееся в соседнем или сопряженном.
Также можно применять для трех и четырех строк. Сложность метода заключается в трудностях визуализации и выявления связей.
Рекурсивный алгоритм решения
Данный алгоритм является одним из самых популярных алгоритмов для решения задачи судоку в программировании. Он подразумевает использования метода "Одиночка" и расстановки в пустые клетки возможных значений этих клеток.
После определения возможных значений, алгоритм рекурсивно подставляет поочереди данные значения в соответствующие клетки и проверяет с помощью метода "Одиночка". Выход из рекурсии - ситуация, когда не осталось пустых клеток.
В программе будет использовать именно такой алгоритм. Он позволяет быстро решать судоку размерностью 9х9 и относительно прост в реализации.
Судоку - NP-полная задача
В общем случае судоку размерностью N^2 x N^2 является NP-полной задачей.
Известно, что задача распознавания того, может ли частичный квадрат быть дополнен до латинского, является NP-полной. Предположим, что квадрат заполнен так:
Если перенести каждый столбец квадрата в начало столбцов матрицы 16х16, а затем заполнить оставшиеся ячейки матрицы полностью, получится задача о решении судоку.
Следовательно, задача о решении судоку - NP-полная. Значит, для нее не существует полиномиального алгоритма.
В качестве контейнера для хранения судоку используется двухмерный std::deque целых числел. Он удобен тем, что позволяет легко производить последовательный обход матрицы и имеет сложность добавления О(1). Для работы алгоритмов проверки ряда, столбца и квадрата3х3 используются контейнеры std::set , а в методе, который проверяет одну ячейку с помощью вышеупомянтых - std::unordered_set , так как добавление в него происходит за константное время, в отличие от логарифмического в std::set . Следовательно, при использовании именно таких контейнеров достигается самая быстрая работа программы, что демонстрируют замеры времени работы программы:
Тесты empty и not_dig(здесь и далее приводятся только additional_file_name вместо полного названия файлов) - это тесты корректности вводимой информации:
- empty - пустой файл
- not_dig - файл, который внутри матрицы содержит не только числа
Во всех случаях выбрасывается исключение, выходной файл не создается.
- Easy, medium, another_medium, hard - судоку различной сложности.
- Hard_1 показывает, что программа имеет возможность решить судоку, имеющую более одного правильного решения(выводится первый корректный вариант). Hard_1 - это файл hard, в котором вместо одного из значений судоку - пустая ячейка. При решении получается другой, правильный вариант решения. Следовательно, у данной задачи(hard_1) - два решения и программа позволяет решить ее.
- Too_easy - пустой судоку.
Оценка сложности алгоритмов
Так как алгоритм рекурсивный, оценка сложности будет зависеть от глубины рекурсии. Можно оценить сложности работы методов класса.
Каждый из методов проверки (строки, столбца и квадрата) проходит по N элементам и добавляет элементы в std::unordered_set за O(1), следовательно, сложность каждого из трех методов O(N). Функция проверки клетки XY использует последовательно три вышеупомянутых метода, каждый из которых имеет сложность NlogN, а затем производит проверку наличия цифры в std::unordered_set за O(1) и добавляет элементы в std::unordered_set . Для N элементов добавление будет иметь сложность N. Следовательно, сложность данной функции O(N).
Методы проверки одиночных цифр для строк, столбцов и квадратов 3х3 в возможных значениях ячейки обходят весь судоку и для каждой пустой ячейки запоминают возможные варианты, проверка производится вышеописанной функцией за O(N). Работа с std::unordered_map производится за константное время. Далее, если есть уникальные варианты, они записывается в соответствующие ячейки. Следовательно, верхняя оценка сложности составляет O(N^3).
Оценка использования памяти
Каждый из способов проверки (строки, столбца и квадрата) требует N объектов для хранения. Значит функция проверки клетки XY требует места для хранения 3N промежуточных и N итоговых объектов.
Стратегия 2. Группы кандидатов
Подсказка 2.1. Скрытые пары, тройки, четвёрки
То же самое если три цифры-кандидата встречаются только в трёх клетках одной строки/столбца/малого квадрата.
Подсказка 2.2. Открытые пары, тройки, четвёрки
5 комментариев:
Штиф Васлер Клёво) Сами делали? NMitra Угу, муж купил судоку и оставил в туалете :) Есть ещё сложные методы решения, но их, кроме парочки, запомнить тяжеловато и встречаются они довольно редко. Поэтому решила их не использовать. Unknown Эээ. не понял решения своего введённого варианта.
Как-то поменялись цифры: метод1, метод2, и бац - решение готово.
И как оно готово?
NMitra :) Что за пример? Igor A. В разных примерах. Но вроде разобрался.
Просто для "не совсем специалистов" не совсем понятен и итог, выдаваемый практически сразу - без промежуточных шагов ("тут одинаково - значит тут стираем - тут остается только это. ") и без особых комментариев.
Ну да ладно. Это же не обучающая программа :)
Спасибо.
Стандартные методы, благодаря которым вы решите головоломку судоку.
Судоку — достаточно популярный вид досуга, который имеет различные стратегии решения и, как результат, оказывается под силу далеко не всем. Поэтому, прежде чем вооружиться карандашом, необходимо точно понимать, что судоку — это намного больше, чем просто запись чисел в строки и колонки. Процесс решения головоломки требует логики и знаний техник, а не догадок и предположений. Если вы только учитесь играть в судоку или уже считаете себя судоку-мастером, следующие советы помогут вам разгадать даже самую сложную головоломку на раз-два.
Что требуется, чтобы решить головоломку?
Вы можете перечитать все известные советы по разгадыванию судоку, но для того, чтобы стать настоящим мастером головоломки, вам нужно больше, чем понимание правил и стратегий игры. Как правило, лучшие игроки в судоку знают, множество секретов.
Можно ли разгадать судоку путем догадок?
Вы, конечно, можете решать судоку путем догадок, но, если ваши предположения неверны и при этом вы зайдете слишком далеко, рано или поздно вы попадете в тупик, и придётся начинать с начала.
Базовая техника
Метки карандашом
Это очень простая стратегия, которая поможет вам решить головоломку. Ее суть: вы используете технику карандашных пометок, вписывая возможные варианты чисел в каждую клетку. Затем анализируете окружающие колонки, строки и блок и исключаете неверные варианты для одной ячейки, оставляя только одно подходящее число.
Если вы только знакомитесь с судоку, скорее всего, вы ничего не поняли. Но как только вы наберетесь опыта и освоите эту технику, вы сможете попробовать решить самые сложные варианты головоломки.
Что такое уникальный прямоугольник в судоку?
В некотором роде это один из спорных моментов в судоку. Речь идет об уникальном прямоугольнике - ситуации, в которой у головоломки могут быть два разных решения. Уникальный прямоугольник состоит из четырех ячеек, которые занимают ровно две строки, два столбца и два поля. У всех четырех ячеек остались одни и те же кандидаты (числа), которые подходят в разные места.
Читайте также: