Do you think you could make this work with a hex grid? You'd maybe just make 1 side of it allow for cutting corners and the other not, I think anyway.
Here is a pic to show difference between hex and sqaure grid:
<img src="https://dl.dropbox.com/u/1024727/c2/hex.PNG" border="0" />