Puz-Graph

由 R. M. Wilson 於 1974 年提出的概念。給定一個有限圖 ，具有 個頂點， 被定義為一個圖，其節點是圖 的標記，其中一個節點未被佔用，即在圖 的 個節點上放置 個不同計數器的方式。這些標記可以被視為 排列 ，因此 具有 個節點。兩個標記在 中被一條邊連線，當且僅當一個標記可以透過沿著圖 的一條邊移動其中一個標籤而轉換為另一個標記。

上面說明了路徑圖 的兩個頂點的可能標記，從而給出瞭如圖所示的 。

如果 是方圖 ，則 由兩個不相交的、具有 12 個節點的環組成。一般來說，-環圖的 puz-圖有 個連通分量，每個連通分量有 個節點 (Vajda 1992)。Wilson 證明了，如果有限的有限簡單雙連通圖 是非多邊形的，則當 是二分圖時，其 puz-圖總是具有兩個連通分量。否則，除了一個令人驚訝的例外， 是連通的。例外是 theta-0 圖的 puz-圖，令人驚訝地具有六個連通分量。

在 中連線兩個標記 和 的路徑表示將 轉換為 的移動序列。因此，當且僅當它們屬於 的同一個連通分量時，它們才能相互轉換。在大多數情況下，這無法透過檢視 來判斷，因為它幾乎總是節點過多，不適合實際使用。這個問題可以使用 Wilson 的一個判據來解決，該判據可以很容易地用 、 和 來表示： 和 可以透過一系列移動連線，當且僅當它們未佔用節點之間的距離以及將 轉換為 的排列要麼都是偶數，要麼都是奇數。

Wilson 的判據可以如下應用於15 拼圖。15 個方塊的每種排列都對應於網格圖 的 15 個節點的標記。由於 是二分圖，因此 是不連通的，所以該拼圖並非總是存在解。這可以透過檢視上面說明的 15 拼圖配置的標記來理解。未佔用節點之間的距離為 0，但是將一個標記轉換為另一個標記的排列是迴圈 (1 2)，它是奇數。因此，從右側的配置開始，不可能解決這個拼圖。

漢諾塔圖 是 個漢諾塔的可能配置的 puz-圖。由於它是連通的，因此這個遊戲總是有一個解。