Решаем судоку. Часть 4 - Расчет всех кандидатов для судоку.

Всем привет, меня зовут Андрей!

Продолжим решать судоку.

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

Напомним, что у нас было следующее судоку:

Рис. 1. Исходное судоку.

Для выявления ячеек, у которых может быть кандидатом единица (единичка), мы составили 3 таблицы:

Рис. 2. Таблицы, помогающие решать судоку.

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

В данной статье мы расскажем, как находить все остальные кандидаты – ведь единицы – это частный случай, а кандидатом может быть любое число от 1 до 9 включительно.

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

Итак, продолжим решать судоку.

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

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

=ЕСЛИ(СМЕЩ(B2;1;1)=п;"**";СМЕЩ(B2;1;1))

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

=ЕСЛИ(ДВССЫЛ("кле_"&$N3&O$2)=п;"**";ДВССЫЛ("кле_"&$N3&O$2))

Вот тут-то и появилась необходимость в тех именах, которые мы присвоили клеткам основного судоку! Напомню, что мы присвоили имена каждой из клеток судоку, и эти имена были кле_А1, кле_А2, и так далее.

Скопировав эту формулу на весь диапазон клеток нашего квадратика, мы получим нужный нам результат. Левая верхняя клетка нашего квадратика будет привязана левой верхней клетке нашего основного судоку (потому что у нее есть имя, и это имя кле_А1. Правая верхняя клетка нашего квадратика будет привязана к правой верхней нашего основного судоку (это уже будет кле_А9), ну и так далее.

После изменения формул квадрата «Замена пустых ячеек на две звездочки» можно продолжить вычисление всех кандидатов для судоку.

Заполним еще три следующих квадрата:

Рис. 3. Сортируем кандидаты для судоку, находим единственные в строке, столбце или блоке.

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

1. Для «левого» квадрата (Один в строке) формула для левой верхней ячейки:

=ЕСЛИ(И($AV3=1;AM3=1);AM3;п)

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

Копирование этой формулы на все клетки квадрата «Один в строке» приведет к заполнению квадрата, корректировка формулы не понадобится.

2. Для «среднего» квадрата (Один в столбце) формула для левой верхней ячейки:

=ЕСЛИ(И(AM$12=1;AM3=1);AM3;п)

Здесь также – одна формула для всего квадрата.

3. Для «правого» квадрата (Один в квадратике) формула для левой верхней ячейки:

=ЕСЛИ(И($AM$13=1;AM3=1);AM3;п)

В отличие от первых двух случаев, здесь формулы будут различаться для каждого из квадратиков. Формула для левой верхней ячейки подойдет для первого квадратика (это диапазон ячеек Excel AM16-AO18):

=ЕСЛИ(И($AM$13=1;AM3=1);AM3;п)

Для второго квадратика (формула приводится для AP16, то есть снова для левой верхней ячейки нашего блока-квадратика):

=ЕСЛИ(И($AN$13=1;AP3=1);AP3;п)

Для третьего квадратика (тоже левая верхняя ячейка):

=ЕСЛИ(И($AO$13=1;AS3=1);AS3;п)

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

Ноль правее квадрата «Один в квадратике» означает, что у нас нет таких «однозначных» кандидатов-единиц. Рассчитывается это число просто:

=СЧЁТ(O16:W24)+СЧЁТ(AA16:AI24)+СЧЁТ(AM16:AU24)

То есть, мы рассчитали сумму «однозначных» кандидатов по всем трем квадратам.

Теперь заполним еще два квадрата:

Рис. 4. Находим новое судоку с учетом новых кандидатов-единиц:

Здесь всё просто. «Левый» квадрат – это объединение предыдущих трех квадратов, а правый – новое судоку. Число в правом верхнем углу «левого» квадрата – это число новых чисел в нашем судоку. Этот нуль закрашен в красный цвет из-за условного форматирования. Ноль – это красный цвет, любое положительное число – зеленый цвет.

Формулы для «левого» квадрата (Все новые цифры 1):

=ЕСЛИ(МАКС(O16;AA16;AM16)=0;п;МАКС(O16;AA16;AM16))

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

Итак, формула для X27:

=СЧЁТ(O28:W36)

Формула для «правого» квадрата (Новое судоку):

=ЕСЛИ(МАКС(ДВССЫЛ("кле_"&$Z28&AA$27);O28)=0;п;МАКС(ДВССЫЛ("кле_"&$Z28&AA$27);O28))

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

Для расчета аналогичных кандидатов «двоек» нужно выполнить следующие действия:

1. Выделить все квадраты от N1 до AV36 включительно;
2. С помощью Ctrl+f заменить все ссылки в формулах на относительные:

Рис. 5. Замена всех ссылок в формулах на относительные

Если при заполнении каждого отдельно взятого квадрата нам были нужны эти «волшебные» знаки доллара, то теперь, когда все формулы выполнили свою задачу, а перед нами стоит другая задача – найти другие кандидаты для судоку – необходимость в этих значках «доллара» отпала. Оставив поле «заменить на:» пустым и нажав на кнопку «Заменить все», мы увидим, что выполнено 972 замен.

3. Скопировать ячейки судоку от N1 до AV36 включительно, и выделить ячейку N38, нажать на кнопку «Вставить».

Мы получим дублирование кандидатов «единичек»:

РИс. 6. Фрагмент листа Excel после копирования блока ячеек.

Здесь представлена только верхняя строчка вновь созданных кадратиков.

Строка 37 нашего судоку будет совсем пустой, это будет «граница» между кандидатами-единицами и кандидатами-двойками, то есть граница между несколькими большими фрагментами листа Excel.

Для превращения кандидатов-единиц в двойки нам потребуется:

- заменить заголовки квадратов (в AA38 заменить «единиц» на «двоек», в AM38 – заменить Кандидаты 1» на «Кандидаты 2»;

- выделить два «правых» квадратика, можно сразу – от AA40 до AU48 включительно;

- с помощью Ctrl+f Заменить все «один» на «два».

И всё – в третьем квадрате уже будут не единицы, а двойки:

Вот что должно получиться:

Рис. 7. Кандидаты-двойки.

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

Что касается второй строчки квадратов (Один в строке, один в столбце, один в квадратике) – там тоже понадобится небольшая корректировка формул. В каждом из этих столбцов – один в строке, один в столбце и один в квадратике нужно Заменить 1) на 2):

Рис. 8. Замена единиц на двойки.

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

А «третья строка» наших квадратов ("Все новые цифры..." и "Новое судоку") вообще не нуждается в корректировке.

По аналогичной схеме можно вычислить все кандидаты – до «кандидаты 9».

Кстати, вот как будут выглядеть кандидаты-девятки:

Рис. 9. Кандидаты - девятки.

Как мы видим, в нашем судоку есть две «однозначные» девятки – это те кандидаты, которые перестают быть кандидатами, потому что переходят в основное судоку.

После того, как мы вычислили все «кандидаты», нам остается всего чуть-чуть:

Рис. 10. Последние шаги к вычислению всех новых кандидатов судоку.

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

Формула для «левого» квадрата:

=СЧЁТ(AM3)+СЧЁТ(AM40)+СЧЁТ(AM77)+СЧЁТ(AM114)+СЧЁТ(AM151)+СЧЁТ(AM188)+СЧЁТ(AM225)+СЧЁТ(AM262)+СЧЁТ(AM299)

Для «среднего»:

=ЕСЛИ(O336=1;СУММ(AM3;AM40;AM77;AM114;AM151;AM188;AM225;AM262;AM299);п)

Для «правого»:

=СУММ(C3;O28;СМЕЩ(O28;1*37;0);СМЕЩ(O28;2*37;0);СМЕЩ(O28;3*37;0);СМЕЩ(O28;4*37;0);СМЕЩ(O28;5*37;0);СМЕЩ(O28;6*37;0);СМЕЩ(O28;7*37;0);СМЕЩ(O28;8*37;0);AA336)

Как видно из этой формулы, в функции "СМЕЩ" не обязательно указывать конкретные числа, вместо них можно указать даже формулы. Так часто бывает более удобно, и вероятность ошибок сводится к минимуму.

И самая последняя коррекция квадрата «новые судоку»:

Рис. 11. Новое судоку после фильтрации лишних значений.

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

=ЕСЛИ(И(AA336<>e;AA336<AM336);AA336;ЕСЛИ(AM336=0;п;AM336))

Формула для N347 (число цифр в новом судоку):

=СЧЁТ(O348:W356)

Формула для X347 (число новых цифр):

=N347-B2

Вот, в принципе, и всё. Остается только один макрос, автоматически добавляющий новые цифры в основное судоку:

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

Итак, вот макрос для решения простых судоку:

Sub Заполнить_очевидные()

10 If Cells(347, 24).Value > 0 Then

Range("O348:W356").Select

Selection.Copy

Range("C3:K11").Select

Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _

:=False, Transpose:=False

Range("B2").Select

End If

20 If Cells(347, 24).Value > 0 Then GoTo 10

End Sub

Как видно, мы назвали этот макрос «Заполнить_очевидные». Кроме того, мы видим, что при необходимости можно присвоить нумерацию всем или избранным строчкам макроса.

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

Вот результат работы этого макроса:

Рис. 12. Результат работы одного макроса - заполенное судоку.

А как решать более сложные судоку – я расскажу в следующих статьях, поэтому приглашаю всех любителей судоку подписаться на мой канал!