Via Puzzle weblog Puzzlinks I found a few days ago a very nice variation of Sudoku, called Battleship Sudoku.
The first (and less preferred by the author) is to put a “minifleet” in a Sudoku grid and fill the empty spaces with numbers according to Sudoku rules.
The second method puts numbers on the fleet of ships so that a correct arrangement of ships will provide clues to solve the Sudoku.
The author prefers the last one. I really like them as already mentioned in a comment; Battleship Sudoku could be as famous as Sudoku. Happy Puzzling