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

Судоку в Excel как способ повторения и закрепления встроенных функций

В курсе информатики средней школы (УМК Угриновича Н.Д.) зачастую сложные темы лучше усваивается учениками с помощью игровых методов

В теме “Кодирование и обработка числовой информации” есть подтема “Электронные таблицы”, в которой ученики 8 и 11 классов (УМК Угриновича Н.Д.) изучают сложный раздел “Встроенные функции Excel”. Для того чтобы упростить подачу такого непростого материала и повысить мотивацию учащихся, я использую судоку.

Судоку – математическая игра-головоломка, известная в России довольно давно под названием “Магический квадрат”.

Классический вариант японского судоку – это квадрат 9х9 клеток, в котором необходимо расставить цифры от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом выделенном квадрате 3х3 все цифры были различны.

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

Нам потребуется знание одной математической функции: =СУММ(ячейка1;я чейка2)

и двух логических функций, совмещенных в одну сложную: =ЕСЛИ(И(ячейка1=45; ячейка2=45); “молодец!”; “попробуй еще!”)

Теперь можно начать писать формулы для проверки правильности решения судоку. Например, в 11 строке мы напишем все формулы для проверки строк квадрата судоку. Итак, в ячейке А11 будет находиться формула =СУММ(A1:I1), в ячейке В11 будет находиться формула =СУММ(A2:I2) и так далее аналогично до ячейки I11, в которой будет находиться формула =СУММ(A9:I9). Теперь в 12 строке проверим все столбцы, также используя диапазон ячеек. В ячейке А12 будет находиться формула =СУММ(A1:А9), в ячейке В12 будет находиться формула =СУММ(В1:В9) и так далее аналогично до ячейки I12, в которой будет находиться формула =СУММ(I1:I9).

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

То есть в ячейке А13 будет находиться формула: =СУММ(A1:С3), в ячейке В13 будет находиться формула: =СУММ(D1:F3) и т.д. И, наконец, в ячейке I13 будет находиться формула: =СУММ(G7:I9).

Так как известно, что сумма чисел от 1 до 9 равна 45, то, соответственно в диапазоне А13:I13 все ячейки должны быть равны 45, если судоку решено верно.

Теперь приступим к анализу полученных результатов. Для этого в ячейке К1 запишем следующую формулу:

=ЕСЛИ(И(A11=45; B11=45; C11=45; D11=45; E11=45; F11=45; G11=45; H11=45; I11=45; A12=45; B12=45; C12=45; D12=45; E12=45; F12=45; G12=45; H12=45; I12=45; A13=45; B13=45; C13=45; D13=45; E13=45; F13=45; G13=45; H13=45; I13=45); “МОЛОДЕЦ!”;”Попробуй еще!”).

Изначально функция ЕСЛИ выглядит так:

=ЕСЛИ(условие; если верно; если не верно).

Мы же сделали сложное условие с логической функцией И, чтобы условие было верным только в случае, если все 27 ячеек равны 45.

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

Классический вариант + дополнительное условие: по двум (главным) диагоналям все числа также должны быть различны. Для этого нам потребуется ввести к уже имеющимся еще две формулы примерно такого вида:

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

Читать еще:  Сложная сводная таблица в excel как сделать

Заполненные справа судоку служат для того, чтоб учитель мог проверить правильность написания формулы, просто введя набор цифр в ячейки Excel. (Приложение)

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

Мои ученики так увлекаются судоку, что принимают участие в чемпионате СНГ по судоку среди школьников, который проводит газета “Информатика”, издательство “Первое сентября”.

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

77314 просмотра

9 ответа

7130 Репутация автора

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

1 плюс

11 Репутация автора

Нелегко дать общее решение. Вам нужно знать несколько вещей, чтобы генерировать определенный вид судоку . например, вы не можете построить судоку с более чем девятью пустыми группами из 9 чисел (строки, блоки 3х3 или столбцы). Считается, что минимальные заданные числа (то есть «подсказки») в судоку с одним решением составляют 17, но позиции чисел для этого судоку очень специфичны, если я не ошибаюсь. Среднее число подсказок для Судоку составляет около 26, и я не уверен, но если вы выйдете из числа заполненной сетки до 26 и оставите их симметричным образом, у вас может быть действующее Судоку. С другой стороны, вы можете просто случайным образом выходить из чисел из завершенных сеток и проверять их с помощью CHECKER или других инструментов, пока не появится OK.

Автор: Daniel Размещён: 03.08.2011 10:14

16 плюса

12799 Репутация автора

Вы можете обмануть. Начните с существующей доски Судоку, которую можно решить, затем возитесь с ней.

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

Ни одно из этих изменений не сделает разрешимую плату неразрешимой.

Автор: rossum Размещён: 03.08.2011 11:29

29 плюса

34935 Репутация автора

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

Я сомневаюсь, что вы можете найти решение, которое было бы намного быстрее, чем это.

Автор: TMS Размещён: 08.08.2011 03:11

48 плюса

17059 Репутация автора

Читать еще:  Как сделать прайс для яндекс маркета в excel?

Вот как это делает моя собственная программа SuDoKu:

Начните с полной, действительной доски (заполнена 81 номерами).

Составьте список всех 81 позиций ячеек и перемешайте его случайным образом.

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

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

Если у текущей доски есть только одно решение, перейдите к шагу 3) и повторите.

Если текущая доска имеет более одного решения, отмените последнее удаление (шаг 3) и продолжите шаг 3 со следующей позиции из списка

Стоп, когда вы проверили все 81 позиции.

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

Конечно, это только вторая половина алгоритма. Первая половина состоит в том, чтобы сначала найти полную действительную доску (заполненную случайным образом!). Она работает очень похоже, но «в другом направлении»:

Начните с пустой доски.

Добавьте случайное число в одну из свободных ячеек (ячейка выбирается случайным образом, а число выбирается случайным образом из списка чисел, действительных для этой ячейки в соответствии с правилами SuDoKu).

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

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

10 плюса

273683 Репутация автора

Если P = NP, не существует алгоритма полиномиального времени для генерации общих задач судоку с одним решением.

В своей магистерской диссертации Такаюки Ято определил «Другая проблема решения» (ASP), где цель, учитывая проблему и какое-то решение, найти другое решение этой проблемы или показать, что ее не существует. Затем Ято определил ASP-полноту, проблемы, для которой трудно найти другое решение, и показал, что судоку является ASP-полной. Так как он также доказывает, что ASP-полнота подразумевает NP-твердость, это означает, что если вы разрешите использовать доски судоку произвольного размера, то не будет алгоритма за полиномиальное время, чтобы проверить, имеет ли созданная вами головоломка уникальное решение (если P = NP).

Извините, что испортил ваши надежды на быстрый алгоритм!

плюса

5015 Репутация автора

Я также думаю, что вам придется явно проверить уникальность. Если у вас меньше 17 акций, уникальное решение очень маловероятно: ничего не найдено, хотя пока не ясно, может ли оно существовать.)

Но вы также можете использовать SAT-решатель, в отличие от написания собственного алгоритма возврата. Таким образом, вы можете в некоторой степени регулировать, насколько трудно будет найти решение: если вы ограничите правила вывода, которые использует SAT-решатель, вы можете проверить, можете ли вы легко решить головоломку. Просто Google для «SAT решения судоку».

Автор: DaveFar Размещён: 02.09.2011 08:33

1 плюс

71 Репутация автора

Вот способ создать классическую головоломку судоку (головоломка судоку с одним и единственным решением; предварительно заполненные квадраты симметричны вокруг центрального квадрата R5C5).

1) начать с полной сетки (используя заполнение группы плюс круговое смещение, чтобы получить его легко)

Читать еще:  Как сделать рассылку по email из excel?

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

3) повторять (2) до тех пор, пока не будут проверены все числа.

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

1 плюс

11 Репутация автора

Решение состоит в том, чтобы разделить на 2 части:
A. Генерация шаблона чисел 600 миллиардов
B. Генерация шаблона маскирования

A) Для шаблона номера самый быстрый способ, который может генерировать уникальные комбинации без затрат времени на поиск или тестирование

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

Первая строка — числа в порядке возрастания.
Вторая строка также находится в порядке возрастания, но начинаются с 4 и вращаются.
Третья строка также находится в порядке возрастания, но начинаются с 7 и вращаются вокруг
строки 4,5,6: замените столбец из трех ячеек на верхний. правый столбец — 2 5 8 и сверните в ячейке 3×3 для последнего столбца
Строка 7,8,9: замените столбец из трех ячеек на верхний правый столбец — 3 6 9 и сверните в ячейке 3×3 для последнего столбца

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

Шаг 2. Перемешайте цифры и замените их во всех остальных ячейках.
Шаг 3. Произвольно переставьте столбцы 1,2 и 3 внутри себя.
Шаг 4. Произвольно переставьте столбцы 4,5 и 6 внутри себя.
Шаг 5. Произвольно переставьте столбцы 7,8 и 9. внутри себя
Шаг 6. Произвольная перестановка строк 1,2 и 3 внутри себя
Шаг 7. Произвольная перестановка строк 4,5 и 6 внутри себя
Шаг 8. Произвольная перестановка строк 7,8 и 9 внутри себя
Шаг 9. Произвольная перестановка в 3 группах столбцов размером 9×3
Шаг 10. Произвольно переставить в 3 ряда строк размером 3×9

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

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

Шаг 1: Начните с выбора 15 случайных местоположений из 81.
Шаг 2: Проверьте с помощью решателя, есть ли у него уникальное решение
Шаг 3: Если решение не уникально, выберите дополнительное местоположение. повторите шаги 2 и 3, пока не будет найдено уникальное решение

Это должно дать вам очень уникальную и быструю доску судоку.

Автор: gapjiba Размещён: 27.03.2019 09:02

плюса

13 Репутация автора

Один из способов генерировать судоку быстрее.

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

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

Вы можете пометить судоку с 9 сетками, обмен строк и столбцов должны выполняться в той же сетке. Как вы можете поменять строки 1-3, строки 4-6, строки 7-9, не обменивать строки 1-4 или строки 1-7. Вы также можете поменять сетку строк (поменять строку 1

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

Ссылка на основную публикацию
Adblock
detector