Как сделать судоку в ворде

Обновлено: 07.07.2024

Необходима помощь в составлении алгоритма генерации массивов судоку.

Стандартный судоку представляет собой таблицу 9*9, заполненную цифрами от 1 до 9 по следующим правилам:
1)ни в одной строке не должно быть повторяющихся цифр

2)ни в одном столбце не должно быть повторяющихся цифр

3)двумерный массив разделен на сектора размерностью 3*3 клетки(таких секторов 9)
и в этих секторах не должно быть повторяющихся цифр

Повторяю, нужен именно алгоритм генерации исходной таблицы, а не алгоритм решения!

я смог додуматься только до такого:

1)назначаю массивы кандидатов для строк, столбцов и секторов
размерность каждого массива n*n,где n - размерность таблицы судоку
то есть если таблица судоку 4*4, то массивы кандидатов выглядят так:

с1:
1 2 3 4 //первая строка
1 2 3 4//вторая строка
1 2 3 4//третья строка
1 2 3 4//четвертая строка

тоже самое и для столбцов, и для секторов.

2)далее в двойном цикле по строкам и столбцам сначала определяем номер сектора(здесь у меня вообще сделано по дилетантски, кто подскажет более оптимальный алгоритм, буду премного благодарен) затем случайно определяем число от 1 до n, затем смотрим присутствует ли оно в массиве кандидатов на эту строчку, столбец и сектор. Если присутствует, то элементу массива судоку присваеваем это число, а в массивах кандидатов его зануляем.

Выглядит это примерно так:
Генерируем к примеру 12 элемент(все описываю для массива судоку 4*4). Номер его строки 3, номер столбца 4, номер сектора 4. Выпало число 3
тогда массивы кандидатов будут выглядеть так:

строки:
1 2 3 4
1 2 3 4
1 2 0 4
1 2 3 4

1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 0

Шаг 2 повторяем до тех пор, пока не будут сгенерированы верно все элементы.

Алгоритм у меня кривой, не хватает одного или нескольких пунктов. Если кто то знает каких пунктов не хватает у меня, или может поделиться своим алгоритмом, то прошу помочь.

в качестве реализации выбрал язык BС++:

Моя программа выдает варианты расстановок для массива 4*4 , да и то не всегда

Можно еще реализовать алгоритм рекурсивно(читал на сайтах), но я не понимаю что представляет из себя алгоритм перебора с возвратом и каким образом с помощью него можно реализовать данную задачу(читал еще про алгоритм раскраски графа)

если кто то знает ссылку на сайт, где объясняется мой вопрос, прошу поделиться.

Прошу не кидать сслыки на сайты, где выкладывают просто исходники или алгоритм типа:
"Смотрим строчки и столбцы с секторами и проверяем, уникально ли число в данной области " - это я и так знаю.

ошибка в примере массивов кандидатов. Недосмотрел:

строки:
1 2 3 4
1 2 3 4
1 2 0 4
1 2 3 4

1 2 3 4
1 2 3 4
1 2 3 4
1 2 0 4

Прогоняя по шагам программу(для массива 9*9), я понял что она зацикливается примерно в таких случаях:

2 7 4 1 9 3 6 8 5
3 6 8 4 5 7 2 1 9
1 9 5 8 6 2 4 3 7
8 4 2 7 2 5 1 9 3
5 3 9 4 2 8 7 6 X

Х - число на котором программа циклится

То есть если в общей области строки и столбца (или сектора) попадается элемент который уже ставили, то программа зацикливается.

Как сделать обработчик таких ситуаций? Тут вроде нужна рекурсия (алгоритм перебора с возвратом наверное), но я не понимаю как этот алгоритм можно применить к данной ситуации.

Прочитал что представляет из себя рекурсия, ну и попытался сгенерировать массив диагональный массив судоку(там нет разделения на сектора, а есть только проверка в главной и побочной диагонали). Составил алгоритм, он описывается так:

1. первую ячейку таблицы назначаем произвольным образом
2. заполняем следующие ячейки:

а. назнаем произвольное число
б. если это число:
не содержится в текущем столбце, текушей строке, или находится на какой либо диагонали и не содержится в ней, то текущей ячейке присваиваем это число
в. если число не удовлетворяет описанным условиям, делаем откат на один шаг и назначаем другое число для предыдущей ячейки, удовлетворяющая описанным выше условиям

г. если число заполненных ячеек = 81, заканчиваем работу

вот код программы составленный вроде по алгоритму, но она почему то не работает(выдает бесконечный массив а потом вылетает). Попытался прогонять по шагам - почему то нормально ставятся только первые 6 ячеек, остальное идет с повторениями. Помогите разобраться чего не хватает в программе(может я неправильно понял принцип действия рекурсии). Помогите разобраться.

Получилось написать програмку генерации правильного судоку с разделением на сектора, теперь встал вопрос о правильном удалении элементов в таблице таким образом, чтобы имелось одно решение. Я вроде составил алгоритм, он вот:

1. выбираем случайным образом координаты ячейки
2. если встретили ячейку с цифрой ноль(т.е. уже удаленную) то возвращаемся на шаг 1, иначе шаг 3
3. сохраняем значение ячеки в какой нибудь буфферной переменной и ставим цифру 0 в данную ячейку
4. восстанавливаем значение предыдущего удаленного элемента таблицы
5. если текущему (т. е. не предыдущему удаленному, а удаленному на данном шаге элементу) можно сопоставить более одного значения из набора 1 2 3 4 5 6 7 8 9 таким образом, чтобы они не противоречили правилам судоку,то возвращаемся на шаг 1, иначе данную ячейку оставляем с цифрой 0.

Но программу составить почему то не получается, я не понимаю как реализовать пункт 4. Вот так бывает, составищь вроде алгоритм , а средств его реализации не знаешь
Помогите, чем сможете.

Большинство из нас, хабражителей, знает, что такое судоку. Не буду рассказывать про правила, а сразу перейду к методикам.
Для решения головоломки, не важно сложной или простой, изначально ищутся ячейки очевидные для заполнения.

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.

Послесловие

Существуют сотни алгоритмов и программ для решения судоку. Иногда для получения результата достаточно навести вебкамеру. Однако для тренировки мозга и прокручивания алгоритмов в голове будет полезно посидеть с ручкой и бумагой, решая судоку.
В статье привел базовые алгоритмы решения. Да-да, именно базовые. Следующим шагом будет разбор продвинутых и сложных методик. Спасибо за внимание.

Алгоритм генерации окончательного набора судоку инвентаря

В судоку трудно играть, легко ли задавать вопросы по судоку? Для удобства объяснения сначала определите Jiugongge судоку, как показано на рисунке ниже, разделите Sudoku на 9 Jiugongge, пронумерованных 1-9 сверху вниз, слева направо. 81 малая решетка Судоку определяется как массив двумерных массивов [9] [9]. Если вы не знаете, как играть в судоку, эта статья не для вас, переместитесь сначала.Энциклопедия судоку БайдуУзнайте о правилах игры в судоку.

Если вы хотите создать программу для создания вопросов судоку, с чего вам начать? Здесь есть две схемы: схема первая, заранее настроить библиотеку судоку, сохранить вопросы о судоку с достаточным количеством данных в качестве данных и случайным образом выбрать вопросы о судоку при их использовании, оставив некоторые свободными; схема вторая, пройти Алгоритм генерирует вопросы судоку в реальном времени и оставляет их пустыми. Как отличный программист, я должен найти более сложное решение два, так как разработать алгоритм для быстрого создания проблемы судоку? Изучив «Красоту в программировании» и ответы блогеров, я подытожил следующие четыре решения.

1. Обычный метод возврата

Этот метод самый простой для понимания, но эффективность выполнения может быть не очень высокой.

Самый оригинальный метод обычного метода «вперед-назад» - начать с верхнего левого угла (0,0) Судоку, сгенерировать случайное число, а затем постепенно сгенерировать окончательное число, соответствующее правилу Судоку, в порядке слева направо и сверху вниз. один. Однако, исходя из опыта, накопленного предшественниками, и проблем, с которыми я столкнулся в моем собственном процессе программирования:Этот метод действительно глупый! Это настолько глупо, что вы не можете просто генерировать случайные судоку из случайно сгенерированных чисел.Поэтому нам нужно использовать метод обратной замены: когда числа 1–9, сгенерированные на определенном этапе, не могут удовлетворить требованиям судоку, нам необходимо вернуться в предыдущее состояние и восстановить другие возможные решения. Таким образом, пока окончательная карта Судоку не будет окончательно собрана, этот процесс иллюстрируется на следующем рисунке:

2. Метод замены матрицы с дворцом в качестве единицы

Этот метод более умный, а метод преобразования матриц прост в реализации, но недостатком является то, что он не может содержать все легальные судоку. Вот шаги для его генерации:

Первый шаг: заполните 9 номеров, которые соответствуют требованиям судоку в пятом доме.

Шаг 2: Поместите содержимое 9-го дома в 5-м доме в два 9-го дома слева и справа путем преобразования строки.

Шаг 3: Поместите содержимое 9-го дома в 5-й дом с помощью преобразования столбца в два 9-го дома сверху и снизу.

Шаг 4: Поместите содержимое 9-го дома в 4-м доме в два верхних и нижних 9-го дома путем преобразования столбцов, а содержимое 9-го дома в 6-м доме поместите в два верхних и нижних девятых дома путем преобразования столбцов. Таким образом, полная карта Судоку создается путем трансформации.

3. Метод возврата с дворцом в качестве единицы в числовом порядке

Можно сказать, что это оптимизированная версия первого метода.

Первый метод генерирует судоку в порядке слева направо и сверху вниз и заполняет его один за другим, однако текущая ситуация программы говорит нам, что этот метод слишком глуп и требует слишком много процессов, чтобы вернуться назад. Производительность очень плохая. Некоторые блогеры упомянули, что метод оптимизации сводится к следующему: в процессе создания судоку мы сначала заполняем 1, 9 дворцов определяются слева направо и сверху вниз. Заполните 2 в том же порядке, пока все числа не будут завершены. Когда ситуация не соответствует правилу судоку, она вернется к предыдущей ситуации.

4. Метод подстановки чисел на основе определенного судоку

Этот метод также более умный, но есть очень фатальная проблема: просто замените число, основная структура судоку не изменилась, поэтому структура является фиксированной. Например, следующее судоку:

Мы помечаем числа в 5-м доме следующим образом: a (3), b (6), c (5), d (7), e (9), f (8), g (2), h (1) , я (4). С помощью этого правила замены вы можете заменить все судоку на изображении выше на букву ai вместо буквы Sudoku, тогда буква a может быть заменена на все цифры 1-9, b может использоваться в 1-9, кроме числа, соответствующего Вместо 8 номеров их всего 9! Альтернативные методы. Следовательно, с помощью этого альтернативного метода, 9 может быть сгенерировано! Карта Судоку с тем же режимом, но разными номерами.

Судоку – популярная числовая головоломка родом из Японии. Это один из самых популярных видов досуга современных людей всех возрастов. Правильно составленный классический судоку может иметь только одно решение, а сам алгоритм составления не так сложен, как кажется на первый взгляд.

Составление судоку – не менее интересное занятие, чем их решение. Тем более что вариантов классической головоломки может быть очень много. Под классической подразумевается разновидность судоку в виде большого квадрата 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 блоков, числа в каждом блоке не повторяются. Поэтому заполняем три случайных блока случайным образом, соблюдая, естественно, правила судоку. Теперь заполняем остальные блоки тоже случайным образом и тоже соблюдая правила судоку. Таким образом у нас получится весьма оригинальная матрица. Мало того, заполняя таким способом матрицу мы можем расположить числа так, как нам будет угодно, а не "как получится", если делать перестановку.

Читайте также: