Really? Just by looking at the figure, bruteforcing for a couple of minutes and then noticing a solution which gives the same problem but 6x6 instead of 8x8, I

Really? Just by looking at the figure, bruteforcing for a couple of minutes and then noticing a solution which gives the same problem but 6x6 instead of 8x8, I was able to solve this without even pen and paper. Unless you're talking about an extremely abstract class of problems, I don't think that statement is true.