Термины и определения Судоку

Представлены используемые термины и определения необходимые для изучения и понимания различных методов решения судоку.

Игровое поле

Игровое поле - квадратное поле из 81 ячейки, разбитое на 27 секторов - 9 строк, 9 столбцов и 9 боксов/квадратов/блоков 3x3. В каждой строке, столбце или боксе по 9 ячеек.

Рис. 1. Игровое поле

Ячейка / Клетка

Ячейка или Клетка - область между линиями сетки игрового поля, может быть трех типов:

• Подсказка - ячейка с цифрой, открывается в начале игры
• Открытая - ячейка с цифрой, открытая игроком
• Свободная - пустая ячейка, в которой могут быть расставлены кандидаты. В течении игры переходит в "Открытую"

Подсказки

Подсказки - открытые цифры в ячейках в начале игры. Цифры в ячейках серого цвета. Например, цифра 6 в A8 (6@A8) или 9 в A9 (9@A9) на Рис. 1

Сектор

Рис. 2. Сектора. Строка А, Столбец 1, Бокс 1.

Сектор - область из 9 ячеек, в которой должно разместиться множество цифр от 1 до 9 без повторений.

На игровом поле 27 уникальных секторов:

• 9 строк (Строки A..K)
• 9 столбцов (Столбцы 1..9)
• 9 боксов 3x3 ячейки (Боксы 1..9)

Линия

Линия - Строка или Столбец

Правила

• в каждом секторе может быть только одна цифра от 1 до 9.
• решение для каждой судоку должно быть единственным.

Судоку

Судоку - головоломка, в которой по имеющимся подсказкам на игровом поле нужно расставить недостающие цифры по установленным правилам.

Рис. 3. Судоку

Первоначальная позиция

Первоначальная позиция - позиция судоку с которой начинается решение головоломки, содержащая определенное количество подсказок.

• Практически было выяснено, что количество подсказок не может быть меньше 17. Может быть записана в текстовой строке из 81 символа, где цифра от 1 до 9 является подсказкой, 0 или Пробел - свободная ячейка. Например:

200835017718649325035721860087310250500970138301580706170208003852493671003107082

• Эту позицию можно загрузить в программу "Sudoku by Peter" через консоль

Кандидаты

Кандидаты - цифры, которые могут быть в свободной ячейке. Расставляются пользователем для удобства принятия решения.
Например, на рис 3 в свободной ячейке A1 - цифры 1,2,3,4,5. Для удобства, кандидата каждой цифры размещают на своем порядковом месте.
Свободная клетка делится на 9 частей 3x3. Место цифры соостветствует порядковому номеру позиции, слева-направо, сверзу-вниз.

Открытые ячейки

Открытые ячейки - ячейки с открытыми игроком цифрами. Цифры темно-синего цвета.

В программе "Sudoku by Peter" есть возможность установить открытые ячейки через консоль.

# sudoku puzzle string;
010000063000400000506000000040060000380091000009750001168003000004000000007510400;
# opened and free (with candidates) cells;
(1)@C4;(1)@D3

Такие ячейки могут использоваться в методе "Avoidable Rectangle"

Открытое судоку

Открытое судоку - судоку в которой все ячейки открыты, свободных не осталось. Открытое судоку является Решением.
Также может быть представлено в текстовом виде:

198634275567821394432795186659248713324917658871356942916582437745163829283479561

Рис. 4. Открытое судоку

Узел / Узел-кандидат / Простой Узел

Узел - Одиночный кандидат цифры в ячейке. Узел-кандидат

Рис. 5. Узел-Кандидат 9@G3

Узел-Кандидат 9@G3

Узел-группа

Если кандидат цифры занимает ячейки на перечении одной Линии (Строки или Столбца) и одного Бокса, то это Узел-группа, или Групповой узел.

Рис. 6. Узел-Группа

Узел-Кандидат 9@G78

Узлы одной цифры в Секторе / Узлы одного кандидата в Секторе

Узлы одной цифры в секторе - все одиночные Узлы-кандидаты в определенном Секторе.

Узел-Истинности

Узел-Истинности - узел в определенном состоянии, т.е. в значении Истина или Ложь

Узел-True / Узел-Истина / Node-True

Узел-True - Узел в состоянии Истина. В текстовом виде может указываться как: {1}@A1, {1g}@A1, {1}@A78, {1g}@A78 В графическом виде имеет зеленый фон.

Узел-False / Узел-Ложь / Node-False

Узел-False - Узел в состоянии Ложь. В текстовом виде может указываться как: {!1}@A1, {1r}@A1, {!1}@A78, {1r}@A78 В графическом виде имеет красный фон.

Состояние Узла

Состояние Узла - Логическое значение Узла. Истина или Ложь.
Истиное значение / Истина - когда Узел является правильным решением. Обычно подкрашивается зеленым.
Истинное значение для Узла-Группы - когда один простой Узел-Кандидат из Узла-Группы является правильным решением.
Ложное значение / Ложь - когда Узел является неправильным решением. Обычно подкрашивается красным. Ложное значение для Узла-Группы - когда все простые Узелы-Кандидаты из Узла-Группы являются неправильным решением.
Отрицание / Обратное состояние - другое состояние от текущего. Если Истина, то Ложь и наоборот если Ложь, то Истина.

Соседние ячейки

Соседние ячейки - для каждой свободной ячейки есть свое уникальное множество соседних ячеек. Это множество соседних свободных ячеек в этой же строке, столбце и боксе.

Рис. 7. Соседние ячейки для B3

Соседние ячейки для B3 в Строке B, Столбце 3, Боксе 1.

Расстановка кандидатов

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

Рис. 8. Кандидаты для цифры 1

Раскрашивание

Во многих методах используется раскрашивание. При этом используются какие-то предположения и получаемые выводы/следствия. Для кандидатов состояние могут быть слудующие:

Рис. 9. Раскрашивание кандидатов

Раскрашивание вытекает из "Предположения => Следствие", или "Если, то"

Например:

• Если 9 в G3 - Истина, то 9 в A3 - ложь (Т.к. кандидаты находятся в одном секторе - Столбце 3)
• Если 9 в G3 - Истина, то 9 в G7,G8 - ложь (Т.к. кандидаты находятся в одном секторе - Строке G)
• Если 9 в G3 - Истина, то 9 в K1,K2 - ложь (Т.к. кандидаты находятся в одном секторе - Бокс 7)

• Кандидат 9 в ячейке G3 (9@G3) - Истина (Раскрашивается зеленым)
• Кандидат 9 в ячейках A3, G7, G8, K1, K2 (6@A1G78K1K2) - Ложь (Раскрашивается красным)

Связи/Линки

Сильная связь / Сильный линк

Сильный Линк - связь между двумя узлами, при которой состояние любого приводит к обратному состоянию другого.

• Узел в связи может быть Простым (Узел-кандидат) или Узел-Группа
• Кандидаты узлов могут быть одинаковыми и разными
• Связь может быть в секторе или ячейке

Рис. 10. Link strong Начало

Рассмотрим взаимосвязь между узлами {9}@D1 и {9}@D9 на рисунке выше.
Т.к. в Строке D для цифры 9 их только два, то про них можно сделать следующие предположения - выводы:

• Если 9@D1 - Истина, то 9@D9 - Ложь
• Если 9@D1 - Ложь, то 9@D9 - Истина
• Если 9@D9 - Истина, то 9@D1 - Ложь
• Если 9@D9 - Ложь, то 9@D1 - Истина

Рис. 11. Link strong Импликации

В таких случаях получается Сильная связь / Сильный Линк.

Рис. 12. Link strong

В графическом виде обозначется сплошной линией, возможно с направленной стрелкой.
В текстовом виде обозначается {9}@D1={9}@D9

Сильный линк Петля / Hinge

Рис. 13. Link strong Петля

Если в ячейке, только два кандидата, то это Сильный Линк Петля

{4}@D9={9}@D9

Сильный линк с Узлами-Группами

В качестве источников Линка могут быть Узлы-Кандидаты.

Рис. 14. Link strong с Узлом-Группой

Слабая связь / Слабый линк

Слабый Линк - связь между двумя узлами, при которой Истинное состояние любого приводит к Ложному состоянию другого.

Рис. 15. Link weak Начало

Рассмотрим взаимосвязь между узлами {4}@D1 и {4}@D9 на рисунке выше.
В отличие от цифры 9 в Строке D для цифры 4 узлы-кандидаты присутствуют в 3 разных боксах, в текущей ситуации можно сделать предположения - выводы:

• Если 4@D1 - Истина, то 4@D9 - Ложь
• Если 4@D9 - Истина, то 4@D1 - Ложь

Внимание!

При 4@D1 или 4@D9 - Ложь, сделать выводов о соседних кандидатах 4 в Секторе D сделать нельзя.

Рис. 16. Link weak

В графическом виде обозначется пунктирной линией, возможно с направленной стрелкой.
В текстовом виде обозначается {4}@D1-{4}@D9

Обозначения

Обозначения секторов

Строки обозначаются буквами A,B,C,D,E,D,G,H,K.

Столбцы обозначаются цифрами от 1 до 9.

Боксы обозачаются буквой b и цифрой номера блока. Например, b1,b3,b9.

Ячейка обозначается пересечением строки и столбца. Например B3, G8, K3.

Несколько ячеек обозначаются B3B4B5. По общим строкам или столбца или секторам можно провести сокращение B345.

Цифра в ячейке: 2@C4, 1@G5

Цифра открытая пользователем: (5)@D8, (9)@B2

Кандидат / Кандидаты: {2}, {34}, {189}

Кандидат в ячейке (Узел-кандидат): {4}@B2, {9}@K7

Узел-Группа: {5}@A45

Кандидаты в ячейках: {18}@D5, {67}@E89