The hardest constraint problems: A double phase transition