NP-Complete Static Square Puzzles
Two such puzzles that I know about are:

Unruly. This website has an online library of puzzles and solutions and a generator for puzzles of arbitrary size.
Masyu. This website has a library of puzzles and solutions. It also links to several variants of the puzzle.

Actually, the page where the Unruly puzzle is found lists more such puzzles, some of which satisfy your conditions, while others don't.