Sudoku at its heart is a graph colouring problem. When you add the new constraints, it changes the connectivity of the graph. This sudoku, with all of its extra constraints, becomes a highly connected graph which greatly reduces the number of possible valid puzzles. Throw in the fact that the grid is already symmetric about both axes of reflection and rotationally symmetric about the centre and that further constrains the set of valid puzzles.

I'm sure you could write a program to take all these constraints and generate a ton of puzzles and then scroll through them to find ones that look great. It also wouldn't be too difficult to sort them in ascending order of givens.