Martin, yes it is legal:
I consider myself a non-smoker but this sort of policy would actually put me off working there. If they banned smoking breaks on work time, that would be okay. If they encouraged people to quit smoking, that would be okay. But this seems like an unwarranted intrusion into the employees’ personal lives.
I do wonder how they define “smoker” also. As I say I consider myself a non-smoker but I have probably smoked about 6 cigars in my life and probably will continue to do so at the rate of a couple per year at special occasions and such.