Методика решения головоломок судоку

Алгоритм решения судоку несложный — повторяйте следующие логические шаги вплоть до полного решения головоломки. Переходите к более тяжелым шагам только тогда, когда более простые шаги уже не помогают открывать новые значения, или сокращать кандидаты в пустых ячейках.

Для начала рекомендуется ознакомится с терминологией игры судоку.

Одиночный кандидат

Все ячейки имеющие только одного кандидата, называются одиночными:

Очень важно каждый раз, после того как было определено значение для какой-то клетки, удостовериться в том, что это значение исключено как кандидат для пустых ячеек, делящих с ним тот же ряд, колонку и регион (программы подобные Simple Sudoku делают это автоматически).

Скрытый одиночный кандидат

Очень часто существует только один кандидат для той или иной строки, колонки, или региона, но это скрыто среди других кандидатов:

Например, в этом примере (вверху) видим, что кандидат 6 есть только в одной ячейке (она выделена желтым цветом). Мы помним, что по правилам судоку, в каждом регионе должны быть все числа от 1 до 9, и число 6 не является исключением. Потому в желтую ячейку следует поставить 6.

Две ситуации описанные выше является единственными, которые непосредственно определяют значение в ячейках. Они помогают в решении только самых простых пазлов. Следующие шаги (в порядке роста сложности алгоритма), применяют для сокращения количества кандидатов в пустых ячейках к состоянию, когда рано или поздно появятся уже известный нам «одиночный» или «скрытый одиночный» кандидат.

Закрытый кандидат

Иногда кандидат в границах того или иного региона может помочь сократить списки возможных кандидатов для своего ряда или колонки. Если точно определенно, что какая-то ячейка в одном из регионов должна содержать специфический кандидат, этот кандидат можно с легкой душой исключить из всех ячеек в этой строке или колонке за пределами региона. В примере (ниже), крайний правый регион может содержать число 2 только в нижней строке (выделено зеленым):

Так-как, хоть бы одна из «зеленых» ячеек должен иметь значение 2, никакие другие ячейки в этом ряду не могут содержать это число. Потому 2 следует удалить из выделенных желтым цветом ячеек.

Закрытый кандидат 2

Иногда кандидат в пределах того или другого ряда или колонки может помочь сократить списки возможных кандидатов для региона. Если точно определенно, что какая-то строка или столбик должна содержать специфический кандидат, этот кандидат можно изъять из соответствующих ячеек в этой строке или колонке в пределах региона.

Опять рассмотрим пример:

В левом столбике кандидат 9 может быть только в одной из клеток среднего региона. Потому одна из выделенных зеленым цветом ячеек должен получить значение 9 (иначе левая колонка была бы без 9) и число 9 можно исключить из остальных клеточек этого региона.

Голая пара

Если две ячейки в группе (строке, столбике или регионе) имеют идентичную пару кандидатов (и только эту пару кандидатов), то никакие другие ячейки в этой группе их иметь не могут:

Эти два кандидата должны быть исключенные из других ячеек группы. В примере приведенном выше, кандидаты 6 и 8 формируют в пределах ряда «голую пару» (выделено зеленым). Потому кандидаты 6 и 8 могут быть исключены из других ячеек этого ряда (желтая ячейка).

«Голые тройки» и «голые четверки» выделяются по тому же принципу, что и «голая пара».

Голые тройки

Голая тройка возникает тогда, когда три ячейки в группе содержат три общие кандидата. Каждая ячейка не может иметь больше трех кандидатов. При этом ячейкам не обязательно иметь всех трех кандидатов. Если эти кандидаты найдены в других ячейках группы, их нужно изъять:

На рисунку размещенном выше, общие кандидаты, как мы видим — 1,4 и 6. Потому кандидаты 1 и 4 в выделенных желтым клеточках могут быть удалены.

Голые четверки

Голая четверка возникает тогда, когда четыре клетки в группе содержат четырех общих кандидата. Каждая клетка не может иметь больше четырех кандидатов. Каждому элементу «голой четверки» не обязательно иметь все четыре кандидата.

На приведенном выше рисунке «голую четверку» образуют ячейки выделенные зеленым цветом. Общие кандидаты — 2, 5, 7 и 9. Потому кандидаты 5 и 7 в выделенных желтым клетках могут быть удалены.

Скрытые пары

Если две ячейки в группе содержат идентичную пару кандидатов и никакие другие ячейки в этой группе не содержат этих кандидатов, то другие кандидаты из этих двух ячеек могут быть изъяты:

На рисунке вверху, кандидаты 1 и 9 размещенные только в выделенных зеленым цветом клетках региона, и потому они формируют пару. Все кандидаты кроме 1 и 9 должны быть исключенные из этих двух ячеек, поскольку одна ячейка должна быть 1, а другая 9.

Скрытые тройки

Если три ячейки в группе содержат трех кандидатов и эти кандидаты не входят в другие ячейки группы, то другие числа из этих трех клеток должны быть изъяты:

На рисунке вверху, кандидаты 3, 6 и 7 найдены только в ячейках выделенных зеленым цветом. Потому, все другие кандидаты могут быть изъяты из этих трех клеток. Скрытые тройки находить тяжело, но они (к счастью) редко используются для решения головоломок.

Скрытые четверки

Если четыре ячейки в группе содержат четырех кандидатов и эти кандидаты не входят в другие клетки группы, то другие числа из этих четырех ячеек должны быть изъяты:

Скрытые четверки находить чрезвычайно сложно, даже когда точно известно, что они существуют. Попробуйте найти скрытую четверку на приведенном выше рисунке.

Следующие шаги решения судоку не намного сложнее предыдущих, но требуют анализа того, как соотносятся между собой кандидаты в разных строках, столбиках и регионах 3×3.

Х-крыло

«X-крыло» — позиция, когда один из кандидатов дважды (и только дважды) встречается в двух строчках головоломки. Эти кандидаты должны входить в две колонки, что обеспечивает формирование прямоугольного Х-крыла. Также две колонки с двумя (и только с двумя) клетками, которые содержат одинаковых кандидатов (входящие в две строки) также формируют X-крыло. Эти четыре клетки — единственные возможные места расположения для «настоящих» кандидатов в этих строках или колонках. Другие подобные кандидаты, расположенные по периметру прямоугольника, образованного «настоящими» кандидатами, должны быть удалены. Возможно эта комбинация была названа X-крылом потому, что в конечном варианте «настоящие» кандидаты должны находиться по диагонали в противоположных углах прямоугольника.

Рассмотрим пример решения Х-крыла (рисунок вверху). Как видим, для легкости восприятия из кандидатов отображены только шестерки (был применен фильтр кандидатов — программа Simple Sudoku это умеет делать).

Синие и ярко-зеленые ячейки формируют классическое «X-крыло» — первая и девятая строчки имеют только по две ячейки с кандидатом 6, их разделяют две колонки (седьмая и восьмая), кандидаты образуют прямоугольник. «Настоящих» кандидатов представляют синие, или ярко-зеленые ячейки. Потому другие кандидаты в шестой и девятой колонках нужно удалить (они выделены желтым контуром).

Рыба-меч

Позиция «рыба-меч» является одним из вариантов позиции «х-крыло» описанной выше:

«Риба-меч» — сложная комбинация образованная тремя строчками. Все эти строчки должны иметь не больше чем три клетки с одинаковыми кандидатами и использовать совместно три колонки. То же относится и к «рыбе-меч» образованной тремя колонками — колонки должны иметь не более трех ячеек с кандидатом и использовать совместно три строки. Эти колонки и строки формируют сетку, узлы которой являются единственно возможными для расположения «настоящих» кандидатов. Остальные кандидаты, находящиеся на линиях пересечения сетки должны быть удалены.

Как всегда пример. На рисунке размещенном вверху, в результате работы фильтра кандидатов, показаны только 5-ки. Три колонки (вторая, пята и восьмая) имеют кандидата 5 не более чем в трех ячейках (в данном случае только в двух). Все ячейки входят также в три строки (первая, четвертая и девятая). Все другие ячейки с кандидатом 5, входящие в линии пересечения сетки (они выделены желтым контуром), нужно удалить.

Решение с цветными метками

В этой комбинации нам интересны кандидаты, находящиеся только в одной или двух ячейках группы (ряда, колонки или региона 3×3). Одна из этих двух ячеек есть «верной», а другая соответственно «ложной», но мы еще не знаем какая. Как правило, в большинстве головоломок судоку есть много соединенных пар. Иногда они, соединяясь образуют целые сложные цепочки, предоставляя нам возможность обнаружить кандидатов, которых можно безопасно изъять.

Для того, чтобы показать связь между этими ячейками используем два цвета — синий и ярко-зеленый:

Если две ячейки в объединенной цепи имеют такой же цвет и разделяют ту же группу, то их цвет должен быть «ложным», потому что каждая группа может иметь только одно значение. Также, если какой-то кандидат за пределами сложной цепочки связан колонкой, рядом или регионом, с другими двумя ячейками выделенными альтернативными цветами, то этот кандидат должен быть изъят.

Чтобы понять все вышесказанное рассмотрим пример (рисунок вверху). Как видим, к головоломке был применен фильтр по кандидату 5. Ячейки отмеченные буквами A и B формируют соединенную пару, так-как они являются единственными кандидатами 5 в восьмой колонке. Ячейки B и C также образуют соединенную пару — они являются единственными кандидатами 5 в правом нижнем регионе. Наконец C и D является единственными кандидатами 5 в восьмой строке и потому также формируют соединенную пару. Эти три соединенных пары образуют цепочку и могут быть выделены альтернативными цветами, как показано на рисунке. Ячейка выделена желтым контуром опосредствованно относится к соединенным парам (A и D). Так-как одна из выделенных альтернативным цветом ячеек должен быть «верной» то этот отдаленный кандидат можно безопасно изъять.

P.S.

Применяя шаги описанные выше можно решить большинство головоломок Судоку. Но есть также сложные пазлы, не подвластные логическому решению. Единственным методом их решения является «метод проб и ошибок» или, говоря иначе «метод научного тыка». Также встречаются Судоку, что имеют несколько решений — это как правило «битые» или неправильно составлены головоломки.

Использованные материалы:
Инструкция по решению Судоку
шаг за шагом от Angus
Johnson (англ.).