次の図に示すような \(16\) 個の領域 \(R_1, R_2, \ldots, R_{16}\) を考えます。

高橋君が建設するお堀を \(1\) つ決めると、それによって、\(16\) 個の領域がお堀の外部にあるものと内部にあるものに分けられます。
例えば次の図では、\(16\) 個の領域がお堀の内部にある \(R_1, R_5, R_6, R_7, R_8, R_9, R_{13}, R_{14}, R_{15}\) と、外部にある \(R_2, R_3, R_4, R_{10}, R_{11}, R_{12}, R_{16}\) に分けられています。

また、高橋君が建設するお堀が異なれば、この分け方も異なります。
よって、\(16\) 個の領域を内部と外部に分ける方法（全 \(2^{16}\) 通り）を全探索し、それぞれに分け方に対して「対応するお堀が存在し、その堀の内部にすべての村が含まれるか」を判定すれば良いです。

下記の \(2\) つの図のような領域の分け方には、対応するお堀が存在しないことに注意して下さい。