Could one make an asymmetric encryption scheme based on Sudoku?
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.