Как сделать судоку в ворде
В создании этой статьи участвовала наша опытная команда редакторов и исследователей, которые проверили ее на точность и полноту.
Команда контент-менеджеров wikiHow тщательно следит за работой редакторов, чтобы гарантировать соответствие каждой статьи нашим высоким стандартам качества.
Вам захотелось попробовать свои силы в судоку, но вы пока не знаете, с чего начать? Головоломки судоку кажутся сложными, так как содержат в себе цифры, но на самом деле они не основаны на математике. Вы спокойно можете решать судоку, даже если у вас нет математических способностей. В действительности, если цифры заменить на буквы, результат останется тем же. Смысл заключается в определении правильного порядка расстановки символов. Начните с изучения основ решения судоку, а затем ознакомьтесь с простыми уловками и более продвинутыми приемами разгадывания этих головоломок.
- Крупные квадраты судоку обычно обозначены более жирными линиями, а мелкие – более тонкими. Также иногда фон крупных квадратов закрашен в шахматном порядке.
Поймите принцип построения рядов и колонок. Основное правило головоломки заключается в том, что в каждом ряду и столбце необходимо расставить цифры от одного до девяти. Это означает, что ни одна цифра в ряду или колонке не должна повторяться.
- Поэтому если в большом квадрате уже присутствует двойка, в него никаким образом нельзя поставить еще одну двойку.
wikiHow работает по принципу вики, а это значит, что многие наши статьи написаны несколькими авторами. При создании этой статьи над ее редактированием и улучшением работали, в том числе анонимно, 10 человек(а).
Любите судоку, но надоело разгадывать их в сборниках? Почему бы не придумать собственную?
- Поменяйте местами ряды 1-3, 4-6 или 7-9.
- Поменяйте местами колонки 1-3, 4-6 или 7-9.
- Поменяйте местами блоки рядов 3x9.
- Поменяйте местами блоки колонок 9x3.
- Поверните сетку на 90, 180 или 270 градусов.
- Отразите сетку по горизонтали, вертикали или диагонали.
- Поменяйте местами цифры.
Сотрите цифры, которые можно вычислить по оставшимся цифрами. Уберите хотя бы по одной из каждого ряда, колонки и блока.
Продолжая усложнять головоломку, убирая все больше цифр, следите, чтобы он оставалась разрешимой. Здесь вам помогут онлайн-инструменты типа [1] и [2]. Если из-за недостающих цифр у головоломки появилось несколько решений или одно, но чрезвычайно сложное, вернитесь на несколько шагов назад и попробуйте убрать другие цифры.
Когда посчитаете, чтоб убрали достаточно цифр, проверьте головоломку, решив ее вручную, чтобы убедиться в ее решаемости и сложности. Если вы довольны, сохраните головоломку и покажите ее миру.
Доброго времени суток!
Думаю, головоломка Судоку не нуждается в представлении. Многие из нас проводят за её решением достаточно много времени. Например, когда нужно убить время в дороге или просто поворочать мозги, чтобы не сохли. На хабре есть довольно много постов о решении головоломки. Но когда человек решает с десяток, а может и сотню головоломок, то найдётся пытливый ум, который задаст себе вопрос «А как же получается таблица Судоку, имеющая единственное решение? И как можно описать алгоритм для сетки 9x9?».
Приведённый алгоритм является вполне логичным. Но моей задачей было описание и реализация. Обо всём этом написано под катом.
- Цифра может появиться только один раз в каждой строчке
- Цифра может появиться только один раз в каждом столбике
- Цифра может появиться только один раз в каждом районе (Район — меньший квадрат со стороной 3х3, на изображении ниже выделен фиолетовым цветом)
Шаг 1. Взять за основу базовую сетку
Сетка должна подчинятся правилам Судоку. Размещаем в первую строку 1 2… 8 9, в строках ниже смещаем на 3 позиции влево, т.е. 4 5… 2 3 и 7 8… 5 6.
Далее переходя в следующий район по вертикали смещаем на 1 позицию влево предыдущий район.
В итоге должна получиться вот такая сетка, её я и назову базовой:
Для реализации создадим класс grid. Заполним его в соответствии с Шагом 1, в котором table — список значений таблицы, метод show — просто наглядный вывод таблицы.
Шаг 2. Перетасовать сетку
Есть несколько видов перестановок, выполнив которые таблица Судоку останется в допустимом состоянии.
К ним относятся:
Для каждой из перестановок напишем метод:
transposing
swap_rows_small
swap_colums_small
Для обмена столбцов можно поменять строки у транспонированной таблицы:
swap_rows_area
swap_colums_area
Может быть есть ещё более сложные преобразования, но, думаю, можно ограничиться этими. Этот каркас инвариантен своей структуре, такие перестановки есть почти тоже самое, что и действия над матрицами относительно определителя или вращение Кубика Рубика.
Теперь, для того чтобы получить случайную комбинацию, достаточно запустить в случайном порядке функции перемешивания. Так и поступим, amt — количество перемешиваний:
Шаг 3. Удаление клеток
После полученного решения нам необходимо получить задачу (именно в такой последовательности мы можем гарантировать однозначность решения). И это самая сложная часть. Какое количество можно убрать, чтобы гарантировать однозначность решения? Это один из важных факторов, от которого зависит сложность Судоку. Всего в Судоку 81 клетка, обычно считают лёгким когда на поле есть 30-35 «подсказок», средним — 25-30, и сложным — 20-25. Это данные большого набора реальных примеров. Нет никаких законов для сложности. Можно сделать 30-клеточный неразрешимый вариант и 22 клеточный «лёгкий».
- Случайный подход — можно попробовать выкинуть 50-60 клеток наугад, но где вероятность что Судоку можно будет решить? Например, если заполнены 3 строки ( = 27 клеток)
- Случайно с простым ограничением — для примера можно взять некое число N в качестве предела, так что N строк и столбцов могут быть пустыми. Принимая N = 0 — для лёгких уровней, N=1 — средний, N=2 — сложный
- Выбрать случайную ячейку N
- Отметить N просмотренной
- Удалить N
- Посчитать решения. Если оно не единственное, то вернуть N обратно
Я уверен, что есть и более сложные подходы в построении таблицы Судоку. Моя цель была достигнута, получился рабочий алгоритм. Теперь мне не нужно искать новые выпуски, я могу их генерировать :)
В принципе, здесь был приведён частный случай Судоку 9х9. Но нет ограничений для использования его на 16х16 и 25х25.
Большинство из нас, хабражителей, знает, что такое судоку. Не буду рассказывать про правила, а сразу перейду к методикам.
Для решения головоломки, не важно сложной или простой, изначально ищутся ячейки очевидные для заполнения.
1.1 «Последний герой»
Рассмотрим седьмой квадрат. Всего четыре свободных клетки, значит что-то можно быстро заполнить.
"8" на D3 блокирует заполнение H3 и J3; точно также "8" на G5 закрывает G1 и G2
С чистой совестью ставим "8" на H1
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. «Нерезиновая»
- Пара или Тройка в квадрате — если они расположены в одной строке, то можно убрать все другие такие же значения из соответствующей строки.
- Пара или Тройка в квадрате — если они расположены в одном столбце, то можно убрать все другие такие же значения из соответствующего столбца.
- Пара или Тройка в строке — если они расположены в одном квадрате, то можно убрать все другие такие же значения из соответствующего квадрата.
- Пара или Тройка в столбце — если они расположены в одном квадрате, то можно убрать все другие такие же значения из соответствующего квадрата.
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.
Послесловие
Существуют сотни алгоритмов и программ для решения судоку. Иногда для получения результата достаточно навести вебкамеру. Однако для тренировки мозга и прокручивания алгоритмов в голове будет полезно посидеть с ручкой и бумагой, решая судоку.
В статье привел базовые алгоритмы решения. Да-да, именно базовые. Следующим шагом будет разбор продвинутых и сложных методик. Спасибо за внимание.
Судоку – популярная числовая головоломка родом из Японии. Это один из самых популярных видов досуга современных людей всех возрастов. Правильно составленный классический судоку может иметь только одно решение, а сам алгоритм составления не так сложен, как кажется на первый взгляд.
Составление судоку – не менее интересное занятие, чем их решение. Тем более что вариантов классической головоломки может быть очень много. Под классической подразумевается разновидность судоку в виде большого квадрата 9х9 цифр, разделенного на маленькие квадраты 3х3.
Запишите девять строк по девять цифр так, чтобы в каждой строке и в каждом столбце каждая цифра встречалась только один раз. Самый простой вариант – это запись цифр от 1 до 9 со сдвигом на три позиции по мере продвижения вниз внутри «большой» строки и на одну позицию относительно первой строки при переходе на следующую большую строку:123 456 789456 789 123789 123 456234 567 891567 891 234891 234 567345 678 912678 912 345912 345 678
Модифицируйте эту начальную комбинацию приведенными ниже способами, совмещая со своей фантазией, и вы каждый раз будете получать новую головоломку. Для начала переставляйте цифры в виде «больших» столбцов и строк, т.е. элементов этой таблицы толщиной в 3 цифры. Таким образом, судоку состоит из трех больших строк и столбцов.
Для того чтобы получился новый судоку, достаточно переставить местами две большие строки и два столбца. Например, поменяйте местами первую и третью большие строки:345 678 912678 912 345912 345 678234 567 891567 891 234891 234 567123 456 789456 789 123789 123 456
Переставьте первый и второй большие столбцы:678 345 912912 678 345345 912 678567 234 891891 567 234234 891 567456 123 789789 456 123123 789 456
Усложните получившийся судоку способом перестановки обычных строк или столбцов. Это можно делать только внутри больших колонок таблицы, поскольку иначе нарушится правило судоку: в каждом из 9 квадратов головоломки каждая цифра встречается только 1 раз.
Запишите в первой большой строке вторую обычную на месте третьей и наоборот, во второй строке поменяйте первую обычную с третьей, а в третьей большой строке – первую со второй:678 345 912345 912 678912 678 345234 891 567891 567 234567 234 891789 456 123456 123 789123 789 456
Первоначальный вариант уже не узнать. Теперь поменяйте тем же образом обычные столбцы внутри больших. Например, в первой большой колонке замените первый столбец на второй, во второй – первый на третий, и в третьей колонке – второй столбец на третий:768 543 912435 219 678192 876 345324 198 567981 765 234657 432 891879 654 123546 321 789213 987 456
Можете делать любые манипуляции, главное - соблюдать правило: переставлять как большие, так и обычные элементы таблицы можно только полностью. Удобнее всего составлять судоку в компьютерной программе, например, в Miscrosoft Excel. Там можно проверить себя после всех перемещений и замен, просчитав сумму каждой строки, столбца или маленького квадрата. Она должна составлять 45. Для этой цели в программе предусмотрены макросы и формулы.
Теперь самое интересное: удаление лишних цифр. В зависимости от того, какой сложности вы хотите добиться, уберите из получившейся таблицы от 30 до 70% цифр.
Не знаю, кому поможет эта фигня. Лично мне не помогла. Я рассчитывал, что мне действительно расскажут принципы составления задач с единственно возможным вариантом решения, а тут! Тасовка блоков. Для загонки чисел в матрицу, я знаю способ попроще и поинтереснее.
Судоку разделено на 9 блоков, числа в каждом блоке не повторяются. Поэтому заполняем три случайных блока случайным образом, соблюдая, естественно, правила судоку. Теперь заполняем остальные блоки тоже случайным образом и тоже соблюдая правила судоку. Таким образом у нас получится весьма оригинальная матрица. Мало того, заполняя таким способом матрицу мы можем расположить числа так, как нам будет угодно, а не "как получится", если делать перестановку.
Читайте также: