algorithm - 8 パズルにはいくつの可能な状態がありますか?

Question

古典的な 8 パズルは、スライディング ブロックのファミリーに属します。私の本 (Stuart Russell と Peter Norwig による人工知能の最新のアプローチ) では、8 パズルには9!/2の可能な状態があると書かれています。しかし、なぜ/2なのですか? どうやってこれを手に入れますか？

Answer 1

9!はパズルの可能な構成の総数であり、 は解ける構成9!/2の総数です。たとえば、次の構成には解決策がありません。

1 2 3
4 5 6
8 7

n パズルの特定の構成の可解性について詳しくは、ウィキペディアの記事を参照するか、MathWorldの説明で @dasblinkenlight が指摘したように参照してください。

解決可能な構成の数を調べる方法の 1 つ9!/2は、解決済みのパズルから開始し、そこからすべての可能な有効で反復しない動きを生成することです。