While doing research on the actual rules to Battleship (they're a lot more complicated than I remember for some reason), I stumbled across a delightful puzzle variation of Battleship, called
Battleship Solitaire.
It's very confusing at first, but after a while you get the hang of it, and damn it's cool. It's a lot more entertaining than Sudoku (I never really got into Sudoku).
I think I'll make the game a dual version game; you can play classic Battleship, or you can go into puzzle mode (think Popcap games)
Nifty game you got there!