Формулировка задачи «магический квадрат»

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

Идея решения 1: исчерпывающий поиск

Основная идея состоит в том, чтобы изучить способы размещения чисел от 1 до 9 в таблице и проверить условие магического квадрата. Итак, главный вопрос: сколько существует способов заполнить такую ​​таблицу? Дай подумать!

Мы можем начать заполнять таблицу одним числом за раз: начиная с размещения 1 где-нибудь и заканчивая размещением 9.

  • Есть девять уникальных способов разместить 1, за которыми следуют восемь способов разместить 2, и так далее, пока последняя цифра 9 не будет помещена в единственную незанятую ячейку таблицы.
  • Значит, 9 · 8 · … · 1 = 9! = 362 880 способов расположить девять чисел в ячейках таблицы 3 × 3.
  • Следовательно, решение этой задачи с помощью полного перебора подразумевает создание всех 362 880 возможных расположений различных целых чисел от 1 до 9 в таблице и проверку для каждого из расположений, совпадают ли все его суммы строк, столбцов и диагоналей.

Если мы еще больше увеличим значение n, то алгоритму исчерпывающего поиска потребуется изучить множество возможных решений, чтобы получить окончательный ответ. Таким образом, это решение неэффективно, потому что объем работы невозможно выполнить вручную. Даже компьютеру потребовалось бы значительное время, чтобы закончить работу!

Итак, критический вопрос: каков был бы эффективный способ решить эту проблему? Можем ли мы получить некоторое математическое представление о проблеме, чтобы решить ее, используя меньшее число шагов? Давай подумаем!

Идея эффективного решения

Несложно решить эту загадку, доказав два критических ограничения магического квадрата 3x3: 1) Значение общей суммы будет равно 15, что также называется магической суммой 2) Центральная ячейка должна содержать значение 5.

Как мы знаем, сумма всех столбцов, строк и диагоналей равна, поэтому магическая сумма = сумма всех чисел в ее строках, деленная на количество строк = сумма всех столбцов, деленная на количество столбцов = (1 + 2 +··· + 9)/ 3 = 15. Таким образом, значение магической суммы равно 15.

Вторым шагом было бы найти значение центральной ячейки. Предположим, что числа в строке 1, строке 2 и строке 3 равны: (a, b, c), (d, e, f), (g, h, i). Здесь «е» — значение числа в центральной ячейке. Как мы можем найти это значение? Давай подумаем!

Как мы знаем, сумма каждой строки, диагонали и столбца будет равна 15. Итак, мы суммируем строку, столбец и диагональ, включающие центральную клетку, т.е. мы складываем числа во второй строке, втором столбце и двух основных диагонали. Вот уравнение:

=> (d + e + f ) + (b + e + h) + (a + e + i) + (g + e + c) = 4*15

=> 3e + (a + b + c) + (d + e + f ) + (g + h + i) = 60

=› 3e + сумма чисел от 1 до 9 = 60

=> 3e + 45 = 60

=> e = 5

Центральная ячейка должна содержать значение 5, а сумма двух других значений строки, диагонали или столбца, включая центральную ячейку, должна быть равна 10. Для достижения магической суммы у нас будет четыре возможных пары оставшихся 8 числа, что дает сумму, равную 10: (1, 9), (2, 8), (3, 7) и (4, 6). Итак, нам нужно построить магический квадрат, расположив вокруг центральной клетки четыре пары чисел. Думать! Глядя на симметрию стола, есть только два разных способа поставить 1 и 9: в углах стола и не в углах стола.

Но размещение чисел 1 и 9 в углах стола не может образовать магический квадрат. Думать! Предположим, мы поместили 1 в верхний левый угол и 9 в нижний правый угол. Если мы поместим число меньше 5 в верхний правый угол, у нас не будет волшебной суммы 15 в первой строке. Точно так же, если мы поместим число больше 5, у нас будет та же проблема с последним столбцом. Поэтому нам нужно игнорировать идею размещения пар (1, 9) в углах стола.

Теперь сосредоточимся на второй возможности разместить пару (1, 9) вокруг центральной строки или столбца таблицы. Есть четыре возможных способа поставить 1 и 9 в одну строку или в один столбец с 5. Для каждого варианта:

  • Строка, содержащая 1, должна быть заполнена 6 и 8.
  • Строка, содержащая 1, должна быть заполнена 2 и 4.
  • Строка, не содержащая 1 или 9, должна быть заполнена 3 и 7.

Как мы видим на рисунке, может быть 8 возможных магических квадратов 3 x 3. Для каждого возможного размещения пары (1, 9) мы можем получить два разных решения, которые являются отражением друг друга. Разумеется, все они симметричны и могут быть получены из одной из восьми вращением и отражением.

Некоторые важные факты, связанные с магическим квадратом 3x3:

  • Центральная ячейка должна содержать значение 5.
  • Значение магической суммы равно 15.
  • Диагональное расположение 1, 5 и 9 невозможно.
  • Строка, содержащая 1, должна быть заполнена 6 и 8.
  • Все 8 решений магического квадрата 3х3 симметричны и могут быть получены вращением и отражением друг друга

Критические идеи для изучения!

  • Количество различных магических квадратов порядка 2х2, 3х3, 4х4 и 5х5 равно 0, 1, 880, 275305224 (без учета полученных вращением и отражением). Точное количество магических квадратов 6x6 неизвестно.
  • С момента своего появления в древней Индии, Японии и Китае магические квадраты на протяжении тысячелетий очаровывали людей. Одна из нерешенных проблем заключается в том, как разработать общий алгоритм для генерации любого магического квадрата порядка NxN (N›2).
  • Можно использовать несколько известных алгоритмов построения магических квадратов произвольного порядка n ≥ 3, которые особенно эффективны для нечетных n. Конечно, эти алгоритмы не основаны на исчерпывающем переборе!

Наслаждайтесь обучением, наслаждайтесь алгоритмами!