--15puzzleについて--

-15puzzleの概要-

スライディングパズルのと呼ばれるもののの一種である。 以下のような4x4のボードの上に、4x4-1である15枚の駒が存在し、 空いている所を利用して駒をスライドすることによって、 駒を目的の配置にすることを行うパズルのことである。

15puzzle_image

パズルには、3x3の8パズルや、5x5の25パズルなど、 さまざまなサイズのパズル考えられる。 一般に、これらのスライドパズルを総称して「nパズル」と呼ぶ。 これをさらに一般化して、4x5の19パズルのような pxqといった盤面についても考えることができる。

-15puzzleの性質-

15puzzleはどのような盤面でも解けるわけではなく、 目的の状態に到達不可能な盤面も存在する。 簡単には、目的の状態から、空白でないタイルを奇数回入れ替えたものは 目的の状態に到達不可能である。 よって盤面のパターンのうち半分の状態は、 目的の状態に到達不可能であることがわかる。
以下の図は到達不可能な盤面の一例

15puzzle_cant_image

15puzzle問題や8パズル問題について、 最短手数で目的の状態を目指した場合、 最低何手で到達できるか、といった事については すでに分かっており、その手数以下で必ず解くことが できる。


戻る