Муратов Сергей Витальевич: другие произведения.

Решаем Судоку (Sudoku)

Журнал "Самиздат": [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь]
Оценка: 6.97*57  Ваша оценка:
  • Аннотация:
    Числовая головоломка.
    С 16 января 2007 Счетчик посещений Counter.CO.KZ

  
  Многие думают, что Цифровую Головоломку Sudoku (Судоку) придумали японцы. Это так же верно, как и все остальное, что делают в Японии. Например, видеомагнитофон изобрел русский Иванов, но наши его не запатентовали, а японцы да (после некоторых улучшений принципиальной схемы). Также получилось и с Судоку. Много лет эту головоломку печатали в Англии, но большой популярностью она не пользовалась. Когда же японцы стали у себя печатать Судоку, то она после них разлетелась по миру. Популярность Судоку в Японии вполне объяснима: кроссворды же они не могут составлять, а чем заполнить досуг?
  Итак мы знаем, что Судоку сегодня популярна везде, где печатают газеты и журналы. Не обошла эта Игра и Россию. Цифровую Головоломку можно найти не только в печатных изданиях, но и в интернете. Вот один из сайтов, где можно и поиграть, и скачать игру на жесткий диск:
  SudokuCB
  
  Кто в затруднении при решении головоломки, может и поучиться этой мудрости, например, здесь (на английском языке):
  Solving 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. И четверке с шестеркой просто некуда деваться, как только идти на свои места.
  
   []
  
  В сверхсложных задачах встречается еще один прием, неотмеченный здесь: когда никаким образом нельзя вычислить единственный ход. Есть как минимум две клетки для одной цифры в квадрате (или ряду/столбике). Перебирать в уме все последствия от выбранной наугад позиции иногда представляется чрезвычайно трудно (многоходовка, однако), тогда я проставляю числа "наугад", но карандашом (единственные варианты я всегда записываю шариковой ручкой). Если через несколько ходов обнаруживается ошибка (например, нельзя вписать в один квадрат или столбик/ряд какое-то число), то весь карандашный вариант стирается и в начальных клетках вписывается второй вариант. Еще можно использовать запись в клетках всех возможных чисел на данный момент (обычно не в начале, а ближе к середине - самому сложному этапу) - это помогает быстрее ориентироваться в поиске решения. Я пользовался этим способом, когда только начинал решать Судоку.
  Самое сложное в решении задач - это выбрать, что анализировать: квадрат, ряд или столбик. И какой из них (а их всех по девять). В любом случае, начинайте с легких головоломок и успехов вам!
  
Оценка: 6.97*57  Ваша оценка:

Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
П.Корнев "Черные сны" А.Гореликова "Зерна огня" В.Седлова "Подсадная невеста для фальшивого жениха" Е.Плахотникова "Ларт Многодобрый" М.Поликарпов "Сербский закат" С.Нергина "По закону перелетных птиц" А.Маслов "Сверкающий Ангел" Д.Казаков "Солнце цвета ночи" М.Мах "Карл Ругер. Боец" В.Выставной "Утечка мозгов" В.Давыдов "Киммерийская крепость" Е.Малиновская "Танец над бездной" Е.Гайдай "Сказка для проклятых" Л.Астахова "Пригоршня вечности"

Сайт - "Художники"
Доска об'явлений "Книги"