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

Автор: Макаров С.П.

Дата: 2014-06-04

Алгоритм решения задач Судоку может быть простым и сложным. Задачи Судоку способствуют развитию логического мышления и умения удерживать в поле зрения значительное количество информации из разных областей таблицы Судоку. По правилам Судоку таблица состоит из 81 ячейки, в которой имеется 9 строк и 9 столбцов. На пересечении первых 3 строк (сверху вниз) и первых 3 столбцов (слева направо) выделяется первая подтаблица, состоящая из 9 ячеек. Соответственно на пересечении первых 3 строк и четвёртого, пятого, шестого столбца выделяется вторая подтаблица из 9 ячеек. Таким образом, в таблице Судоку выделяется 9 подтаблиц размерностью 9 ячеек каждая (то есть 9*9 = 81). Во всех ячейках таблицы Судоку должны быть проставлены цифры от 1 до 9. Главное требование заключается в том, чтобы ни в одной подтаблице, ни в одном столбце, ни в одной строке цифры не повторялись. Поскольку любой столбец, любая строка, любая подтаблица состоят из 9 ячеек, то, естественно, в каждой строке, в каждом столбце, в каждой подтаблице должны стоят все цифры от 1 до 9. При этом последовательность цифр может быть любой. На мой взгляд, наиболее эффективно решать задачи Судоку, используя следующий алгоритм:

Первое. Найдите в таблице Судоку незаполненную ячейку и сосчитайте суммарное количество заполненных ячеек в строке, столбце и подтаблице, к которым относится незаполненная ячейка. Для незаполненной ячейки, в которой подсчитанное Вами суммарное количество заполненных связанных ячеек является максимальным, проставьте допустимые значения. Например, если в строке в заполненных ячейках стоят цифры 5, 2, 4, 7, в столбце 1, 3 и в подтаблице проставлена цифра 9, то допустимыми значениями для незаполненной ячейки являются цифры 6 и 8. Запишите карандашом в незаполненной ячейке допустимое значение 68. Найдите следующую незаполненную ячейку с максимальным суммарным количеством заполненных связанных ячеек и таким же способом проставьте допустимое значение.

Второе. Если у вас в одном столбце, либо в одной подтаблице, либо в одной строке в качестве допустимого значения снова окажется такое же, какое было ранее (например, 68), то это означает, что в других ячейках этого же столбца (строки, подтаблицы) не могут стоят цифры 6 или 8. С учётом этого продолжайте заполнять пустые ячейки допустимыми значениями. Если у Вас в качестве допустимого значения окажется одна цифра (например, 8), то в этой подтаблице, в строке и в столбце, связанном с ячейкой, сотрите цифру 8 во всех ячейках, где эта цифра была проставлена в качестве допустимого значения. Убрав цифру 8, в ячейке останется только цифра 6. Аналогично сотрите все цифры 6 из допустимых значений в строке, столбце, подтаблице, с которой связана ячейка с цифрой 6.

Третье. Постоянно следите за тем, что, возможно, в какой-то строке, либо в подтаблице, либо в столбце в качестве допустимого значения какая- то цифра встречается один раз. Например, в первой строке в трёх незаполненных ячейках стоят допустимые значения: 468, 68, 68. Цифра 4 встречается только один раз. Следовательно, в этой ячейке оставляем цифру 4 и одновременно стираем цифру 4 из всех допустимых значений в ячейках связанных с ячейкой, в которой мы только что оставили цифру 4.

Четвёртое. Если у вас окажутся одинаковые допустимые значения в трёх ячейках (например, 456) одного столбца, либо строки, либо подтаблицы, то это означает, что в других ячейках этого же столбца, строки, подтаблицы цифр 4, 5 и 6 не должно быть.

Пользуясь этим алгоритмом, вы довольно быстро и легко решите задачи Судоку, в которых первоначально проставлены цифры в 30 и более ячейках. Наиболее трудными являются задачи Судоку, в которых первоначально проставлены цифры менее чем в 20 ячейках.
С помощью программы «Генератор головоломок Судоку и помощник в их решении», приобретенной - ЗДЕСЬ в нашем магазине, Вы можете решить Судоку любой сложности. Но, чтобы получить звание Мастера, Вам необходимо научиться решать задачи без ошибок. Этой программой Вы сможете генерировать Судоку четырёх уровней сложности. В качестве примера размещаем бесплатно - ЗДЕСЬ -28 задач Судоку, из них 6 очень лёгких, 6 лёгких, 8 средней трудности и 8 повышенной трудности. Эти задачи вы можете скачать бесплатно. После того, как Вы решите все задачи, напишите нам на e-mail: PUTJATO@Yandex.ru. Успехов Вам в развитии Вашего интеллектуального потенциала!

Просмотров: 2638

Комментарии

Добавить Ваш комментарий: