기말과제 - 8puzzle 구현(A*알고리즘)

 

import cv2
import sys
import copy
import heapq
import random
import pyautogui
import matplotlib
import matplotlib.pyplot as plt

matplotlib.use('TkAgg') #그래프를 렌더링하는데 필요한 백엔드를 지정하는 코드

imgDic = {1: 'C:/Users/cdh39/PycharmProjects/puzzle/num_1.png',
          2: 'C:/Users/cdh39/PycharmProjects/puzzle/num_2.png',
          3: 'C:/Users/cdh39/PycharmProjects/puzzle/num_3.png',
          4: 'C:/Users/cdh39/PycharmProjects/puzzle/num_4.png',
          5: 'C:/Users/cdh39/PycharmProjects/puzzle/num_5.png',
          6: 'C:/Users/cdh39/PycharmProjects/puzzle/num_6.png',
          7: 'C:/Users/cdh39/PycharmProjects/puzzle/num_7.png',
          8: 'C:/Users/cdh39/PycharmProjects/puzzle/num_8.png',
          0: 'C:/Users/cdh39/PycharmProjects/puzzle/num_0.png'}
def check_zero(puzzle):  # 퍼즐 내에서 0의 위치를 찾아 리턴
    for i in range(3):
        for j in range(3):
            if puzzle[i][j] == 0:
                return i, j
def valid_move(x, y): # 0의 위치가 3x3 배열을 벗어날 경우 false, 벗어나지 않을 경우 true 반환
    return 0 <= x < 3 and 0 <= y < 3

def swap(puzzle, x1, y1, x2, y2):  #두 퍼즐을 스왑하는 함수
    puzzle[x1][y1], puzzle[x2][y2] = puzzle[x2][y2], puzzle[x1][y1]

def shuffle_puzzle(puzzle, moves):  #moves 는 스왑 수(몇 번 이동하는지)
    x, y = check_zero(puzzle)

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  #상하좌우 이동

    for i in range(moves):
        while True:
            dx, dy = random.choice(directions)   #상하좌우 중 하나 랜덤 선택
            new_x, new_y = x + dx, y + dy        # 0의 좌표 + 상하좌우 중 랜덤 좌표값
            if valid_move(new_x, new_y):         #만약 이동할 0의 위치가 유효한 위치이면
                swap(puzzle, x, y, new_x, new_y) #현재 0이 위치한 퍼즐과 이동할 위치의 퍼즐을 스왑
                x, y = new_x, new_y              #0의 좌표값을 이동한 좌표값으로 갱신
                break

keyList = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]  #목표 퍼즐이자 섞을 퍼즐
goal_puzzle = copy.deepcopy(keyList)         #goal_puzzle은 수동모드 시 정답인지 확인하기 위한 변수

print("목표 퍼즐")
for i in range(3):
    for j in range(3):
        print(keyList[i][j], end=' ')
    print()

shuffle_puzzle(keyList, 100) #keyList에서 0을 moves 번만큼 움직임
print("\n섞은 후의 퍼즐")
for i in range(3):
    for j in range(3):
        print(keyList[i][j], end=' ')
    print()

# 전체그림의 너비와 높이가 각각 5인치인 3x3 서브플롯을 생성(fig는 전체 그림 객체, axes는 서브플롯 객체)
fig, axes = plt.subplots(3, 3, figsize=(5, 5))

# img 는 이미지 파일을 읽어들여 openCV에서 처리할 수 있는 형식으로 로드됨
img1 = cv2.imread(imgDic[keyList[0][0]])
img2 = cv2.imread(imgDic[keyList[0][1]])
img3 = cv2.imread(imgDic[keyList[0][2]])
img4 = cv2.imread(imgDic[keyList[1][0]])
img5 = cv2.imread(imgDic[keyList[1][1]])
img6 = cv2.imread(imgDic[keyList[1][2]])
img7 = cv2.imread(imgDic[keyList[2][0]])
img8 = cv2.imread(imgDic[keyList[2][1]])
img9 = cv2.imread(imgDic[keyList[2][2]])

def print_plot(img1, img2, img3, img4, img5, img6, img7, img8, img9):
    plt.subplot(3, 3, 1)               # 3행 3열의 격자 중 1번째 서브플롯을 선택
    plt.gca().axes.xaxis.set_visible(False)  # x축 눈금과 레이블이 보이지 않게
    plt.gca().axes.yaxis.set_visible(False)  # y축 눈금과 레이블이 보이지 않게
    plt.imshow(img1)                         # img1 이미지를 서브플롯에 출력

    plt.subplot(3, 3, 2)
    plt.gca().axes.xaxis.set_visible(False)
    plt.gca().axes.yaxis.set_visible(False)
    plt.imshow(img2)

    plt.subplot(3, 3, 3)
    plt.gca().axes.xaxis.set_visible(False)
    plt.gca().axes.yaxis.set_visible(False)
    plt.imshow(img3)

    plt.subplot(3, 3, 4)
    plt.gca().axes.xaxis.set_visible(False)
    plt.gca().axes.yaxis.set_visible(False)
    plt.imshow(img4)

    plt.subplot(3, 3, 5)
    plt.gca().axes.xaxis.set_visible(False)
    plt.gca().axes.yaxis.set_visible(False)
    plt.imshow(img5)

    plt.subplot(3, 3, 6)
    plt.gca().axes.xaxis.set_visible(False)
    plt.gca().axes.yaxis.set_visible(False)
    plt.imshow(img6)

    plt.subplot(3, 3, 7)
    plt.gca().axes.xaxis.set_visible(False)
    plt.gca().axes.yaxis.set_visible(False)
    plt.imshow(img7)

    plt.subplot(3, 3, 8)
    plt.gca().axes.xaxis.set_visible(False)
    plt.gca().axes.yaxis.set_visible(False)
    plt.imshow(img8)

    plt.subplot(3, 3, 9)
    plt.gca().axes.xaxis.set_visible(False)
    plt.gca().axes.yaxis.set_visible(False)
    plt.imshow(img9)

def swap_image(x1, y1, x2, y2): #수동모드 시 사용하는 함수로 퍼즐의 값을 스왑하고 퍼즐이미지도 갱신한다.

    tmp = keyList[x1][y1]
    keyList[x1][y1] = keyList[x2][y2]
    keyList[x2][y2] = tmp

    img1 = cv2.imread(imgDic[keyList[0][0]])
    img2 = cv2.imread(imgDic[keyList[0][1]])
    img3 = cv2.imread(imgDic[keyList[0][2]])
    img4 = cv2.imread(imgDic[keyList[1][0]])
    img5 = cv2.imread(imgDic[keyList[1][1]])
    img6 = cv2.imread(imgDic[keyList[1][2]])
    img7 = cv2.imread(imgDic[keyList[2][0]])
    img8 = cv2.imread(imgDic[keyList[2][1]])
    img9 = cv2.imread(imgDic[keyList[2][2]])
    print_plot(img1, img2, img3, img4, img5, img6, img7, img8, img9)


answer_cnt = 0  #정답을 맞추기까지 걸린 횟수
def draw_puzzle(event):

    global answer_cnt     #전역변수를 수정하기 위해 global 키워드 사용함
    answer_cnt += 1

    if keyList == goal_puzzle:  # 목표 퍼즐에 도달하면 프로그램 종료
        print(f"시도 횟수 : {answer_cnt - 1}")
        print("정답입니다!")
        sys.exit(0)

    if event.button == 1:                   # 왼쪽 마우스가 클릭되면(1)
        fore = pyautogui.getActiveWindow()  # fore에 현재 활성화된 창을 불러오고
        pos = pyautogui.position()          # pos 는 현재 마우스 커서 위치
        x = pos.x - fore.left               # 활성화된 창 내에서 마우스 커서의 x좌표 위치
        y = pos.y - fore.top                # 활성화된 창 내에서 마우스 커서의 y좌표 위치
        print("x좌표 : ", x, ", y좌표 : ", y)

        zero_x, zero_y = check_zero(keyList) #0이 위치한 좌표 확인
        print(f"0 위치 : [{zero_x}][{zero_y}]")

        # 서브플롯 1
        if (x >= 73 and x <= 195) and (y >= 90 and y <= 215):
            if zero_x == 1 and zero_y == 0:
                swap_image(0, 0, 1, 0)
            elif zero_x == 0 and zero_y == 1:
                swap_image(0, 0, 0, 1)

        # 서브플롯 2
        if (x >= 200 and x <= 325) and (y >= 90 and y <= 215):
            if zero_x == 0 and zero_y == 0:
                swap_image(0, 1, 0, 0)
            elif zero_x == 1 and zero_y == 1:
                swap_image(0, 1, 1, 1)
            elif zero_x == 0 and zero_y == 2:
                swap_image(0, 1, 0, 2)
        # 서브플롯 3
        if (x >= 330 and x <= 455) and (y >= 90 and y <= 215):
            if zero_x == 0 and zero_y == 1:
                swap_image(0, 2, 0, 1)
            elif zero_x == 1 and zero_y == 2:
                swap_image(0, 2, 1, 2)

        # 서브플롯 4
        if (x >= 73 and x <= 195) and (y >= 220 and y <= 345):
            if zero_x == 0 and zero_y == 0:
                swap_image(1, 0, 0, 0)
            elif zero_x == 1 and zero_y == 1:
                swap_image(1, 0, 1, 1)
            elif zero_x == 2 and zero_y == 0:
                swap_image(1, 0, 2, 0)

        # 서브플롯 5
        if (x >= 200 and x <= 325) and (y >= 220 and y <= 345):
            if zero_x == 0 and zero_y == 1:
                swap_image(1, 1, 0, 1)
            elif zero_x == 1 and zero_y == 0:
                swap_image(1, 1, 1, 0)
            elif zero_x == 1 and zero_y == 2:
                swap_image(1, 1, 1, 2)
            elif zero_x == 2 and zero_y == 1:
                swap_image(1, 1, 2, 1)
        # 서브플롯 6
        if (x >= 330 and x <= 455) and (y >= 220 and y <= 345):
            if zero_x == 0 and zero_y == 2:
                swap_image(1, 2, 0, 2)
            elif zero_x == 1 and zero_y == 1:
                swap_image(1, 2, 1, 1)
            elif zero_x == 2 and zero_y == 2:
                swap_image(1, 2, 2, 2)

        # 서브플롯 7
        if (x >= 73 and x <= 195) and (y >= 350 and y <= 475):
            if zero_x == 1 and zero_y == 0:
                swap_image(2, 0, 1, 0)
            elif zero_x == 2 and zero_y == 1:
                swap_image(2, 0, 2, 1)

        # 서브플롯 8
        if (x >= 200 and x <= 325) and (y >= 350 and y <= 475):
            if zero_x == 1 and zero_y == 1:
                swap_image(2, 1, 1, 1)
            elif zero_x == 2 and zero_y == 0:
                swap_image(2, 1, 2, 0)
            elif zero_x == 2 and zero_y == 2:
                swap_image(2, 1, 2, 2)

        # 서브플롯 9
        if (x >= 330 and x <= 455) and (y >= 350 and y <= 475):
            if zero_x == 1 and zero_y == 2:
                swap_image(2, 2, 1, 2)
            elif zero_x == 2 and zero_y == 1:
                swap_image(2, 2, 2, 1)
    plt.show()

def auto_puzzle(event): #자동모드 시 실행하는 이벤트 함수
    global keyList
    solution = astar(keyList)

    print(f"시도 횟수 : {len(solution) - 1}번 ")

    for i in solution:
        matrix = i

        img1 = cv2.imread(imgDic[matrix[0][0]])
        img2 = cv2.imread(imgDic[matrix[0][1]])
        img3 = cv2.imread(imgDic[matrix[0][2]])
        img4 = cv2.imread(imgDic[matrix[1][0]])
        img5 = cv2.imread(imgDic[matrix[1][1]])
        img6 = cv2.imread(imgDic[matrix[1][2]])
        img7 = cv2.imread(imgDic[matrix[2][0]])
        img8 = cv2.imread(imgDic[matrix[2][1]])
        img9 = cv2.imread(imgDic[matrix[2][2]])
        print_plot(img1, img2, img3, img4, img5, img6, img7, img8, img9)
        plt.draw()
        plt.pause(1.0)

    print("퍼즐이 완성되었습니다.")
    sys.exit(0)

def h(puzzle, goal): #매개변수로 전달받은 puzzle이 목표퍼즐인 goal과 서로 다른 인덱스 위치 개수 반환
    cnt = 0
    for i in range(3):
        for j in range(3):
            if puzzle[i][j] != goal[i][j] and puzzle[i][j] != 0: #0인 경우는 제외(빈칸처리)
                cnt += 1
    return cnt

def f(puzzle, goal, level): # 노드의 레벨과 휴리스틱값 더한 값 반환
    return level + h(puzzle, goal)
def move_puzzle(puzzle, x, y, direction): #퍼즐에서 서로 자리를 바꾸기 위한 함수
    new_puzzle = copy.deepcopy(puzzle)    #객체의 깊은 복사(원본 값이 변경되더라도 영향x)
    if direction == 'up' and x > 0:
        new_puzzle[x][y], new_puzzle[x-1][y] = new_puzzle[x-1][y], new_puzzle[x][y]
    elif direction == 'down' and x < 2:
        new_puzzle[x][y], new_puzzle[x+1][y] = new_puzzle[x+1][y], new_puzzle[x][y]
    elif direction == 'left' and y > 0:
        new_puzzle[x][y], new_puzzle[x][y-1] = new_puzzle[x][y-1], new_puzzle[x][y]
    elif direction == 'right' and y < 2:
        new_puzzle[x][y], new_puzzle[x][y+1] = new_puzzle[x][y+1], new_puzzle[x][y]
    else:
        return None
    return new_puzzle

def astar(start):  # a* 알고리즘 (f함수 값 기준으로 최소힙 사용)
    visit = set()        #노드의 중복을 방지하기 위한 집합 변수
    priority_queue = []  #우선순위 큐
    goal = goal_puzzle   #목표 퍼즐
    oper = ['up', 'down', 'right', 'left']
    node_id = 0  # 각 노드에 고유한 식별자 부여
    #시작 노드 생성
    start_node = {
        'data': start,          #현재 상태의 퍼즐
        'hval': h(start, goal), #시작 노드의 휴리스틱값
        'level': 0,             #현재 노드의 레벨(depth)
        'parent': None,         #현재 노드의 부모 노드
        'id': node_id           #현재 노드의 고유 식별자
    }
    #시작 노드(초기퍼즐)을 우선순위 큐에 삽입
    heapq.heappush(priority_queue, (start_node['hval'], node_id, start_node))
    node_id += 1

    while priority_queue:
        _, _, current = heapq.heappop(priority_queue) # 가장 낮은 f 값을 가진 노드를 꺼냄

        if h(current['data'], goal) == 0:  # 정답과 같으면
            return print_path(current)     # 경로 출력
        else:
            visit.add(tuple(map(tuple, current['data']))) #방문한 노드 기록
            x, y = check_zero(current['data'])            #0의 위치 확인

            for op in oper: #가능한 모든 연산에 반복
                next_puzzle = move_puzzle([row[:] for row in current['data']], x, y, op) #얇은 복사
                #입력받은 퍼즐의 모든 경우의 수 중에서 None 이 아닌 경우와 방문하지 않은 상태면
                if next_puzzle is not None and tuple(map(tuple, next_puzzle)) not in visit:
                    next_node = {
                        'data': next_puzzle,
                        'hval': h(next_puzzle, goal),
                        'level': current['level'] + 1,
                        'parent': current,
                        'id': node_id
                    }
                    #제외할 거 다 제외한 퍼즐을 우선순위 큐에 삽입
                    heapq.heappush(priority_queue, (f(next_node['data'], goal,
                                                    next_node['level']), node_id, next_node))
                    node_id += 1
def print_path(node):   #초기퍼즐부터 목표퍼즐까지 푸는 과정을 반환하는 함수(node 는 목표 퍼즐)
    path = []                     #과정을 담기 위한 리스트
    while node:
        path.append(node['data']) #현재 노드의 데이터를 path 리스트에 추가
        node = node['parent']     #현재 노드를 그 부모 노드로 업데이트(거슬러 올라감)
    return path[::-1]             #path 리스트를 역순으로 뒤집는다.


#########################################################################################

choice = int(input("\n1.수동모드  2.자동모드 중 하나를 선택하세요 : "))

if choice == 1:
    # 맨 처음 화면 초기화
    print_plot(img1, img2, img3, img4, img5, img6, img7, img8, img9)

    # 마우스 이벤트가 발생할 때마다 draw_puzzle 함수 실행
    cid = plt.connect('button_press_event', draw_puzzle)

    plt.subplots_adjust(wspace=0.01, hspace=0.02) # 서브 플롯 간의 여백 조정

    plt.show()  # 플롯을 화면에 표현

elif choice == 2:
    # 맨 처음 화면 초기화
    print_plot(img1, img2, img3, img4, img5, img6, img7, img8, img9)

    # 마우스 이벤트가 발생할 때마다 draw_puzzle 함수 실행
    cid = plt.connect('button_press_event', auto_puzzle)

    plt.subplots_adjust(wspace=0.01, hspace=0.02) # 서브 플롯 간의 여백 조정

    plt.show()  # 플롯을 화면에 표현