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 mor

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