Could one make an asymmetric encryption scheme based on Sudoku? I was reading about a Polly Cracker encryption scheme based on the graph 3-coloring problem.  Aren't Latin squares just a form of the same problem?  If so, does this mean Sudoku can be used for public/private key encryption?
Sure. How efficient vs secure is another matter.

Look up Merkle's puzzles, as well. A latin square as a higher dimensional object can be related to differential properties of good mappings.