Consider the following \(16\) regions \(R_1, R_2, \ldots,\) and \(R_{16}\).

Once Takahashi determines a moat to build, each of \(16\) regions belongs to either inside or outside the moat.
For example, in the following diagram, the \(16\) regions are divided into two groups: those inside the moat, \(R_1, R_5, R_6, R_7, R_8, R_9, R_{13}, R_{14}, R_{15}\), and those outside, \(R_2, R_3, R_4, R_{10}, R_{11}, R_{12}, R_{16}\).

Also, if two moats that Takahashi builds are different, then the divisions are also different.
Therefore, we can brute force through all the possible way to split \(16\) regions into two groups, inside and outside, and check if “there exists a corresponding moat, and all the villages are included inside the moat.”

Note that divisions of regions like the following two diagrams does not correspond to a moat.