Some people will say that in a sandbox you should have no rules. Personally, I think that that is an odd way to go, except perhaps in single-player games. The way I define a sandbox is that a sandbox is a game that gives players choices. A sandbox is a game where the player should have to weigh the pros and cons of a situation and then make a decision based on the information that is avaible.

I think this video best describes what a sandbox game should be like:

http://www.youtube.com/watch?v=oq2oxt7Nrxo