Problem:


フロッピーキューブ

フロッピーキューブをプログラミングで解いてみましょう。フロッピーキューブは図のように表面に色のついた９個の立方体から構成されている立体パズルで、キューブの列を回転させることによって、６つの各面の色をそろえます。 

フロッピーキューブに対しては下図のような４種類の操作を行うことができ、一回の操作で、端にある３つの隣接したキューブを１８０度回転することができます。わかりやすいように、図では、上面に＋(赤色)、下面に＊(緑色)、右前面に□(黄色)、左前面に●(青色)、右奥面に○(水色)、左奥面に■紫色) の記号が付いている状態を初期状態としています。

フロッピーキューブの初期状態が与えられるので、パズルを解くために必要な最小の操作回数を求めるプログラムを作成してください。 

入力

入力は以下の形式で与えられる。 

N
puzzle1
puzzle2
:
puzzleN

１行目のN (1 ≤ N ≤ 30) は操作回数を計算したいパズルの数である。続くN行に各フロッピーキューブの初期状態 puzzlei が与えられる。puzzlei は以下の形式で与えられる。 

p1 p2 p3 p4 p5 p6 p7 p8 p9 p10 p11 p12 p13 p14 p15 p16 p17 p18 p19 p20 p21 p22 p23 p24 p25 p26 p27 p28 p29 p30 

各フロッピーキューブの情報は 30 個の整数 pi (1 ≤ pi ≤ 6) からなる。pi は、下図のようにフロッピーキューブの各面に番号 i を振ったときの、そのキューブの面の色を表す。

パズルは、多くとも８回の操作で解くことができると仮定してよい。

出力

パズルごとに、最小の操作回数を１行に出力する。 

入出力例

入力例 

4
1 1 1 1 1 1 1 1 1 2 2 2 4 4 4 6 6 6 5 5 5 3 3 3 3 3 3 3 3 3
3 3 3 1 1 1 1 1 1 2 2 2 4 4 6 4 6 6 5 5 5 3 3 3 3 3 3 1 1 1
3 3 3 1 1 3 1 1 1 2 2 5 6 4 4 4 6 6 2 5 5 3 3 3 1 3 3 1 1 1
1 3 1 3 1 3 3 1 3 2 2 2 6 4 4 6 6 4 5 5 5 1 3 1 1 3 1 3 1 3

出力例

0
1
2
7



Sample input:
4
1 1 1 1 1 1 1 1 1 2 2 2 4 4 4 6 6 6 5 5 5 3 3 3 3 3 3 3 3 3
3 3 3 1 1 1 1 1 1 2 2 2 4 4 6 4 6 6 5 5 5 3 3 3 3 3 3 1 1 1
3 3 3 1 1 3 1 1 1 2 2 5 6 4 4 4 6 6 2 5 5 3 3 3 1 3 3 1 1 1
1 3 1 3 1 3 3 1 3 2 2 2 6 4 4 6 6 4 5 5 5 1 3 1 1 3 1 3 1 3


Sample output:
0
1
2
7

Submission status: Time Limit Exceeded

Solution code:
def op1 (p) :
    q = [i for i in p]
    q[12] = p[17]
    q[17] = p[12]
    q[6] = p[21]
    q[7] = p[22]
    q[8] = p[23]
    q[21] = p[6]
    q[22] = p[7]
    q[23] = p[8]
    q[9] = p[11]
    q[11] = p[9]
    return q

def op2 (p) :
    q = [i for i in p]
    q[14] = p[15]
    q[15] = p[14]
    q[0] = p[27]
    q[1] = p[28]
    q[2] = p[29]
    q[27] = p[0]
    q[28] = p[1]
    q[29] = p[2]
    q[18] = p[20]
    q[20] = p[18]
    return q

def op3 (p) :
    q = [i for i in p]
    q[9] = p[20]
    q[20] = p[9]
    q[0] = p[23]
    q[3] = p[26]
    q[6] = p[29]
    q[23] = p[0]
    q[26] = p[3]
    q[29] = p[6]
    q[15] = p[17]
    q[17] = p[15]

    return q

def op4 (p) :
    q = [i for i in p]
    q[11] = p[18]
    q[18] = p[11]
    q[2] = p[21]
    q[5] = p[24]
    q[8] = p[27]
    q[21] = p[2]
    q[24] = p[5]
    q[27] = p[8]
    q[14] = p[12]
    q[12] = p[14]

    return q

def valid (p) :
    for i in range(1, 9) :
        if (p[0] != p[i]) :
            return False

    for i in range(10, 12) :
        if (p[9] != p[i]) :
            return False

    for i in range(13, 15) :
        if (p[12] != p[i]) :
            return False

    for i in range(16, 18) :
        if (p[15] != p[i]) :
            return False

    for i in range(19, 21) :
        if (p[18] != p[i]) :
            return False

    for i in range(22, 30) :
        if (p[21] != p[i]) :
            return False
    return True

def solve (n, p) :

    if (n > 8) :
        return 100

    if (valid(p)) :
        return 0 

    s = [solve(n + 1, op1(p)), solve(n + 1, op2(p)), solve(n + 1, op3(p)), solve(n + 1, op4(p))]
    s.sort()
    return s[0] + 1
    

N = int(input())
for i in range(0, N) :
    p = [int(term) - 1 for term in input().split()]
    print(solve(0, p))

Submission status: Time Limit Exceeded

Solution code:
def op1 (p) :
    return (
        p[ 0],p[ 1],p[ 2],p[ 3],p[ 4],p[ 5],p[21],p[22],p[23],p[11],p[10],p[9],p[17],p[13],p[14],
        p[15],p[16],p[12],p[18],p[19],p[20],p[ 6],p[ 7],p[ 8],p[24],p[25],p[26],p[27],p[28],p[29]
    )
def op2 (p) :
    return (
        p[27],p[28],p[29],p[ 3],p[ 4],p[ 5],p[ 6],p[ 7],p[ 8],p[ 9],p[10],p[11],p[12],p[13],p[15],
        p[14],p[16],p[17],p[20],p[19],p[18],p[21],p[22],p[23],p[24],p[25],p[26],p[ 0],p[ 1],p [2]
    )
    q = [i for i in p]
    q[14] = p[15]
    q[15] = p[14]
    q[0] = p[27]
    q[1] = p[28]
    q[2] = p[29]
    q[27] = p[0]
    q[28] = p[1]
    q[29] = p[2]
    q[18] = p[20]
    q[20] = p[18]
    return q

def op3 (p) :
    return (
        p[23],p[ 1],p[ 2],p[26],p[ 4],p[ 5],p[29],p[ 7],p[ 8],p[20],p[10],p[11],p[12],p[13],p[14],
        p[15],p[16],p[17],p[18],p[19],p[ 9],p[21],p[22],p[ 0],p[24],p[25],p[ 3],p[27],p[28],p[ 6]
    )

def op4 (p) :
    return (
        p[ 0],p[ 1],p[21],p[ 3],p[ 4],p[24],p[ 6],p[ 7],p[27],p[ 9],p[10],p[18],p[14],p[13],p[12],
        p[15],p[16],p[17],p[11],p[19],p[20],p[ 2],p[22],p[23],p[ 5],p[25],p[26],p[ 8],p[28],p[29]
    )

def valid (p) :
    for i in range(1, 9) :
        if (p[0] != p[i]) :
            return False

    for i in range(10, 12) :
        if (p[9] != p[i]) :
            return False

    for i in range(13, 15) :
        if (p[12] != p[i]) :
            return False

    for i in range(16, 18) :
        if (p[15] != p[i]) :
            return False

    for i in range(19, 21) :
        if (p[18] != p[i]) :
            return False

    for i in range(22, 30) :
        if (p[21] != p[i]) :
            return False
    return True

def solve (n, p) :

    if (n > 8) :
        return 100

    if (valid(p)) :
        return 0 

    s = [solve(n + 1, op1(p)), solve(n + 1, op2(p)), solve(n + 1, op3(p)), solve(n + 1, op4(p))]
    s.sort()
    return s[0] + 1
    

N = int(input())
for i in range(0, N) :
    p = tuple([int(term) - 1 for term in input().split()])
    print(solve(0, p))

Submission status: Time Limit Exceeded

Solution code:
def op1 (p) :
    return (
        p[ 0],p[ 1],p[ 2],p[ 3],p[ 4],p[ 5],p[21],p[22],p[23],p[11],p[10],p[9],p[17],p[13],p[14],
        p[15],p[16],p[12],p[18],p[19],p[20],p[ 6],p[ 7],p[ 8],p[24],p[25],p[26],p[27],p[28],p[29]
    )
def op2 (p) :
    return (
        p[27],p[28],p[29],p[ 3],p[ 4],p[ 5],p[ 6],p[ 7],p[ 8],p[ 9],p[10],p[11],p[12],p[13],p[15],
        p[14],p[16],p[17],p[20],p[19],p[18],p[21],p[22],p[23],p[24],p[25],p[26],p[ 0],p[ 1],p [2]
    )
def op3 (p) :
    return (
        p[23],p[ 1],p[ 2],p[26],p[ 4],p[ 5],p[29],p[ 7],p[ 8],p[20],p[10],p[11],p[12],p[13],p[14],
        p[15],p[16],p[17],p[18],p[19],p[ 9],p[21],p[22],p[ 0],p[24],p[25],p[ 3],p[27],p[28],p[ 6]
    )
def op4 (p) :
    return (
        p[ 0],p[ 1],p[21],p[ 3],p[ 4],p[24],p[ 6],p[ 7],p[27],p[ 9],p[10],p[18],p[14],p[13],p[12],
        p[15],p[16],p[17],p[11],p[19],p[20],p[ 2],p[22],p[23],p[ 5],p[25],p[26],p[ 8],p[28],p[29]
    )

def valid (p) :
    for i in range(1, 9) :
        if (p[0] != p[i]) :
            return False

    for i in range(10, 12) :
        if (p[9] != p[i]) :
            return False

    for i in range(13, 15) :
        if (p[12] != p[i]) :
            return False

    for i in range(16, 18) :
        if (p[15] != p[i]) :
            return False

    for i in range(19, 21) :
        if (p[18] != p[i]) :
            return False

    for i in range(22, 30) :
        if (p[21] != p[i]) :
            return False
    return True

def solve (n, p) :

    if (n > 8) :
        return 100

    if (valid(p)) :
        return 0 

    s = [solve(n + 1, op1(p)), solve(n + 1, op2(p)), solve(n + 1, op3(p)), solve(n + 1, op4(p))]
    s.sort()
    return s[0] + 1
    

N = int(input())
for i in range(0, N) :
    p = tuple([int(term) - 1 for term in input().split()])
    print(solve(0, p))

Submission status: Accepted

Solution code:

def check(p):
    for i in range(1, 9):
        if p[i] != p[0]:
            return False
    for i in range(10, 12):
        if p[i] != p[9]:
            return False
    for i in range(13, 15):
        if p[i] != p[12]:
            return False
    for i in range(16, 18):
        if p[i] != p[15]:
            return False
    for i in range(19, 21):
        if p[i] != p[18]:
            return False
    for i in range(22, 30):
        if p[i] != p[21]:
            return False
    return True
    
    
def turn1(p):
    p[6], p[21] = p[21], p[6]
    p[7], p[22] = p[22], p[7]
    p[8], p[23] = p[23], p[8]
    p[12], p[17] = p[17], p[12]
    p[9], p[11] = p[11], p[9]
    

def turn2(p):
    p[0], p[27] = p[27], p[0]
    p[1], p[28] = p[28], p[1]   
    p[2], p[29] = p[29], p[2]
    p[14], p[15] = p[15], p[14]
    p[18], p[20] = p[20], p[18]
    
def turn3(p):
    p[0], p[23] = p[23], p[0]
    p[3], p[26] = p[26], p[3]
    p[6], p[29] = p[29], p[6]
    p[20], p[9] = p[9], p[20]
    p[17], p[15] = p[15], p[17]

def turn4(p):
    p[2], p[21] = p[21], p[2]
    p[5], p[24] = p[24], p[5]
    p[8], p[27] = p[27], p[8]
    p[18], p[11] = p[11], p[18]
    p[14], p[12] = p[12], p[14]


def search(p, cnt):
    if cnt == 8:
        return cnt
    if check(p):
        return cnt
    
    r = 100
    turn1(p)
    r = min(r, search(p, cnt+1))
    turn1(p)
    turn2(p)
    r = min(r, search(p, cnt+1))
    turn2(p)
    turn3(p)
    r = min(r, search(p, cnt+1))
    turn3(p)
    turn4(p)
    r = min(r, search(p, cnt+1))
    turn4(p)

    return r


N = int(input())
for l in range(N):
    p = [int(i) for i in input().split()]
    print(search(p, 0))

Submission status: Accepted

Solution code:
import sys
f = sys.stdin

p = [
(27,28,29, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,15,14,16,17,20,19,18,21,22,23,24,25,26, 0, 1, 2),
( 0, 1, 2, 3, 4, 5,21,22,23,11,10, 9,17,13,14,15,16,12,18,19,20, 6, 7, 8,24,25,26,27,28,29),
( 0, 1,21, 3, 4,24, 6, 7,27, 9,10,18,14,13,12,15,16,17,11,19,20, 2,22,23, 5,25,26, 8,28,29),
(23, 1, 2,26, 4, 5,29, 7, 8,20,10,11,12,13,14,17,16,15,18,19, 9,21,22, 0,24,25, 3,27,28, 6)]

def t(c,p):
    return tuple(c[i] for i in p)

start = (1,1,1,1,1,1,1,1,1,2,2,2,4,4,4,6,6,6,5,5,5,3,3,3,3,3,3,3,3,3)
cache ={start:0}

def create_cache(c,cnt):
    cnt += 1
    if cnt > 8:
        return
    for pi in p:
        ci = t(c,pi)
        if ci not in cache or cache[ci] > cnt:
            cache[ci] = cnt
            create_cache(ci, cnt)

create_cache(start, 0)
            

n = int(f.readline())
for i in range(n):
    c = tuple(map(int, f.readline().split()))
    if c in cache:
        print(cache[c])
    else:
        print('not found')

Submission status: Accepted

Solution code:
def rotate(p, comm):
    if comm==0:
        p[0],p[1],p[2], p[27],p[28],p[29] = p[27],p[28],p[29], p[0],p[1],p[2]
        p[14], p[15] = p[15], p[14]
        p[18], p[20] = p[20], p[18]
    elif comm==1:
        p[2],p[5],p[8], p[21],p[24],p[27] = p[21],p[24],p[27], p[2],p[5],p[8]
        p[11], p[18] = p[18], p[11]
        p[12], p[14] = p[14], p[12]
    elif comm==2:
        p[6],p[7],p[8], p[21],p[22],p[23] = p[21],p[22],p[23], p[6],p[7],p[8]
        p[12], p[17] = p[17], p[12]
        p[9], p[11] = p[11], p[9]
    elif comm==3:
        p[0],p[3],p[6], p[23],p[26],p[29] = p[23],p[26],p[29], p[0],p[3],p[6]
        p[9], p[20] = p[20], p[9]
        p[15], p[17] = p[17], p[15]
def all_eq(A, left, right):
    return all(A[i]==A[left] for i in xrange(left, right))
def is_correct(p):
    return all_eq(p, 9, 12) and all_eq(p, 12, 15) and all_eq(p, 15, 18) and all_eq(p, 18, 21) and all_eq(p, 0, 9) and all_eq(p, 21, 30)
def dfs(p, cnt, f):
    ret = 9
    if cnt==9:
        return 9
    if is_correct(p):
        return cnt
    for k in xrange(4):
        if k==f:
            continue
        rotate(p, k)
        ret = min(ret, dfs(p, cnt+1, k))
        rotate(p, k)
    return ret

n = input()
for _ in xrange(n):
    p = map(int, raw_input().split())
    print dfs(p, 0, -1)

Submission status: Accepted

Solution code:
def rotate(p, comm):
    if comm==0:
        p[0],p[1],p[2], p[27],p[28],p[29] = p[27],p[28],p[29], p[0],p[1],p[2]
        p[14], p[15] = p[15], p[14]
        p[18], p[20] = p[20], p[18]
    elif comm==1:
        p[2],p[5],p[8], p[21],p[24],p[27] = p[21],p[24],p[27], p[2],p[5],p[8]
        p[11], p[18] = p[18], p[11]
        p[12], p[14] = p[14], p[12]
    elif comm==2:
        p[6],p[7],p[8], p[21],p[22],p[23] = p[21],p[22],p[23], p[6],p[7],p[8]
        p[12], p[17] = p[17], p[12]
        p[9], p[11] = p[11], p[9]
    elif comm==3:
        p[0],p[3],p[6], p[23],p[26],p[29] = p[23],p[26],p[29], p[0],p[3],p[6]
        p[9], p[20] = p[20], p[9]
        p[15], p[17] = p[17], p[15]
def all_eq(A, left, right):
    return all(A[i]==A[left] for i in xrange(left, right))
def is_correct(p):
    return all_eq(p, 9, 12) and all_eq(p, 12, 15) and all_eq(p, 15, 18) and all_eq(p, 18, 21) and all_eq(p, 0, 9) and all_eq(p, 21, 30)
ans = 8
def dfs(p, cnt, f):
    global ans
    if cnt>ans:
        return
    if is_correct(p):
        ans = cnt
        return
    for k in xrange(4):
        if k==f:
            continue
        rotate(p, k)
        dfs(p, cnt+1, k)
        rotate(p, k)

n = input()
for _ in xrange(n):
    p = map(int, raw_input().split())
    ans = 8
    dfs(p, 0, -1)
    print ans

Submission status: Accepted

Solution code:
def rotate(p, comm):
    if comm==0:
        p[0],p[1],p[2], p[27],p[28],p[29] = p[27],p[28],p[29], p[0],p[1],p[2]
        p[14], p[15] = p[15], p[14]
        p[18], p[20] = p[20], p[18]
    elif comm==1:
        p[2],p[5],p[8], p[21],p[24],p[27] = p[21],p[24],p[27], p[2],p[5],p[8]
        p[11], p[18] = p[18], p[11]
        p[12], p[14] = p[14], p[12]
    elif comm==2:
        p[6],p[7],p[8], p[21],p[22],p[23] = p[21],p[22],p[23], p[6],p[7],p[8]
        p[12], p[17] = p[17], p[12]
        p[9], p[11] = p[11], p[9]
    elif comm==3:
        p[0],p[3],p[6], p[23],p[26],p[29] = p[23],p[26],p[29], p[0],p[3],p[6]
        p[9], p[20] = p[20], p[9]
        p[15], p[17] = p[17], p[15]
def all_eq(A, left, right):
    return all(A[i]==A[left] for i in xrange(left, right))
def is_correct(p):
    return all_eq(p, 9, 12) and all_eq(p, 12, 15) and all_eq(p, 15, 18) and all_eq(p, 18, 21) and all_eq(p, 0, 9) and all_eq(p, 21, 30)
ans = 8
def dfs(p, cnt, f):
    global ans
    if ans<=cnt:
        return
    if is_correct(p):
        ans = cnt
        return
    for k in xrange(4):
        if ans<=cnt+1:
            break
        if k==f:
            continue
        rotate(p, k)
        dfs(p, cnt+1, k)
        rotate(p, k)

n = input()
for _ in xrange(n):
    p = map(int, raw_input().split())
    ans = 8
    dfs(p, 0, -1)
    print ans

Submission status: Accepted

Solution code:
def rotate(p,comm):
    if comm==0:
        p[0],p[1],p[2],p[27],p[28],p[29]=p[27],p[28],p[29],p[0],p[1],p[2]
        p[14],p[15]=p[15],p[14]
        p[18],p[20]=p[20],p[18]
    elif comm==1:
        p[2],p[5],p[8],p[21],p[24],p[27]=p[21],p[24],p[27],p[2],p[5],p[8]
        p[11],p[18]=p[18],p[11]
        p[12],p[14]=p[14],p[12]
    elif comm==2:
        p[6],p[7],p[8],p[21],p[22],p[23]=p[21],p[22],p[23],p[6],p[7],p[8]
        p[12],p[17]=p[17],p[12]
        p[9],p[11]=p[11],p[9]
    elif comm==3:
        p[0],p[3],p[6],p[23],p[26],p[29]=p[23],p[26],p[29],p[0],p[3],p[6]
        p[9],p[20]=p[20],p[9]
        p[15],p[17]=p[17],p[15]

def all_eq(A,left,right):
    return all(A[i]==A[left] for i in xrange(left,right))
def is_correct(p):
    return all_eq(p,9,12) and all_eq(p,12,15) and all_eq(p,15,18) and all_eq(p,18,21) and all_eq(p,0,9) and all_eq(p,21,30)

ans=8
def dfs(p,cnt,f):
    global ans
    if ans<=cnt:
        return
    if is_correct(p):
        ans=cnt
        return
    for k in xrange(4):
        if ans<=cnt+1:
            break
        if k==f:
            continue
        rotate(p,k)
        dfs(p,cnt+1,k)
        rotate(p,k)
n=input()
for _ in xrange(n):
#n=int(raw_input())
    p=map(int,raw_input().split())
    ans=8
    dfs(p,0,-1)
    print ans

Submission status: Accepted

Solution code:
import heapq

swap_list = [
    {(6, 21), (7, 22), (8, 23), (9, 11), (12, 17)},
    {(0, 27), (1, 28), (2, 29), (14, 15), (18, 20)},
    {(0, 23), (3, 26), (6, 29), (15, 17), (9, 20)},
    {(2, 21), (5, 24), (8, 27), (12, 14), (11, 18)}
]


def check_complete(cube):
    for surface in (cube[:9], cube[9:12], cube[12:15], cube[15:18], cube[18:21]):
        val = surface[0]
        if any(block - val for block in surface):
            return False
    return True


def next_cubes(cube, prev):
    nc = [None] * 4
    for i in range(4):
        if i != prev:
            nci = cube[:]
            for a, b in swap_list[i]:
                nci[a], nci[b] = cube[b], cube[a]
            nc[i] = nci
    return nc


n = int(input())
while n:
    cube0 = list(map(int, input().split()))
    checked = []
    queue = [(0, cube0, -1)]
    while queue:
        cnt, cube, prev = heapq.heappop(queue)
        if cube in checked:
            continue
        if check_complete(cube):
            print(cnt)
            break
        checked.append(cube)
        for i, next_cube in enumerate(next_cubes(cube, prev)):
            if next_cube and not next_cube in checked:
                heapq.heappush(queue, (cnt + 1, next_cube, i))

    n -= 1

Submission status: Accepted

Solution code:
def op1 (p) :
    return (
        p[ 0],p[ 1],p[ 2],p[ 3],p[ 4],p[ 5],p[21],p[22],p[23],p[11],p[10],p[ 9],p[17],p[13],p[14],
        p[15],p[16],p[12],p[18],p[19],p[20],p[ 6],p[ 7],p[ 8],p[24],p[25],p[26],p[27],p[28],p[29]
    )

def op2 (p) :
    return (
        p[27],p[28],p[29],p[ 3],p[ 4],p[ 5],p[ 6],p[ 7],p[ 8],p[ 9],p[10],p[11],p[12],p[13],p[15],
        p[14],p[16],p[17],p[20],p[19],p[18],p[21],p[22],p[23],p[24],p[25],p[26],p[ 0],p[ 1],p [2]
    )

def op3 (p) :
    return (
        p[23],p[ 1],p[ 2],p[26],p[ 4],p[ 5],p[29],p[ 7],p[ 8],p[20],p[10],p[11],p[12],p[13],p[14],
        p[17],p[16],p[15],p[18],p[19],p[ 9],p[21],p[22],p[ 0],p[24],p[25],p[ 3],p[27],p[28],p[ 6]
    )

def op4 (p) :
    return (
        p[ 0],p[ 1],p[21],p[ 3],p[ 4],p[24],p[ 6],p[ 7],p[27],p[ 9],p[10],p[18],p[14],p[13],p[12],
        p[15],p[16],p[17],p[11],p[19],p[20],p[ 2],p[22],p[23],p[ 5],p[25],p[26],p[ 8],p[28],p[29]
    )

def op (p, i) :
    if (i == 1) :
        return op1(p)
    elif (i == 2) :
        return op2(p)
    elif (i == 3) :
        return op3(p)
    elif (i == 4) :
        return op4(p)

def valid (p) :
    for i in range(1, 9) :
        if (p[0] != p[i]) :
            return False

    for i in range(22, 30) :
        if (p[21] != p[i]) :
            return False

    for i in range(10, 12) :
        if (p[9] != p[i]) :
            return False

    for i in range(13, 15) :
        if (p[12] != p[i]) :
            return False

    for i in range(16, 18) :
        if (p[15] != p[i]) :
            return False

    for i in range(19, 21) :
        if (p[18] != p[i]) :
            return False

    q = (p[0], p[9], p[12], p[15], p[18], p[21])

    if (q == (0, 1, 3, 5, 4, 2)) :
        return True
    if (q == (0, 3, 5, 4, 1, 2)) :
        return True
    if (q == (0, 5, 4, 1, 3, 2)) :
        return True
    if (q == (0, 4, 1, 3, 5, 2)) :
        return True

    if (q == (2, 1, 5, 3, 4, 0)) :
        return True
    if (q == (2, 5, 3, 4, 1, 0)) :
        return True
    if (q == (2, 3, 4, 1, 5, 0)) :
        return True
    if (q == (2, 4, 1, 5, 3, 0)) :
        return True

    return False

def solve (n, p, i) :
    global minimum
    if (n > 9) :
        return

    if (n >= minimum) :
        return

    if (valid(p)) :
        minimum = min(minimum, n)
        return

    for j in range(1, 5) :
        if (i != j) :
            solve(n + 1, op(p, j), j)
    return

minimum = 100
N = int(input())
for kk in range(0, N) :
    minimum = 100
    p = tuple([int(term) - 1 for term in input().split()])
    if (valid(p)) :
        print(0)
        continue
    for i in range(1, 5) :
        solve(1, op(p, i), i)
    print(minimum)

Submission status: Accepted

Solution code:
from collections import deque

def is_solved(puzzle):
  check1 = puzzle[0]
  for i in range(1, 9):
    if puzzle[i] != check1:
      return False

  check2 = puzzle[9]
  if puzzle[10] != check2 or puzzle[11] != check2:
    return False

  check3 = puzzle[12]
  if puzzle[13] != check3 or puzzle[14] != check3:
    return False

  return True


def myhash(p):
  ret = 0
  for i in range(len(p)):
    ret += 200 ** i * p[i]
  return ret

def spin1(p):
  r = [i for i in p]
  r[0], r[3], r[6], r[23], r[26], r[29] = p[23], p[26], p[29], p[0], p[3], p[6]
  r[9], r[20] = p[20], p[9]
  r[15], r[17] = p[17], p[15]
  return r

def spin2(p):
  r = [i for i in p]
  r[2], r[5], r[8], r[21], r[24], r[27] = p[21], p[24], p[27], p[2], p[5], p[8]
  r[11], r[18] = p[18], p[11]
  r[12], r[14] = p[14], p[12]
  return r

def spin3(p):
  r = [i for i in p]
  r[0], r[1], r[2], r[27], r[28], r[29] = p[27], p[28], p[29], p[0], p[1], p[2]
  r[14], r[15] = p[15], p[14]
  r[18], r[20] = p[20], p[18]
  return r

def spin4(p):
  r = [i for i in p]
  r[6], r[7], r[8], r[21], r[22], r[23] = p[21], p[22], p[23], p[6], p[7], p[8]
  r[12], r[17] = p[17], p[12]
  r[9], r[11] = p[11], p[9]
  return r

def main():
  
  spin_lst = [spin1, spin2, spin3, spin4]
  
  n = int(input())
  
  for i in range(n):
    puz = list(map(int, input().split()))
    
    dic = {}
    dic[myhash(puz)] = 0
  
    que = deque()
    que.append((puz, 0))
  
    while que:
      p, score = que.popleft()
      
      if is_solved(p):
        print(score)
        break
  
      for spin in spin_lst:
        spined = spin(p)
        h = myhash(spined)
        if not h in dic:
          dic[h] = score + 1
          que.append((spined, score + 1))

main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()

# Cubeクラス
class Cube:
    # CP, CO, EO配列を作る
    def __init__(self):
        self.Cp = [0, 1, 2, 3]
        self.Eo = [0, 0, 0, 0]
    
    # 回転処理 CP (コーナーの位置)
    def move_cp(self, num):
        res = [i for i in self.Cp]
        res[num], res[(num + 1) % 4] = res[(num + 1) % 4], res[num]
        return res

    # 回転処理 EO (エッジの向き)
    def move_eo(self, num):
        res = [i for i in self.Eo]
        res[num] += 1
        res[num] %= 2
        return res

    # 回転処理 全体
    def move(self, num):
        res = Cube()
        res.Eo = self.move_eo(num)
        res.Cp = self.move_cp(num)
        return res
    
    # CP, CO, EOの配列インデックスを返す
    def idxes(self):
        cp_idx = 0
        for i in range(4):
            cnt = 0
            for j in self.Cp[:i]:
                if j < self.Cp[i]:
                    cnt += 1
            cp_idx += fac[3 - i] * (self.Cp[i] - cnt)
        
        eo_idx = 0
        for i in range(4):
            eo_idx *= 2
            eo_idx += self.Eo[i]

        return cp_idx, eo_idx

# 階乗をO(1)で計算できるよう前計算
fac = [1 for _ in range(5)]
for i in range(1, 5):
    fac[i] = fac[i - 1] * i


solved = Cube() # 揃っている状態のパズルを定義しておく

# 枝刈りに使うcp, eo配列
cp = [100 for _ in range(fac[4])]
eo = [100 for _ in range(2 ** 4)]

# 幅優先探索を行う。キューを使う。
# 要素はパズルの状態とその状態になるまでにかかった手数、最後に回した2手を表す。
que = deque([[solved, 0, -10, -20]])
while que:
    status, num, l_mov, ll_mov = que.popleft()

    # 回転処理を行うかのフラグ
    move_flag = 2

    # cp, eo配列を更新する。どれか一つでも更新されたら次に動かす操作をする。
    idxes = status.idxes()
    for i, arr in zip(idxes, [cp, eo]):
        if arr[i] < 100:
            move_flag -= 1
        else:
            arr[i] = num
    
    # cp, eoの一つも更新されなかったらこのパズルを動かす必要はない。
    if not move_flag:
        continue

    # 直前の2手が上下または右左であったとき(l_movとll_movの差が2であったとき)にTrueになるフラグ
    mov_flag = True if abs(l_mov - ll_mov) == 2 else False

    # 次に回す手をfor文で回す
    for mov in range(4):
        # 計算量の削減!!!!!
        if mov == l_mov or (mov_flag and mov == ll_mov):
            continue

        # パズルを動かす
        n_status = status.move(mov)        

        que.append([n_status, num + 1, mov, l_mov])


# 深さ優先探索
def dfs(status, depth, num, l_mov, ll_mov):

    # 最大深さに達していたらFalseを返す
    if num == depth:
        return False
    
    # depth以内にCP, EOのどちらか一つでも揃わないとわかったら枝刈りをする
    continue_flag = False
    idxes = status.idxes()
    for i, arr in zip(idxes, [cp, eo]):
        if arr[i] + num > depth:
            continue_flag = True
            break
    if continue_flag:
        return False

    # 揃ったかどうかのフラグ
    flag = False

    # 直前の2手が上下または右左であったとき(l_movとll_movの差が2であったとき)にTrueになるフラグ
    mov_flag = True if abs(l_mov - ll_mov) == 2 else False

    # 次に回す手をfor文で回す
    for mov in range(4):
        # 計算量の削減!!!!!
        if mov == l_mov or (mov_flag and mov == ll_mov):
            continue

        # パズルを動かす
        n_status = status.move(mov)

        # 揃ったか?
        if num + 1 == depth:
            if n_status.Cp == solved.Cp and n_status.Eo == solved.Eo:
                flag = True
                break
        else:
            flag = flag or dfs(n_status, depth, num + 1, mov, l_mov)
    
    return flag


n = int(input())

for _ in range(n):
    # 入力
    p = [int(i) for i in input().split()]

    # 入力されたパズルの色の状態をpuzzleに格納 ここはどうしても手打ちが必要
    puzzle = Cube()
    for i, j in enumerate([[15, 20], [18, 14], [12, 11], [9, 17]]): # CPの処理
        tmp = [[6, 5, 4, 2], [5, 4, 2, 6]]
        for k in range(4):
            flag = 0
            for l in range(2):
                for m in range(2):
                    if p[j[l]] == tmp[m][k]:
                        flag += 1
            if flag == 2:
                puzzle.Cp[i] = k
                break
    for i, j in enumerate([1, 5, 7, 3]): # EOの処理
        if p[j] == 3:
            puzzle.Eo[i] = 1
    
    # 0手で揃う場合のみ例外
    if puzzle.Eo == solved.Eo and puzzle.Cp == solved.Cp:
        print(0)
        continue

    # IDA* 最大深さは7。
    for depth in range(1, 8):
        if dfs(puzzle, depth, 0, -10, -20):
            print(depth)
            break
    else:
        print(8)

Submission status: Accepted

Solution code:
from collections import deque

class FloppyCube:

    solution = [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 
		 2, 2, 2, 4, 4, 4, 6, 6, 6, 5, 5, 5,
		 3, 3, 3, 3, 3, 3, 3, 3, 3 ];

    def __init__( self ):
        self.face = []
        self.step = 0

    def copy( self, s ):
        for i in range(30):
            self.face.append(s.face[i])
        self.step = s.step

    def IsSolved( self ):
        for i in range(30):
            if self.face[i] != self.solution[i] : return False
        return True

    def Swap( self, n, m ):
        self.face[n],self.face[m] = self.face[m],self.face[n]
    
    def Rotate( self, side ):
        if side == 0:
            self.Swap( 12, 17 )
            self.Swap( 9, 11 )
            self.Swap( 6, 21 )
            self.Swap( 7, 22 )
            self.Swap( 8, 23 )
        elif side == 1:
            self.Swap( 14, 15 )
            self.Swap( 18, 20 )
            self.Swap( 0, 27 )
            self.Swap( 1, 28 )
            self.Swap( 2, 29 )
        elif side == 2:
            self.Swap( 11, 18 )
            self.Swap( 12, 14 )
            self.Swap( 2, 21 )
            self.Swap( 5, 24 )
            self.Swap( 8, 27 )
        else:
            self.Swap( 9, 20 )
            self.Swap( 15, 17 )
            self.Swap( 0, 23 )
            self.Swap( 3, 26 )
            self.Swap( 6, 29 )
        

n = int(input())
s = FloppyCube()
for i in range(n):
    s.step = 0
    s.face = list(map(int,input().split()))

    q = deque()
    q.append(s)
    
    while q :
        s = q.popleft()
        if s.IsSolved(): break
        
        s.step += 1
        if s.step <= 8:
            for i in range(4):
                t = FloppyCube()
                t.copy( s )
                t.Rotate(i)
                q.append(t)
    print(s.step)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
rot1 = [1,2,3,4,5,6,22,23,24,12,11,10,18,14,15,16,17,13,19,20,21,7,8,9,25,26,27,28,29,30]
rot2 = [28,29,30,4,5,6,7,8,9,10,11,12,13,14,16,15,17,18,21,20,19,22,23,24,25,26,27,1,2,3]
rot3 = [24,2,3,27,5,6,30,8,9,21,11,12,13,14,15,18,17,16,19,20,10,22,23,1,25,26,4,28,29,7]
rot4 = [1,2,22,4,5,25,7,8,28,10,11,19,15,14,13,16,17,18,12,20,21,3,23,24,6,26,27,9,29,30]
N = int(input())
for _ in range(N):
    closeset = set()
    finstate = (1,1,1,1,1,1,1,1,1,2,2,2,4,4,4,6,6,6,5,5,5,3,3,3,3,3,3,3,3,3)
    state = tuple(map(int,input().split()))
    que = [(0,state,0)]
    while que:
        numope, cstate, lasope = heappop(que)
        if cstate == finstate: break
        if cstate in closeset: continue
        closeset.add(cstate)
        for ope,rot in zip(range(1,5),[rot1,rot2,rot3,rot4]):
            if lasope != ope:
                nstate = tuple(cstate[i-1] for i in rot)
                heappush(que,(numope+1,nstate,ope))
    print(numope)

Submission status: Accepted

Solution code:
from collections import deque
def _flip(a, swap_pair):
    for i, j in zip(*swap_pair):
        a[i], a[j] = a[j], a[i]
    return a

swap_pair = (
    [[1, 2, 3, 15, 21], [28, 29, 30, 16, 19]],
    [[7, 8, 9, 13, 10], [22, 23, 24, 18, 12]],
    [[1, 4, 7, 10, 16], [24, 27, 30, 21, 18]],
    [[3, 6, 9, 12, 15], [22, 25, 28, 19, 13]]
)
def flip(a):
    for pair in swap_pair:
        yield _flip(a[:], pair)

for _ in [0]*int(input()):
    puzzle = [0]+list(map(int, input().split()))
    dq = deque([(puzzle, 0, -1)])
    popleft, append = dq.popleft, dq.append

    while dq:
        p, cnt, i = popleft()
        if len(set(p[1:10])) == len(set(p[10:13])) == len(set(p[13:16])) == len(set(p[16:19])) == len(set(p[19:22])) == 1:
            print(cnt)
            break
        cnt += 1
        for j, _p in enumerate(flip(p)):
            if i == j:
                continue
            append((_p, cnt, j))