슬라이드 퍼즐 알고리즘 (Slide Puzzle Algorithm)

0. 알아야할점!! 이 포스트는 퍼즐을 푸는 알고리즘인 A* 알고리즘이 아닌 슬라이드 퍼즐 같은 형태를 풀수있는지 없는지 알수있는 알고리즘이다. A*에비해 짦은 코드만으로 간편하게 확인할수있는게 장점이다. 1. 슬라이드 퍼즐이란?? 아래와 같이 15 개의 타일 (모든 타일에는 1에서 15까지의 숫자가 하나 있음)과 하나의 빈 공간이있는 4 × 4 보드가 있고 목표는 빈 공간을 사용하여 순서대로 타일에 숫자를 배치하는 것 이다. 인접한 4 개의 타일 (왼쪽, 오른쪽, 위, 아래)을 빈 공간으로 밀어 넣을 수 있다. 예를 들면 2. Inversion이란 무엇인가?? 타일이 N 행 (2차 배열)으로 펼쳐지는 대신 단일 행 (1차 배열)으로 되어있다고 가정하면, a가 b 앞에 나타나지만 a> b가 나타나면 타일..