第23講：守護者

02-12

陸仁賈：今天要講到的一個東西，歸納出來就九個字：「物理成環而邏輯無環」。
程旭袁：莫非，是生成樹協議（Spanning Tree Protocol），那個簡稱STP的東西？
陸仁賈：當然不是！那啥，你計算機網路學多了吧！今天看一種特別的結構，需要使用到共軛對這一特殊的東西。

Part 1 守護者（Guardian）

如圖所示，我們發現，如果把r2c3(4)和r6c7(4)都去掉後，就會出現{r25, c17, b6}(4)的共軛對，剛好是5個，且恰好成環。

如果說，這五個共軛對單獨存在於盤面之中，會發生什麼樣的奇妙情況呢？

因為鏈需要交替存在，所以我們隨便選取一個節點作為鏈頭，比如r5c1(4)，向上走鏈結構。我們之前說過一點。強關係的定義下的兩個候選數，是一定滿足弱關係的定義的，但該用強關係還是弱關係，取決於關係的交替出現情況。也就是說，共軛對肯定是強關係了，不過以r5c1(4)作為鏈頭向上引出AIC的話，那麼r2c1(4)和r2c7(4)應為弱關係。隨即出現以下鏈結構：

(r5c1=r2c1-r2c7=r4c7-r5c8=r5c1)(4) => r5c1=4 => r2c1, r5c8<>4 => r4c7, r2c7=4（c7矛盾）

當我們得到r5c1=4時，同時可以知道的是r2c1和r5c8都不填4，於是r2和b6之中，r4c7和r2c7就應當填4。此時發現，r24c7(4)同列，所以矛盾。所以，直接「裸露」出來的五個共軛對首尾成環是完全不可以的，也就是說，r2c3(4)和r6c7(4)不同時為假。

所以r2c3(4)和r6c7(4)至少有一個為真，於是刪除交集，故r2c7, r6c3<>4。

這個技巧稱為守護者（Guardian）。很不幸的是，它的邏輯很複雜，接下來我就來講一下原理，這會讓你覺得技巧尋找和理解起來更加輕鬆一些。

Part 2 守護者的原理說明

我們有一個理論：多於3個的單數個共軛對首尾成環時，結構一定是不存在的。而這一節我就會告訴你為什麼。如果你對證明看興趣的話，可以簡單看一下，僅供參考。如果實在記不住過程的論證的大概過程的話，可以直接背下結論。

證明過程可以採用圖論的二染色來證明：奇數個頂點的環，無論如何進行二染色，總有兩個相鄰頂點同色。

這裡我們把二染色想像成共軛對之中一真一假的情況，這個說法就相當於，最終一定會產生兩個相鄰節點同真或同假的現象，這樣就不滿足共軛對的要求（有且僅有一個為真）。

如果不熟悉圖論的小夥伴呢，還可以嘗試用代數的角度來說明這一點（這裡只給出大概證明思路）。

如果有n個共軛對首尾成環的話（n>3且n是單數），那也就說有n個區域下都存在這樣的共軛對，共軛對意味著，兩個候選數有且僅有一個為真。恰好的是，由於是首尾成環，所以每一個節點都共同存在於兩個共軛對所在的區域下。

那麼，最少需要有 $iggllfloorfrac{n}{2}iggr floor$ 個為真，而最多 $left(iggllfloorfrac{n}{2}iggr floor+1 ight)$ 個為真。（ $lfloor x floor$ 表示 $x$ 的向下取整，比如 $lfloor 1.6 floor=1$ 、 $lfloor -0.4 floor=-1$ 等）

那麼，在範圍以內（閉區間 $[iggllfloorfrac{n}{2}iggr floor, iggllfloorfrac{n}{2}iggr floor+1]$ ），只有兩個整數可取，使得這個說法有意義，也就是這個閉區間的上下界。

當內部有 $iggllfloorfrac{n}{2}iggr floor$ 個為真時，總出現某一區域下的共軛對的兩候選數都為假的情況；（想一下為什麼。）
當內部有 $left( iggllfloorfrac{n}{2}iggr floor-1 ight)$ 個為真時，總出現某一區域下的共軛對的兩候選數都為真的情況。（想一下為什麼。）

所以，均與共軛對要求不符，矛盾。所以，n個共軛對首尾成環依然是不成立的，其中n>3且n是單數。

綜上所述，單數個共軛對首尾成環是不可能存在的結構。希望你記住這一點。所以守護者的邏輯就浮現出來了：為了規避單數個共軛對首尾成環，那麼找出所有「防止」共軛對出現的數，它們不可同時為假。

其實也就是剛才利用二染色的展開說明的過程。

接下來的示例就是也是這樣的結構。

如圖所示。想一下為什麼哦！

Part 3 死環（Guardian Pair/Dead Loop）

如圖所示，感覺略熟悉：感覺有點像是UR類型2的感覺，也有點像是遠程數對。它的邏輯是這樣的：

如果r69c3(5)同假時，r69和c3均產生29數對，在刪除所有的2和9後，2和9獨自構成由5個共軛對首尾拼接成環的守護者結構，這種結構是不成立的，所以r69c3(5)不可同為假。換句話說，r69c3(5)至少一個為真。所以，c3的其餘單元格都不應該填5，即r24c3<>5。

這個結構利用到了數對的刪除的特性，隨之產生共軛對首尾成環的守護者的出錯情況。它使用了兩個結構長相一模一樣，但候選數不同的守護者結構2和9。這個技巧叫做死環（Dead Loop），意味著r69c3(5)同假時，內部結構是直接會「死掉」的，技巧由胡蒙汀（探長）發現並命名。

Part 4 總結

這一節是針對講到的技巧做的一個統一的難度歸納和理論分析。

守護者

英文名：Guardian
難度係數：SER 無，XR 6.6 + GDRC（長度5 ~ 15）
命名空間：Tech.Chain.Wing.Irregular.Broken

使用到的術語：

生成樹協議（計算機網路術語）

英文名：Spanning Tree Protocol
解釋：為了防止區域網下網路環回的一種計算機網路協議，解決網路之中廣播風暴（Broadcast Storm）問題。該協議定義於IEEE802.1D之中。