= Solution
A simple square-lattice polygon has even perimeter at least four. Generate a <self-avoiding walk> of length $M-1$, reject unless its endpoint is a neighbour of the origin, then add the final <edge> to close it.
``
sap <- function(M) {
stopifnot(length(M) == 1L, is.finite(M), M >= 4,
M == floor(M), M %% 2 == 0)
repeat {
path <- saw(M - 1L)
if (sum(abs(path[nrow(path), ])) == 1L) {
return(rbind(path, c(0L, 0L)))
}
}
}
``
The output has $M+1$ coordinate rows and $M$ unit edges. The first $M$ vertices are distinct by the call to `saw`; the last row repeats only the origin. Neighbouring lattice edges cannot create an additional crossing without a repeated <vertex>. A rectangle of perimeter $M$ exists for every permitted even $M$, giving a positive <probability> of eventual acceptance.
Back to article page
