[Arnavion]

I'd assume that you'd be able to open the most squares by opening those that are completely disconnected from all other squares. That is, make a checkered pattern where there is at least one border of unopened squares around every opened one. (Except for 3's on the corners, 5's on the edges, and 8's anywhere in between, of course.)

Edit: Ah, this doesn't work, because of "You are still expected to select one of the adjacent cells." Clever.