МЕТОД КАЧЕЛЕЙ ПЛЮС ЛАТИНСКИЕ КВАДРАТЫ

 

Часть I

 

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

 

Придётся напомнить читателям, что при построении идеального квадрата надо сначала посмотреть, к какой серии порядков относится выбранный вами порядок. Я различаю такие серии порядков для идеальных квадратов:

а) нечётные порядки не кратные 3: n = 3(2k - 1) + 2 и n = 3(2k + 1) - 2, k = 1, 2, 3…;

б) нечётные порядки кратные 3: n = 3(2k + 1), k = 1, 2, 3…;

в) чётно-чётные порядки кратные 8: n = 8k, k = 1, 2, 3…;

г) чётно-чётные порядки не кратные 8: n = 4(2k + 1), k = 1, 2, 3…

 

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

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

 

Теперь остановлюсь на серии порядков группы б), к которой принадлежат и квадраты 15-ого порядка.

 

В статье http://www.klassikpoez.narod.ru/idealob11.htm была найдена группа частных решений для идеальных квадратов данной серии порядков. Это значит, что найдена закономерность, по которой составляются начальные цепочки для всех идеальных квадратов этой частной группы, начиная с квадрата 15-ого порядка. А начальная цепочка, как известно, в методе стандартных качелей определяет всё, что нужно для формирования образующей таблицы. По образующей таблице элементарно строится и сам идеальный квадрат. Алгоритм этот не был реализован, то есть не составлена программа, позволяющая построить квадрат любого порядка из данной серии порядков (только один квадрат, поэтому группа и названа группой частных решений).

 

Посмотрю на эту группу частных решений с точки зрения построения с помощью латинских квадратов. В статье, посвящённой построению идеальных квадратов 15-ого порядка с помощью ортогональных латинских квадратов, был рассмотрен пример для группы идеальных квадратов, построенных методом стандартных качелей. Установлено, по какой схеме составляются латинские квадраты. Приведу ещё один пример для того, чтобы представляемая здесь группа частных решений была полной. На рис. 1 вы видите идеальный квадрат 15-ого порядка из рассматриваемой группы частных решений.

 

 

Рис. 1

 

Как я уже сказала, квадрат этот построен методом стандартных качелей, начальная цепочка имеет форму “ход конём”, шаги качания качелей 6+7 (через 6 ячеек влево, через 7 ячеек вправо). Начальная цепочка квадрата:

 

1  3  6  14  7  5  4  8  12  11  9  2  10  13  15

 

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

 

0  2  5  13  6  4  3  7  11  10  8  1  9  12  14

 

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

 

 

Рис. 2

 

Этот латинский квадрат является нетрадиционным идеальным магическим квадратом с магической константой 105. Обратите внимание на то, как в латинском квадрате повторилась начальная цепочка идеального квадрата, во всех ячейках начальной цепочки записано число 0 (что соответствует нулевому циклу качания качелей). Ещё заметьте, что номера циклов качания качелей в точном порядке (начиная с нуля) записаны в центральной строке латинского квадрата, а во всех остальных строках происходит циклический сдвиг этой последовательности чисел с постоянным шагом. Очевидно, что шаг этого сдвига определяется шагами качания качелей.

Вот и все премудрости составления первого латинского квадрата! А второй латинский квадрат в этой схеме получается из первого отражением относительно горизонтальной оси симметрии.

 

Всё очень просто. И переходим теперь к построению идеального квадрата следующего порядка в данной серии порядков – 21-ого. В указанной выше статье берём начальную цепочку для этого идеального квадрата:

 

1  3  6  20  7  5  4  8  12  9  11  13  10  14  18  17  15  2  16  19  21

 

Как по начальной цепочке определить номера циклов качания качелей, читатели уже знают. Шаги качания качелей в этом квадрате будут такие: 9+10. Составляем первый латинский квадрат (рис. 3):

 

 

Рис. 3

 

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

 

c_ij = 21*a_ij + b_ij +1

 

где a_ij – элементы первого латинского квадрата, b_ij – соответствующие элементы второго латинского квадрата, c_ij – соответствующие элементы идеального квадрата.

 

Напомню так же, что первый и второй латинские квадраты можно поменять местами.

На рис. 4 вы видите готовый идеальный квадрат 21-ого порядка. Это второй квадрат из рассматриваемой группы частных решений.

 

 

Рис. 4

 

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

 

Очевидно, что приведённый алгоритм легко реализовать. При построении этой группы частных решений методом качелей я построила вручную (то есть без программы) идеальный квадрат 51-ого порядка. Предлагаю читателям построить другие идеальные квадраты из этой группы с помощью латинских квадратов. А также реализовать этот очень простой алгоритм, то есть составить программу, которая позволит построить идеальный квадрат любого порядка, принадлежащий рассматриваемой группе частных решений. Продублирую здесь начальные цепочки, которые составлены для идеальных квадратов рассматриваемой частной группы, n = 15–111 (рис. 5).

 

 

                                                     Рис. 5

 

Понятно, что составление начальных цепочек может быть продолжено для следующих порядков. Начиная с 63-ого порядка, показаны половины начальных цепочек. Совершенно очевидно, как по первой половине начальной цепочки составляется вторая половина: все числа, симметрично расположенные относительно центрального числа начальной цепочки (оно выделено красным цветом), комплементарны, то есть в сумме дают одну и ту же величину – (n+1). А центральное число начальной цепочки равно половине этой суммы. Используя начальные цепочки из этой таблицы, я построила вручную идеальные квадраты 15-ого, 21-ого, 27-ого, 33-ого и 51-ого порядков методом качелей (для порядков 15, 21 и 27 составлены также программы). Здесь было показано построение идеальных квадратов 15-ого и 21-ого порядков с помощью ортогональных латинских квадратов, тоже вручную. Выбирайте, какой метод вам больше нравится. Стройте дальше идеальные квадраты. Это очень интересное и увлекательное занятие!

 

Пожалуй, покажу ещё один пример для закрепления. Будем строить с помощью ортогональных латинских квадратов идеальный квадрат 27-ого порядка. Берём из таблицы с рис. 5 начальную цепочку этого квадрата, вычитаем из каждого числа начальной цепочки единицу и получаем номера циклов качания качелей. Шаги качания качелей в этом квадрате будут такие: 12+13. Вообще, для любого n из рассматриваемой серии порядков шаги качания для стандартных качелей определяются так: [(n-1)/2-1]+ (n-1)/2.

Всё готово для составления первого латинского квадрата. На рис. 6 вы видите этот латинский квадрат. Он является нетрадиционным идеальным магическим квадратом с магической константой 351.

 

 

Рис. 6

 

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

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

 

В программе, которую я здесь покажу, строится идеальный квадрат любого порядка из рассматриваемой серии порядков, но вы должны ввести в программу начальную цепочку. Итак, программа сначала запросит порядок квадрата, а затем первую половину начальной цепочки (до центрального числа, это число вводить не надо). Вторую половину начальной цепочки программа достроит сама. Как только вы введёте половину начальной цепочки, программа мгновенно выдаст вам идеальный квадрат. В таблице на рис. 5 есть начальные цепочки до порядка n=111. Все идеальные квадраты этой группы частных решений до этого порядка вы сможете построить по приведённой программе (если, конечно, позволят ресурсы памяти). Далее вы видите идеальный квадрат 27-ого порядка, который построен по этой программе в таком виде, как он записан в файл. Точно такой же квадрат был построен в статье http://www.klassikpoez.narod.ru/idealob11.htm методом качелей (см. рис. 5 в указанной статье, там квадрат помещён в матрицу).

 

213  320  237  272  346  268  378  460  381  438  512  412  518  625  602  552  36  578  661  712  14  72  150  692  181  124  101

 598  548  39  576  659  715  10  68  153  690  179  127  97  209  321  239  291  326  265  376  486  379  435  492  431  520  626

 317  240  293  345  245  373  484  405  433  489  411  539  628  599  544  35  579  657  713  13  64  149  693  177  125  100  205

 545  31  575  660  711  11  67  145  689  180  123  98  208  313  236  294  347  264  353  481  403  459  487  408  519  647  601

 232  290  348  266  372  461  400  457  513  406  516  627  620  547  32  571  656  714  9  65  148  685  176  126  96  206  316

 34  572  652  710  12  63  146  688  172  122  99  204  314  235  286  344  267  374  480  380  454  511  432  514  624  600  566

 289  340  263  375  482  399  434  508  430  540  622  597  546  53  574  653  706  8  66  144  686  175  118  95  207  312  233

 593  655  707  4  62  147  684  173  121  91  203  315  231  287  343  259  371  483  401  453  488  427  538  648  595  543  33

 341  262  367  479  402  455  507  407  535  646  621  541  30  573  674  709  5  58  143  687  171  119  94  199  311  234  285

 654  728  7  59  139  683  174  117  92  202  307  230  288  339  260  370  475  398  456  509  426  515  643  619  567  28  570

 258  368  478  394  452  510  428  534  623  616  565  54  568  651  708  26  61  140  679  170  120  90  200  310  226  284  342

 705  6  80  142  680  166  116  93  198  308  229  280  338  261  366  476  397  448  506  429  536  642  596  562  52  594  649

 369  474  395  451  502  425  537  644  615  542  49  592  675  703  3  60  161  682  167  112  89  201  306  227  283  334  257

 1  57  141  701  169  113  85  197  309  225  281  337  253  365  477  393  449  505  421  533  645  617  561  29  589  673  729

 473  396  447  503  424  529  641  618  563  48  569  670  727  27  55  138  681  188  115  86  193  305  228  279  335  256  361

 81  136  678  168  134  88  194  301  224  282  333  254  364  469  392  450  501  422  532  637  614  564  50  588  650  724  25

 388  446  504  420  530  640  610  560  51  590  669  704  22  79  162  676  165  114  107  196  302  220  278  336  252  362  472

 160  702  163  111  87  215  304  221  274  332  255  360  470  391  442  500  423  528  638  613  556  47  591  671  723  2  76

 445  496  419  531  636  611  559  43  587  672  725  21  56  157  700  189  109  84  195  323  223  275  328  251  363  468  389

 697  187  135  82  192  303  242  277  329  247  359  471  387  443  499  415  527  639  609  557  46  583  668  726  23  75  137

 497  418  523  635  612  555  44  586  664  722  24  77  156  677  184  133  108  190  300  222  296  331  248  355  467  390  441

 164  130  106  216  298  219  276  350  250  356  463  386  444  495  416  526  631  608  558  42  584  667  718  20  78  158  696

 414  524  634  604  554  45  582  665  721  16  74  159  698  183  110  103  214  324  217  273  330  269  358  464  382  440  498

 129  83  211  322  243  271  327  249  377  466  383  436  494  417  522  632  607  550  41  585  663  719  19  70  155  699  185

 525  630  605  553  37  581  666  717  17  73  151  695  186  131  102  191  319  241  297  325  246  357  485  385  437  490  413

 104  210  299  238  295  351  244  354  465  404  439  491  409  521  633  603  551  40  577  662  720  15  71  154  691  182  132

 629  606  549  38  580  658  716  18  69  152  694  178  128  105  212  318  218  292  349  270  352  462  384  458  493  410  517

 

Теперь приведу текст программы.

 

ТЕКСТ ПРОГРАММЫ

(язык QBASIC)

 

 5 OPEN "MK.txt" FOR OUTPUT AS #1

10 PRINT "VVEDITE PORYADOK KVADRATA"

15 INPUT N

20 IF N < 15 THEN 15

25 IF N / 2 - INT(N / 2) = 0 THEN 15

30 IF N / 3 - INT(N / 3) <> 0 THEN 15

35 IF N - 3 * INT(N / 3) = 1 THEN 15

40 IF N - 3 * INT(N / 3) = 2 THEN 15

45 DIM A(N, N), B(N, N), C(N, N)

50 PRINT "VVEDITE PERVUYU POLOVINU NACALNOJ CEPOCHKI"

55 K = (N - 1) / 2

60 FOR I = 1 TO K: INPUT A(K + 1, I): NEXT I

62 FOR I = 1 TO K: A(K + 1, I) = A(K + 1, I) - 1: NEXT I

65 A(K + 1, K + 1) = K

70 FOR I = N TO K + 2 STEP -1

75 A(K + 1, I) = N - 1 - A(K + 1, N + 1 - I)

80 NEXT I

100 Z = K + 2: J = N - K

110 FOR I = 1 TO K: A(Z, I) = A(Z - 1, I + J): NEXT I

115 FOR I = K + 1 TO N: A(Z, I) = A(Z - 1, I - K): NEXT I

120 Z = Z + 1

125 IF Z > N THEN 135

130 GOTO 110

135 Z = K

140 FOR I = 1 TO J: A(Z, I) = A(Z + 1, I + K): NEXT I

145 FOR I = J + 1 TO N: A(Z, I) = A(Z + 1, I - J): NEXT I

150 Z = Z - 1

155 IF Z < 1 THEN 165

160 GOTO 140

165 FOR I = 1 TO N

170 FOR M = 1 TO N

175 B(I, M) = A(N + 1 - I, M)

180 C(I, M) = N * A(I, M) + B(I, M) + 1

185 NEXT M

190 NEXT I

200 FOR X = 1 TO N

205 FOR Y = 1 TO N

210 PRINT C(X, Y);

215 PRINT #1, C(X, Y);

220 NEXT Y

225 PRINT : PRINT #1,

230 NEXT X

235 PRINT : PRINT #1,

240 CLOSE #1

250 END

 

Построенный квадрат программа запишет в файл MK.txt, а также выведет на экран монитора.

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

Мой Бейсик на удивление молодец сегодня! Он позволил мне построить идеальный квадрат 111-ого порядка. Вы можете посмотреть на этот квадрат здесь:

 

http://www.natalimak1.narod.ru/mk/id111.TXT

 

Только не забывайте, что порядки квадратов должны принадлежать рассматриваемой серии порядков, а именно быть нечётными, кратными 3 и не меньше 15. В общем виде данная группа порядков запишется так: n = 3(2k + 1), k = 2, 3, 4…

 

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

 

***

Продолжение читайте здесь:

 

http://www.natalimak1.narod.ru/kachlat1.htm

 

 

Читайте мою виртуальную книгу “Волшебный мир магических квадратов”:

 

http://www.klassikpoez.narod.ru/glavnaja.htm

 

 

22 – 23 августа 2008 г.

г. Саратов

 

       Пишите мне!

Приглашаю всех на форум!

На главную страницу