개념
8-Puzzle은 3x3 격자에 8개의 숫자 타일과 빈칸 하나가 있는 퍼즐이다. 빈칸을 움직여 목표 배치를 만드는 문제이다.
상태 공간
각 타일 배치가 하나의 상태가 된다. 가능한 배치 수가 매우 많기 때문에 상태 공간 탐색이 필요하다. 강의자료에서는 8-puzzle을 통해 깊이 우선 탐색, 너비 우선 탐색, 휴리스틱 탐색, A star 알고리즘을 설명한다.
전체 9개 위치의 순열 중 실제로 도달 가능한 상태는 절반이다.
휴리스틱
8-puzzle에서 자주 쓰는 휴리스틱은 목표 상태와 다른 위치에 있는 타일 수, 각 타일이 목표 위치까지 이동해야 하는 맨해튼 거리의 합이다.