4차 마방진 찾기

4차 마방진을 구하는 가장 간단한 java 소스는 아래와 같은 형식이다

// row 1
for (a=1; a<=MAX; a++) {
  for (b=1; b<=MAX; b++) {
    for (c=1; c<=MAX; c++) {
      for (d=1; d<=MAX; d++) {
        if (a+b+c+d != 34) continue;
// row 2
for (e=1; e<=MAX; e++) {
  for (f=1; f<=MAX; f++) {
    for (g=1; g<=MAX; g++) {
      for (h=1; h<=MAX; h++) {
        if (e+f+g+h != 34) continue;

// row 3
for (i=1; i<=MAX; i++) {
  for (j=1; j<=MAX; j++) {
    for (k=1; k<=MAX; k++) {
      for (l=1; l<=MAX; l++) {
        if (i+j+k+l != 34) continue;

// row 4
for (m=1; m<=MAX; m++) {
  for (n=1; n<=MAX; n++) {
    for (o=1; o<=MAX; o++) {
      for (p=1; p<=MAX; p++) {
        if (m+n+o+p != 34) continue;

        // check sum(col 1,2,3,4)
        // check sum diagonal, reverse diagonal
}}}}  }}}}  }}}} }}}}


Intel i5-10400 2.90GHz CPU, Windows 10, Java 11 환경에서 32초만 880개 찾았습니다 


2024-11-03 11:12:38   1  2 15 16,  12 14  3  5,  13  7 10  4,   8 11  6  9
2024-11-03 11:12:39   1  2 15 16,  13 14  3  4,  12  7 10  5,   8 11  6  9
2024-11-03 11:12:39   1  2 16 15,  13 14  4  3,  12  7  9  6,   8 11  5 10
2024-11-03 11:12:39   1  3 14 16,  10 13  4  7,  15  6 11  2,   8 12  5  9
......
2024-11-03 11:13:11  16 13  2  3,   4  1 14 15,   5  8 11 10,   9 12  7  6
2024-11-03 11:13:11  16 13  2  3,   4  1 14 15,   9 12  7  6,   5  8 11 10
2024-11-03 11:13:11  16 13  3  2,   4  1 15 14,   5  8 10 11,   9 12  6  7
2024-11-03 11:13:11  16 13  3  2,   4  1 15 14,   9 12  6  7,   5  8 10 11

2024-11-03 11:13:11 Square44.solve(145):  0:00:32 cnt: 880


이렇게 단순한 코드말고 빠른 알고리즘을 찾아보자
위 코딩은 레고조각 16개를 조립하는 모양이다
오른쪽 그림과 같이 4개씩 긴 a,b,c,d,e,f 6개 조각을 조립하면 찾는 속도를 높일 수 있다



1~16중 4개를 선택해서 32가 만들어 진 순열을 2064개를 미리 만들어 놓고, 이를 이용해서 4차 마방진을 구하는 가장 간단한 java 소스는 아래와 같은 형식이다

public void solveUq() {
  for (byte[] ar : pm.getOnePm()) {
    for (byte[] br : getLike(0)) {
      for (byte[] cr : getLike(01)) {
        for (byte[] dr : getLike(10,11)) {
          for (byte[] er : getLike(20,21)) {
           for (byte[] fr : getLike(30,31)) {
    
             // check sum(col 1,2,3,4)
             // check sum diagonal, reverse diagonal

  }}}}
} 

public void solveDig(boolean is11) {
  // is11 : 1이 (0,0) 개 (1,1) 인가 ?
  ...
}



개선된 알고리즘을 적용하면 0.202초만 880개 찾았습니다


2024-11-03 13:59:30 Permu.makePerm(208):  0:00:00 nPerm: 2064
2024-11-03 13:59:30 Magic40.solve0(27): 
2024-11-03 13:59:30 Magic40.solve0(36): solveUq()  	 0.112  ans:464
2024-11-03 13:59:30 Magic40.solve0(40): solveDig00() 0.168  ans:208
2024-11-03 13:59:30 Magic40.solve0(44): solveDig11() 0.202  ans:208
순열 관리 모듈이 추가되어 로직은 다소 복잡하지만 속도는 약 160 배 빠르게 계산됩니다.


그럼 찾아진 마방진을 구경해 보자, 아래 문자열 위를 마우스로 움직여 봐요


유일(1,2)대각(1,1)대각(2,2)
Check 8BA9651ED2Bad E3587AC1942FSUM 50EB8D36279C
F03C478BA9651ED20DB6E3587AC1942FFA4150EB8D36279C
F03C5A96874B2DE10D7AE394B6C1582FF68190E74D3A2B5C
F03C69A5874B1ED20CB7F3486AD1952EEB4150FA9C36278D
F03C965A4B872DE10C7BF384A6D1592EE78150FA9C362B4D
F03CA5694B871ED20F96C35A78E1B42DEB4190F65C3A278D
F03CA785496B1ED20F5AC396B4E1782DE78190F65C3A2B4D
E03D49A7B6581FC20E97D34A68F1B52CDA6170CB8F34259E
E03D5B86974A2CF10E5BD386A4F1792CD6A170CB8F34295E
E03D79A4865B1FC20DA7F4386BC1925EDA61B0C74F38259E
E03D856B7A941FC20AD7F4386BC1952ED6A1B0C74F38295E
E03D974A5B862CF10F87D43A69E1B25CCB6170DA9E34258F
E03DB5684A971FC20BD6E5387CA1924FC7A1B0D65E38294F
D03E4A97B5682FC10B7CE592D6A1384FED2150FA8B47369C
D03E6B85A7491CF20AD7F5286CB1934EE69150FA8B473D2C
D03E7A94856B2FC10A7DF582C6B1394EED2180F75B4A369C
D03E865B79A42FC10F4B95A6E2D1783CE69180F75B4A3D2C
D03EA7496B851CF20F4BE5A192D6783CCA7160BD9F42358E
D03EB65849A72FC10F96A53C78E1D24BC7A160BD9F42385E
C03F596AB7842ED10F3CA596D2E1784BCA71D0B62F49358E
C03F7B84956A2ED10E97B52C68F1D34AC7A1D0B62F49385E
C03F7B84A6591DE20E3DB586C2F1794AFC2130ED8B56479A
C03FB74859A62ED10D7AB6C1E394582FF68190E72B5C4D3A
C03FB964578A2ED10B7CD6A1E592384FED2130FC9A56478B
C03FB7486A951DE209E7F6185CB2A34DE78130FC9A564D2B
F05A3C96872D4BE1097EF681C5B23A4DED2190F63A5C478B
F05A69C3872D1EB409E7F6183AD4C52BE78190F63A5C4D2B
F05A963C2D874BE1097EF681A3D45C2BD96240BFAE51378C
F05AC3692D871EB40CB7F61829E5D34AD78240BFAE51396C
E05B29C7D6381FA40BC7F61829E5D43ACF1270E98B5634AD
E05B3D86972C4AF10DA7B61C58F2E349CF1290E76B5834AD
E05B79C2863D1FA40BC7D61A38F4E529BC6170AD8F52439E
E05B836D7C921FA40D6BA7C1F294583EB6C170AD8F52493E
E05B972C3D864AF10B6DC7A1F492385EBC61D0A72F58439E
E05BD3682C971FA40B5EC792F4A1386DB6C1D0A72F58493E
B05E2C97D3684FA109F6E7185CA3B24DAD6170BC9E52438F
B05E6D83C7291AF40A5FD782E4B1396CA7C1D0B63E58492F
B05E7C92836D4FA1096FD782E4B13A5CFC1230DE8B6547A9
B05E863D79C24FA10A5FE781D4B2396CFA1450BE8D6327C9
B05EC7296D831AF4096FE781D4B23A5CEC3120DF9B64578A
B05ED63829C74FA10D3EA794F2C1586BE78120DF9B645C3A


4차 마방진 계산 java 소스 받기, Java Src 20개로 만들어진 Project 입니다

Download