Всем привет, меня зовут Андрей, это снова я!
Есть одна знаменитая шахматная задача: нужно разместить 8 ферзей на стандартной шахматной доске размером 8х8 таким образом, чтобы ферзи не угрожали друг другу.
Напомню, что ферзь - это такая шахматная фигура, которая может ходить и по вертикали, и по горизонтали, и по диагонали.
Существует ровно 92 варианта решения данной задачи. Давайте найдем все эти 92 варианта с помощью эксель.
Вначале создадим новый файл эксель, сохраним его как файл с поддержкой макросов. Пусть единица символизирует наличие ферзя в этой клетке. Затем начнем придумывать первый ("черновой") вариант решения задачи, даже если в нем не будут на первом этапе соблюдены все условия (имеются ввиду следующие условия: на каждой вертикали и на каждой горизонтали должен быть ровно 1 ферзь; на каждой диагонали - большой или маленькой - должно быть не больше одного ферзя. Только в этом случае будет считаться, что ферзи не будут угрожать друг другу):
Тут единицы символизируют те клетки шахматной доски, где могут находиться ферзи одного цвета. В строке № 9 эксель находятся суммы единиц по столбцам, а столбец I - это сумма единиц по строкам. В данном варианте, действительно, соблюдены не все условия (хотя в каждой строке и в каждом столбце есть только по одному ферзю (по одной единице), как и должно быть, но есть такая диагональ, которая содержит две единицы (два ферзя). Если кодировать эту диагональ так, как она кодируется в эксель, то это будет диагональ A1-H8 в эксель.
Но у шахматной доски есть свои обозначения клеток:
Если те единицы, что расположены на листе эксель на рисунке 1, превратить в ферзи на шахматной доске, то мы получим следующую картину:
Ферзи здесь неспроста не белые, а черные, потому что та задача, что перед нами стояла, решена не полностью (можно сказать, что не решена совсем).
Если ввести условную кодировку каждой позиции, состоящей из восьми ферзей, то приведенная выше позиция будет иметь код: 13572468, потому что, если читать все строчки сверху вниз, то в верхней строке ферзь будет в самом левом столбце (он же столбец № 1, если считать слева направо, во второй строке сверху ферзь будет в столбце № 3, в третьей строке - в столбце № 5, ну и так далее.
Теперь обозначим, где находятся все диагонали на шахматной доске (большие и маленькие), причем на каждой из этих диагонали должно быть не больше одного ферзя. Эти диагонали можно разбить на две группы:
- "восходящие" (потому что они параллельны восходящему графику y=x):
- "нисходящие" (потому что они параллельны нисходящему графику y=-x)
Итак, если на каждой вертикали и на каждой горизонтали в конечной расстановке ферзей может быть ровно 1 ферзь, то на каждой диагонали должно быть не больше одного ферзя (0 или 1), (потому что диагоналей у нас больше, чем ферзей).
Можно с помощью условного форматирования особо выделить ячейки в пределах квадрата от A1 до H8 эксель таким образом, чтобы особо выделялись две единицы, если они вдруг случайно окажутся в одной строке или в одном столбце.
Если сначала выделить весь диапазон от A1 до H8 эксель, то эту задачу можно решить с помощью всего одной формулы условного форматирования:
=ИЛИ(И($I1>1;A1=1);И(A$9>1;A1=1))
Это сама формула, а формат для этой формулы простой - красный цвет шрифта и такой же цвет заливки (фона).
Вот один из возможных результатов работы этого условного формата:
Здесь красные квадратики - это единицы, но они не видны,потому что цвет фона совпадает с цветом шрифта.
Кстати, к тем суммарным единицам, которые означают суммы строк и столбцов, тоже можно применить условное форматирование, чтобы все значения, не равные единице, как-то выделялись.
К ячейкам внутри квадрата A1-H8 можно также применить еще один вид условного форматирования. Его смысл в том, чтобы выделить каким-то цветом (например, оранжево-рыжим), такие пустые ячейки, если они являются частью того столбца, в котором находится ровно одна единица, или частью такой строки, в которой тоже находится ровно одна единица.
Если вначале выделить весь диапазон A1-H8, то можно будет потом применить следующую формулу условного форматирования:
=ИЛИ(И(A1<>1;$I1=1);И(A1<>1;A$9=1))
Это сама формула, а формат для нее простой: оранжевый текст и оранжевый фон.
А вот и результат применения тех двух формул условного форматирования, о которых только что говорилось, применительно к тем единицам, что уже были показаны на рисунке 1:
Благодаря такому формату, во-первых, единички становятся более заметными. А, кроме того, во-вторых, если вдруг мы захотим находить решение задачи о восьми ферзях вручную, без помощи макросов, то с каждым новым появлением единицы на поле в оранжево-рыжий цвет окрашиваются те клетки, в которых не должно быть второй единицы. Правда, учитываются только единицы в строках и столбцах, но не в диагоналях.
А для контроля диагоналей составим таблицу, в которой все диагонали превратятся в столбцы, потому что так их удобней контролировать и суммировать.
На своем канале я уже говорил про функцию СМЕЩ(), вот и тут она нам тоже пригодится.
Ячейки J1-J2 будут дублировать самую левую верхнюю из "восходящих" диагоналей, в ней всего 2 ячейки.
В ячейке J1 мы будем дублировать значение ячейки B1. Но формула будет не "=B1", а немного другой:
=СМЕЩ($A$1;0;1)
Действительно, по сравнению с ячейкой A1 ячейка B1 будет на 0 строк ниже (они находятся в одной и той же строке) и на 1 столбец правее.
В ячейке J2 будет формула:
=СМЕЩ($A$1;1;0)
По сравнению с ячейкой A1 ячейка A2 будет на 1 строку ниже 1 на 0 столбцов правее (они находятся в одном и том же столбце).
Мы видим, что эти формулы очень похожи, более того, для этой диагонали, если мы просуммируем смещение по строкам и смещение по столбцам, то получим одно и то же число (единицу, потому что 1=0+1).
Аналогичная ситуация будет для следующей диагонали, тоже "восходящей", но расположенной чуть ниже. Там будет 3 ячейки, а сумма смещений уже будет не 1, а 2. И так далее, пока не закончатся все "восходящие" диагонали: каждая сумма на 1 больше предыдущей.
Основные формулы для копий "восходящих" диагоналей приведены в галерее:
Что касается формул "нисходящих" диагоналей, там формулы похожие, но суммы будут изменяться уже по другому принципу.
G1 и H2 - это части самой правой верхней "нисходящей" диагонали.
Ячейка W1 дублирует ячейку G1, формула такая:
=СМЕЩ($A$1;0;6)
Действительно, по сравнению с ячейкой A1 ячейка G1 будет на 0 строк ниже (они находятся в одной и той же строке) и на 6 столбцов правее.
Ячейка чуть ниже (W2) дублирует ячейку H2, формула такая:
=СМЕЩ($A$1;1;7)
По сравнению с ячейкой A1 ячейка H2 будет на 1 строку ниже 1 на 7 столбцов правее.
Здесь мы видим, что если заполнять таблицу по столбцам, то в пределах одного и того же столбца цифры смещения будут увеличиваться на 1 и по строкам, и по столбцам, чем ниже формула, тем больше значения смещения и по строкам, и по столбцам.
Кроме того, можно вначале заполнить только верхнюю строчку, там тоже есть своя динамика. Если начало самой правой верхней "нисходящей" диагонали смещено относительно A1 на 0 строк и 6 столбцов, то следующая диагональ уже будет смещена на 0 строк и 5 столбцов, то есть мы имеем разницу в единицу.
Аналогично, следующая пара цифр будет 0 и 4, а после пары 0 и 0 (это часть самой большой "нисходящей" диагонали), будет пара 1 и 0, но теперь уже 1 - это смещение по строкам, а 0 - по столбцам. Затем 2 и 0, и так далее.
Все нужные формулы приведены в галерее.
Если для диапазона ячеек J1-AI8 применить условное форматирование, аналогичное тому, что мы уже применяли для диапазона от A1 до H8, то мы будем видеть как те диагонали, где есть как минимум два ферзя, так и те диагонали, где все в порядке.
Выделяем диапазон J1...AI8, вводим формулу
=И(J$9>1;J1=1)
Формат для данной формулы: красный шрифт и красный фон.
Вторая формула для данного (того же) диапазона:
=И(J$9=1;J1<>1)
Здесь формат - это рыжий фон и рыжий шрифт.
Если эти оба формата применить к той ситуации, что у нас была на первом рисунке, то мы получим:
Здесь к ячейкам девятой строки, где находятся суммы диагоналей, тоже применено условное форматирование. Красный фон и красный шрифт для всех тех ячеек, значение которых больше единицы. А больше единицы - это значит, что два ферзя угрожают друг другу на той или иной диагонали.
Идем дальше. В столбце AK с помощью функции ПОИСКПОЗ() автоматически вычисляем, на каком именно месте в каждой строке находится единица (если надо написать подробнее формулу, пишите в комментариях, я отвечу):
Затем высчитываем "контрольные суммы":
Здесь AK9 - это максимум среди ячеек A9...H9 (суммы единиц по вертикалям), AM1 - это максимум среди ячеек I1...I8 (суммы единиц по горизонталям), AO9 - это максимум среди ячеек J9...AI9 (суммы ферзей-единиц по диагоналям) AQ9 - это максимум среди трех только что названных максимумов. Красные квадратики - это цифры, которые больше единицы. Если AQ9 равно единице, то это значит, что все условия выполнены, и по вертикалям, и по горизонталям, и по диагоналям содержится нужное количество единиц-ферзей.
Теперь составим макрос, который будет перебирать все варианты расположения ферзей (единиц) в квадрате A1...H8 эксель. Мы уже говорили о том, что каждую ситуацию, при которой в одном столбце и в одной строке есть один ферзь (одна единица), можно закодировать с помощью цифр от 1 до 8. И если мы возьмем восьмизначные числа от 12345678 до 87654321 таким образом, что каждое из этих чисел будет состоять из разных цифр от 1 до 8 включительно, в соответствии с каждым из этих числом-шифром размещать единицы-ферзи в нужных клетках, каждый раз проверять все маленькие и большие диагонали, тогда мы точно сможем получить все 92 варианта, которые будут удовлетворять всем условиям, а именно: ферзи не будут угрожать друг другу ни по горизонталям, ни по вертикалям, ни по диагоналям.
Если бы мы перебирали все числа подряд от 12345678 до 87654321 включительно, тогда нам пришлось бы перебирать 40320 вариантов (это факториал числа 8). Мы применим "большую скорость", чтобы уменьшить время обработки данных. Но в самом середине макроса придется отменять ускорение, иначе не получится решить задачу правильно из-за того, что ввиду отсутствия пересчета ячеек не будет возможности постоянного слежения за контрольными суммами.
Составим макрос таким образом, чтобы сразу отсечь все очевидные неправильные варианты, например, те одинаковые единицы, что стоят на одной и той же диагонали совсем рядом друг с другом.
Вот самый оптимальный вариант макроса:
Sub GenerateNumbers_007()
'Ускорение_включить()
'отключаем обновление экрана
Application.ScreenUpdating = False
'Отключаем автоматический пересчет формул
Application.Calculation = xlCalculationManual
'Отключаем отслеживание событий
Application.EnableEvents = False
'Отключаем разбиение на печатные страницы
ActiveWorkbook.ActiveSheet.DisplayPageBreaks = False
m01 = 1
Dim i As Integer, j As Integer, k As Integer, l As Integer, m As Integer, n As Integer, p As Integer, q As Integer
Dim number As String
For i = 1 To 8
For j = 1 To 8
If j - i = 1 And j < 8 Then j = j + 1
If i - j = 1 And j < 5 Then j = j + 3
If i - j = 1 And j >= 5 Then
GoTo Next_j
End If
If j - i = 1 And j = 8 Then
GoTo Next_j
End If
If j <> i Then
For k = 1 To 8
If k - j = 1 And k < 8 Then k = k + 1
If j - k = 1 And k < 5 Then k = k + 3
If j - k = 1 And k >= 5 Then
GoTo Next_k
End If
If k - j = 1 And k = 8 Then
GoTo Next_k
End If
If k <> i And k <> j Then
For l = 1 To 8
If l - k = 1 And l < 8 Then l = l + 1
If k - l = 1 And l < 5 Then l = l + 3
If k - l = 1 And l >= 5 Then
GoTo Next_l
End If
If l - k = 1 And l = 8 Then
GoTo Next_l
End If
If l <> i And l <> j And l <> k Then
For m = 1 To 8
If m - l = 1 And m < 8 Then m = m + 1
If l - m = 1 And m < 5 Then m = m + 3
If l - m = 1 And m >= 5 Then
GoTo Next_m
End If
If m - l = 1 And m = 8 Then
GoTo Next_m
End If
If Abs(m - l) = 1 And m < 8 Then m = m + 1
If m <> i And m <> j And m <> k And m <> l Then
For n = 1 To 8
If n - m = 1 And n < 8 Then n = n + 1
If m - n = 1 And n < 5 Then n = n + 3
If m - n = 1 And n >= 5 Then
GoTo Next_n
End If
If n - m = 1 And n = 8 Then
GoTo Next_n
End If
If Abs(n - m) = 1 And n < 8 Then n = n + 1
If n <> i And n <> j And n <> k And n <> l And n <> m Then
For p = 1 To 8
If p - n = 1 And p < 8 Then p = p + 1
If n - p = 1 And p < 5 Then p = p + 3
If n - p = 1 And p >= 5 Then
GoTo Next_p
End If
If p - n = 1 And p = 8 Then
GoTo Next_p
End If
If Abs(p - n) = 1 And p < 8 Then p = p + 1
If p <> i And p <> j And p <> k And p <> l And p <> m And p <> n Then
For q = 1 To 8
If q - p = 1 And q < 8 Then q = q + 1
If p - q = 1 And q < 5 Then q = q + 3
If p - q = 1 And q >= 5 Then
GoTo Next_q
End If
If q - p = 1 And q = 8 Then
GoTo Next_q
End If
If Abs(q - p) = 1 And q < 8 Then q = q + 1
If q <> i And q <> j And q <> k And q <> l And q <> m And q <> n And q <> p Then
number = i & j & k & l & m & n & p & q
For s1 = 1 To 8
For s2 = 1 To 8
Cells(s1, s2) = 0
Next s2
Next s1
Cells(1, i) = 1
Cells(2, j) = 1
Cells(3, k) = 1
Cells(4, l) = 1
Cells(5, m) = 1
Cells(6, n) = 1
Cells(7, p) = 1
Cells(8, q) = 1
'Ускорение_выключить()
'Возвращаем обновление экрана
Application.ScreenUpdating = True
'Возвращаем автоматический пересчет формул
Application.Calculation = xlCalculationAutomatic
'Включаем отслеживание событий
Application.EnableEvents = True
If Cells(9, 43) = 1 Then
Cells(m01, 46) = number
m01 = m01 + 1
End If
'Ускорение_включить()
'отключаем обновление экрана
Application.ScreenUpdating = False
'Отключаем автоматический пересчет формул
Application.Calculation = xlCalculationManual
'Отключаем отслеживание событий
Application.EnableEvents = False
'Отключаем разбиение на печатные страницы
ActiveWorkbook.ActiveSheet.DisplayPageBreaks = False
End If
Next_q:
Next q
End If
Next_p:
Next p
End If
Next_n:
Next n
End If
Next_m:
Next m
End If
Next_l:
Next l
End If
Next_k:
Next k
End If
Next_j:
Next j
Next i
'Ускорение_выключить()
'Возвращаем обновление экрана
Application.ScreenUpdating = True
'Возвращаем автоматический пересчет формул
Application.Calculation = xlCalculationAutomatic
'Включаем отслеживание событий
Application.EnableEvents = True
End Sub
В этом макросе Next_j: (с двоеточием, как и все остальные строки, которые заканчиваются на двоеточие) - это номера строк самого макроса, строки можно в VBA нумеровать не только цифрами, но и другими удобными переменными. Главное - поставить после переменной, обозначающей номер строки, двоеточие. Некоторым строкам мы присвоили такие имена-номера для того, чтобы была возможность досрочно выходить из цикла for...next в тех случаях, если точно известно, что при этой комбинации цифр задачу с ферзями решить нельзя. Например, если один ферзь стоит в левом верхнем углу доски (первая строка сверху), то во второй сверху строке не может быть ферзя во втором столбце. Этим самым мы не будем перебирать варианты от 12345678 до 12876543, это уже 720 вариантов! (Имеются ввиду только те 8-значные числа, которые состоят из разных цифр от 1 до 8). Или еще пример: если в какой-то строке есть ферзь в предпоследнем столбце, то в следующей строке уже целых три последних столбца не могут содержать ферзя, поэтому надо при наличии подобных ситуаций досрочно завершать цикл for...next.
Время выполнения всего макроса даже на не самом мощном компьютере - около четырех минут. Результат - это 92 кода, символизирующих расстановки ферзей, они будут размещены в столбце AT эксель.
Весь конечный результат будет виден только после окончания работы макроса, а в процессе работы макроса можно или не видеть ни одного результата (в столбце AT), или можно видеть появление нужных цифр несколькими порциями.
Во время выполнения макроса можно наблюдать за единицами, которые очень быстро "скачут" по полю от A1 до H8 эксель, это достаточно красивое и интересное зрелище.
Если в какую-то свободную ячейку, например, AQ11, еще до начала выполнения этого макроса ввести формулу, в которой высчитывается сумма значений в столбце AT, то можно во время выполнения макроса следить за количеством найденных вариантов на том или ином этапе решения задачи (обычно значения заполняются "блоками" по несколько значений в каждом блоке).
Самый последний вариант расстановки ферзей будет иметь шифр 84136275, а расстановка ферзей согласно этому шифру будет следующая:
А вот и все возможные коды (шифры) расстановки ферзей, 92 варианта:
15863724 16837425 17468253 17582463 24683175 25713864 25741863 26174835 26831475 27368514 27581463 28613574 31758246 35281746 35286471 35714286 35841726 36258174 36271485 36275184 36418572 36428571 36814752 36815724 36824175 37285146 37286415 38471625 41582736 41586372 42586137 42736815 42736851 42751863 42857136 42861357 46152837 46827135 46831752 47185263 47382516 47526138 47531682 48136275 48157263 48531726 51468273 51842736 51863724 52468317 52473861 52617483 52814736 53168247 53172864 53847162 57138642 57142863 57248136 57263148 57263184 57413862 58413627 58417263 61528374 62713584 62714853 63175824 63184275 63185247 63571428 63581427 63724815 63728514 63741825 64158273 64285713 64713528 64718253 68241753 71386425 72418536 72631485 73168524 73825164 74258136 74286135 75316824 82417536 82531746 83162574 84136275