Genetic algorithms usually do exploit the structure of the problem in order to make crossover/mutation more efficient. This is indeed what the OP says:

For more difficult Sudoku puzzles, I would definitely go with the permutation genome