ALDS1_13の解答例(Python)

ゲーム・パズルに関する問題です． コードの内容自体は大したことはしていないのですが，書き方が下手なのでだいぶ分かりづらいかもしれません． アルゴリズムについて詳しく知りたい方は参考文献などをご覧ください．

1. ALDS1_13_A: 8 Queens Problem

• find_dangerous(queens_list)
クイーンの位置のリストに対して互いに襲わないような位置になっているかと安全な位置を返します．

# ALDS1_13_A 
n = int(input())

def find_dangerous(queens_list):
    safe_positions = [[1 for _ in range(8)] for _ in range(8)]
    for queen in queens_list:
        x,y = queen
        if safe_positions[y][x] == 0:
            return False,False
        
        # 横を消す
        for i in range(8):
            if 0 <= i < 8:
                if [i,y] in queens_list and i!=x:
                    return False,safe_positions
                safe_positions[y][i] = 0

        # 縦を消す
        for i in range(8):
            if 0 <= i < 8:
                if [x,i] in queens_list and i!=y:
                    return False,safe_positions
                safe_positions[i][x] = 0

        # 斜めを消す
        for i in range(-8,8):
            if 0 <= x+i < 8 and 0 <= y+i < 8:
                if [x+i,y+i] in queens_list and i!=0:
                    return False,safe_positions
                safe_positions[y+i][x+i] = 0
            if 0 <= x-i < 8 and 0 <= y+i < 8:
                if [x-i,y+i] in queens_list and i!=0:
                    return False,safe_positions
                safe_positions[y+i][x-i] = 0
                
    # 条件を満たしている
    return True,safe_positions

# まだクイーンが置かれていない行を管理する
rows = [i for i in range(8)]

queens_list = []
for _ in range(n):
    y,x = map(int,input().split(" ")) # 二次元配列で管理するとx,yが入れ替わる
    rows.remove(y) # クイーンが置かれた行を削除
    queens_list.append([x,y])
    
# もともと置いてあるクイーン
isSafe,safe_positions = find_dangerous(queens_list)

# 行別で置ける場所を管理する
safe_positions_dict = {}
for i in range(8):
    safe_positions_dict[i] = []
    for j in range(8):
        # 置ける場所なら辞書に追加
        if safe_positions[i][j] == 1:
            safe_positions_dict[i].append([j,i])

idx = 0 # 行のインデックス
idx_list = [0 for _ in range(len(rows))] # 行からどの位置を選ぶかのインデックス
while len(queens_list) < 8:
    row = rows[idx]
    idx2 = idx_list[idx]
    pos = safe_positions_dict[row][idx2]
    queens_list.append(pos)
        
    isSafe,safe_positions = find_dangerous(queens_list)
    
    if not isSafe:
        # 置けなければ同じ行の違う位置に変える
        idx_list[idx] += 1
        queens_list.pop() # 最後に置いたクイーンを取り除く
        while True:
            idx2 = idx_list[idx]
            row = rows[idx]
            # 同じ行にこれ以上置ける場所がなければ前の行に戻す
            if idx2 >= len(safe_positions_dict[row]):
                idx_list[idx] = 0 # 今の行のインデックスを0に戻す
                idx -= 1 # 1行前に戻す
                idx_list[idx] += 1 # この位置はダメだったので次の位置に進める
                queens_list.pop() # 戻った行のクイーンを取り除く
            else:
                break
    else:
        idx += 1 # 条件を満たしているので次の行に進める
        
queens_list = sorted(queens_list, key=lambda x: x[1])

for queen in queens_list:
    print("."*(queen[0]) + "Q" + "."*(7-queen[0]))

2. ALDS1_13_B: 8 Puzzle

# ALDS1_13_B

# 空白を上へ
def up_space(A,idx0,turn):
    # 既に一番上にある場合は何もしない
    if idx0 in (0,1,2):
        return A,idx0,turn
    else:
        A2 = A[:]
        # 空白を上に
        A2[idx0] = A2[idx0-3]
        A2[idx0-3] = "0"
        return A2, idx0-3,turn+1
    
# 空白を下へ
def down_space(A,idx0,turn):
    # 既に一番上にある場合は何もしない
    if idx0 in (6,7,8):
        return A,idx0,turn
    else:
        A2 = A[:]
        # 空白を下に
        A2[idx0] = A2[idx0+3]
        A2[idx0+3] = "0"
        return A2, idx0+3,turn+1
    
# 空白を右へ
def right_space(A,idx0,turn):
    # 既に一番右にある場合は何もしない
    if idx0 in (2,5,8):
        return A,idx0,turn
    else:
        A2 = A[:]
        # 空白を右に
        A2[idx0] = A2[idx0+1]
        A2[idx0+1] = "0"
        return A2, idx0+1,turn+1
    
# 空白を左へ
def left_space(A,idx0,turn):
    # 既に一番右にある場合は何もしない
    if idx0 in (0,3,6):
        return A,idx0,turn
    else:
        A2 = A[:]
        # 空白を右に
        A2[idx0] = A2[idx0-1]
        A2[idx0-1] = "0"
        return A2, idx0-1,turn+1
    
from collections import deque

G = ["1","2","3","4","5","6","7","8","0"]

A = []
for _ in range(3):
    A += input().split(" ")

# 幅優先探索で適当に動かして揃わないかを調べています
state_set = set() # リストで包含関係を調べると遅いのでsetを使う
current_state = deque([(A,A.index("0"),0)])
while current_state:
    A ,idx0, turn = current_state.popleft()
    
    # 空白を上に動かして揃わないかを調べる
    A2 = up_space(A,idx0,turn)
    str_A = "".join(A2[0])
    if str_A not in state_set:
        state_set.add(str_A) # 文字列に直してからstate_setに追加
        current_state.append(A2) # 動かした後の状態をcurrent_stateに追加
        if A2[0] == G:
            break
    
    # 空白を下に動かして揃わないかを調べる
    A2 = down_space(A,idx0,turn)
    str_A = "".join(A2[0])
    if str_A not in state_set:
        state_set.add(str_A) # 文字列に直してからstate_setに追加
        current_state.append(A2) # 動かした後の状態をcurrent_stateに追加
        if A2[0] == G:
            break
       
    # 空白を左に動かして揃わないかを調べる
    A2 = left_space(A,idx0,turn)
    str_A = "".join(A2[0])
    if str_A not in state_set:
        state_set.add(str_A) # 文字列に直してからstate_setに追加
        current_state.append(A2) # 動かした後の状態をcurrent_stateに追加
        if A2[0] == G:
            break
        
    # 空白を右に動かして揃わないかを調べる
    A2 = right_space(A,idx0,turn)
    str_A = "".join(A2[0])
    if str_A not in state_set:
        state_set.add(str_A) # 文字列に直してからstate_setに追加
        current_state.append(A2) # 動かした後の状態をcurrent_stateに追加
        if A2[0] == G:
            break
            
turn = A2[2]
print(turn)

3. ALDS1_13_C: 15 Puzzle

# ALDS1_13_C
import heapq
from collections import deque

# ゴールの状態とのマンハッタン距離を調べる
def search_dist(A,G):
    distance = 0
    for i in range(len(A)):
        if A[i]=="0":
            pass
        else:
            x,y=i//4,i%4
            x2,y2=((int(A[i])-1)//4,(int(A[i])-1)%4) 
            distance+=abs(x-x2)+abs(y-y2)
    return distance

# 遷移後に距離がどれだけ変わるかを調べる関数
def change_dist(P,idx0,idx1):
    dist = 0
    x,y=idx0//4,idx0%4 
    x2,y2=((int(P[idx0])-1)//4,(int(P[idx0])-1)%4) 
    dist+=abs(x-x2) + abs(y-y2)
    
    x,y=idx1//4,idx1%4 
    x2,y2=((int(P[idx1])-1)//4,(int(P[idx1])-1)%4) 
    dist-=abs(x-x2) + abs(y-y2)
    return dist

# 空白を上に移動したときの ゴールとのマンハッタン距離，遷移後の状態，空白の位置，手数を返す関数
def up_space(A,idx0,turn,dist):
    if idx0 in (0,1,2,3):
        return dist,A,idx0,turn
    else:
        A2=A[:]
        A2[idx0]=A2[idx0-4] 
        dist += change_dist(A2,idx0,idx0-4)
        A2[idx0-4]="0" 
        return dist,A2, idx0-4,turn+1

# 空白を下に移動したときの ゴールとのマンハッタン距離，遷移後の状態，空白の位置，手数を返す関数
def down_space(A,idx0,turn,dist):
    if idx0 in (12,13,14,15):
        return dist,A,idx0,turn
    else:
        A2 = A[:]
        A2[idx0]=A2[idx0+4] 
        dist += change_dist(A2,idx0,idx0+4)
        A2[idx0+4]="0"
        return dist,A2, idx0+4,turn+1
    
# 空白を右に移動したときの ゴールとのマンハッタン距離，遷移後の状態，空白の位置，手数を返す関数
def right_space(A,idx0,turn,dist):
    if idx0 in (3,7,11,15):
        return dist,A,idx0,turn
    else:
        A2=A[:]
        A2[idx0]=A2[idx0+1]
        dist += change_dist(A2,idx0,idx0+1)
        A2[idx0+1]="0" 
        return dist,A2, idx0+1,turn+1

# 空白を左に移動したときの ゴールとのマンハッタン距離，遷移後の状態，空白の位置，手数を返す関数
def left_space(A,idx0,turn,dist):
    if idx0 in (0,4,8,12):
        return dist,A,idx0,turn
    else:
        A2=A[:]
        A2[idx0]=A2[idx0-1]
        dist += change_dist(A2,idx0,idx0-1)
        A2[idx0-1]="0"
        return dist,A2, idx0-1,turn+1
    
# 処理を関数化したもの
def update_max_turn(max_turn,min_state):
    A2_str = "".join(A2[1]) # 局面を文字列化したもの
    
    # まだ調べていない場合
    if A2_str not in state_set:
        state_set.add(A2_str) # 調査済みに追加
        turn_dict[A2_str]=A2[3]
        if A2[0]+A2[3]<=max_turn:
            # 15手以内に終わるなら何ターンで終わるかを調べる
            if A2_str in state_dict.keys():
                turn=turn_dict[A2_str]+state_dict[A2_str]
                if turn <= max_turn:
                    min_state = A2_str
                max_turn=min(turn,max_turn)
            # 15手以内に終わらないなら遷移後の状態をキューに追加して調べる
            else:
                heapq.heappush(current_state, A2)
    # 既に調べていた場合
    else:
        # 15手以内に終わるなら何ターンで終わるかを調べる
        if A2_str in state_dict.keys():
            turn=A2[3] + state_dict[A2_str]
            if turn <= max_turn:
                min_state = A2_str
                max_turn=min(turn,max_turn)
        # 15手以内に終わらない場合
        else:
            # 知っている最短手数より速く到達していれば調べなおす
            if A2[3] < turn_dict[A2_str]:
                current_state.insert(0,A2)

        turn_dict[A2_str]=min(A2[3],turn_dict[A2_str]) 
        
    return max_turn, min_state
    
G=["1","2","3","4","5","6","7","8","9","10","11","12","13","14","15","0"]
turn0 = 0
current_state = deque([(search_dist(G,G),G,G.index("0"),0)])
state_dict = {"".join(G):0}
state_set=set(["".join(G)])

# ゴールから15手分を幅優先探索で調べておく
while current_state:
    dist, A ,idx0, turn = current_state.popleft()
    
    if turn >= 15:
        break
    
    if turn0 != turn:
        turn0 = turn
    
    A2=up_space(A,idx0,turn,dist)
    if "".join(A2[1]) not in state_set:
        state_set.add("".join(A2[1])) 
        state_dict["".join(A2[1])]=A2[3]
        current_state.append(A2)
        
    A2 = down_space(A,idx0,turn,dist)
    if "".join(A2[1]) not in state_set:
        state_set.add("".join(A2[1])) 
        state_dict["".join(A2[1])]=A2[3]
        current_state.append(A2)
        
    A2=left_space(A,idx0,turn,dist)
    if "".join(A2[1]) not in state_set:
        state_set.add("".join(A2[1])) 
        state_dict["".join(A2[1])]=A2[3]
        current_state.append(A2)
        
    A2=right_space(A,idx0,turn,dist)
    if "".join(A2[1]) not in state_set:
        state_set.add("".join(A2[1])) 
        state_dict["".join(A2[1])]=A2[3]
        current_state.append(A2)

########################################3

A=[]
for _ in range(4):
    A += input().split(" ")

# 調査済みの状態をstate_setに追加する
state_set=set(["".join(A)]) 

# ゴールとのマンハッタン距離を優先度として優先度付きキューで管理する
current_state=[(search_dist(A,G),A,A.index("0"),0)] 
heapq.heapify(current_state)

# max_turnより手数のかかるものは調査を打ち切りする
max_turn=45

turn_dict={"".join(A):0}

min_state = "" # 一番短い手数で到達できた状態を記録しておく

if "".join(A) in state_dict.keys():
    print(state_dict["".join(A)])
else:
    while current_state:
        # ゴールから最もマンハッタン距離の近いものを優先して調べる
        dist, A ,idx0, turn = heapq.heappop(current_state)
        
        # 既に分かっている最短手数(max_turn)以上の手数がかかるならその状態の探索を打ち切り
        if dist+turn>=max_turn:
            continue
            
        # 空白を上下左右に動かしたときどうなるかを update_max_turn で調べる
        A2=up_space(A,idx0,turn,dist)
        max_turn, min_state = update_max_turn(max_turn,min_state)
            
        A2 = down_space(A,idx0,turn,dist)
        max_turn, min_state = update_max_turn(max_turn,min_state)
            
        A2=left_space(A,idx0,turn,dist)
        max_turn, min_state = update_max_turn(max_turn,min_state)
            
        A2=right_space(A,idx0,turn,dist)
        max_turn, min_state = update_max_turn(max_turn,min_state)
            
    print(turn_dict[min_state] + state_dict[min_state])