Как решать судоку
Судоку, или магический квадрат, — это цифровая головоломка, решать которую надо на специальном игровом поле.
Классическое поле представляет собой расчерченный квадрат размерами 9 на 9 клеток. Большая фигура, в свою очередь, состоит из девяти малых, размерами 3 на 3 клетки каждая.
Иллюстрация: Анна Гуридова / Лайфхакер
В каждой строке и столбце цифрами заполнены лишь несколько клеточек. Задача играющего — выяснить, каких цифр не хватает, и правильно расположить их во всех пустых ячейках квадрата.
Эксперты утверждают , что существует 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 по остаточному принципу ставим в единственную свободную ячейку — в центральном, втором столбце:
Иллюстрация: Анна Гуридова / Лайфхакер
Затем переключитесь на следующий малый квадрат с небольшим количеством незаполненных ячеек.
Как разгадывать судоку: правила и секреты, как играть, способы и стратегии решения
Люди придумали огромное количество головоломок, загадок, которые тренируют мозг. Японские судоку – популярные задачки, эффективно прокачивающие извилины. Кроме необходимости обдумывать большое количество вариантов расположения цифр, необходимо делать это на несколько шагов вперед. Головоломка не позволяет мозгу расслабиться. В материале рассмотрены главные способы разгадывания судоку. Это поможет как новичкам, так и опытным фанатам задач.
Содержание статьи:
История возникновения судоку
Многие считают, что занятие произошло из Японии. Это верно лишь отчасти. 300 лет тому назад математик из Швейцарии Леонард Эйлер в ходе расследований изобрел увлекательную загадку под названием «латинский квадрат». На ее основе в 70-х годах в Америке придумали квадраты-головоломки с цифрами.
Из США они распространились в Японии. Там родилось их название, сохранившееся до сегодняшнего дня – судоку. Также именно в этой стране они приобрели неожиданную популярность. Это случилось в середине 1980-х годов. Из Японии головоломка стала путешествовать по всему миру, и добралась до России. В 2004 году судоку появились в британских газетах, спустя год стали выпускать электронные вариации головоломки.
Виды судоку
Сначала появилась классическая версия, затем игру модернизировали и придумали другие вариации:
- Классическая головоломка. Игровое поле представляет собой большой квадрат, поделенный на 9х9 клеток.
- Судоку-пазл. В нем поле представлено не в виде квадрата, а в произвольной форме.
- Диагональные судоку. В них цифры не должны повторяться дополнительно и по диагонали. Эта игра имеет подвиды.
- Гигантские судоку. Головоломки размером от 12х12 до 25х25.
- Головоломка-произведение. В ячейках обозначено произведение чисел.
- Судоку чет-нечет. Смысл заключается в том, что в конкретные клетки ставят только четные или нечетные цифры. Это служит подсказкой для игрока.
- Судоку-суммы состоят из блоков, в которых стоит сумма цифр, находящихся в данной области.
- Головоломка «больше-меньше» содержит знак, который указывает на соседнюю клетку.
- Самурай представляет собой сочетание из двух, трех, четырех и более судоку, которые объединены общей зоной. Их решение связано друг с другом.
Существует еще одна разновидность – сумдоку. Иногда ее называют судоку-киллер или убийца. В данной игре игровое поле рисуется так же, как в традиционной головоломке. Но дополнительным решением стало использование цветовых блоков, для каждого из которых обозначена сумма значений. И в данной игре цифры могут повторяться.
Термины в игре с расшифровкой
- Клетка или ячейка – элемент головоломки, в котором должна стоять любая цифра от 1 до 9. Каждая клетка принадлежит трем группам – строке, столбцу и сегменту.
- Строка или ряд – 9 клеток идут по горизонтали.
- Столбец или колонка – включает в себя 9 ячеек, расположенных по вертикальной линии.
- Область, блок или квадрат – зона, состоящая из 3х3 клеток. Всего в судоку 9 блоков.
- Кандидаты – вероятные цифры, допустимые в клетке. Их обозначают маленьким шрифтом в углу. Когда все кандидаты исчезают в ходе игры, и остается одно значение, оно признается единственно верным.
Правила игры в судоку
Игровое поле головоломки занимает мало пространства, в отличие от кроссвордов и сканвордов. Оно включает в себя 81 ячейку. Они разбиты на маленькие блоки размером 3х3 см. Поле легко помещается на простом тетрадном листе.
Игровое поле судоку
В большой квадрат выборочно внесены цифры в некоторые клетки. Смысл задания заключается в том, что необходимо заполнить недостающие пустые клеточки. Правила достаточно просты, что исключает множественные решения.
В каждой колонке или ряду должны быть проставлены цифры от 1 до 9. Также показатели не повторяются в пределах одного блока (столбика, строки или квадрата). Судоку разделяются на несколько уровней сложности – в зависимости от количества заполненных цифр. Чем их меньше, тем сложнее игра. Обычно существует пять уровней, самый трудный могут решить только опытные игроки.
В каждом выделенном блоке не должно быть повторяющихся цифр
В разгадывании судоку используют несколько методов решения. Самые простые головоломки разгадывают методом дедукции. Существует как минимум одна клетка, в которой ставится определенная цифра, и только она туда подходит.
Судоку сложных уровней можно разгадывать часами. Правильно построенная задача предполагает только один способ ее решения. При внесении цифры стоит помнить, что ее можно написать в клетку только, если она отсутствует в горизонтальной и вертикальной линии и в малом квадрате, состоящем из 9 ячеек.
Как играть в судоку
Существуют некоторые рекомендации и советы, как быстро и находчиво отгадывать головоломки:
Первый совет — никогда не дублировать цифры.
Вверху в левом блоке, который обведен в синий квадрат, заполнены семь цифр из 9. В нем отсутствуют числа 5 и 6. Понимая, каких значений не хватает, игрок может воспользоваться методикой исключения и включить дедуктивное мышление. Такие способы помогут определить, какие конкретно синглы должны содержаться в пустых ячейках.
К примеру, в квадратике четко установлено, что недостает 5 и 6, но посмотрев на соседние столбцы, строчки и блоки, наверняка сказать нельзя, где и какая цифра должна стоять. Ввиду этого игрок пропускает квадратик и приступает к заполнению следующего, и так далее по цепочке.
Еще один совет гласит – не стоит гадать. Судоку – логическая головоломка, и не нужно выдвигать предположения, где поставить цифры. Если точно неизвестно о расположении значения, то переходят на другую область – строку, столбик или квадрат. Сканируют до тех пор, пока не обнаружится очевидность постановки той или иной цифры.
Приступая к разгадыванию судоку, специалисты рекомендуют вооружиться простым карандашом. Цифру в любой момент можно стереть простым ластиком. Если использовать ручку, то при ошибке игра будет испорчена. Но ее можно самостоятельно переписать на тетрадный лист. С опытом и большим количеством разгаданных головоломок придут навыки и новые варианты решения задачи.
Чтобы не запутаться, рекомендуется карандашиком подписывать в пустых клетках цифры-кандидаты, которые теоретически могут быть в них. Для примера возьмем одну ячейку и посмотрим, как мы получили вероятные цифры для нее:
Нам надо узнать вероятные цифры для фиолетовой ячейки. Для этого мы смотри на ее столбец, строку и квадрат.
- В столбце у нас имеются цифры 6, 8, 3, 7 и 2. Следовательно, их уже нельзя вписать в нашу ячейку.
- В строке есть цифры 8, 2 и 3. Они тоже нам не подходят.
- В квадрате есть еще цифры: 8, 6 и 3.
Далее мы смотрим, какие цифры остались, и вписываем их в ячейку: 1, 4, 5 и 9. Их не было ни в одном их смежных блоков. Таким образом, мы знаем, что одна из этих цифр точно будет находиться в данной ячейке. Остается только различными методами исключить оставшиеся три неверные цифры.
Для этого имеются различные способы решения судоку. О них мы поговорим ниже.
Способы и методы решения судоку
Опытным и логическим путем установлены определенные методы разгадывания головоломки. Ниже представлены наиболее популярные.
Единственно возможные варианты (одиночка, последний герой)
Они определяются после исключения цифр, которые внесены в игровое поле. На таком принципе построены простые судоку. Данная отгадка предполагает 2 вида синглов – скрытые и очевидные.
Очевидные варианты рассмотрены на примере ниже.
В данном примере цифра «4» — единственно верный вариант, так как на перекрестии везде содержатся все остальные цифры
Если ответ на разгадку однозначен и не вызывает никаких сомнений, то сингл является очевидным. Чтобы понять, что написать в желтой клетке, нужно посмотреть на сопряженные с ней строку, столбец и квадрат:
- В строке уже имеются цифры 9, 1, 6 и 5. Следовательно, эти цифры никак не могут быть в искомой клетке.
- В столбце есть цифры 2, 3, 8. Они также уже не подходят.
- В квадрате имеются цифры 7 и уже знакомые нам 8 и 6.
- Следовательно, единственной отсутствующей цифрой на данном перекрестии является 4.
Скрытые варианты
На примере в выделенной желтым клетке имеется единственная не повторяющаяся во всем блоке цифра — 8. Следовательно, именно она должна быть вписана в клетку.
Данная отгадка предполагает, что число можно вписать в ячейку, если другое расположение недопустимо. Установить, в какой клетке должен стоять сингл, можно после расстановки предполагаемых вариантов и выявлений числа, которое больше нигде не дублируется. Руководство по разгадке судоку:
- в 7 и 9 строчках изначально стоит «8»;
- также 8 присутствует в столбце А;
- в нижний правый квадрат можно вписать 8 только в единственную ячейку – В8, потому другие варианты исключены.
Указывающие пары
Если в одном блоке (столбце, квадрате или строке) в «вероятных» вариантах присутствуют одинаковые цифры, то их можно вычеркнуть из сопряженного блока (столбца, квадрата или строки соответственно).
Иногда такой способ бывает полезным, в особенности, когда игрок находит несколько таких совпадений, как на картинке ниже:
Здесь мы смотрим на квадрат номер три (выделен бледно-желтым). В нем точно ДОЛЖНА быть цифра 3, так как в других клетках квадрата, помимо строки B, ее нет даже в вероятных. Следовательно, можно убрать все остальные тройки на данной строке, то есть B1, B2 и B3.
То же самое с квадратом 8 (выделен светло-голубым). В нем обязательно должна быть цифра 2, и как раз есть два варианта в одной строке G (G4, G5). Значит можно убрать все остальные двойки на данной строке вне этого квадрата (то есть можно убрать G2).
Группы кандидатов
Скрытые пары, тройки и четверки — если 2 цифры находятся только в двух ячейках в одной вертикали, горизонтали или блоке, то другие числа в этих двух клетках исключаются.
В белено-желтых и оранжевых клетках — возможные цифры. Например, 13 — значит либо 1, либо 3; 169 — либо 1, либо 6, либо 9 и т.д.
В 9 строку можно ввести только одну 2. Это объясняется тем, что в ячейке 8 столбика могут находиться только 6 и 9. Аналогично вычисляются цифры, когда 3 кандидата стоят только в трех ячейках строки, столбца или блока.
Открытые двойки, тройки, четверки
Правило следующее – если в двух ячейках по горизонтали, вертикали или в маленьком квадрате используются лишь 2 одинаковые цифры и больше ничего, то эти же кандидаты из других клеток строки, столбца или блока можно смело исключать. Изначально в примере было так.
Потом приобрело вид:
В третью строчку можно вписать одну четверку, поскольку в 8 столбике ее не может быть.
Запертая цифра в квадрате
Теперь рассмотрим следующий пример.
На игровом поле синим фоном выделен квадратик. Кандидаты на место четверки обозначены зеленым цветом. Эти клетки находятся по одной вертикальной линии. Если на отрезке, выделенном оранжевым фоном, будет стоять четверка, значит, в синем блоке ее некуда вписать. Поэтому исключают 4 из оранжевых клеток.
Далее рассмотрен пример для цифры 2.
В третьем блоке сверху зеленым цветом выделены кандидаты, в которых будет подбираться двойка.
Запертая цифра в строчке
Эта головоломка похожа на вышеописанную, но имеется различие. В синей строке кандидаты на 7 расположены в пределах одного квадрата. Из всех остальных ячеек фигуры, обозначенных оранжевым тоном, семерки исключаются.
Закрытый сингл в столбике
Как и на прошлом игровом поле, в столбике кандидаты на восьмерку находятся на территории одного квадратика. Аналогичным образом цифра 8 удаляется из остальных ячеек.
Пошаговое решение судоку с объяснением
Далее представлен полный пример, как нужно играть в головоломку, от начала до конца. В судоку не обозначены строки и столбцы, но здесь они необходимы для более понятной картинки решения задачи.
Сначала в ячейки вписывают всех кандидатов, цифры ставят маленькими и в уголках клетки.
Следующий шаг – обозначить единственных кандидатов. На картинке они выделены серым фоном. А также их вычеркивают из других клеток в столбце, строке и блоке. Их выделили желтым цветом.
Проведя процедуру, заметно, что снова образовались открытые и единственные кандидаты. В первой строчке двойка присутствует только в ячейке В1. Ее так же вычеркивают из клеток-кандидатов.
В итоге получается такое поле.
Следующий этап – отыскать скрытых кандидатов. Они обозначены серыми клетками. Их удаляют из кандидатов в другие ячейки столбца, строки и блока. Они выделяются желтым фоном.
В определенных местах снова появились скрытые кандидаты. В первом ряду цифра 5 присутствует только в ячейке С1. Их опять вычеркивают из кандидатов в другие места строк, столбцов и квадратов.
Далее рассматривают строчку Н5. В пятой строке двойка встречается только в одной ячейке. Затем продолжают анализировать судоку относительно клетки.
После этого в некоторых местах остались единственные допустимые цифры. Их нужно удалить из других вертикальных, горизонтальных линий и квадратиков.
Остается заключительный этап – вписать открытые цифры и закончить решение головоломки.
Это традиционный способ решения судоку. Игрок может начать заполнение с других ячеек и цифр, как ему удобнее. Данный пример наглядно продемонстрировал, что головоломка имеет единственно правильную разгадку и отыскать ее нужно логическим мышлением, а не перебиранием и гаданием.
Полезные видео-ролики о судоку:
Небольшие лайфхаки для судоку от опытных игроков
Сначала рекомендуется проверить, присутствуют ли на игровом полотне квадратики с одной пустующей клеткой. Если таковые существуют, то нужно их заполнить. К примеру, в квадрате указаны цифры 1,3,5,8,9,4,7,6. Не хватает одной двойки, ее вписывают в пустое место квадрата.
Далее зрительно проверяют каждую колонку и ряд на предмет отсутствия в них всего одного числа. При наличии выясняют, какое значение должно встать в клетку. Пример – в столбике расположены цифры – 2,9,4,3,1,8,6,7. Сразу становится понятно, что в данном случае нужно написать пятерку.
Если в двух больших квадратах ряда располагается, например, шестерка, то ее также нужно проверить в третьем квадрате. С помощью указательного пальца проводят по строкам с располагающимися на них шестерками, поскольку в третьей фигуре на их месте она не может находиться.
В красных ячейках третьего квадрата точно не может быть цифры 6.
Эксперты рекомендуют рассматривать сразу группу ячеек. Если игрок увидит большое скопление одинаковых цифр на полотне, то это поможет заполнить квадратики, в которых не хватает этих позиций.
К примеру, на поле присутствует много семерок. Используют вышеописанную методику просмотра полотна, чтобы внести цифру 7 в недостающие клетки.
Постоянно нужно перепроверять клетки. По ходу разгадывания чисел нужно просматривать поле и возвращаться к тем элементам, которые были раньше незаполненными.
Методы решения судоку для продвинутых игроков
В данном разделе описаны сложные технологии, которые пригодятся опытным и отъявленным любителям судоку:
- Анализируют блоки из трех больших квадратов в строке или столбце. Выбирают одну цифру и выясняют, можно ли ее разместить во все 3 квадрата. К примеру, игрок рассматривает восьмерку. Нужно узнать, в каких колонках и рядах она уже находится, и применить эту информацию для анализа трех квадратов. В процессе заполнения клеток другие пустые ячейки постепенно находят свое решение.
- Проверяя пустые клетки, стоит использовать ту же технологию, что и при внесении цифр.
- Некоторые эксперты начинают разгадывать с цифры 1 и направляются по линиям, потом – по блокам. Так человек не запутается и предостережет себя от многих ошибок.
- Всегда проверяют, какой цифры недостает там, где осталось много пустот.
- Если зашли в тупик, и появилось много пустого пространства, нужно мысленно поделить квадрат на отрезки. Важно поразмыслить, какие цифры могут туда встать, потом станет понятно, какие значения будут располагаться в других квадратиках на соседних линиях.
Метод «сокращение» предполагает, что с каждым шагом и разгадыванием количество предполагаемых цифр сокращается, а решение базируется на методике «одиночка». Способ «сокращение» выделяется в самостоятельное звено, поскольку пользователь должен провести тщательный анализ всех колонок, рядов и квадратов с постепенным исключением синглов. Как итог – единственно правильное решение.
Усложненный метод «сокращения». Согласно столбцу 8, четверки могут находиться лишь в квадрате 3. Убираем лишние четверки в квадрате, и находим, что в C7 остается только 2
Цветовой метод – стратегия, которая незначительно отличается от вышеописанной. Ее смысл заключается в том, что клетки или числа окрашены в разные оттенки. Такое решение позволит игроку визуализировать весь ход разгадывания, но не каждый человек сможет ее использовать. Некоторые люди сбиваются, и у них снижается сосредоточенность.
Для правильного использования цветового окрашивания рекомендуется взять 3-4 оттенка и заполнять ими одинаковые варианты в разных колонках, рядах и квадратиках. Также другим тоном выделяют спорные клетки.
Чтобы быстрее освоиться и понять технологию разгадывания, стоит взять ручку и бумагу. Это поможет потренироваться, задействовать свой мозг в отличие от электронных вариантов, содержащих подсказки.
Еще один любопытный, но, в целом, бесполезный способ решения судоку – метод проб и ошибок. Пользователь выбирает пробное число из 2 или 3 вероятных. Далее проверяет все блоки. Недостаток технологии состоит в том, что человек должен использовать компьютер. На бумажном листке не получится вернуться к исходным данным.
Методология «рыба меч» основана на следующем правиле: если кандидат располагается в первой, второй и третьей колонке или только в трех рядах, то в других строчках этот сингл можно вычеркивать. Подробное описание шагов:
- Отыскивают строки, чтобы кандидат в них присутствовал не выше 3 раз. Но в то же время он включается в три столбика.
- Теперь выбрасывают кандидата из других строк и столбцов, в которых его не будет.
- Такая же цепочка размышления применяется в трех колонках, когда сингл присутствует в трех рядах.
Наглядно рассмотрим задачку. В трех рядах – в 3,5 и 7 кандидат пятерка обнаружена не более трех раз. Эти клетки заполнены желтым фоном. Кроме того, ячейки входят в три столбца – 3,4 и 7.
Техника решения «рыба меч» предполагает, что из других вертикальных клеток кандидата пятерку можно смело вычеркивать. Они обозначены зеленой заливкой.
В другой задачке, указанной ниже, аналогичным образом используется методы «рыба меч», но уже в отношении трех колонок. В поле понятно, что кандидата единицу нужно удалить из клеток зеленого оттенка.
Не нужно форсировать события и торопиться решить задачку. Игра предполагает усердное размышление, отбор и анализ выполнения. Сложные комбинации необходимо разгадывать обдуманно и не спеша. Суть игры – не слепое угадывание, а долгая, интересная цепочка умозаключений, приводящая к развитию логики. С опытом придет глубокое понимание такой, казалось бы, незамысловатой игры.
Электронные варианты судоку
Игра судоку в электронном исполнении предоставляет игроку возможность самому выбрать уровень сложности в зависимости от своего опыта и мастерства. Также ему предложено разгадать другие варианты судоку.
Игру скачивают на телефон, планшет или ноутбук, играют в режиме онлайн. Загрузив головоломку, пользователь увидит игровое поле, в клетках которого уже обозначены некоторые цифры. Их нельзя менять, удалять или переносить. Синглы заложены программой.
Взглянув на полотно, игрок должен решить, с чего начать отгадывание судоку. Обычно определяют строчку, колонку или блок, которые заполнены цифрами по максимуму.
Часто электронные вариации предлагают воспользоваться подсказками. Их количество достигает нескольких штук за одну игру.
Судоку: так сколько же их? Часть 1/2
Привет Хабр! Данная публикация возникла после просматривания этого поста, в котором автор пытается посчитать количество различных судоку. Желая более точно разобраться в вопросе, я за пару минут нагуглил точный ответ, приведенный в данной статье. Текст этой статьи мне показался интересным сам по себе, поэтому я решил сделать перевод (в довольно вольном стиле).
К сожалению, оригинал данной статьи написан для дебилов очень широкого круга читателей, в том плане, что тема рассматривается не очень глубоко, но довольно подробно. При этом поясняется только общий подход к решению задачи, без технических деталей, и, фактически, обрывается на самом интересном месте формулировкой «ну а дальше они посчитали на компьютере». В итоге я немного дополнил изложение своими комментариями: они либо отмечены курсивом, либо спрятаны под спойлеры. В них раскрываются некоторые технические моменты более подробно. Возможно, пост вместе с этими комментариями суммарно тянет на полноценную статью, нежели чем на просто перевод, но я решил оставить все как есть (на самом деле, я не нашел кнопки перевода перевода обратно в обычную статью, а создавать новую публикацию только ради этого было лень).
Введение
Судоку — это головоломка, которая завоевала мировую популярность с 2005 года. Для того, чтобы решить судоку, нужны только логика и метод проб и ошибок. Сложная математика появляются лишь при более пристальном рассмотрении: для подсчета количества различных сеток судоку нужна комбинаторика, чтобы определить количество этих сеток без учета всевозможных симметрий понадобится теория групп, а для решения судоку в промышленных масштабах — теория сложности алгоритмов.
Впервые головоломка судоку в известном нам виде была опубликована в 1979 году в американском журнале Dell Magazines под названием «Numbers in Place» за авторством Говарда Гэрнса (Howard Garns). В 1984 году судоку впервые было опубликовано в Японии в журнале Nikoli. Именно Маки Кадзи (Maki Kaji), президент компании Nikoli (которая, кстати, специализируется на всяких пазлах и логических играх), дал головоломке название «судоку», что в переводе с японского означает «одинокие числа». Когда игра стала популярной в Японии, на нее обратил внимание новозеландец Вэйн Гулд (Wayne Gould). Вэйн написал программу, которая могла генерировать сотни судоку. В 2004 году он опубликовал некоторые из этих пазлов в Лондонских газетах. Вскоре после этого лихорадка судоку охватила всю Англию. В 2005 году головоломка стала популярной в Соединенных Штатах. Судоку стали регулярно публиковаться во множестве газет и журналов, радуя людей по всему миру.
Классическая версия судоку имеет вид квадратной таблицы 9×9, итого — 81 ячейка. Эта таблица разделена на 9 блоков 3×3. В некоторых ячейках находятся числа из множества <1,2,3,4,5,6,7,8,9>(эти числа нельзя менять), остальные ячейки пусты. Цель игры — заполнить все пустые ячейки, используя только вышеупомянутые девять чисел, так, чтобы на каждой горизонтали, на каждой вертикали, а также в каждом блоке каждое из чисел присутствовало бы ровно один раз. Мы будем называть эти ограничения Главным Правилом игры.
Описанные выше правила относятся к судоку порядка 3. В общем же случае, судоку порядка n — это таблица n 2 ×n 2 , разделенная на n 2 блоков размера n×n каждый. И все это нужно заполнить числами от 1 до n 2 так, чтобы выполнялось Главное Правило.
Например, на следующей картинке можно видеть пример судоку, а также его решение:
Подходы к решению
Говорят, для решения судоку не нужна математика — это не правда. Это на самом деле означает, что не нужна только арифметика. Головоломка не зависит от того факта, что мы используем цифры от 1 до 9. Мы можем с легкостью заменить эти 9 цифр на буквы, цвета или сорта суши. Фактически, для решения судоку нужно применять такой вид математического мышления, как логическая дедукция.
Самая простая эвристика для решения судоку — сначала для каждой пустой клетки выписать всевозможные числа, которые туда можно записать, не противореча Главному Правилу, ориентируясь по числам, данным изначально. Если для какой-то ячейки возможен только один вариант — именно его нужно записать в эту ячейку.
Другой подход для решения — выбрать число, а после этого — строку, столбец или блок. После этого следует рассмотреть все позиции в строке/столбце/блоке и проверить, можно ли туда поместить выбранное число, не нарушая Главного Правила. Если число подходит только для одной позиции — можно смело его туда вписать. Как только это будет сделано, выбранное число может быть исключено из возможных вариантов для всех остальных пустых ячеек в соответствующих строке, столбце и блоке.
Обычно этих двух правил не достаточно для полного заполнения сетки судоку. Часто требуется более сложные методы для достижения прогресса, а иногда требуется перебирать варианты и откатываться в случае неудачного выбора. Более изощренная стратегия состоит в том, чтобы рассмотреть пары или тройки ячеек в строке, столбце или блоке. Может оказаться, что для рассматриваемой пары ячеек подходят только два числа из группы, но непонятно какое из них в какую из этих двух ячеек поместить. Однако, из этого можно заключить, что числа из данной пары не могут появиться на каких либо других местах в рассматриваемой группе. Это уменьшает количество вариантов в других пустых ячейках и помогает подобраться ближе к решению. Аналогично, если тройку чисел можно поместить только в определенную тройку позиций (непонятно в каком порядке), то эти три числа можно исключить из рассмотрения для всех остальных ячеек по соседству.
Заметим, что кроме данных эвристик существует множество других. Вы даже можете придумать свои собственные стратегии решения.
Когда ни одна из простых эвристик не помогает — нужно попробовать выбрать пустую ячейку с наименьшим числом вариантов и попробовать один из вариантов. В случае получения противоречия (повторяющиеся числа в строке, столбце или блоке) следует отменить все свои действия до момента выбора и попробовать другой вариант.
Упражнение: Попробуйте применить описанные выше методы на этом судоку:
В интернете можно найти множество других судоку любой сложности и на любой вкус.
Так сколько же их?
Это очень интересный вопрос. Так сколько же различных судоку 9×9? Сколькими способами можно заполнить таблицу 9×9 числами от 1 до 9 так, чтобы выполнялось Главное Правило? Мы опишем метод, с помощью которого Бертрам Фельгенхауэр (Bertram Felgenhauer) и Фразер Джарвис (Frazer Jarvis) посчитали это количество в начале 2006 года.
Сначала договоримся об обозначениях. Будем называть полосой тройку блоков, центры которых расположены на одной горизонтали. Итого мы имеем три полосы — верхнюю, нижнюю и среднюю. Стеком будем называть тройку блоков, центры которых расположены на одной вертикали. Стеков, как и полос, у нас тоже три — левый, правый и средний. Ячейку на пересечении i-й строки и j-го столбца будем обозначать как (i,j).
Приготовления окончены и мы готовы посчитать число N — количество различных судоку. Сперва обозначим все блоки судоку следующим образом:
Сколькими способами можно заполнить блок B1? Поскольку для блока B1 у нас 9 чисел, одно для кажой ячейки, в первую из них мы можем записать одно из чисел одним из 9 способов. Для каждого из этих 9 способов у нас есть 8 способов разместить одно из оставшихся чисел ровно 8 способами. Для третьей ячейки для каждого из этих 9×8 способов количество вариантов идти дальше — ровно 7. Мы, по сути, пытаемся построить всевозможные перестановки длины 9 и нужное нам количество способов заполнить блок B1 равно количеству этих перестановок — 9! = 9×8×7×6×7×4×3×2×1 = 362880. Начиная с судоку, в котором блок B1 заполнен определенным образом, мы можем получить судоку с любым другим заполнением блока B1 с помощью простого переобозначния чисел (вспомним, что нам неважно какие числа где находятся — главное знать где одинаковые числа, а где различные). Поэтому, для простоты, заполним блок B1 числами от 1 до 9 в порядке, показанном на рисунке:
Пусть количество судоку, в которых блок B1 заполнен именно так, как на картинке, равно N1. Общее количество судоку будет N1×9!, отсюда N1=N/9!.
Рассмотрим все способы заполнить первую строку в блоках B2 и B3. Поскольку 1, 2 и 3 уже присутствуют в блоке B1, эти числа больше не могут быть использованы в данной строке. Только числа 4, 5, 6, 7, 8 и 9 из второй и третьей строк блока B1 могут быть использованы в первой строке блоков B2 и B3.
Упражнение: Перечислите все возможные способы заполнения первой строки в блоках B2 и B3 с точностью до перестановки цифр. Подсказка: всего имеется десять способов разбиения шести чисел на две части по три, а меняя B2 на B3, мы получаем еще десять способов. Итого — двадцать.
Назовем два из этих вариантов чистыми верхними строками: когда числа <4,5,6>, как во второй строке блока B1 располагаются вместе в B2, а числа <7,8,9>, как в третьей строке блока B1, располагаются вместе в B3 (ну и случай, когда B2 и B3 поменяны местами). Все остальные способы — это смешанные верхние строки, поскольку там в первой строке B2 и B3 множества <4,5,6>и <7,8,9>смешаны друг с другом.
Ну так вот, у нас есть эти двадцать способов, и мы хотим узнать, как заполнить остальные ячейки в первой полосе.
Упражнение: Подумайте немного о том, как можно заполнить первую полосу начиная с чистой верхней строки 1,2,3;<4,5,6>; <7,8,9>(мы пишем a,b,c, если три числа идут в зафиксированном порядке и
Помните, мы не меняем порядок в блоке B1, поскольку мы уже учитываем колчество сеток, которые получаются путем перемешивания девяки чисел в B1.
Оказывается, для чистой верхней строки 1,2,3;<4,5,6>; <7,8,9>— ровно (3!) 6 способов, поскольку нам обязательно нужно поместить <7,8,9>; <1,2,3>на вторую строку в блоках B2 и B3, а <1,2,3>; <4,5,6>— на третью строку. После этого мы можем произвольным образом менять местами числа в этих шести тройках в B2 и B3 для того, чтобы получить все конфигурации. Для второй чистой верхней строки ответ тот же, поскольку все, что мы меняется местами — это блоки B2 и B3.
Для случая смешанных верхних строк все неммого сложнее. Давайте рассмотрим верхнюю строку 1,2,3;<4,6,8>;<5,7,9>. Далее первую полосу можно заполнить так, как показано на картинке ниже, где a, b и c — это числа 1, 2, 3 в любом порядке.
Как только число a выбрано, b и c — это оставшиеся два числа в любом порядке, поскольку они находятся в одних и тех же строках. Для a три способа выбора, а затем мы можем просто перемешать числа в шести тройках в B2 и B3 в любом порядке — и всегда будет получаться подходящая первая полоса. Итого, количество конфигураций — 3x(3!) 6 . Несложно показать, что в оставшихся семнадцати способах мы получим то же самое число.
Теперь мы можем посчитать общее количество различных верхних полос для фиксированного блока B1: 2х(3!) 6 +18x3x(3!) 6 =2612736. Первая часть суммы — это количество полос для чистых верхних полос, а вторая — для смешанных.
Вместо того, чтобы посчитать количество разничных полностью заполненных сеток для каждого из этих 2612736 вариантов, Фельгенхауэр и Джарвис сначала определили у каких из этих верхних полос одно и то же количество вариантов полного заполнения. Этот анализ сокращает количество полос, которые нам нужно будет рассмотреть для дальнейших рассчетов.
Есть несколько операций, которые оставляют количество полностью заполненных сеток неизменным: переназначение чисел, перестановка любых блоков в первой полосе, перемешивание столбцов в любом блоке, изменение порядка трех строк в полосе. Как только какие либо из операций меняют порядок чисел в B1 — мы просто переназначаем числа так, чтобы привести блок B1 к стандартному виду.
Когда мы меняем местами блоки B1, B2 и B3 — количество заполнений сеток сохраняется, поскольку мы начинаем с корректной сетки судоку, и единственный способ сохранить корректность в дальнейшем — это поменяить местами B4, B5, B6 и B7, B8, B9 так, как мы поменяли B1, B2, B3. В итоге все стеки останутся теми же самыми. Другими словами, каждое корректное заполнение всей сетки для одной верхней полосы дает ровно одно корректное заполнение сетки для другой верхней полосы, полученной перемешиванием блоков B1, B2, B3.
Упражнение: Убедитесь сами, что если поменять местами блоки B2 и B3 в следующей сетке, то единственный способ сохранить сетку корректной — это поменять местами B5 и B6, а также B8 и B9. Стеки остаются те же самые, но меняются их расположения.
Упражнение: Пусть у вас есть корректно заполненная сетка судоку и вы меняете местами некоторые столбцы в каком либо из блоков B1, B2 или B3. Что нужно дополнительно сделать с остальными столбцами, чтобы сетка судоку осталась корректной? Например, если вы поменяли местами первый и второй столбцы в блоке B2, как бы вы исправили оставшуюся часть сетки так, чтобы она все еще удовлетворяла Главному Правилу?
Последнее упражнение говорит нам о том, что каждое заполнение первой полосы дает нам уникальное заполнение для такой первой полосы, в которой столбцы упорядочены определенным образом внутри блоков.
Это наблюдение позволяет нам уменьшить количество первых полос, которые нам нужно рассмотреть. Согласно Фельгенхауэру и Джарвису, мы перемешиваем столбцы в блоках B2 и B3 таким образом, что значения в самой верхней строке идут в возрастающем порядке. После этого мы возможно меняем местами блоки B2 и B3 так, чтобы самое первое число в блоке B2 (левое верхнее) было меньше, чем самое первое число в блоке B3. Эта операция называется лексикографической редукцией. Поскольку для каждого из двух блоков у нас ровно 6 различных перестановок и всего 2 способа упорядочить блоки друг относительно друга, лексикографическая редукция говорит нам, что для любой первой полосы можно построить класс из 6 2 ×2=72 первых полос с одним и тем же количеством полных заполнений сеток (и для всех элементов из каждого класса это построение будет приводить к этому же классу). Таким образом, нам теперь нужно рассмотреть только 2612736/72=36288 первых полос.
Думаю, здесь самое время начать писать код для того, чтобы сделать статью чуть более хардкорной. Мы собираемся проверить, что лексикографически редуцированных верхних полос, в которых блок B1 стандартный — ровно 36288 штук.
Для начала опишем структуру для нашей полосы (я, как обычно, пишу на C++):
В коде пояснений заслуживает разве что метод is_valid(): он проверяет, что Главное Правило для полосы выполняется. Если аргумент with_zeros равен true, то метод не принимает во внимание нули (а нулями мы будем обозначать ячейки частично заполненных полос, в которые пока еще не назначена ни одна цифра).
Код для генерации всех интересующих нас полос выглядит следующим образом:
Сначала мы подготавливаем starting_bands — полосы, в которых заполнен блок B1 и первые строки блоков B2 и B3. Их всего 10 штук, поскольку для поддержания лексикографического порядка мы не учитываем варианты, когда блок B2 «больше» блока B3. После этого мы простеньким перебором находим все искомые полосы. Выкладки, приведенные выше по тексту в коде не используются — они больше для «головы», чем для машины. Главное что числа в итоге сошлись. А сгенерированные полосы мы потом еще будем использовать в следующем спойлере.
Для каждого из этих вариантов рассмотрим всевозможные перестановки трех верхних блоков: их ровно 6. А для каждого из этих вариантов имеется 6 3 перестановок столбцов внутри всех блоков. После того, как мы все перемешали, вы переназначаем числа так, чтобы в блоке B1 они все шли в стандартном порядке. Мы также можем произвольно перемешать три верхние строки, после чего опять переназначить числа, чтобы блок B1 стал стандартным. После каждой из этих операций количество заполнение всей сетки для данной первой полосы останется неизменным. Фельгенхауэр и Джарвис при помощи компьютерной программы определили, что эти операции сокращают количество первых полос, которые имеет смысл рассматривать, с 36288 до всего лишь 416.
Упражнение: Рассмотрите определенную первую полосу. Проделайте над ней некоторые операции, которые сохраняют количество заполнений всей сетки судоку. Можете начать со следующего: поменяйте местами первую и вторую строки. После этого переназначьте числа в блоке B1, чтобы привести его к стандартной форме. Выполните лексикографическую редукцию.
Главное, на что следует обратить внимание: полоса, с которой мы начали, и полоса, которой закончили, имеют одинаковое количество заполнения всей сетки судоку. Поэтому вместо вычисления количества заполнений сеток для каждой полосы мы можем подсчитывать их количество только для одной из них.
Начиная с этого момента начинаются некоторые неочевидности — авторы оригинал предлагают поверить им наслово. Но мы не такие — мы будем писать код для того, чтобы удостовериться лично. А именно: сейчас мы будем проверять тот факт, что выполняя описанные выше операции, мы в итоге получим ровно 416 вариантов.
Для большей наглядности опишем что же мы сейчас будем делать: мы будем строить граф. Представьте себе, что каждая из лексикографически редуцированных полос — это вершина графа (т.е. у нас всего 36288 вершин). Когда мы применяем к полосе какую либо операцию (которая перемешивает числа, но не меняет количество итоговых сеток для данной полосы) — мы в нашем графе соединяем ребром начальную полосу и конечную. Ребра неориентированные, поскольку каждая из рассмотренных выше операций обратима — мы можем вернуть все взад делая действия в обратном порядке. Теперь давайте для каждой полосы применим всевозможные операции и проведем всевозможные ребра. Тогда, для любых двух вершин, соединенных цепочкой ребер, ответ будет одинаковый. Да и вообще — он будет один и тот же для всех вершин в одной компоненте связности. То есть, нам нужно посчитать количество компонент связности в полученном графе — и их должно оказаться ровно 416.
Сначала внесем модификации в структуру BAND:
Теперь мы можем нашу полосу лексикографически редуцировать (метод normalize()), а также делать все 3 операции, описанные выше. При применении операции создается копия объекта, затем к копии применяется операция, затем результат нормализуется (чтобы не выходить за пределы редуцированных 36288 полос).
Теперь мы можем посчитать количество компонент связности при помощи стандартного обхода в глубину. При этом граф явно не строится.
Операторы сравнения нужны для того, чтобы их мог использовать set. В итоге программа действительно находит ровно 416 компонент связности. В comp_sizes складываются размеры этих компонент, а в ident_bands — одна из вершин из каждой компоненты (полоса — представитель класса). Следует отметить, что получаемые компоненты не всегда имеют одинаковый размер. Например, программа выводит следующие размеры:
1 27 18 54 6 9 54 108 9 54 108 54 54 108 54 54 54 18 6 108 54 54 6 18 6 54 18 54 18 54 2 54 108 108 108 54 108 108 108 108 54 108 108 108 54 108 108 54 108 54 108 54 108 108 108 54 108 108 108 54 108 108 108 54 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 54 108 108 108 108 108 108 108 54 108 108 108 108 54 108 108 108 18 108 108 54 108 108 108 54 54 108 108 108 54 54 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 54 108 108 108 108 108 108 108 108 108 108 108 108 108 108 54 54 54 18 54 54 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 54 108 108 108 108 54 108 108 54 108 108 108 108 108 108 108 108 108 36 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 54 108 54 108 108 108 108 108 108 108 54 108 108 108 54 108 108 108 108 54 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 54 108 108 54 108 108 108 108 108 54 108 108 108 108 108 108 54 54 54 54 54 54 6 18 54 18 108 54 54 108 54 54 108 54 54 108 108 108 108 54 108 108 108 108 108 54 108 108 108 108 108 108 108 54 54 108 108 108 108 108 54 108 54 108 108 54 54 108 108 108 108 108 108 54 18 18 54 54 108 54 54 108 108 54 108 108 54 108 108 108 108 108 54 108 54 18 54 108 108 54 54 108 108 54 54 108 108 108 54 54 108 108 108 108 108 108 108 54 36 108 108 108 108 108 54 108 108 108 108 108 54 108 108 54 54 108 54 108 108 108 54 54 108 108 108 54 18 108 54 54 54 108 54 18 18 54 54 54 108 18 54 54 54 54 3 27 9 9
Ну и теперь, по сути, можно посчитать количество итоговых заполнений для каждого представителя, умножить на количество вершин в соответствующей компоненте и в конце все сложить. Но с этим пока не будем торопиться.
Существует еще несколько операций, которые сокращают количество сеток для рассмотрения. Если у нас есть пара чисел такая, что a и b находятся в одном столбце, причем a — на i-й строке, а b — на j-ой, и, ко всему прочему, есть такая же пара в другом столбце, причем для этого столбца a уже находится на j-ой строке, а b — на i-ой (т.е. эти четыре числа находятся в углах некоторого прямоугольника, и противоположные числа равны), то мы можем поменять местами числа в обеих парах и получить новую корректную полосу с тем же количеством конечных сеток. Например, в судоку, приведенном чуть выше, числа 8 и 9 в шестом и девятом столбцах формируют такую конфигурацию. Рассмотрев все возможные случаи, Фельгенхауэр и Джарвис сократили необходимое для рассмотрения число первых полос с 416 до 174.
Но и это еще не все. Они рассмотрели другие конфигурации одинаковых множеств (из трех и более чисел), лежащих друг напротив друга в двух различных столбцах или строках, которые можно поменять местами и ответ от этого не изменится. Это сокращает количество вариантов до 71, а если дополнительно рассмотреть эти варианты и применить там более сложные симметрии — количество полос для рассмотрения можно сократить до 44. И для каждой из этих 44 полос все остальные полосы в соответствующем классе имеют такое же количество полных заполнений всей сетки.
Давайте дополним нашу программу новыми операциями для того, чтобы получить улучшения до 174 и до 71 полосы. До 44 полос мы улучшать не будем — там все совсем сложно, да и внятной информации об этом очень мало. Фельгенхауэр и Джарвис в своей статье улучшают только до 71, а число 44 они приводят уже в конце после всех вычислений (впрочем, они также пишут, что там есть подходящие преобразования, чтобы получить искомые 44 полосы — об этом в конце данного спойлера).
Итак, завайте добавим операцию свапания двух пар чисел, которые располагаются в углах одного прямоугольника. К уже написанному коду это добавить очень просто:
Мы просто перебираем все прямоугольники (единственная оптимизация — левый и правый столбцы этого прямоугольника должны лежать в различных блоках по понятным причинам) и проверяем, что в противоположных углах одинаковые числа. Если это так — делаем изменение полосы, иначе оставляем полосу неизменной (тогда, фактически, в нашем графе генерирует петля, которая ни на что не влияет).
Если запустить обновленный код — мы получим, как и ожидалось, ровно 174 полосы.
Добавим еще операций:
Первая из операций swap_3x2() — это случай, когда мы ищем одинаковые подмножества в двух столбцах. Дело в том, что подмножество размера 1 не бывает (иначе нарушается Главное Правило), подмножество размера 2 уже обрабатывается процедурой swap_cross(), а всего строк у нас 3. Значит, нам нужно проверять только один вариант — все три числа в двух столбцах. Для них существуют ровно два варианта соответствия:
Если все совпало — мы просто меняем местами столбцы. Иначе — оставляем полосу неизменной.
Для второй операции swap_mask() мы перебираем всевозможные подмножества столбцов и смотрим для двух строк — одинаковые ли получаются множества чисел для этих подмножеств столбцов. Примеры подходящих вариантов:
При совпадении мы меняем местами найденные подмножества (свапаем пару в каждом столбце). При несовпадении — ничего не делаем.
Следует отметить, что рассмотренная ранее операция swap_cross() — это частный случай swap_mask(). Поэтому swap_cross() можно вообще выкинуть за ненадобностью.
На этот раз запуск программы будет долгим — на моей машине программа работает около 30 секунд. Но результат тот, что и ожидался — 71. Понятно, что код написан далеко не оптимально, но для наших целей такой производительности хватает более чем.
Размеры компонент связности получаются следующие:
4 108 72 216 24 216 216 2592 216 216 1296 1404 540 108 72 510 702 270 2214 6 504 6 1350 666 702 18 756 20 2268 1134 2592 972 270 864 864 972 2052 486 270 1620 540 432 144 432 864 324 540 270 270 234 6 18 540 288 216 54 108 108 288 54 378 108 108 54 108 54 108 36 108 54 54
Что же до операций, которые сокращают число вариантов до 44, то они выглядят как-то так:
Можете попробовать описать их более формально и реализовать в коде.
Пусть C — одна из 44 полос. Тогда количество способов, которым C можно дополнить до полной сетки судоку, обозначим на nC. Нам также понадобится число mC — общее количество полос, для которых количество конечных заполнений такое же, как и у C. Когда общее количество различных судоку будет равно N=ΣCmCnC, то есть сумма mCnC по всем 44 полосам.
Фельгенхауэр и Джарвис написали компьютерную программу для выполнения итоговых рассчетов. Они вычислили число N1 (количество корректных заполнений, в которых B1 в стандартной форме) для каждой из 44 полос. Затем они умножили это число за 9!, чтобы получить ответ. Они обнаружили, что количество всевозможных корректных сеток судоку 9 на 9 равно N=6670903752021072936960, что приблизительно равно 6.671×10 21 .
Давайте и мы допишем нашу программу для рассчетов. Начнем со структуры GRID — сетки судоку, в которую можно вписывать числа и для каждой пустой ячейки узнавать можно ли в нее записать какое-либо число или нет.
Массивы флагов R, C и B хранят информацию о том, какие числа уже отмечены в соответствующих строках, столбцах и блоках. Это позволяет затем быстро определить можно ли поставить в какую-либо ячейку какое-либо число или нет.
Следующая процедура для каждой полосы BAND строит начальную сетку для перебора GRID и запускает перебор:
На самом деле, данная процедура в самом начале заполняет первый столбец сетки, да не всеми способами, а только лексикографически редуцированными — это сокращает дальнейший перебор ровно в 72 раза (главное потом не забыть домножить ответ на 72). Итого каждый вызов процедуры process_band() запускает dfs2() ровно 10 раз.
Сам же перебор выглядит следующим образом:
Перебор совершенно бесхитростный. Мы перебираем все оставшиеся незаполненные клетки в следующем порядке: сначала идем сверху вниз по второму столбцу (в блоках B4 и B7), затем идем сверху вниз по третьему столбцу и так далее.
Один запуск dfs2() на моей машине работает около 30 секунд, т.е. на обработку одной полосы нужно около 5 минут. Реализацию, конечно же, можно немного ускорить, вы можете попробовать сделать это самостоятельно. Программа Фельгенхауэра и Джарвиса для одной полосы работает около 2 минут (как они пишут в своей статье), т.е. всего в 2,5 раза быстрее нашей реализации. Полная обработка всех 71 полос (для нашей программы) занимает 6 часов.
В результате работы программа выводит следующее:
Для получения финального результата нужно воспользоваться калькулятором (длинную арифметику писать не хотелось), и… все совпадает! Можете сверить числа с теми, что получились у Фельгенхауэра и Джарвиса тут.
Полный код нашей программы (чтобы не собирать кусками из спойлеров) находится тут.
Как решать Судоку? Правила игры, простые объяснения
Хотите знать, как решать Судоку, но не понимаете, как играть? Если да, то тут мы рассмотрим базовые правила и основы для начинающих. Далее в приведенном ниже материале мы шаг за шагом будем изучать, как играть в судоку.
1. Изучите всё игровое поле
Каждая головоломка Судоку включает в себя сетку из клеток размером 9×9, сгруппированных на сектора 3 на 3.
Всего в сетке Судоку 81 клетка, и когда головоломка будет завершена, каждый квадрат будет содержать ровно одно число.
2. Запомните правила Судоку
Для решения Судоку есть небольшой список очень простых правил:
- В каждой ячейке (всего их 81) может находиться одно единственное число.
- Для заполнения Судоку таблицы используется следующий ряд чисел: 1, 2, 3, 4, 5, 6, 7, 8 и 9.
- В каждом секторе 3×3 клетки должны быть расположены числа от 1 до 9 без повторений.
- В каждом вертикальном столбце должны быть расположены числа от 1 до 9 без повторений.
- В каждой горизонтальной строке должны быть расположены числа от 1 до 9 без повторений.
Как только головоломка решена, это означает, что каждая строка, столбец и сектор 3 на 3 будут содержать все числа от 1 до 9 без повторений.
Другими словами, ни одно число не может повторяться в любом секторе 3×3, строке или столбце.
3. Найдите все клетки, в которых может быть только одно число
При старте новой игры часть клеток уже заполнена числами. В зависимости от уровня сложности головоломки на основании стартовых чисел можно со стопроцентной точностью определить местоположение некоторых определнных чисел в определенной клетке. Не нарушая никаких правил, можем заключить, что это такие клетки, в которых может стоять только одно число.
Например, только число 2 может находиться в квадрате с координатами R8C2, выделенном ниже.
Числа 1, 8 и 9 не могут располагаться в выделенном квадрате, так как эти числа уже есть в секторе 3 на 3. Числа 3 и 5 не подходят, так как они уже находятся в том же столбце C2, что и выделенный квадрат. Наконец, числа 4, 6 и 7 не подходят, так как они уже находятся в той же строке R8, что и выделенная клетка.
Это означает, что единственное оставшееся число, которое может поместиться в этот квадрат, — это число 2.
4. Опирайтесь на разгаданные числа, чтобы заполнить другие клетки
Когда вы начнете заполнять клетки, которые могут быть только с одним числом, вы будете добавлять новые числа в сетку, что поможет «установить» (узнать) другие числа в остальных клетках.
Например, добавление 2 в клетку R8C2 на шаге 3 позволяет определить, что в верхнем левом секторе 3×3, в клетке R3C3, выделенной ниже, тоже должна находиться 2.
Это следует из того, что 2 в R8C2 (на шаге 3) исключает нахождение 2 в среднем столбце С2. Точно так же две двойки в строках R1 и R2 исключают наличие двойки в первых двух строках верхнего левого сектора 3×3.
Поэтому в клетке R3C3 должна быть 2.
Примечание. Не каждый раз, когда вы добавляете новое число в сетку, будет «открываться» («решаться») новая клетка. Чем сложнее головоломка, тем больше чисел вам придется разгадать, чтобы понять какие числа должны быть в других клетках.
5. Используйте «карандашные заметки»
Если вы в данный момент не решаете простые Судоку для начинающих, то у вас скоро закончатся возможные числа, которые вы можете однозначно определить. Когда вы дойдете до этого момента, пора начинать «помечать карандашом» возможных кандидатов для различных ячеек.
Здесь вы можете использовать технику «карандашных заметок», чтобы перечислить все возможные числа-кандидаты, которые может содержать клетка, на основе имеющейся у вас информации.
Вместо того чтобы сосредотачиваться на добавлении всех возможных чисел в каждую пустую ячейку, проще и быстрее сосредоточиться на определенных клетках и числах за раз.
Например, возвращаясь к предыдущему примеру, мы видим, что добавление карандашных пометок для числа 4 в трех левых секторах 3 на 3 помогло выявить местоположение одной из четверок. Рассмотрим подробнее.
Расположенные при старте игры четверки в сетке исключили все клетки в трех левых секторах, кроме тех, к которым мы «дописали карандашом» отмеченные четверки, как показано ниже.
Если вы внимательно посмотрите на вероятные места для 4, вы, возможно, заметите, что в третьем столбце C3 есть только одно возможное место.
Поскольку столбец под номером три (C3), как и любой другой, должен содержать только одну единственную цифру 4, а клетка R9C3 — это единственная клетка в третьем столбце, которая может содержать цифру 4, то, используя логику (в строках R8 и R6 столбца C3 не может быть четвёрки), мы приходим к выводу, что цифра 4 должна стоять в этой ячейке.
6. Повторяйте предыдущие шаги до тех пор, пока не разгадаете головоломку
Дочитав до этого шага, можно с уверенностью сказать, что теперь вы изучили, как решать Судоку.
Дальнейшее решение сводится к повторению описанных выше шагов, пока вы не заполните в таблице все имеющиеся клетки.
Решение же более сложных Судоку чаще всего требует использовать более продвинутые техники, но в данным момент вы можете оттачивать свои практические навыки, решая головоломки простого и среднего уровня.
Теперь, когда вы знаете, как играть в Судоку, ознакомьтесь с нашим списком советов по Судоку, чтобы улучшить свою скорость.