--15puzzleについて--
-15puzzleの概要-
スライディングパズルのと呼ばれるもののの一種である。
以下のような4x4のボードの上に、4x4-1である15枚の駒が存在し、
空いている所を利用して駒をスライドすることによって、
駒を目的の配置にすることを行うパズルのことである。
パズルには、3x3の8パズルや、5x5の25パズルなど、
さまざまなサイズのパズル考えられる。
一般に、これらのスライドパズルを総称して「nパズル」と呼ぶ。
これをさらに一般化して、4x5の19パズルのような
pxqといった盤面についても考えることができる。
-15puzzleの性質-
15puzzleはどのような盤面でも解けるわけではなく、
目的の状態に到達不可能な盤面も存在する。
簡単には、目的の状態から、空白でないタイルを奇数回入れ替えたものは
目的の状態に到達不可能である。
よって盤面のパターンのうち半分の状態は、
目的の状態に到達不可能であることがわかる。
以下の図は到達不可能な盤面の一例
15puzzle問題や8パズル問題について、
最短手数で目的の状態を目指した場合、
最低何手で到達できるか、といった事については
すでに分かっており、その手数以下で必ず解くことが
できる。