소수로만 이뤄진 마방진

요즘 사이트가 침체(?) 된거 같아 문제하나 투척하고 갑니다.^^

마방진은 각각의 숫자가 다르고 행과 열 및 대각선의 합이 같은 정사각 행렬이다.

가령 3x3 행렬의 마방진 중 대표적인 것은 다음과 같다.

4 9 2

3 5 7

8 1 6

그렇다면 3x3 마방진 중 500보다 작은 소수로만 이루어진 마방진을 몇개나 만들 수 있을까?

출력: 3x3 마방진 중 최대 500이하 소수로만 이뤄진 마방진의 갯수

단 1은 소수가 아니며, 회전하여서 같은 마방진은 1개로 생각한다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

2개의 풀이가 있습니다.

먼저 sieve와 primes를 초기화한 다음 찾아봅니다.

#define N 500

char sieve[N] = {0,};
int primes[N] = {0,};
int len = 0;

int main(int argc, const char * argv[]) {
    // sieve
    sieve[0] = -1;
    sieve[1] = -1;
    for (int i=2; i<N; i++) {
        if (sieve[i] == -1)
            continue;
        sieve[i] = 1;
        primes[len++] = i;
        for (int p=i*2; p<N; p += i) {
            sieve[p] = -1;
        }
    }

    int count = count_magic_squares(primes, len);
    printf("%d\n", count);

    return 0;
}

마방진 채우는 건 백트래킹을 사용하면 될것 같습니다.

// assume that nums[] are sorted
int count_magic_squares(int nums[], int len) {
    int count = 0;
    int square[9] = {0,};
    bt(square, 0, nums, len, &count);
    return count;
}

bt의 기본뼈대는 금방 만들어집니다. 한글자씩 채우면서 마방진 룰을 어기면 더이상 진행하지 않고 백트랙합니다.

void bt(int square[], int i, int nums[], int len, int* count) {
    if (i == 9) {
        ++(*count);
        return;
    }

    for (int k=0; k<len; k++) {
        if (nums[k]) { // not used
            square[i] = nums[k];
            nums[k] = 0; // use

            if (magic(square, i))
                bt(square, i+1, nums, len, count);

            nums[k] = square[i]; // recover
            square[i] = 0;
        }
    }
}

magic()은 채우진 숫자들로 마방진의 룰을 어기는지 확인합니다. (가로/세로/대각선 합이 같다) 여기서 조금이라도 빨리 룰 체크가 가능하도록 채우는 순서를 조금 바꿔봤습니다.

// 0 1 2
// 3 5 6
// 4 8 7

int magic(int s[], int i) {
    if (i < 3) return 1;
    int sum = s[0] + s[1] + s[2];

    if (i < 4) return 1;
    if (s[0] + s[3] + s[4] != sum) return 0;

    if (i < 5) return 1;
    if (s[2] + s[5] + s[4] != sum) return 0;

    if (i < 6) return 1;
    if (s[3] + s[5] + s[6] != sum) return 0;

    if (i < 7) return 1;
    if (s[0] + s[5] + s[7] != sum) return 0;
    if (s[2] + s[6] + s[7] != sum) return 0;

    if (i < 8) return 1;
    if (s[4] + s[8] + s[7] != sum) return 0;
    if (s[1] + s[5] + s[8] != sum) return 0;
    return 1;
}

이러면 .. 오래 걸려도 답은 나옵니다. 그런데.. 그 답은 90도씩 4번 회전 가능하고 거기다 거울상이 있으니 총 8번 중복되어 계산됩니다. 그냥 마지막에 8로 나눠줘도 되고 쉽게 기준 점을 정해서 0번이 2번과 4번보다 커야하고(회전 방지), 2번이 4번보다 커야 하고(거울상 방지)의 규칙을 추가하면 됩니다.

오래 걸리는 문제는.. 잘 모르겠네요. 일단 넣어보는 소수가 정렬되었다는 점을 이용해서 우선은 더 큰 값이 들어오는 걸 방지하는 것도 될 것 같아요. 그래서 룰을 어겼을 때 0을 반환하는 대신 더 큰 값은 시도하지 마라는 의미로 -1을 반환한다면 .. 조금 더 단축될 것 같습니다.

int magic(int s[], int i) {
    if (i < 2) return 1;
    if (s[0] < s[2]) return -1;    // 중복제거 및 s[2] 자리에 더 큰 값은 시도하지 마라 (-1)

    if (i < 3) return 1;
    int sum = s[0] + s[1] + s[2];  // 합을 구했음

    int s4 = sum - s[0] - s[3];    // s[4] 자리에 와야 하는 값이 정해짐
    if (s4 < 2) return -1;         // 만약 2보다 작다면 더 큰 값은 시도해볼 필요도 없음
    if (s4 > N || sieve[s4] != 1) return 0;  // 그 값이 소수 아니어도 더 볼 필요없음
    ...
}

이런 식으로 룰 체크를 조금 강화하니 조금 빨라지긴 하네요.

참, -1 반환 때문에 bt()도 바뀌었습니다.

void bt(int square[], int i, int nums[], int len, int* count) {
    if (i == 9) {
        //printsquare(square);
        ++(*count);
        return;
    }

    for (int k=0; k<len; k++) {
        if (nums[k]) { // not used
            square[i] = nums[k];
            nums[k] = 0; // use

            int result = magic(square, i);
            if (result == 1)
                bt(square, i+1, nums, len, count);

            nums[k] = square[i]; // recover
            square[i] = 0;

            if (result == -1) {  // no further search
                break;
            }
        }
    }
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

39개 나오는거 같네요.

간략한 풀이 과정입니다.

a1 a2 a3

a4 a5 a6

a7 a8 a9

의 각각의 합을 b 라고 하면

a1+a2+a3=b

a4+a5+a6=b

a7+a8+a9=b

f1) sum(a[1:9])=3*b 가 성립하고

a1+a5+a9=b

a2+a5+a8=b

a3+a5+a7=b

a4+a5+a6=b

f2) 3a5+sum(a[1:9])=4b

가 성립하게 됩니다.

f1)-f2) 를 하면

f3) a5=b/3 이게 되죠

이걸 가지고 마방진에 다시 입력을 해보면

b/3+d1 b/3+d2 b/3+d3

b/3+d4 b/3+0 b/3+d6

b/3+d7 b/3+d8 b/3+d9

이렇게 적어도 큰 문제는 없을거구요

d1+b/3 + 0+b/3 +d9+b/3 = b

d2+b/3 + 0+b/3 +d8+b/3 = b

d3+b/3 + 0+b/3 +d7+b/3 = b

d4+b/3 + 0+b/3 +d6+b/3 = b

이 성립하게되고

d9=-d1 d8=-d2 d7=-d3 d6=-d4 가 됩니다.

다시 적어보면

b/3+d1 b/3+d2 b/3+d3

b/3+d4 b/3+0 b/3-d4

b/3-d3 b/3-d2 b/3-d1

이 변화에는 큰 문제 없어보입니다. 이제 양측 끝쪽 가로 세로의 식을 적어보면

f3) b/3+d1 + b/3+d2 + b/3+d3 = b

f4) b/3+d3 + b/3-d4 + b/3-d1 = b 이고

d3=d4+d1 이 되고

-d2=d4+2*d1 가 되는것을 확인해볼수 있습니다.

즉 편차값 2개(d4,d1)가 있다면

이 두개를 더한값(d3=d4+d1)과

이 두개중 하나를 더 더한값 (-d2=d4+2*d1) 으로 편차값은 구성될수 있다고 볼수 있습니다.

그 내용을 python 3 로 표현하였습니다.

#마방진 테스트 함수 입니다. 
def is_mabang(test):
    _1st_line=sum(test[0:3])
    _2nd_line=sum(test[3:6])
    _3rd_line=sum(test[6:9])
    _1st_col=sum(test[0::3])
    _2nd_col=sum(test[1::3])
    _3rd_col=sum(test[2::3])
    RAO=sum(test[0::4])
    LAO=sum(test[2:7:2])
    result=[_1st_line,_2nd_line,_3rd_line,_1st_col,_2nd_col,_3rd_col,RAO,LAO]
    return len(set(result))==1

#솟수 생성함수입니다. 
def core03(l):
    if l<20:
        return [2, 3, 5, 7, 11, 13, 17, 19]
    SqrtL=int(l**0.5)
    TargetSet =set(range(SqrtL,l))
    TinyPrimeList=core03(int(l**0.50)+1)
    for i in TinyPrimeList:
        TargetSet = TargetSet -set(range(i*2,l,i))
    result= sorted(list(set(TinyPrimeList + list(sorted(TargetSet)))))
    return result
#500까지의 prime number 를 구합니다. 
total_prime_list=core03(500)
#print(len(total_prime_list))
#갯수는 95개군요. 
#이번에 알게된 재미난 툴 itertools 입니다. 
import itertools
'''
#뭔가.. 헛짓을 했더랬죠 이걸 실행시키면 hell gate 를 여는 느낌입니다. 
test01=itertools.permutations(total_prime_list,9)
k=0    
for j in test01:
    k+=1
    print(j)
    if k==200:
        break

test01=itertools.combinations(total_prime_list,9)
k=0    
for j in test01:
    k+=1
print(k)
'''
result01=[]
#중간 숫자를 기준으로 평균값이 중간이 나오는 숫자쌍을 찾아봅니다. 
for i in total_prime_list[4:-4]:
    temp=[]
    temp.append(i)
    if len(total_prime_list[total_prime_list.index(i)+1:])>=len(total_prime_list[:total_prime_list.index(i)]):
        for j in total_prime_list[:total_prime_list.index(i)]:
            if i-j+i in total_prime_list:
                temp.append(j)
                temp.append(i-j+i)
    else:
        for j in total_prime_list[total_prime_list.index(i)+1:]:
            if i-j+i in total_prime_list:
                temp.append(j)
                temp.append(i-j+i)
    #그러고는 그게 9개가 넘는지 확인하는 과정입니다. 
    if len(temp)>9:
        result01.append(sorted(temp))
#편차 a b c d(오름차순) 와 중간값 m 으로 9개의 숫자로 이루어진 마방진을 구성한다치면
#c==a+b 이며 d==a*2+b 또는 d==a+b*2일 경우 마방진이 성립하더군요.. 이외의 방법이 더 있을수 있지만 
#제가 가지고 있는 마방진의 지식은 이것이 전부였습니다.
#그래서 찾습니다. 꾸역꾸역   
#itertools.combinations 란 함수는 리스트 내부에서 주어진 숫자의 갯수만큼의 조합을 찾아내 주는...(말이 어렵습니다) 
#경우의 수 를 모두 찾아주지만 순서는 신경쓰지 않는... 아시죠? 중학교땐가 고등학교때인가.. ..

result02=[]
import itertools
for i in result01:
    temp01=[]
    temp02=sorted([i[(len(i)-1)//2]-x for x in i[:(len(i)-1)//2]])
    for j in itertools.combinations(temp02[:-2],2):
        if sum(j) in temp02:
            if sum(j)+j[0] in temp02:
                result02.append([i[(len(i)-1)//2],j[0],j[1],sum(j),sum(j)+j[0]])
            #한주영님의 지적으로 뒤늦게 추가. 또한번 더 수정!
            if sum(j)+j[1] in temp02:
                result02.append([i[(len(i)-1)//2],j[0],j[1],sum(j),sum(j)+j[1]])

#검산과정입니다 한주영님의 지적으로 버그 수정을 완료하였습니다. 
result03=[]
result04=[]
for i in result02:
    result03.append(sorted([i[0],i[0]-i[1],i[0]+i[1],i[0]-i[2],i[0]+i[2],i[0]-i[3],i[0]+i[3],i[0]-i[4],i[0]+i[4]]))
for i in result03:
    temp1=[]
    temp2=[]
    #d==a*2+b(a<b) 인 경우는 오름차수의 리스트가 다음과 같은 변형을 줄때 마방진이 형성됩니다. 
    for j in [1,6,5,8,4,0,3,2,7]:
        temp1.append(i[j])
    #d==b*2+a(a<b) 인 경우는 오름차수의 리스트가 다음과 같은 변형을 줄때 마방진이 형성됩니다. 
    for j in [6,5,1,0,4,8,7,3,2]:     
        temp2.append(i[j])
    if is_mabang(temp1):
        result04.append(temp1)
    elif is_mabang(temp2):
        result04.append(temp2)
    else:
        print(i)

'''
In [1]: result04
Out[1]:
[[17, 89, 71, 113, 59, 5, 47, 29, 101],         
 [41, 89, 83, 113, 71, 29, 59, 53, 101],        
 [103, 79, 37, 7, 73, 139, 109, 67, 43],        
 [29, 131, 107, 167, 89, 11, 71, 47, 149],      
 [139, 127, 43, 7, 103, 199, 163, 79, 67],      
 [37, 151, 139, 211, 109, 7, 79, 67, 181],      
 [157, 151, 73, 43, 127, 211, 181, 103, 97],    
 [43, 181, 157, 241, 127, 13, 97, 73, 211],     
 [173, 149, 71, 29, 131, 233, 191, 113, 89],    
 [47, 191, 173, 263, 137, 11, 101, 83, 227],    
 [199, 151, 67, 7, 139, 271, 211, 127, 79],     
 [59, 197, 191, 281, 149, 17, 107, 101, 239],   
 [61, 199, 193, 283, 151, 19, 109, 103, 241],   
 [37, 271, 163, 283, 157, 31, 151, 43, 277],    
 [71, 233, 197, 293, 167, 41, 137, 101, 263],   
 [53, 251, 197, 311, 167, 23, 137, 83, 281],    
 [233, 197, 89, 29, 173, 317, 257, 149, 113],   
 [257, 191, 89, 11, 179, 347, 269, 167, 101],   
 [251, 233, 89, 29, 191, 353, 293, 149, 131],   
 [71, 269, 233, 353, 191, 29, 149, 113, 311],   
 [73, 277, 229, 349, 193, 37, 157, 109, 313],   
 [43, 349, 241, 409, 211, 13, 181, 73, 379],    
 [137, 281, 263, 353, 227, 101, 191, 173, 317], 
 [317, 263, 101, 11, 227, 443, 353, 191, 137],  
 [89, 347, 281, 431, 239, 47, 197, 131, 389],   
 [73, 379, 271, 439, 241, 43, 211, 103, 409],   
 [331, 283, 109, 19, 241, 463, 373, 199, 151],  
 [61, 379, 283, 463, 241, 19, 199, 103, 421],   
 [71, 419, 263, 443, 251, 59, 239, 83, 431],    
 [41, 443, 269, 479, 251, 23, 233, 59, 461],    
 [47, 443, 281, 491, 257, 23, 233, 71, 467],    
 [173, 347, 269, 359, 263, 167, 257, 179, 353], 
 [137, 359, 293, 419, 263, 107, 233, 167, 389], 
 [59, 467, 281, 491, 269, 47, 257, 71, 479],    
 [149, 347, 311, 431, 269, 107, 227, 191, 389], 
 [347, 311, 149, 71, 269, 467, 389, 227, 191],  
 [359, 311, 137, 47, 269, 491, 401, 227, 179],  
 [103, 379, 331, 499, 271, 43, 211, 163, 439],  
 [101, 431, 311, 491, 281, 71, 251, 131, 461],  
 [167, 359, 353, 479, 293, 107, 233, 227, 419]] 
In [2]: len(result04)
Out[2]: 40


앗, 저는 40개로 알았는데.. 뭔가 놓친게 있나보군요. 어떻게 검증하면 되려나.. ㅠ.ㅠ - Han Jooyung, 2016/11/10 06:32 M D
+1 앗. 하나를 저도 빠트렸네요 그래도 39개 밖에 안나오는데요.. 저도 증명이 완벽하지가 않아서...ㅜ.ㅜ - Lee SeungChan, 2016/11/10 10:55 M D
일단 제 알고리즘엔 큰 문제는 없어보이는데... 소소한 버그로 갯수차이가 나는것 같습니다. ... 아마도 미묘한 숫자차이일거라고...ㅡ.ㅡ.... - Lee SeungChan, 2016/11/11 15:59 M D
+1 확인해보니 11개가 마방진이 아니네요. [37, 103, 79, 139, 73, 7, 67, 43, 109] [43, 139, 127, 199, 103, 7, 79, 67, 163] [73, 157, 151, 211, 127, 43, 103, 97, 181] [71, 173, 149, 233, 131, 29, 113, 89, 191] [67, 199, 151, 271, 139, 7, 127, 79, 211] [89, 233, 197, 317, 173, 29, 149, 113, 257] [89, 257, 191, 347, 179, 11, 167, 101, 269] [89, 251, 233, 353, 191, 29, 149, 131, 293] [101, 317, 263, 443, 227, 11, 191, 137, 353] [109, 331, 283, 463, 241, 19, 199, 151, 373] [137, 359, 311, 491, 269, 47, 227, 179, 401] 11개 중 마지막 줄(올려주신 결과 중 아래서 4번째)만 보자면 가로합은 모두 807인데 세로 합이 855, 807, 759 이렇게 다릅니다. 검증하는 코드에서 .. is_mabang을 호출하지 않아서 미리 발견하지 못하셨나봐요. ㅎㅎ - Han Jooyung, 2016/11/12 00:54 M D
... ㅇㅇ 왠지 빠트린게 있을듯 하였습니다. 마저 수정하였고 이제 모두 마방진임을 확인하였습니다. 한주영님 실례가 되지 않는다면 혹시 제 리스트보다 하나 더 나오는 조합을 공유해 주시면 어느부분이 부족한지 채워보겠습니다. - Lee SeungChan, 2016/11/12 03:42 M D
+1 [389,71,347,227,269,311,191,467,149] 입니다 - Han Jooyung, 2016/11/12 09:57 M D
덕분에 버그하나 잡고 40개를 찍게 되네요. 도와주신 한주영님께 감사드립니다. - Lee SeungChan, 2016/11/14 01:08 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 2
python x 1
기 타 x 1