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

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

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:
Школа кожевенного мастерства: сумки, ремни своими руками
Оценка: 4.56*49  Ваша оценка:
  • Аннотация:
    Числовая головоломка.
    С 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. И четверке с шестеркой просто некуда деваться, как только идти на свои места.
  
   []
  
  В сверхсложных задачах встречается еще один прием, неотмеченный здесь: когда никаким образом нельзя вычислить единственный ход. Есть как минимум две клетки для одной цифры в квадрате (или ряду/столбике). Перебирать в уме все последствия от выбранной наугад позиции иногда представляется чрезвычайно трудно (многоходовка, однако), тогда я проставляю числа "наугад", но карандашом (единственные варианты я всегда записываю шариковой ручкой). Если через несколько ходов обнаруживается ошибка (например, нельзя вписать в один квадрат или столбик/ряд какое-то число), то весь карандашный вариант стирается и в начальных клетках вписывается второй вариант. Еще можно использовать запись в клетках всех возможных чисел на данный момент (обычно не в начале, а ближе к середине - самому сложному этапу) - это помогает быстрее ориентироваться в поиске решения. Я пользовался этим способом, когда только начинал решать Судоку.
  Самое сложное в решении задач - это выбрать, что анализировать: квадрат, ряд или столбик. И какой из них (а их всех по девять). В любом случае, начинайте с легких головоломок и успехов вам!
  
Оценка: 4.56*49  Ваша оценка:
Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
О.Болдырева "Крадуш. Чужие души" М.Николаев "Вторжение на Землю"

Как попасть в этoт список

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