Многие думают, что Цифровую Головоломку Sudoku (Судоку) придумали японцы. Это так же верно, как и все остальное, что делают в Японии. Например, видеомагнитофон изобрел русский Иванов, но наши его не запатентовали, а японцы да (после некоторых улучшений принципиальной схемы). Также получилось и с Судоку. Много лет эту головоломку печатали в Англии, но большой популярностью она не пользовалась. Когда же японцы стали у себя печатать Судоку, то она после них разлетелась по миру. Популярность Судоку в Японии вполне объяснима: кроссворды же они не могут составлять, а чем заполнить досуг?
Итак мы знаем, что Судоку сегодня популярна везде, где печатают газеты и журналы. Не обошла эта Игра и Россию. Цифровую Головоломку можно найти не только в печатных изданиях, но и в интернете. Вот один из сайтов, где можно и поиграть, и скачать игру на жесткий диск:
Правда, там приводится решение простенькой Головоломки, которую без особых хлопот может решить любой начинающий.
Я не стал копаться в инете в поисках русского текста, показывающего решение Судоку (попросту было лень), но думаю, что и там (если есть) приводится алгоритм решения простых задач (что совершенно логично).
По своему опыту видел, что люди, решающие легкие задачи без особого труда, спотыкаются на сложных. Вот и решил я выложить здесь решение одной из трудных задач Судоку, которую взял из программы, предложенной выше, на уровне Extreme - Предельная сложность. По правде говоря, в некоторых печатных изданиях я решал задачи и посложнее, но может быть это было мое субъективное мнение, основанное на еще незрелом опыте.
Итак, перед вами Судоку из компьютерной программы SudokuCB. Если этот текст сейчас читает несведущий читатель, то коротенько объясню:
Мы имеем квадратное ПОЛЕ, поделенное на 9х9=81 КЛЕТОК. В каждую КЛЕТКУ должно быть вписано число от 1 до 9 так, чтобы оно не повторилось ни в РЯДУ по-горизонтали, ни в СТОЛБИКЕ по-вертикали, ни в КВАДРАТЕ 3х3, выделенного жирными линиями. В самом конце статьи можете посмотреть конечный результат.
Естественно, при решении такой задачи нужно находить единственно правильное решение по каждому числу. Двоякость не допускается - иначе Головоломка не сложится.
Иллюстрации я раскрасил:
1- Зеленый КВАДРАТ, зеленый горизонтальный РЯД или зеленый СТОЛБИК - это "зона", которую я анализирую для поиска единственного решения.
2- Зеленое число - это искомое число, найденное в процессе анализа.
3- Зеленое число, пустое внутри (в данной задаче встречается дважды), - это промежуточные дуплеты (2) или триплеты (3) помогающие проследить алгоритм поиска на несколько ходов вперед.
4- Красная линия показывает, что по этому направлению не может быть проставлено число, от которого эта линия начинается.
Для удобства своего объяснения я буду использовать нумерацию РЯДОВ, СТОЛБИКОВ и КВАДРАТОВ "3х3" от 1 до 9. Порядок номеров: слева - направо и сверху вниз.
Чтобы не перегружать страницу очень большим количеством иллюстраций, на одной картинке я изобразил поиск нескольких чисел.
Это начальная позиция Головоломки.
Сначала находим 1-у во втором квадрате. Красные линии, идущие от единиц с 5-го и 8-го квадратов перечеркивают остальные пустые клетки.
Как находится 1 в четвертом квадрате:
1- сначала определяем, где в шестом квадрате могут быть единицы, проводя красные линии от 1-ы в 5-м и 1-ы в 9-м квадратах (две пустые единички в верхнем ряду). Уже от них проводим красную линию в сторону 4-го квадрата + красная горизонтальная линия от 1-ы 5-го квадрата.
Поиск возможных двоек не увенчался успехом, но я нашел тройку в 9-м квадрате, проведя красные линии от троек в 3-м и 6-м квадратах.
Просканировал возможные варианты на 4, 5, 6, 7 и ничего не нашел. Первая восьмёрка нашлась в 8-м квадрате (см. красные линии от восьмерок со 2-го, 5-го и 7-го квадратов).
Девятку я не нашел и начал поиск опять по новому кругу от единицы. (я всегда хожу по-кругу, чтобы не пропустить важную для поиска цифру)
Сначала определил единицу в 1-м квадрате:
1- Красные линии от единиц во 2-м и 9-м квадратах определили возможные положения единицы в 3-м квадрате (две пустые 1-ы), от них красные линии протянулись в 1-й кадрат. Остальные красные линии видны на рисунке.
Следующую 1-у я нашел в квадрате 7.
Первая двойка нашлась в квадрате 4, после чего там же определилась и первая пятёрка.
8-ка квадрата 1 определяется по красным линиям от восьмерок с квадратов 4 и 7.
Девятка 9-го ряда определяется следующим образом:
Так как этот ряд должен иметь 9, но её не может быть ни в квадрате 7, ни в квадрате 8 (см. красные линии от соответствующих девяток), то она может быть только в квадрате 9.
9 для первого ряда: её не может быть в квадрате 2 - значит в квадрате 3. Оставшуюся пустую клетку первого ряда заполняем цифрой 5.
Сразу две девятки нашлись в квадратах 5 и 6. Думаю, что красные линии ясно объясняют алгоритм поиска.
Четверка 6-го квадрата находится по красным линиям от четверок 3-го и 9-го квадратов. (Как видите, после девятки я нашел четверку, но вы должны знать, что я сканировал до этого числа 1,2 и 3)
Четверка 5-го столбика определяется просто: она не может быть в 4-м ряду (четвертая сверху) и в 7-м - значит только в 6-м. Для этого столбика остаются только два числа: 3 и 6. Тройки не может быть в 8-м квадрате, следовательно - только в 5-м (или 4-м ряду, что то же самое). Тогда шестерка занимает положение в оставшейся пустой клетке.
На следующей картинке очередь необязательна: сначала находим восьмерку, а затем единицу или наоборот.
Продолжаем расставлять восьмерки: сначала находим 8-у в квадрате 9, а уже от нее ведём красную линию для определения 8-и в квадрате 3.
И здесь очередь нахождения 1 и 6 в квадрате 3 не обязательна.
Сначала определяемся с 7-й в 9-м столбике: её не может быть в квадрате 6, тогда она во втором ряду. От 5-и в первом квадрате тянем красную линию и получаем 5-у в 3-м квадрате. Последнюю клетку заполняем цифрой 2.
Второй ряд, цифра 2 может быть только в квадрате 2. Оставшаяся клетка второго квадрата заполняется цифрой 4. И совершенно просто находится 4 в первом квадрате. Последняя клетка второго ряда - цифра 9.
Сначала мы находим 4-у в квадрате 8 (красная линия от 4-и в квадрате 2). Оставшуюся клетку 8-го квадрата заполняем цифрой 7 и от неё ведем красную линию вверх до квадрата 5 - новая семерка определилась. В девятом ряду незапоненная клетка осталась для семерки.
Следующая иллюстрация. Первый шаг - пятерка, затем двойка (можно и наоборот) и оставшаяся клетка - 6.
В шестом ряду семерка может стоять только на втором месте, тогда для первой клетки - цифра 3. Последняя клетка квадрата 4 за шестеркой, тогда в квадрате 6 совсем просто разобраться, где будет 6, а где 5.
Если в первом квадрате семерка может быть только в правом нижнем углу, то и тройка примостится рядом.
В седьмом столбике семерка может быть только там, где я её поставил. Заполнить последнюю клетку столбика может только 2, тогда пятерке есть только одно место в квадрате 9.
Последний штрих к картине: анализируем 7 ряд, 2 столбик и расставляем последние числа. Сначала 9, затем 3 и 2. И четверке с шестеркой просто некуда деваться, как только идти на свои места.
В сверхсложных задачах встречается еще один прием, неотмеченный здесь: когда никаким образом нельзя вычислить единственный ход. Есть как минимум две клетки для одной цифры в квадрате (или ряду/столбике). Перебирать в уме все последствия от выбранной наугад позиции иногда представляется чрезвычайно трудно (многоходовка, однако), тогда я проставляю числа "наугад", но карандашем (единственные варианты я всегда записываю шариковой ручкой). Если через несколько ходов обнаруживается ошибка (например, нельзя вписать в один квадрат или столбик/ряд какое-то число), то весь карандашный вариант стирается и в начальных клетках вписывается второй вариант. Еще можно использовать запись в клетках всех возможных чисел на данный момент (обычно не в начале, а ближе к середине - самому сложному этапу) - это помогает быстрее ориентироваться в поиске решения. Я пользовался этим способом, когда только начинал решать Судоку.
Самое сложное в решении задач - это выбрать, что анализировать: квадрат, ряд или столбик. И какой из них (а их всех по девять). В любом случае, начинайте с легких головоломок и успехов вам!
![[]](/img/m/muratow_s_w/sudoku/1.jpg)
![[]](/img/m/muratow_s_w/sudoku/2.jpg)
![[]](/img/m/muratow_s_w/sudoku/3.jpg)
![[]](/img/m/muratow_s_w/sudoku/4.jpg)
![[]](/img/m/muratow_s_w/sudoku/5.jpg)
![[]](/img/m/muratow_s_w/sudoku/6.jpg)
![[]](/img/m/muratow_s_w/sudoku/7.jpg)
![[]](/img/m/muratow_s_w/sudoku/8.jpg)
![[]](/img/m/muratow_s_w/sudoku/9.jpg)
![[]](/img/m/muratow_s_w/sudoku/10.jpg)
![[]](/img/m/muratow_s_w/sudoku/11.jpg)
![[]](/img/m/muratow_s_w/sudoku/12.jpg)
![[]](/img/m/muratow_s_w/sudoku/13.jpg)
![[]](/img/m/muratow_s_w/sudoku/14.jpg)
![[]](/img/m/muratow_s_w/sudoku/15.jpg)
![[]](/img/m/muratow_s_w/sudoku/16.jpg)
![[]](/img/m/muratow_s_w/sudoku/17.jpg)
![[]](/img/m/muratow_s_w/sudoku/18.jpg)
![[]](/img/m/muratow_s_w/sudoku/19.jpg)
![[]](/img/m/muratow_s_w/sudoku/20.jpg)