1. DSolving: a novel and efficient intelligent algorithm for large-scale sliding puzzles(2017)

• paper : https://www.tandfonline.com/doi/pdf/10.1080/0952813X.2016.1259270?needAccess=true

• 압도적으로 빠른 시간
  • versus A-star 기반 (Manhattan 거리) 알고리즘
• 단, optimal solution을 못 얻을 때도 있음.
  • BFS, A-star는 optimal solution을 위해 모든 expanded states를 저장해야하고, 이는 factorial(# of tile)로, 조그마한 sliding puzzle도 구현하기 힘들 수 있음.
  • 더군다나, 애초에 $M\times N$ puzzle은 NP-hard 문제.
    • 참고 : FINDING A SHORTEST SOLUTION FOR THE N xN EXTENSION OF THE H-PUZZLE IS INTRACTABLE
      

2. A Selective Macro-learning Algorithm and its Application to the NxN Sliding-Tile Puzzle(1998)

Paper: https://www.jair.org/index.php/jair/article/view/10207/24256

• 우선 $N\times N$ puzzle.

• 학습할 경우 위의 Heuristic한 방법들은 압도함

• 다만 학습 안 하면 밀리는 모습(versus BFS, weighted A-star, ....)
• 그리고 애초에 Learning-based algorithm은 쓰지도 못할것

3. Operator-oriented genetic algorithm and its application to sliding block puzzle problem(2005)

• Paper: https://link.springer.com/chapter/10.1007/BFb0029738?noAccess=true

• 본격적으로 슬라이딩 퍼즐을 다루지는 않음(예시로만 사용).

• Operator-oriented genetic algorithm 설명.

• 패스

4. PARITY PROPERTY OF HEXAGONAL SLIDING PUZZLES(2022)

• Paper: https://arxiv.org/pdf/2201.00919.pdf

• 사실 퍼즐 종류가 직사각형 퍼즐과는 다르지만, $4\times 4$ 슬라이딩 퍼즐을 어느 정도 언급하고 있기 때문에 정리.

  • Questions relating to the puzzle graph have been previously studied and resolved for the 15 Puzzle which is the most famous, and unsolvable, square sliding puzzle of all time.

• 15 Puzzle을 풀 수 있는지 여부는 그래프를 2개로 나누는 parity property에 의존한다 알려져 있음

• 즉, 해당 연구는 주어진 puzzle이 해결 가능한지, 불가능한지 따질 수 있는 토대를 제공
  • Putting together the results by Johnson and Story tells us that it is possible to solve a sliding puzzle on a rectangular shaped board with square tiles and exactly one tile missing, if and only if the following holds: if we slide tiles of the starting configuration so that the missing tile is in the same position as in the target, the permutations of tiles in the starting and the final configurations have the same parity.
  • the set of all configurations is partitioned in two big sets that are determined by parity and that this partition characterizes when a puzzle, a given started and final configuration, has a solution or not
• 다만 Solvability of squared sliding puzzle에 대해서 연구를 더 찾아볼 필요가 있긴 함(아직 이해하지 않았음)

5. Solving the Sliding Puzzle(2015, Blog)

• https://abnerrjo.github.io/blog/2015/12/06/solving-the-sliding-puzzle/

• Sliding puzzle 구현 코드(js..)위주이나, BFS, A* 알고리즘에 대해서도 간단히 느림.

• BFS : 쉽지만 너무 느림

• A*

  • Heuristic 1 : Misplaced tiles
  • Heuristic 2 : Manhattan distance

6. Sliding Puzzles: How to solve for ANY size! | Tutorial(2016, Youtube)

• https://www.youtube.com/watch?v=P9Xib-dWlqU

• 모든 사이즈의 슬라이딩 퍼즐을 푸는 법을 소개중.