[Solved]: Why do puzzles like Masyu lie in NP?

Because a problem is in NP if, and only if, “yes” instances have succinct certificates. Informally, this means that the solution to any instance is at most polynomially large in the size of the instance, and if you’re given an instance and something that is claimed to be a solution to it, you can check in polynomial time that it really is a solution. More formally, a language $LsubseteqSigma^*$ is in NP if, and only if, there is a relation $Rsubseteq Sigma^*timesSigma^*$ such that:

1. there is a polynomial $p$ such that, for all $(x,y)in R$, $|y|leq p(|x|)$;
2. the problem of determining whether $(x,y)in R$ is in P;
3. $L = {xmid exists y,(x,y)in R}$.

For example, consider graph 3-colourability. You can describe a graph on $n$ vertices just by writing out its adjacency matrix, which requires $n^2$ bits. If a graph is 3-colourable, you can describe a colouring in $2n$ bits: just list the colour of each vertex in turn (say, $00$ for red, $01$ for green, $10$ for blue). So, if a string $x$ describes a graph, and that graph is 3-colourable, each 3-colouring can be described in a string $y$ with length $2sqrt{|x|}leq 2|x|$. Furthermore, if I give you a decription of a graph and a description of a 3-colouring, you can easily check in polynomial time that it really is a 3-colouring: just check that adjacent vertices always have different colours. So, the relation $${(x,y)mid xtext{ describes a graph $G$ and $y$ describes a 3-colouring of }G}$$ proves that 3-colourability is in NP. So, to show that Masyu is in NP, we just need to construct the corresponding relation $R$. We can describe an $ntimes n$ instance of Masyu in $2n^2$ bits: for each square in turn, write $00$ if it’s blank, $01$ if it contains a black circle and $10$ if it’s a white circle. We can describe a solution in $3n^2$ bits: for each square in turn, write $000$ if the square isn’t on the solution path, and $100$, $101$, $110$ and $111$ if it’s on the path and the next square is the one to the right, left, up and down, respectively. It’s easy to check in polynomial time that a claimed solution really is a solution: just find a square that’s on the path, follow the path and check it satisfies the criteria.