如何說明掃雷遊戲中一個連通分支可能包含的雷數是連續的?

一個連通分支是指以下方法構造出的圖的連通分支：若兩個未知塊和同一個數字相鄰，則它們之間連一條無向邊。

例:左上的連通分支可能包含2,3,或者4個雷;

左下可能包含4或5個雷

右上有可能包含1或者2個雷.

如何說明,如果一個連通分支里可能包含X或Y個雷,那麼雷數也可以是X和Y之間任意一個數?

感覺構建一個異或門使得兩個點必須同正負似乎可以舉出反例…具體的圖回家畫畫再說…

首先，我們可以通過這裡的方法構建出一個具有兩個輸入的異或門，然後指定最後結果為0，即指定兩個輸入必須同號。

然後把我們的兩個輸入貼在一起，形成大致類似

0 0 1 2 2 1 0 0
1 1 2 * * 2 1 1
x x" 3 x y 3 y" y
1 1 2 * * 2 2 1
0 0 1 2 2 1 0 0


的輸入端，因為已知x XOR y == 0所以這個聯通量中只能有0或者2個雷。

信號分裂

0 1 x" 1 0
1 2 x 2 1
2 * 4 * 1
x x" * 3 2
2 * 4 * 1
1 2 x 2 1
0 1 x" 1 0


這樣有了輸入，信號分裂，交叉，與門、非門與或門以後我們可以用邏輯表達式

x XOR y = ((NOT x) AND y) OR ((NOT y) AND x) 來構建出一個異或門

又因為這裡指定x XOR y == 0 所以可以得到

(NOT x) AND y == 0

與

(NOT y) AND x == 0

這裡給出一個設計是

0
- AND -
NOT |
x y
SP INP SP
x y
| NOT
- AND -
0


其中INP為輸入，SP為分裂，NOT為非門，AND為與門

這裡還需要解決一個奇偶步長調整的問題，但感覺可能比較簡單……

由是可見，原命題為假。

補充一種更簡單的設計，其實我們只需要將輸入的兩個信號通過導線對接即可確保兩個變數同號。

題主修正了連通的定義以後就更加簡單了。

* * * * *
* x" * x" *
* 6 x 6 *
* * 5 * *
4 * x" * 4
2 * * * 2


考慮如圖連通量，易知x與x"互斥，此連通量中只可能存在1或者3顆雷。