Elsewhere in this thread, a commenter points out that the square grid regular expression puzzle can encode 3SAT instances, so I was wrong to call these easier than the hexagonal version.