난 멍청하기 때문에 계산기의 도움을 빌려서 2x3~3x3에 한해서 brute forcing을 했음.......


1 2 3 

4 5    같은 슬라이딩 퍼즐은


[[1, 2, 3], [4, 5, 0]]으로 표현 가능함. 


그리고 임의의 저런 배열에 대해서,

빈칸으로 사각형 움직인다는 게 0이랑 인접한 거 바꾸는 거니까,


주어진 배열에 대해서 그 다음 동작을 했을 때 나올 수 있는 경우의 수를 모두 알려주는 함수 f 를 정의했음.


가령, f([[1, 2, 3], [4, 5, 0]])는 


[

[[1, 2, 3], [4, 0, 5]],

[[1, 2, 0], [4, 5, 3]]

]


이렇게 나옴. 각각 

1 2 3

4   5


1 2 

4 5 3


을 의미함.



이제, A에다가  [[1, 2, 3], [4, 5, 0]] 원소 하나를 넣은 뒤에, 


A의 원소 각각에 함수 f를 각각 적용하면서 나오는 결과 중 A의 원소에 없는 게 있으면 A에다가 그 원소를 추가, 이 과정을 A에 추가되는 원소가 없을 때까지 반복함.  g(A)는 이걸 실행하는 거임.  


그러면 이 과정을 끝마친 다음에 A에 [[1 2 3], [5 4 0]]이 있는지 확인해 보면 되겠지?


구체적인 코드는 다음과 같음. 




import copy


def permute(A, x, y):

    C=copy.deepcopy(A)

    a=C[x[0]][x[1]]

    b=C[y[0]][y[1]]

    C[x[0]][x[1]]=b

    C[y[0]][y[1]]=a

    return C

    

def f(A):

    B=[]

    for i in range(len(A)):

        for j in range(len(A[i])):

            if(A[i][j]==0):

                z=(i, j)

    permu=[]

    i=z[0]

    j=z[1]

    if (i-1>-1):

        permu.append([i-1,j])


    if (i+1

        permu.append([i+1, j])

    if (j-1>-1):

        permu.append([i, j-1])

    if (j+1

        permu.append([i, j+1])

    for a in permu:

        B.append(permute(A, a, z))

    return B

    

def g(B):

    for a in B:

        for k in f(a):

            if not (k in B):

                B.append(k)



A=[]

A.append([[1, 2, 3], [4, 5, 0]])


g(A)


print(len(A))






와! 없음. 


즉,


1 2 3

4 5     에서 아무리 슬라이드를 해 봐도 


1 2 3

5 4      은 절대 만들 수가 없음. 


2 3 1

4 5   는 만들 수 있고.


4x4 사각형에서는 과연 어떻게 되려나?



3x3 사각형까지는 brute force해봤는데, 이거 계산하는 데 대략 12시간 정도 걸린 듯.


4x4에 대해서는 brute force할 엄두가 안 난다.