Судоку пошаговое решение: Пошаговое решение судоку: как разгадывать, заполнять, играть

Содержание

Пошаговое решение судоку: как разгадывать, заполнять, играть

Программа решения судоку с объяснениями (онлайн)

Описание:

* может не работать на браузерах устаревших версий

Правила игры

Судоку — это игра-головоломка, где необходимо заполнить пустые клетки так, чтобы
  1. каждая строка,
  2. каждый столбец,
  3. каждый малый квадрат 3×3
содержали все цифры от 1 до 9 (каждая цифра встречается только один раз).

Алгоритм заполнения ячеек судоку

Способ 1. «Скрытые одиночки»

В клетку строки заполняется цифра, если

  1. она отсутствует в строке,
  2. её можно вписать только в одну пустую клетку строки. Число становится кандидатом клетки, если этой цифры нет
    • в малом квадрате 3×3, который содержит клетку,
    • в столбце, который содержит клетку

Таким образом проверяется каждая цифра от 1 до 9 в первой строке, а затем во всех строках.

В клетку столбца ставится цифра, если

  1. она отсутствует в столбце,
  2. её можно вписать только в одну пустую клетку столбца. Число становится кандидатом клетки, если этой цифры нет
    • в малом квадрате 3×3, который содержит клетку,
    • в строке, который содержит клетку

Таким образом проверяется каждая цифра от 1 до 9 в первом столбце, а затем во всех столбцах.

В клетку малого квадрата 3×3 заполняется цифра, если

  1. она отсутствует в малом квадрате 3×3,
  2. её можно вписать только в одну пустую клетку малого квадрата 3×3. Число становится кандидатом клетки, если этой цифры нет
    • в столбце, который содержит клетку,
    • в строке, который содержит клетку

Таким образом проверяется каждая цифра от 1 до 9 в первом малом квадрате 3×3, а затем во всех малых квадратах 3×3.

Способ 2. «Одиночки»

В клетку заносится цифра, если

  1. в строке, которая содержит клетку,
  2. в столбце, который содержит клетку,
  3. в малом блоке 3×3, который содержит клетку
уже есть все числа от 1 до 9, кроме искомого.

Таким образом проверяются все клетки.

Методы разгадывания судоку

Стратегия 1. Кандидат в двух-трёх клетках одного квадрата

Для того чтобы отгадать число в сложных кроссвордах нужно расписать кандидатов клетки. На бумаге получается месиво, в котором взгляд не цепляется ни за одну идею. Поэтому вначале указываются кандидаты, если:

  1. 3
    6 8
    9
    5
    6
    4 9
    5 4 2 9 9 3 8
    6 4 5
    1 7 3 5
    в строку можно вставить цифру-кандидата только в две-три клетки, которые обязательно должны находиться в общем блоке 3×3. Тогда эта цифра-кандидат из других оставшихся клеток общего квадрата 3×3 исключается.
  2. В клетке можно указать только цифру «2» (см. способ «Одиночки»), т.к. «6» и «9» должны располагаться в других клетках блока 3×3
    3
    6 8
    9
    5
    6
    4 9
    5 4 2 6 9 9 3 8
    6 4 5
    1 7 6 2 3 5
    в столбец можно вставить цифру-кандидата только в две-три клетки, которые обязательно должны находиться в общем блоке 3×3. Тогда эта цифра-кандидат из других оставшихся клеток общего квадрата 3×3 исключается.
  3. В клетке можно указать только цифру «2» (см. способ «Одиночки»)
    , т.к. «4» и «5» должны располагаться в других клетках столбца
    8 9 1
    3 6 2
    7
    6 7 45
    2 3 8
    9 1 45
    в квадрат 3×3 можно вставить цифру-кандидата только в две-три клетки, которые обязательно должны находиться в общей строке/столбце. Тогда эта цифра-кандидат из других оставшихся клеток общей строки/столбца исключается.

Если новые «скрытые одиночки» и «одиночки» обнаружены не были, то расписываются все возможные кандидаты для всех пустых клеток с учётом исключённых. А потом вычёркиваются те, что не подходят по причинам, описанным в Стратегии 2.

Стратегия 2. Группы кандидатов

Подсказка 2.1. Скрытые пары, тройки, четвёрки

Если две цифры-кандидата встречаются только в двух клетках одной строки/столбца/малого квадрата, то другие кандидаты в этих двух клетках удаляются

Было
7 5 8 4 6 3 2 1 9
13 2 13 5 9 8 6 7 4
4 9 6 17 12 27 38 5 38
8 17 17 2 4 6 9 3 5
2 6 4 3 5 9 7 8 1
5 3 9 8 7 1 4 26 26
6 147 137 179 8 27 5 249 23
9 478 2 67 3 5 1 46 68
13 18 5 169 12 4 38 269 7
Стало
7 5 8 4 6 3 2 1 9
13 2 13 5 9 8
6
7 4
4 9 6 17 12 27 38 5 38
8 17 17 2 4 6 9 3 5
2 6 4 3 5 9 7 8 1
5 3 9 8 7 1 4 26 26
6 147 137 179 8 27 5 249 23
9 478 2 67 3 5 1 46 68
13 18 5 69 2 4 38 69 7
В 9-ую строку можно записать только одну «2» (см. способ «Скрытые одиночки»), так как в клетке 8-ого столбца могут быть только числа «6» и «9».

То же самое если три цифры-кандидата встречаются только в трёх клетках одной строки/столбца/малого квадрата.

Подсказка 2.2. Открытые пары, тройки, четвёрки

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

Было
5 8 147 1237 6 9 24 1234 14
29
39 17 1237 4 12 6 5 8
26 36 14 123 8 5 7 1234 9
7 49 8 6 129 3 5 124 14
1 2 6 49 5 7 489 48 3
49 5 3 8 129 14 249 7 6
3 7 5 19 19 6 48 48 2
46 46 2 5 3 8 1 9 7
8 1 9 24 7 24 3 6 5
Стало
5 8 147 1237 6 9 24 123 14
29 39 17 1237 4 12 6 5 8
26 36 4 123 8 5 7 123 9
7 49 8 6 129 3 5 12 14
1 2 6 49 5 7 489 48 3
49 5 3 8 129 14 249 7 6
3 7 5 19 19 6 48 48 2
46 46 2 5 3 8 1 9 7
8 1 9 24 7 24 3 6 5
В 3-ю строку можно записать только одну «4» (см. способ «Скрытые одиночки»), так как в 8-ом столбце «4» не может быть, поскольку «4» в этом столбце находится или в 5-ой строке, или в 7-ой.

Пример «Открытые тройки» в 7-ом столбце из цифр «4», «6», «9»

Было
79 6 3 5 48 17 2 1489 1489
79 5 4 2 68 17 3 1689 189
1 2 8 46 3 9 46 5 7
2 4 9 7 1 6 58 38 358
5 8 6 49 2 3 149 7 149
3 7 1 8 49 5 49 2 6
46 3 7 1 5 8 469 469 2
68 9 2 3 7 4 1568 168 158
48 1 5 69 69 2 7 348 348
Стало
79 6 3 5 48 17 2 1489 1489
79 5 4 2 68 17 3 1689 189
1 2 8 46 3 9 46 5 7
2 4 9 7 1 6 58 38 358
5 8 6 49 2 3 1 7 149
3 7 1 8 49 5 49 2 6
46 3 7 1 5 8 469 469 2
68 9 2 3 7 4 158 168 158
48 1 5 69 69 2 7 348 348
В клетке можно указать только цифру «1» (см. способ «Одиночки»), т.к. «4» и «9» должны располагаться в других ячейках столбца.

Пример «Открытые четвёрки» в малом квадрате из цифр «4», «5», «7», «8»

Было
3 89 15 268 458 126 7 14589 4589
19 789 2 78 4578 17 3 14589 6
4 678 156 3 578 9 2 158 58
6 1 7 45 2 45 89 89 3
2 3 9 1 6 8 45 45 7
5 4 8 79 79 3 6 2 1
179 5 4 26789 789 267 189 3 289
79 2 3 45789 1 457 4589 6 4589
8 69 16 2459 3 245 1459 7 2459
Стало
3 89 15 26 458 126 7 14589 4589
19 789 2 78 4578 1 3 14589 6
4 678 156 3 578 9 2 158 58
6 1 7 45 2 45 89 89 3
2 3 9 1 6 8 45 45 7
5 4 8 79 79 3 6 2 1
179 5 4 26789 789 267 189 3 289
79 2 3 45789 1 457 4589 6 4589
8 69 16 2459 3 245 1459 7 2459
В клетке можно указать только цифру «1» (см. способ «Одиночки»), т.к. «7» должна располагаться в других клетках малого квадрата.

Методы решения судоку / Хабр

1. Основы

Большинство из нас, хабражителей, знает, что такое судоку. Не буду рассказывать про правила, а сразу перейду к методикам.
Для решения головоломки, не важно сложной или простой, изначально ищутся ячейки очевидные для заполнения.
1.1 «Последний герой»


Рассмотрим седьмой квадрат. Всего четыре свободных клетки, значит что-то можно быстро заполнить.
«8» на D3 блокирует заполнение h4 и J3; точно также «8» на G5 закрывает G1 и G2
С чистой совестью ставим «8» на h2

1.2 «Последний герой» в строке

После просмотра квадратов на очевидные решения, переходим к столбцам и строкам.
Рассмотрим «4» на поле. Понятно, что она будет где-то в строке A.
У нас есть «4» на G3, что зыкрывает A3, есть «4» на F7, убирающая A7. И ещё одна «4» во втором квадрате запрещает её повтор на A4 и A6.
«Последний герой» для нашей «4» это A2

1.3 «Выбора нет»


Иногда есть несколько причин для конкретного расположения. «4» в J8 будет отличным примером.
Синие стрелки показывают, что это последнее возможное число в квадрате. Красные и синие стрелки дают нам последнее число в столбце 8. Зеленые стрелки дают последнее возможное число в строке J.
Как видим, выбора у нас нет, кроме как поставить эту «4» на место.
1.4 «А кто, как не я?»


Заполнение чисел проще проводить вышеописанными методами. Однако проверка числа, как последнего возможного значения, тоже даёт результаты. Метод стоит применять, когда кажется, что все числа есть, но чего-то не хватает.
«5» в B1 ставится исходя из того, что все числа от «1» до «9«, кроме «5» есть в строке, столбце и квадрате (отмечено зеленым).

На жаргоне это «Голая одиночка«. Если заполнять поле возможными значениями (кандидатами), то в ячейке такое число будет единственным возможным. Развивая эту методику, можно искать «Скрытые одиночки» — числа, уникальные для конкретной строки, столбца или квадрата.

2. «Голая миля»
2.1 «Голые» пары

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

В этом примере несколько «голых пар».
Красным в строке А выделены ячейки А2 и А3, обе содержащие «1» и «6«. Я пока не знаю, как именно они расположены здесь, но я спокойно могу убрать все другие «1» и «6» из строки A (отмечено желтым). Также А2 и А3 принадлежат общему квадрату, поэтому убираем «1» из C1.
2.2 «Threesome»

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

Комбинации кандидатов для «голой тройки» могуть быть такими:

[abc] [abc] [abc] // три числа в трех ячейках.
[abc] [abc] [ab] // любые комбинации.
[abc] [ab] [ab] // любые комбинации.
[ab] [aс] [bc]

В этом примере все довольно очевидно. В пятом квадрате ячейки E4, E5, E6 содержат [5,8,9], [5,8], [5,9] соответственно. Получается, что в общем у этих трех ячеек есть [5,8,9], и только эти числа там могут быть. Это позволяет нам убрать их из других кандидатов блока. Этот трюк даёт нам решение «3» для ячейки E7.

2.3 «Великолепная четверка»

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

В указанном примере в первом квадрате ячейки A1, B1, B2 и C1 в общем содержат [1,5,6,8], поэтому эти числа займут только эти ячейки и никакие другие. Убираем подсвеченных желтым кандидатов.

3. «Все тайное становится явным»
3.1 Скрытые пары

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

В этой головоломке мы видим, что 6 и 7 есть в первом и втором квадратах. Кроме этого 6 и 7 есть в столбце 7. Комбинируя эти условия, мы можем утверждать, что в ячейках A8 и A9 будут только эти значения и все другие кандидаты мы убираем.


Более интересный и сложный пример скрытых пар. Синим выделена пара [2,4] в D3 и E3, убирающая 3, 5, 6, 7 из этих ячеек. Красным выделены две скрытые пары, состоящие из [3,7]. C одной стороны, они уникальны для для двух ячеек в 7 столбце, с другой стороны — для строки E. Выделеные желтым кандидаты убираются.

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

Мы можем развить скрытые пары до скрытых троек или даже скрытых четверок. Скрытая тройка состоит из трех пар чисел, расположенных в одном блоке. Такие как [a,b,c], [a,b,c] и[a,b,c]. Однако, как и в случае с «голыми тройками», в каждой из трех ячеек не обязательно должно быть по три числа. Сработают всего три числа в трех ячейках. Например [ab], [aс], [bc]. Скрытые тройки будут замаскированы другими кандидатами в ячейках, поэтому сначала надо убедиться, что тройка применима к конкретному блоку.


В этом сложном примере есть две скрытые тройки. Первая, отмеченная красным, в столбце А. Ячейка А4 содержит [2,5,6], A7 — [2,6] и ячейка A9 -[2,5]. Эти три ячейки единственные, где могут быть 2 ,5 или 6, поэтому только они там и будут. Следовательно убираем лишних кандидатов.

Вторая, в столбце 9. [4,7,8] уникальны для ячеек B9, C9 и F9. Используя ту же логику, убираем кандидатов.

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


Прекрасный пример скрытых четверок. [1,4,6,9] в пятом квадрате могут быть только в четырех ячейках D4, D6, F4, F6. Следуя нашей логике, убираем всеъ других кандидатов (отмеченых желтым).
4. «Нерезиновая»

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

  1. Пара или Тройка в квадрате — если они расположены в одной строке, то можно убрать все другие такие же значения из соответствующей строки.
  2. Пара или Тройка в квадрате — если они расположены в одном столбце, то можно убрать все другие такие же значения из соответствующего столбца.
  3. Пара или Тройка в строке — если они расположены в одном квадрате, то можно убрать все другие такие же значения из соответствующего квадрата.
  4. Пара или Тройка в столбце — если они расположены в одном квадрате, то можно убрать все другие такие же значения из соответствующего квадрата.

4.1 Указавыющие пары, тройки

В качестве примера покажу эту головоломку. В третьем квадрате «3» находится только в B7 и B9. Следуя утверждению №1, мы убираем кандидатов из B1, B2, B3. Аналогично, «2» из восьмого квадрата убирает возможное значение из G2.


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

4.2 Сокращаем несокращаемое


Эта стратегия включает в себя аккуратный анализ и сравнение строк и столбцов с содержимым квадратов (правила №3, №4).
Рассмотрим строку А. «2» возможны только в А4 и А5. Следуя правилу №3, убираем «2» их B5, C4, C5.


Продолжим решать головоломку. Имеем единственное расположение «4» в пределах одного квадрата в 8 столбце. Согласно правилу №4, убираем лишних кандитатов и, в добавок, получаем решение «2» для C7.

Послесловие

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

5 способов, как решать сложные судоку