15パズルは、スライディングブロックパズルのひとつである。4×4のボードの上に4×4-1すなわち15枚の駒があり、1駒ぶんの空きを利用して駒をスライドし、駒を目的の配置にする。3×3のボード上で8枚の駒で同様に遊ぶものは8パズルと呼ばれる。m×nのボードとm×n-1個の駒（m, n ≧ 2）に一般化できる。目的の配置において右下の隅ないし左上の隅を空きとしたものが多い。空所を利用した駒の移動のみが正しい手として許され、複数個の駒を外して並べ直すといったことが許されない等は他のスライディングブロックパズルと同様である。左上からカレンダーのような順に並べた配置に戻す、あるいはそのような配置から何らかの配置へ並べ替えるパズルである。冒頭の図では 12 の駒または 15 の駒を移動させることができる。空白部分に隣接する、縦又は横に連続した複数の駒を一斉にスライド(例えば冒頭の図で 8 と12、13 と 14 と 15)させてもよい。コンピュータゲームでは、スワイプ等でそのような操作を許すようプログラミングするのが親切である。ただし、最短手数などの評価においては「1手」が異なったものになる。「数字の渦巻き」という問題を例とする。まず、初期配置は以下の通りである。たとえば、「8」の駒を下にずらせば次のようになる。次に「5」を右にずらせば次のようになる。これを繰り返して目的の形にする。ひとつの手法として、まず上辺や左辺を目的の配置にして固定してしまうことでより小さなサイズのパズルに帰着させ、再帰的に解くというものがある。ただし駒が番号ではなく絵柄等の場合、端の行や列がわかりづらいこともある。コンピュータに解かせる場合も、全局面をなんらかの探索手法で探索して一定時間内に目的の配置に近づく手順が見つからない場合に、同様に部分問題に持ち込むようフォールバックを入れたりする。天才パズル作家・サム・ロイドが「15パズルで、14と15 を入れ替えた状態を元に戻す」という（絶対に解けることのない（後述））問題に1,000ドルの賞金をかけて出題したため、その懸賞により15パズルは大きく普及し、15パズルの商品も多く販売されるようになった。このパズルの初期配置として有名な例に「目的の配置から14と15を入れ替えた状態」というものがある。一般化も可能だが、まずはこれを例として考える。15パズルを数学的に分析すると、1個の駒のスライドという操作は「空き」とその駒の入換えと見ることができ、これは群論でいう「互換」である。ここで、ある状態から操作を続けて元の位置に空きが戻ったとすると、それには必ず偶数回の操作＝偶数回の入換えが必要であり、その配置は元の配置からの偶数回の互換（偶置換）となっている。一方、14と15の入換えは1回の入換えであり、奇置換である。従って、14と15を入れ替えた状態から目的の配置にすることはできない。一般化すると、15パズルではランダムな配置から指定された配置への変換はできないことがある。パズルでは「パリティの考え方」といったようにも言われる。外してバラバラにできる駒だと、駒を紛失してしまうこともあるため、スライドはできるが駒を外すことができない構造にした製品などもある（後述。自作例もある）。副作用として、上述のような不可能な状態にしてしまうことが無い、という利点がある一方、パズルとしてはいきなりバラバラの配置にしてしまうことができない、という欠点とも言える。コンピュータゲームでも、いきなりランダムな配置になるのではなく、目的の配置からバラバラになってゆくようなデモ式のものがある（OS XのDashboardウィジェットなど）。n×nパズルにおいて、最短手数を求める問題はNP困難である。最短手数の定数倍の変形を求める多項式時間アルゴリズムが提案されている。8パズルは任意の可能な配置へ31手以内で変形でき、31手が必要な配置は確認されている。15パズルは任意の可能な配置へ80手以内で変形でき、80手が必要な配置は確認されている。簡単なソルバーをプログラミングする場合、評価関数を各駒の目的の位置までのマンハッタン距離の和とするのが手頃である。日本では明治40年（1907年）に書かれた書物「世界遊戯法大全」に「十五置き換え遊び」の名で紹介されている。他の古典的スライディングブロックパズルと同様、多数のパズル業者が製造・販売している。前述のように駒が外れない構造のものもある。また番号でなく何らかの絵柄をあしらって、いわゆるキャラクター商品等とするにも手頃であるためそういった商品も多く「セイカのパズル できるんです！」等がある。絵柄の場合ジグソーパズル等と違い、区別が不可能な駒は避ける必要がある。コンピュータゲームとしての実装も多く、Mac OS XのDashboard用Widgets（ウィジェット）やWindows Vistaのガジェット等、デスクアクセサリ型アプリが多い。ファイナルファンタジー(第一作、作中のミニゲーム)やゼルダの伝説 風のタクト(やはり作中のミニゲーム)など、ミニゲームとして仕込まれることも多い。

出典:wikipedia