15パズル
n×nパズルにおいて、最短手数を求める問題はNP困難である。最短手数の定数倍の変形を求める多項式時間アルゴリズムが提案されている。
8パズルは任意の可能な配置へ31手以内で変形でき、31手が必要な配置は確認されている。15パズルは任意の可能な配置へ80手以内で変形でき、80手が必要な配置は確認されている。
簡単なソルバーをプログラミングする場合、評価関数を各駒の目的の位置までのマンハッタン距離の和とするのが手頃である。