MPH 在回應裡說，他找出程式碼之後，發現已經「看不懂」了，僅記得當初用到的規則相當簡單。我想，他說到軟體工程、或者軟體開發的一個大問題了。人會遺忘、溝通會失真、軟硬體會演進、需求會改變。該怎樣做，才能妥當地處理這類問題？
扯遠了，還是回到主題吧。
上回曾經提到，從下圖的提示中，我們可以推論出 (0,0) 與 (0,2) 的方格中有地雷。為什麼呢？
因為「如果 (0,0) 是安全的，那麼從 (1,0) 的提示（它周圍恰有一個地雷）可知，(0,1) 必然內含地雷。但是，由於 (1,2) 提示它的周圍恰有一個地雷，因此 (0,2) 必然是安全的。但如此一來，(1,1) 的周圍就只有一個地雷，與系統所給的提示（有兩個地雷）相抵觸。」
因此，在上圖中，(0,0) 必然內含地雷。
類似地，若我們假設 (0,1) 含有地雷，也可以推導出矛盾。因此，(0,1) 格子必然是安全的。
這樣的推論方式，其實就相當於邏輯證明中的「歸謬法」（Proof by Contradiction）。先假設某個方格 C 有（或沒有）地雷，如果可以推導出矛盾，那麼就可以知道 C 不含（或含有）地雷（因為 C 的狀態滿足排中律：它要嘛「有地雷」、要嘛「沒有地雷」，沒有其他的可能）。
雖然有向學弟們提到這個想法，但他們都以為程式寫起來會頗複雜。為了「證明」它並不如想像中「那麼」複雜，我用 PHP5 把這個想法實作了一下，結果只需增加不到 10% （大約三十幾）行的程式碼。
對上圖的提示，這個程式會先假設 (0,2) 是安全的，然後得到矛盾。於是，將 (0,2) 標示有炸彈後，套用上回提到的簡單演算法，就可以判斷出 (0,1) 是安全的：
再來一個「看似更困難」的問題。從下圖的提示裡，我們是否能夠知道那些格子是安全的？
它其實並沒有更困難。運用歸謬法和上回所提到的簡單演算法，我們是可以推得，上圖有提示的格子周遭多數格子的屬性（含有、或不含地雷）。
沒有留言:
張貼留言