BFS / DFS 이용한 8-puzzle 문제

너비 우선 탐색과 깊이 우선 탐색을 이용한 문제를 받게 되어서 이번 글을 쓰게 되었다.

---

8-puzzle을 파이썬으로 프로그래밍 해보자

 
문제는 다음과 같다 initial 초기의 배열에 있는 원소를 한번씩 움직여서 내가 원하는 배열(goal)을 찾게되면 탐색을 종료하고 goal이라는 배열을 반환하면 된다.

---

 상태를 나타내는 클래스

 

# 상태를 나타내는 클래스
class State:
  def __init__(self, board, goal, moves=0):
    self.board = board
    self.moves = moves
    self.goal = goal

  # i1과 i2를 교환하여서 새로운 상태를 반환한다. 
  def get_new_board(self, i1, i2, moves):
    new_board = self.board[:]
    new_board[i1], new_board[i2] = new_board[i2], new_board[i1]
    return State(new_board, self.goal, moves)

  def expand(self, moves):
    result = []
    i = self.board.index(0)# 숫자 0(빈칸)의 위치를 찾는다. 
    if not i in [0, 1, 2] :# UP 연산자 
      result.append(self.get_new_board(i, i-3, moves))
    if not i in [0, 3, 6] :# LEFT 연산자 
      result.append(self.get_new_board(i, i-1, moves))
    if not i in [2, 5, 8]:# DOWN 연산자 
      result.append(self.get_new_board(i, i+1, moves))
    if not i in [6, 7, 8]:# RIGHT 연산자 
      result.append(self.get_new_board(i, i+3, moves))
    return result

 # 객체를 출력할 때 사용한다. 
  def __str__(self):
    return str(self.board[:3]) +"\n"+\
    str(self.board[3:6]) +"\n"+\
    str(self.board[6:]) +"\n"+\
    "------------------"

  def __eq__(self, other):
    return self.board == other.board

 
위 코드는 board(초기 배열), goal(원하는 배열), moves(얼마나 움직였나)를 이용하는 문제다.
처음에 주어지는 코드는 이게 끝이고 DFS와 BFS를 직접 구현하여 initial에서 goal까지 되는 것을 구현하면 된다.

---

구현

 

(1) BFS
 

from collections import deque

class State:
    def __init__(self, board, goal, moves=0):
        self.board = board
        self.moves = moves
        self.goal = goal

    def get_new_board(self, i1, i2, moves):
        new_board = self.board[:]
        new_board[i1], new_board[i2] = new_board[i2], new_board[i1]
        return State(new_board, self.goal, moves)

    def expand(self, moves):
        result = []
        i = self.board.index(0)
        if not i in [0, 1, 2]:
            result.append(self.get_new_board(i, i-3, moves))
        if not i in [0, 3, 6]:
            result.append(self.get_new_board(i, i-1, moves))
        if not i in [2, 5, 8]:
            result.append(self.get_new_board(i, i+1, moves))
        if not i in [6, 7, 8]:
            result.append(self.get_new_board(i, i+3, moves))
        return result

    def __str__(self):
        return str(self.board[:3]) + "\n" + \
               str(self.board[3:6]) + "\n" + \
               str(self.board[6:]) + "\n" + \
               "------------------"

    def __eq__(self, other):
        return self.board == other.board

def bfs(start_state):
    queue = deque([start_state])
    visited = set()
    
    while queue:
        current_state = queue.popleft()
        visited.add(tuple(current_state.board))
        
        if current_state.board == current_state.goal:
            return current_state.moves
        
        for next_state in current_state.expand(current_state.moves + 1):
            if tuple(next_state.board) not in visited:
                queue.append(next_state)
                visited.add(tuple(next_state.board))

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

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

start_state = State(puzzle, goal)
min_moves = bfs(start_state)
print("Minimum moves required:", min_moves)

 
min_moves = 4 값이 도출된다.
 
 
(2) DFS
 

class State:
    def __init__(self, board, goal, moves=0):
        self.board = board
        self.moves = moves
        self.goal = goal

    def get_new_board(self, i1, i2, moves):
        new_board = self.board[:]
        new_board[i1], new_board[i2] = new_board[i2], new_board[i1]
        return State(new_board, self.goal, moves)

    def expand(self, moves):
        result = []
        i = self.board.index(0)
        if not i in [0, 1, 2]:
            result.append(self.get_new_board(i, i-3, moves))
        if not i in [0, 3, 6]:
            result.append(self.get_new_board(i, i-1, moves))
        if not i in [2, 5, 8]:
            result.append(self.get_new_board(i, i+1, moves))
        if not i in [6, 7, 8]:
            result.append(self.get_new_board(i, i+3, moves))
        return result

    def __str__(self):
        return str(self.board[:3]) + "\n" + \
               str(self.board[3:6]) + "\n" + \
               str(self.board[6:]) + "\n" + \
               "------------------"

    def __eq__(self, other):
        return self.board == other.board

# DFS 알고리즘
def dfs(start_state):
    stack = [(start_state, set())]

    while stack:
        current_state, visited = stack.pop()
        visited.add(tuple(current_state.board))

        if current_state.board == current_state.goal:
            return current_state.moves

        for next_state in current_state.expand(current_state.moves + 1):
            if tuple(next_state.board) not in visited:
                stack.append((next_state, visited))

    return None

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

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

start_state = State(puzzle, goal)
min_moves = dfs(start_state)
print("Minimum moves required:", min_moves)

 
min_moves = 520 값이 도출된다.

---

번외

 

DFS 알고리즘에서 알 수 있던 사실 중에서 DFS는 스택을 이용한 방법과 재귀함수를 이용한 방법 총 두가지로 나뉜다.
근데 여기서 재귀함수를 이용하여 풀 경우에 재귀 깊이 초과 오류를 범하게 된다. 그래서 코드를 최적화 하고 스택의 최대 깊이를 수정하는 과정이 필요했다.
 
오류가 난 코드지만 재귀함수를 이용한 코드도 올려두겠다.
 

class State:
    def __init__(self, board, goal, moves=0):
        self.board = board
        self.moves = moves
        self.goal = goal

    def get_new_board(self, i1, i2, moves):
        new_board = self.board[:]
        new_board[i1], new_board[i2] = new_board[i2], new_board[i1]
        return State(new_board, self.goal, moves)

    def expand(self, moves):
        result = []
        i = self.board.index(0)
        if not i in [0, 1, 2]:
            result.append(self.get_new_board(i, i-3, moves))
        if not i in [0, 3, 6]:
            result.append(self.get_new_board(i, i-1, moves))
        if not i in [2, 5, 8]:
            result.append(self.get_new_board(i, i+1, moves))
        if not i in [6, 7, 8]:
            result.append(self.get_new_board(i, i+3, moves))
        return result

    def __str__(self):
        return str(self.board[:3]) + "\n" + \
               str(self.board[3:6]) + "\n" + \
               str(self.board[6:]) + "\n" + \
               "------------------"

    def __eq__(self, other):
        return self.board == other.board

# DFS 알고리즘
def dfs(current_state, visited):
    visited.add(tuple(current_state.board))

    if current_state.board == current_state.goal:
        return current_state.moves

    for next_state in current_state.expand(current_state.moves + 1):
        if tuple(next_state.board) not in visited:
            result = dfs(next_state, visited)
            if result is not None:
                return result

    return None

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

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

start_state = State(puzzle, goal)
visited = set()
min_moves = dfs(start_state, visited)
print("Minimum moves required:", min_moves)