[python] 8-puzzle problem (1) BFS, DFS

[파이썬] 8-퍼즐 문제

다음 그림과 같이 8개의 숫자와 빈칸을 이용해 숫자를 정렬하는 퍼즐을 말한다. 

출처: 위키백과

위 그림과는 달리 아래 모양으로 정렬하도록 하겠다. 
빈칸은 0으로 표기.

1 2 3
4 5 6
7 8 0

 

맹목적 탐색법의 대표적인 두 가지 방법으로 맹목적 탐색의 문제점을 알아본다. 

(1) 너비 우선 탐색(BFS, Breadth-first search)

너비 우선 탐색: comdoc.tistory.com/entry/24-graph-width-first-search

최단 경로 찾기: comdoc.tistory.com/entry/25-그래프-최단-경로-찾기

비교적 잘 작동하는 코드지만, 탐색이 길어지면 에러가 발생한다. 

(본인의 PC에서는) marked의 원소가 181440개를 초과되면 에러가 발생한다. 
(실제로 발생한 적은 없고, 확인을 위해 풀이가 불가능한 조합으로 테스트했다.)

from collections import deque
from random import randint


def exchange(board: str, prev_pos: int, new_pos: int) -> str:
    new_board = list(board)
    new_board[prev_pos], new_board[new_pos] = new_board[new_pos], new_board[prev_pos]
    return ''.join(new_board)


def expand(board: str) -> list:
    result = []
    position = board.index('0')
    if position not in (0, 1, 2):  # UP
        result.append(exchange(board, position, position - 3))
    if position not in (0, 3, 6):  # LEFT
        result.append(exchange(board, position, position - 1))
    if position not in (2, 5, 8):  # RIGHT
        result.append(exchange(board, position, position + 1))
    if position not in (6, 7, 8):  # DOWN
        result.append(exchange(board, position, position + 3))
    return result


def pprint(board: str):
    print(' '.join(board[:3]))
    print(' '.join(board[3:6]))
    print(' '.join(board[6:]))
    print('-----')


def randomize_start() -> str:
    board = []
    while not is_solvable(board):
        board = []
        while len(board) != 9:
            temp = str(randint(0, 8))
            if temp not in board:
                board.append(temp)
    return ''.join(board)


def is_solvable(board: list) -> bool:
    if not board:
        return False
    inversion = 0
    for i in range(len(board) - 1):
        if board[i] == '0':
            continue
        for j in range(i + 1, len(board)):
            if board[j] == '0':
                continue
            if board[i] > board[j]:
                inversion += 1
    return inversion % 2 == 0


def bfs(start: str, goal: str) -> dict:
    que = deque()
    que.append(start)
    marked = {start: None}
    while que and (current := que.popleft()) != goal:
        for state in expand(current):
            if state not in marked:
                marked[state] = current
                que.append(state)
    return marked


def print_path(start: str, goal: str, marked):
    path = []
    node = goal
    while node != start:
        path.append(node)
        node = marked[node]
    path.append(start)
    for each in path[::-1]:
        pprint(each)


def main():
    # start = '123506784'
    start = randomize_start()
    goal = '123456780'
    marked = bfs(start, goal)
    # marked = dfs(start, goal)
    print_path(start, goal, marked)
    print(start)
    print(len(marked))


if __name__ == '__main__':
    main()

1 2 3
5 0 6
7 8 4
-----
1 2 3
0 5 6
7 8 4
-----
1 2 3
7 5 6
0 8 4
-----
1 2 3
7 5 6
8 0 4
-----
1 2 3
7 5 6
8 4 0
-----
1 2 3
7 5 0
8 4 6
-----
1 2 3
7 0 5
8 4 6
-----
1 2 3
7 4 5
8 0 6
-----
1 2 3
7 4 5
0 8 6
-----
1 2 3
0 4 5
7 8 6
-----
1 2 3
4 0 5
7 8 6
-----
1 2 3
4 5 0
7 8 6
-----
1 2 3
4 5 6
7 8 0
-----
123506784
3067

코드를 보면 랜덤하게 start를 만드는 부분이 있다. 
"123456780" 상태에서 반복적으로 빈칸을 랜덤하게 움직인 뒤 시작하는 방법도 있겠지만, 
랜덤하게 start를 설정한 뒤 풀 수 있는지 확인하는 방식을 이용했다. 
참고로 n-Puzzle의 경우 숫자의 역전의 횟수가 짝수인 경우만 풀이 가능하다. 
https://math.stackexchange.com/questions/293527/how-to-check-if-a-8-puzzle-is-solvable

 

(2) 깊이 우선 탐색(DFS, depth-first search)

깊이 우선 탐색 참고: comdoc.tistory.com/entry/23-그래프-깊이-우선-검색depth-first-search

def dfs(start: str, goal: str) -> dict:
    stack = [start]
    marked = {start: None}
    while stack:
        current = stack.pop()
        if current == goal:
            break
        for state in expand(current):
            if state not in marked:
                marked[state] = current
                stack.append(state)
    return marked

bfs는 파이썬 3.8의 대입연산자 := (바다코끼리 연산자)를 이용해서 코딩했고,
(배운 건 자꾸 써먹어야...)
dfs는 이전 스타일로 코딩했다.