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

Секреты прохождения классического судоку

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

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

Терминология судоку

• Клетка. Основной элемент судоку. Все клетки должны быть заполнены цифрами от 1 до 9. Каждая из клеток входит одновременно в ряд, колонку и область.
• Группа. Групп несколько: ряд — 9 горизонтальных клеток; колонка — 9 вертикальных клеток; область — малый квадрат размером 3×3 клетки. В каждом судоку 9 областей.
• Сегмент. Часть области — 3 горизонтальных или вертикальных клетки. В каждой области 6 сегментов — частей большого ряда или колонки.
• Кандидаты. Цифры, которые могут быть вписаны в клетку (на рисунке — мелким шрифтом). Когда все кандидаты, кроме одного, вычеркнуты, цифру можно вносить «на постоянной основе». Два кандидата — пара, три — трио, четыре — квартет.

Способы решения судоку

За годы существования судоку было разработано множество подходов к решению. Мы предлагаем несколько методов, от простого — к сложному.

1. Синглы (единственные варианты)

Синглы определяются после исключения цифр, которые уже вписаны в ряды, колонки или области. Таким способом решают простые судоку.

1.1. Очевидные синглы

Если путем исключения можно выявить единственно возможное число, сингл называют очевидным.

• Цифры 1, 5, 6, 9 исключены — они есть в ряду.
• 2, 3, 8 — расположены в колонке.
• 6, 7, 8 — могут присутствовать в области.
• Единственным кандидатом в клетке E6 остается 4.

1.2. Скрытые синглы

Число можно вписать в клетку, если другое расположение в группе невозможно. Определить такую вероятность можно после расстановки кандидатов и выявления цифры, которая больше нигде не повторяется.

• В седьмом и девятом ряду 8 вписана изначально.
• 8 есть в колонке А.
• В нижней левой области вписать 8 можно только в одну клетку — B8, поэтому остальных кандидатов нужно исключить.

2. Исключение кандидатов

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

2.1. Сегмент 1

Если удалось определить, что число может быть вписано в единственную клетку, его исключают из кандидатов в ряду, колонке и области.

• В правой верхней области 6 должно находиться в сегментах G1 или H1 (других вариантов нет — второй ряд и третья колонка заняты), поэтому цифру можно исключит из кандидатов для клетки С1.

2.2. Сегмент 2

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

• Число 2 можно вписать в третий ряд второй области — D3 или E3. Поэтому 2 можно исключить из кандидатов в клетки первого и второго ряда этой области.
• С учетом уже назначенных чисел третьего ряда, а также колонок B и H, число 2 может находиться только во второй области в третьем ряду и его можно исключить из D1, E1, E2 и F2.

3. Группы кандидатов

3.1. Очевидные группы кандидатов

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

• Пара 1/4 (второй ряд) повторяется в клетках G2 и H2. Один из кандидатов обязательно расположится в G2, другой — в H2. Это значит, что 1 и 4 можно исключить из остальных клеток ряда.
• Также пару 1/4 можно исключить из других клеток области.
• В трех клетках группы не содержатся другие кандидаты, кроме трех, значит эти числа могут быть исключены из остальных клеток группы.

Три клетки группы не обязательно должны содержать все числа трио — в этих клетках не может быть других кандидатов.

Во втором ряду в клетках A, С и G имеется трио 1, 4, 6, значит, данные клетки обязательно разместят одну из этих цифр. Следовательно, 1, 4, 6 не могут занимать другое место в ряду, их присутствие можно исключить.

• С квартетом дела обстоят аналогично — если четыре клетки содержат одинаковый квартет (даже в неполном составе), эти числа исключаются из других клеток группы.
• Это правило распространяется на любой по численности набор кандидатов — вероятность расположения цифр в других клетках можно исключить.
• Очевидные группы кандидатов позволяют исключить кандидатов из других клеток группы.

3.2. Скрытые группы кандидатов

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

В клетках A и C встречается пара 4/6. Таким образом, остальных кандидатов из этих двух клеток можно исключить — в одной из клеток обязательно разместится 4, в другой 6.

Правило относится и к очевидным трио и квартетам, при этом клетки могут не содержать все числа из трио или квартета. Рассмотреть скрытые трио и, тем более, квартеты сложно, но встречаются они нечасто.

4. Сложные методы

Сложность этих методов относится не к пониманию их сути, а к применению в решении судоку.

4.1. Связанные пары (бабочка)

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

В переносе на колонки метод формулируется аналогично, но тогда нужно исключить кандидатов в рядах.

Например, цифра 9 для колонок B и H может находиться только во втором и восьмом рядах (фиолетовые клетки). Из остальных клеток этих рядов 9 можно исключить.

Рассмотрим колонку B. Если 9 не в B2, она может быть только в B8, для колонки H — наоборот. То есть, варианты расположения 9: B2 и H8 или B8 и H2, из остальных клеток этих рядов девятку можно исключить. Метод применим и к областям.

Этот метод может применяться к областям:

• В колонках B и C цифра 9 может находиться в ячейках B3, B9, C2 и C8.
• Поскольку B3 и C2, B9 и C8 находятся внутри одной области, 9 может быть исключена из остальных клеток этих двух областей.

4.2. Сложносвязанные пары (рыба)

Метод похож на предыдущий, но сложнее. Его применяют, когда один из кандидатов присутствует в трех рядах (не более) и при этом — в одних и тех же трех колонках.

1. Из остальных рядов этих трех колонок кандидата можно исключить. Аналогично метод применяется к трем колонкам, тогда кандидаты исключаются из рядов:
2. 2 встречается только в двух клетках колонок C, F и H. Эти клетки находятся в трех рядах — втором, четвертом и восьмом:

• Второй ряд. 2 может быть только в F2 или в H2,
• Четвертый ряд: C4 или H4.
• Восьмой ряд: C8 или F8.

Из остальных клеток этих рядов 2 можно исключить.

4.3. Связанные кандидаты

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

Когда несколько пар связанных кандидатов соединены, число можно исключить из других клеток — число в них не появится в любом случае.

• В колонке B число 7 может находиться B2 или B4.
• Аналогично в первом ряду C1 и H1 — если один кандидат верен, то другой нет.
• Эти связи кандидатов объединены в первой области.
• Если 7 находится в B4, ее можно исключить из H1. Если она не в B4, тогда в B2. Если не находится в C1, тогда в H1, но не в H7.
• В любом случае 7 не может находиться в H1.

4.4. Цепочки

Метод используется, когда во многих клетках только два кандидата. Выбирая одного в начальной клетке, вы формируете цепочку выборов, которая приводит к удалению кандидата из какой-либо клетки.

• Если при выборе другого кандидата в начальной клетке вы приходите к удалению того же кандидата, он может быть удален.
• Например, если 3 верно в клетке B2, то выполняется цепочка заключений (красная линия):

• B2 — 3, D2 — 5, E3 — 7, E5 — 8, A5 — 5, таким образом 5 не находится в A4.

Если же в B2 находится 2, тогда мы имеем (зеленая линия):

• B2 — 2, B4 — 5 и опять 5 не находится в A4.

В любом случае кандидат 5 может быть исключен из клетки A4.

5. Предположения

Иногда вышеперечисленные методы не помогают продвинуться в решении. Тогда можно выбрать кандидата в клетке и посмотреть, к чему приведет такой выбор. Если рассуждения заканчиваются тупиком, тогда придется вернуться в начало и попробовать другой вариант.

Этот метод ближе к гаданию на кофейной гуще и обычно не используется при решении судоку.

© Старецкая Елена, BBF. ru

Источник: https://BBF.ru/magazine/26/7372/

Как решать судоку — способы, методы и стратегия

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

Правила судоку

Данная головоломка занимает мало места, в отличие от сканвордов, кроссвордов и так далее. Игровое поле, состоящее из 81 квадратов, ячейки разбиты на малые блоки, размером 3*3. Его можно легко уместить на листке бумаги.

Задание выглядит в виде выборочно заполненных клеток, которые необходимо дополнить значениями и заполнить всю табличку. В судоку правила игры очень просты и позволяют исключить множественные решения. В каждой строке или столбце проставляются цифры от 1 до 9.

Также значения не повторяются в рамках одного малого блока.

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

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

Правила, как разгадывать судоку

Чтобы получить верное решение, необходимо учесть несколько простых правил:

• Цифра может быть записана в ячейку только в том случае, если ее нет в горизонтальной и вертикальной линии, а также в малом квадрате 3*3.
• Если она может быть записана исключительно в одну клетку.

Если оба пункта учтены, значит можно быть уверенным, что ячейка заполнена верно.

Как решать судоку простые?

Рассмотрим на конкретном примере как разгадывать судоку. Игровое поле на картинке представляет собой относительно простой вариант игры. Правила игры судоку для простых сводятся к выявлению зависимостей в горизонтальной и вертикальной плоскости и в отдельных квадратах.

Например, в центральной вертикали не хватает цифр 3, 4, 5. Четверка не может находиться в нижнем квадрате, так как в нем уже присутствует. Также можно исключить пустую центральную клетку, так как мы видим 4 в горизонтальной линии. Из этого делаем вывод, что она располагается в верхнем квадрате. Аналогично можем проставить 3 и 5 и получить следующий результат.

• 
• Проведя линии в верхнем среднем малом квадрате 3*3 можно исключить ячейки, в которых не может находиться цифра 3.
• 

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

Такой метод некоторые называют «Последний герой» или «Одиночка». Он также используется в качестве одного из нескольких на мастерских уровнях. Среднее время, затрачиваемое на простой уровень сложности, колеблется около 20 минут.

Как решать сложные судоку?

Многие задаются вопросом, как решать судоку, есть ли стандартные методы и стратегия. Как и в любой логической головоломке есть. Самый простой из них мы рассмотрели. Чтобы перейти на более высокий уровень, необходимо иметь больший запас времени, усидчивость, терпение.

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

Рассмотрим несколько популярных методик, применяемых профессиональными «судокуведами» на следующем примере.

1. 
2. В первую очередь необходимо заполнить пустые ячейки возможными вариантами, чтобы максимально облегчить решение и иметь перед глазами полную картину.
3. 

Ответ, как решить судоку сложные для каждого свой. Кому то удобнее использовать разные цвета для окрашивания ечеек или цифр, кто то предпочитает черно-белый вариант. На рисунке видно, что нет ни одной ячейки, в которой бы стояла единственная цифра, однако, это не говорит о том, что в данном задании нет одиночек.

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

Данное действие повлечет за собой возможность проставить цифру 3 в оранжевой клетке и смело вычеркнуть ее из соответствующик фиолетовых по вертикали и малом блоке 3*3.

• 
• Таким же образом проверяем остальные клеточки и проставляем единицы в обведенных клетках, так как они также являются единственными в своих строках.
• 
• Чтобы разобраться, как решать судоку сложные, необходимо вооружиться несколькими простыми методами.

Метод «Открытые пары»

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

В примере такими парочками являются 4 и 9 из третьей строки. Они наглядно показывают, как разгадывать сложные судоку.

Их комбинация говорит о том, что в данных клетках могут быть проставлены исключительно 4 или 9. Этот вывод делается на основании правил судоку.

Из выделенных зеленым ячеек можно удалить значения синих и тем самым сократить количество вариантов. При этом располагающаяся в первой строке комбинация 1249 называется по аналогии «открытой четверкой». Также можно встретить «открытые тройки».

Такие действия влекут за собой появление других открытых пар, например 1 и 2 в верхней строке, которые также дают возможность сузить круг комбинаций.

Параллельно проставляем в обведенной ячейке первого квадрата 7, так как пятерка в данной строке в любом случае будет располагаться в нижнем блоке.

Метод «Скрытые пары/тройки/четверки»

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

Как это поможет разгадывать судоку? Прием позволяет вычеркнуть остальные цифры, так как они служат фоном и не могут быть проставлены в выбранные клетки. Данная стратегия имеет несколько других названий, например «Ячейка не резиновая», «Тайное становится явным».

Сами имена объясняют суть метода и соответствие правилу, говорящему о возможности проставить единственную цифру.

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

Перекрестное исключение

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

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

Исходя из этих данных, цифру 2 можно удалить из других ячеек в указанных столбцах.

Также можно применять для трех и четырех строк. Сложность метода заключается в трудностях визуализации и выявления связей.

Метод «Сокращение»

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

Цветовой метод

Данная стратегия мало отличается от описанной, и заключается в цветовой индикации ячеек или цифр. Способ помогает визуализировать весь ход решения, однако, подходит не всем. Некоторых расцветка сбивает и мешает сосредоточиться. Чтобы грамотно использовать гамму, необходимо выбрать два-три цвета и окрашивать в них одинаковые варианты в разных блоках/линиях, а также спорные ячейки.

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

Команда BrainApps рассмотрела несколько наиболее популярных, понятных и действенных методик, однако, существует множество других алгоритмов. Например, метод «Проб и ошибок», когда выбирается пробный вариант из двух или трех возможных и проверяется вся цепочка.

Источник: https://brainapps.ru/blog/2017/02/kak-reshat-sudoku-sposoby-metody-i-st-2/

C#, VBA Excel: Программу решения СУДОКУ бесплатно скачать на компьютер

1. Судоку не так проста…

Судоку – это известная головоломка, появившаяся в Америке и ставшая культовой в Японии. Количество поклонников этого магического квадрата постоянно увеличивается. Появляются и все новые варианты: 5х5, 6х6, 7х7, 16х16 и т.д. Интеллект, логика, внимательность – помогают нам справиться с заданиями и получать заслуженное удовольствие.

Из Википедии мы знаем, что долгое время оставался открытым вопрос о минимальном количестве открытых клеток, необходимых для однозначного решения судоку. Например, не было известно, существует ли однозначно решаемая судоку, в которой известны (открыты) всего 16 клеток. Оказывается, для решения этого вопроса, потребовалось использовать проект распределённых вычисле́ний…

Технология distributed computing, grid computing, volunteer computing или распределённых вычисле́ний — способ решения трудоёмких вычислительных задач с использованием двух и более компьютеров, объединённых в сеть.

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

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

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

При этом для распределенных вычислений приходится также учитывать возможное различие в вычислительных ресурсах, которые будут доступны для расчёта различных подзадач.

Более того, не всякую задачу можно разделить на подзадачи, которые можно решать параллельно.

Оказывается, только в 2012 году проект распределённых вычислений на платформе BOINC убедительно доказал, что однозначно решаемых судоку с 16 подсказками не существует…

2. VBA Excel для решения кроссворда Судоку

Я не ломал себе голову вопросом однозначности решений в зависимости от количества подсказок…

Так, из спортивного интереса, я когда-то написал программку для решения этой японской головоломки на VBA (Excel). Целью было — просто проверять, имеется ли решение для данного варианта конкретной Судоку.

Поэтому и решал методом простого перебора с проверкой истинности условий по всем 18 линиям и 9 квадратикам.

Если Вы вписали число в клетку, то при старте (кнопка «Решить») шрифт в этой ячейке станет красным и уже ни программа, ни кнопка «Очистить» изменять ее не будут. Такое право (изменять или очищать красную ячейку) предоставляется только пользователю…
Алгоритм этот, конечно, работает не рационально и долго. Почти целую минуту… Хотя для человека это недостижимый результат…

Кого интересует код на VBA (Excel)
решение сплошным перебором – скачивайте бесплатно…

3. Интеллектуальное решение Судоку – программа на C# (Visual Studio 2010)

• От жалости к компьютеру (его не рациональному труду) и зародилась мысль, решить задачу не методом сплошного перебора, а логично… наиболее коротким путем.
• Идея: присваивать одно из альтернативных значений клетке только в том случае, если по методу исключений уже невозможно определить значение ни для одной из ячеек поля.
• Минимум классов предметной области:

• Доступность
• Клетка
• Регион
• ход

Понятно, что и каждая клетка, и каждый регион, будь то строка, столбец или квадратик, в конкретный момент решения (на определенном ходе) обладают определенной доступностью – набором цифр, которые еще не использовались в этом регионе. Доступность может выступать предком для классов «клетка» и «регион».

А ход — представляет собой объект, который в начальный период присваивает одной единственной клетке альтернативное значение (именно одна единственная клетка получает инициализацию на очередном ходе, некое случайно-очередное значение), а затем выполняет цепочку необратимых (логически обоснованных) изменений, которые повлекло за собой это первое присвоение (по методу исключений).

Сколько клеток получат свое значение на одном ходе неизвестно – это дело конкретного случая.
Сколько будет ходов всего – тоже дело конкретного случая.
Но если алгоритм на определенном ходе заходит в тупик, то производится «откат» , то есть очистка всех ячеек измененных на этом ходу.

Конечно, предметную область можно развивать и дальше… Добавлять новые методы, позволяющие еще более тщательно анализировать текущее состояние поля, перед тем как делать ход… Это, конечно, еще более сократит время решения… но для этого надо бы иметь соперника… С кем бы имело смысл соревноваться… А так, с точки зрения пользователя, программа работает практически мгновенно. При условии, что Судоку реальное (т.е. не менее 17 клеток на начальный момент заполнено)…

4. Судоку (Sudoku) бесплатно скачать программу на компьютер

1. Скачивайте и тестируйте программу,
2. а через некоторое время исходный код будет открыт, и, конечно,
   в первую очередь для читателей рассылки ! …
3. Можно использовать программу и для составления судоку… Набрасываете на поле несколько чисел, заставляете программу решить и начинаете некоторые клетки очищать… Когда будете очищать очередную клетку, просто проверьте, что решение является единственным. Ведь по условию, правильная судоку должна иметь единственное решение… Иначе очистите другую…

5. Удобно использовать Судоку при онлайн (online) играх на время

Конечно, если Ваша цель – доказать себе, т.е.

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

Какие бы сложные варианты головоломок Судоку (Sudoku) не встретились, вы можете не сомневаться, что решение будет найдено… И даже не одно, а все имеющиеся для данной комбинации подсказок…
Можете проверять себя… Можете поражать противников скоростью просчета вариантов.

Другие примеры на тему «Компьютерные игры (учебные, простенькие)»

Другие примеры на языках «C»,«C++»,«C#»

Можно достаточно легко переделать программу на составление (генерацию) судоку…

Если на этой странице не нашлось того, что Вы так искали…

         Не расстраивайтесь, не все потеряно… Смело щелкайте…

       телефон: +7(919) 572-59-92 +7(987) 848-79-61

460040, г.Оренбург       © 2010    Учебные программы и сайты для студентов  

Источник: https://orenstudent.ru/Sudoku2.htm

Судоку своими руками

Хочу рассказать вам, дорогие читатели блога, об одной своей программке на Icon, о которой очень хотелось рассказать когда-то давно (еще в 2016 году), но тогда не хватало времени, чтобы описать свой игровой эксперимент. Так уж сложилось, что самое интересное, что я делаю на Icon — это игры, и данный случай — не исключение.

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

Итак, начнем с того, что такое судоку.

Судоку — это популярная японская головоломка, которая представляет собой цифровое поле 9 на 9 клеток, в котором уже поставлены некоторые цифры от 1 до 9.

Также, внутри квадрата 9 на 9, есть разделение линиями на меньшие квадраты размером 3 на 3.

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

Вот так выглядит обычное поле для игры в судоку:

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

Теперь можно приступить к реализации задуманного…

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

procedure grid(win)
local i,j,siz
siz:=40
every i:=0 to 8 do {
every j:=0 to 8 do {
Fg(win,»gray»)
DrawRectangle(win,i*siz,j*siz,siz,siz)
}
}
end

procedure square(win)
local i,j
every i:=0 to 2 do {
every j:=0 to 2 do {
WAttrib(win,»linewidth=2″)
Fg(win,»black»)
DrawRectangle(win,i*120,j*120,120,120)
}
}
end

procedure lremove(l,n)
local a,b
a:=l[1:n]
b:=l[n+1:*l+1]
return a|||b
end

procedure r_str()
local pull,s,i
s:=»»
pull:=[1,2,3,4,5,6,7,8,9]
every i:=1 to 9 do {
randomize()
siz:=?(*pull)
s||:=pull[siz]
pull:=lremove(pull,siz)
}
return s
end

Работают эти процедуры так: сначала с помощью процедуры grid, мы в окне программы просто чертим серую сетку из 81 квадрата (т.е. делаем обычное игровое поле, размером 9 на 9); затем с помощью процедуры square мы выделяем жирными черными линиями 9 квадратов размером 3 на 3 (т.е.

разделяем игровое поле на несколько крупных квадратов, согласно правилам судоку); далее используя вспомогательную процедуру lremove для удаления из списка n-ого элемента реализуем необходимую нам далее процедуру r_str, которая формирует одну строку нашего судоку и которая пригодиться нам далее.

• Теперь, начинается самое интересное: создание алгоритма построения судоку из одной строки случайно сгенерированных неповторяющихся цифр (вот зачем нам процедура r_str).
• Алгоритм построения судоку после очень долгих раздумий получился таким: сначала мы берем строку случайных цифр, а затем создаем из нее 8 оставшихся строк с помощью сдвига самой строки на некоторые фиксированные значения сдвига вправо (данные значения были найдены в ходе долгих поисков по интернету и некоторых экспериментов), затем все 9 строк из цифр мы размещаем на игровом поле, после чего случайным образом стираем некоторое количество цифр (количество цифр определено экспериментально).
• Реализация соответственно будет такой:

procedure sshift(s,n)
local a
a:=repl(s,n)
if s=0 then return s else return a[(n+1)+:(*s)]
end

procedure hide()
local i,j
every i:=0 to 9 do {
every j:=0 to 9 do {
if ((?100)-?7)>30 then {
EraseArea(i*40+1,j*40+1,38,38)
}
}
}
end

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

procedure sudoku()
local i,sh,s,j
s:=r_str()
sh:=[0,3,3,4,3,3,4,3,3]
every i:=1 to *sh do {
s:=sshift(s,sh[i])
every j:=1 to *s do {
Fg(«blue»)
DrawString((i-1)*40+15,(j-1)*40+25,s[j])
put(solv,i,j,s[j])
}
}
end

Процедура удаления цифр также весьма проста:

procedure hide()
local i,j
every i:=0 to 9 do {
every j:=0 to 9 do {
if ((?100)-?7)>30 then {
EraseArea(i*40+1,j*40+1,38,38)
}
}
}
end

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

procedure show_solve(col)
local i,j,zz,xx,yy,W
W:=WOpen(«size=360,400»)
grid(W)
square(W)
Fg(W,col)
every i:=1 to *solv by 3 do {
xx:=(solv[i]-1)*40+15
yy:=(solv[i+1]-1)*40+25
zz:=solv[i+2]
DrawString(W,xx,yy,zz)
}
case Event(W) of {
&lpress : if Active(W) then WClose(W)
}
end

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

procedure find_xy(a,b)
local i,j,xx,yy,t
every i:=1 to 9 do {
every j:=1 to 9 do {
xx:=i*40
yy:=j*40
if xx<=a<=(xx+40) & yy<=b<=(yy+40) then {
GotoXY(xx+15,yy+25)
Fg(«red»)
t:=WRead()
DrawString(xx+15,yy+25,t)
}
}
}
end

procedure clear_xy(a,b)
local i,j,xx,yy,t
every i:=1 to 9 do {
every j:=1 to 9 do {
xx:=i*40
yy:=j*40
if xx<=a<=(xx+40) & yy<=b<=(yy+40) then {
EraseArea(xx+1,yy+1,38,38)
}
}
}

link graphics,random
global solv,sud
procedure main()
local W,i,j
W:=WOpen(«size=360,400»)
solv:=list()
grid(W)
square(W)
sudoku()
hide()
repeat {
case Event() of {
&lpress : find_xy(&x,&y)
&rpress : clear_xy(&x,&y)
«s» : show_solve(«darkgreen»)
«q» : exit()

}
}
WDone()
end

1. Итак, пользователь делает ход, щелкнув левой клавишей мыши по интересующей его клетке и осуществив вод нужной цифры, отмена хода осуществляется щелчком правой клавишей мыши по неправильно поставленной цифре (защита от дурака, к сожалению, не предусмотрена, поскольку писалось все, как говорится, на коленке); а отображение правильного решения осуществляется по нажатию клавиши s.
2. Это выглядит так:
3. 
4. Подводя итоги, скажу, что мой папа очень был доволен тем, что получил в свои руки классную минималистическую игрушку, за которой он может отдохнуть от работы, однако, для себя я вынес следующую мораль: не стоит писать код в таком стиле, даже если программа делается за один вечер, а необходимо детально вникнуть в проблему и создать качественный код, поскольку внезапно может выясниться, что исходник программы всплывает через несколько лет…

Источник: https://lhs-blog.info/programming/iconlang/sudoku-svoimi-rukami/

Програмная реализация нахождения решения головоломки «Судоку» в 1С

 КИРИЛЛ ТКАЧЕНКО, инженер 1-й кат., ФГАОУ ВО «Севастопольский государственный университет», tkachenkokirillstanislavovich@gmail.com

Программная реализация нахождения решения головоломки «Судоку» в 1С

Рассматривается программная система для нахождения решения головоломки «Судоку» средствами языка программирования 1С. Разработанный модуль управляемого приложения выполняет поиск решения рекурсивным способом. Укрепим знания разработчика по типовым структурам данных и управляющим конструкциям

Наилучшие результаты в области творчества почти получаются, когда «автор… не был связан маркетинговыми и рекламными обязательствами… Ему ничего и никому не надо было доказывать. Он был волен использовать то, что ему нравилось…» [1].

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

Одной их таких головоломок является широко известная «Судоку».

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

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

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

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

Вследствие того, что на предприятиях и в организациях востребована среда 1С, стоит вести разработку именно на этой платформе, доступной для многих специалистов в ИТ-области, программистов и непрограммистов. Существуют программные реализации и на других языках программирования [2].

Программа и подпрограмма инициализации

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

Объявляются используемые несколькими подпрограммами модуля переменные и константы:

Перем N, КодСимволаНоль, Судоку, СчЗамен, ИсхДанные;

В константе N будет хранится длина стороны поля, равная 9, в КодСимволаНоль – код нуля. В переменной Судоку – все поле для головоломки, СчЗамен – количество произведенных замен, ИсхДанные – входные данные дляфункционирования.

• Процедура ИнициализацияКонстант() инициализирует константы:
• Процедура ИнициализацияКонстант()
•     N = 9;
•     КодСимволаНоль = КодСимвола(«0»);
• КонецПроцедуры
• В N присваивается 9, в КодСимволаНоль – код нуля.
• Процедура ИнициализацияПеременных() инициализирует переменные:
• Процедура ИнициализацияПеременных()
•     Судоку = Новый Массив(N, N);
•     ИсхДанные = Новый Массив();
•     ИсхДанные.Добавить(«000006201»);
•     ИсхДанные.Добавить(«070510060»);
•     ИсхДанные.Добавить(«006080059»);
•     ИсхДанные.Добавить(«120000000»);
•     ИсхДанные.Добавить(«080940500»);
•     ИсхДанные.Добавить(«590000000»);
•     ИсхДанные.Добавить(«001050073»);
•     ИсхДанные.Добавить(«030460080»);
•     ИсхДанные.Добавить(«000003604»);
•     СчЗамен = 0;
• КонецПроцедуры
• В Судоку помещается пустой массив 9 на 9, ИсхДанные – 9 строк по 9 символов входных данных (упрощенное хранение малого количества входных данных), СчЗамен – 0.
• Подпрограммы получения исходных данных и вывода поля
• Для вывода поля на экран служит процедура ПечатьСудоку():
• Процедура ПечатьСудоку()
•     Перем Рез, ТекСтрок, ТекСтолб;
•     Рез = «+—+—+—+»
• «»;
•     Для ТекСтрок = 0 По N — 1 Цикл
•         Для ТекСтолб = 0 По N — 1 Цикл
•             Если ТекСтолб % 3 = 0 Тогда
•                 Рез = Рез + «|»;
•             КонецЕсли;
•             Рез = Рез + Символ(Судоку[ТекСтрок][ТекСтолб] + КодСимволаНоль);
•         КонецЦикла;
•         Рез = Рез + «|»
• «»;
•         Если ТекСтрок % 3 = 2 Тогда
•             Рез = Рез + «+—+—+—+»
• «»;
•         КонецЕсли;
•     КонецЦикла;
•     Рез = Рез + «»
• «»;
•     Сообщить(Рез);
• КонецПроцедуры

Эта процедура выводит содержимое поля головоломки. Используются три переменные: Рез, ТекСтрок, ТекСтолб.

В переменной Рез находится результат, текстовая строка, разбитая на отдельные строки терминаторами. Здесь и далее переменная ТекСтрок содержит номер рассматриваемой в настоящее время строки, а ТекСтолб – соответственно столбца.

Построчно, а затем постолбцово рассматриваются данные ячеек игрового поля. Содержимое ячейки поля преобразуется в десятичную цифру, когда к ней добавляется код нуля, а затем полученная величина преобразуется в символ по коду.

Вконце каждой строки добавляется вертикальная черта с терминатором. Если номер столбца делится на 3 без остатка, то добавляется вертикальная черта.

Если номер строки делится на 3 с остатком 2, то есть после каждой третьей строки, торезультат конкатенируется с «+—+—+—+» и терминатором.

1. Преобразование входных данных во внутреннее представление производится процедурой СтрокиВСудоку():
2. Процедура СтрокиВСудоку()
3.     Перем ТекСтрок, ТекСтолб;
4.     Для ТекСтрок = 0 По N — 1 Цикл
5.         Для ТекСтолб = 0 По N — 1 Цикл
6.             Судоку[ТекСтрок][ТекСтолб] = КодСимвола(ИсхДанные[ТекСтрок], ТекСтолб + 1) — КодСимволаНоль;
7.         КонецЦикла;
8.     КонецЦикла;
9. КонецПроцедуры

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

• По строкам и по столбцам клетке поля присваивается цифра, которая должна там содержаться: для этого от кода символа в исходных данных отнимается код нуля.
• Подпрограмма поиска решения
• Поиск решения осуществляется в рекурсивной функции Решить():
• Функция Решить()

…

1.     Возврат Ложь;
2. КонецФункции
3. Эта функция возвращает ложь, если решение не было найдено.
4. Объявляются переменные:
5.     Перем ЦифраВСудоку;
6.     Перем НСтроки, НСтолбца;
7.     Перем НетНулей;
8.     Перем ТекСтрок, ТекСтолб, ТекЦифра;
9.     Перем НачСтрок, НачСтолб, КонСтрок, КонСтолб;
10. В одномерном массиве ЦифраВСудоку хранится вектор флажков, отмечающих встречу с цифры на поле, чтобы избежать ее повторного использования.
11. В индексных переменных НСтроки и НСтолбца находится номер найденного нуля.
12. Во флажке НетНулей отмечается факт его ненахождения.
13. Номер текущих рассматриваемых строки и столбца располагаются в ТекСтрок и ТекСтолб соответственно, а десятичной цифры – в ТекЦифра.
14. Граничные индексы заполнения поля для строк – НачСтрок и КонСтрок, столбцов – НачСтолб и КонСтолб.
15. Присваивается начальное значение:
16.     ЦифраВСудоку = Новый Массив(10);
17.     НСтроки = 0;
18.     НСтолбца = 0;
19.     НетНулей = Истина;
20. Новый массив в ЦифраВСудоку, начальные нули – в НСтроки, НСтолбца, отсутствие нулей на поле НетНулей – Истина.
21. Ищется первый сверху и слева нуль:
22.     ТекСтрок = 0;
23.     Пока НетНулей И (ТекСтрок < N) Цикл
24.         ТекСтолб = 0;
25.         Пока НетНулей И (ТекСтолб < N) Цикл
26.         Если Судоку[ТекСтрок][ТекСтолб] = 0 Тогда
27.                 НетНулей = Ложь;
28.                 НСтроки = ТекСтрок;
29.                 НСтолбца = ТекСтолб;
30.             КонецЕсли;
31.             ТекСтолб = ТекСтолб + 1;
32.         КонецЦикла;
33.         ТекСтрок = ТекСтрок + 1;
34.     КонецЦикла;

Поиск выполняется типовым алгоритмом для двумерного массива с ограничениями на первый найденный элемент. Перед внешним циклом с предусловием счетчику ТекСтрок присваивается 0.

Предусловием является одновременная истинность: отсутствие нулей на поле и выхода за границу поля по строкам. Выполняется тело цикла, в конце происходит увеличение счетчика ТекСтрок.

Выполняется тело внутреннего цикла, в конце происходит увеличение счетчика ТекСтолб. В теле внутреннего цикла проверяется условие равенства ячейки поля нулю. При его выполнении фиксируются столбец и строка найденной ячейки и факт наличия нулей.

•     Если НетНулей Тогда
•         Возврат Истина;
•     КонецЕсли;
• В случае ненахождения нулевого элемента головоломка считается успешно решенной.
• Считается, что ни одна из цифр не повторяется:
•     Для ТекЦифра = 0 По 9 Цикл
•         ЦифраВСудоку[ТекЦифра] = Ложь;
•     КонецЦикла;
• Границы для заполнения цифрами соответствуют квадрату 3 на 3, в котором находится найденный нулевой элемент:
•     НачСтрок = Цел(НСтроки / 3) * 3;
•     НачСтолб = Цел(НСтолбца / 3) * 3;
•     КонСтрок = НачСтрок + 3;
•     КонСтолб = НачСтолб + 3;

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

1. Все имеющиеся в «кресте» для этого элемента цифры отмечаются как присутствующие:
2.     Для ТекСтрок = 0 По N — 1 Цикл
3.         ЦифраВСудоку[Судоку[НСтроки][ТекСтрок]] = Истина;
4.         ЦифраВСудоку[Судоку[ТекСтрок][НСтолбца]] = Истина;
5.     КонецЦикла;
6. В цикле со счетчиком для всех ячеек, у которых номер строки соответствует номеру строки нулевой ячейки или номер столбца – столбцу нулевой ячейки.
7. А также все имеющиеся в квадрате этого элемента цифры отмечаются как присутствующие:
8.     Для ТекСтрок = НачСтрок По КонСтрок — 1 Цикл
9.         Для ТекСтолб = НачСтолб По КонСтолб — 1 Цикл
10.             ЦифраВСудоку[Судоку[ТекСтрок][ТекСтолб]] = Истина;
11.         КонецЦикла;
12.     КонецЦикла;
13. То есть для всех ячеек, строки которых имеют номера НачСтрок, …, КонСтрок – 1 и столбцы – номера НачСтолб, …, КонСтолб – 1, содержащиеся в этих ячейках цифры отмечаются как присутствующие.
14. Для каждой возможной десятичной цифры:
15.     Для ТекЦифра = 1 По 9 Цикл
16.         Если Не ЦифраВСудоку[ТекЦифра] Тогда
17.             СчЗамен = СчЗамен + 1;
18.             Судоку[НСтроки][НСтолбца] = ТекЦифра;
19.             Если Решить() Тогда
20.                 Возврат Истина;
21.             КонецЕсли;
22.             Судоку[НСтроки][НСтолбца] = 0;
23.         КонецЕсли;
24.     КонецЦикла;

Если она не использована, то увеличивается счетчик изменений поля, затем эта цифра присваивается нулевому элементу. В случае успешного рекурсивного запуска решения возвращается Истина. Иначе элементу возвращается нулевое значение, и процесс повторяется.

• Подпрограмма запуска
• Головная процедура Главная() выполняет запуск :
• Процедура Главная()
•     ИнициализацияКонстант();
•     ИнициализацияПеременных();
•     СтрокиВСудоку();
•     ПечатьСудоку();
•     Сообщить(«»);
•     Решить();
•     ПечатьСудоку();
•     Сообщить(«»);
•     Сообщить(«Число замен: » + СчЗамен);
•     Сообщить(«»);
• КонецПроцедуры
• Происходит инициализация констант, переменных, ввод исходных данных и их вывод сразу, поиск решения, вывод результата.
• Точка входа достаточно проста: Главная();.

Полный исходный код и результаты работы на сайте журнала http://samag.ru.

1. 
2. Рисунок 1. Результаты работы программы
3. Полученное решение хорошо демонстрирует применение базовых элементов языковых средств 1С по управлению процессом вычислений, в частности рекурсивную обработку информации, циклические структуры, условные операторы, иможет найти свое место при разработке и отладке нетривиальных алгоритмов оперативного управления.

Источник: http://samag.ru/archive/article/3544