It’s a contract thing called detrimental reliance. As I understand it, basically you relied on a promise to do something only in the event the promise was upheld then it wasn’t. It wouldn’t hurt to speak to a lawyer for a consultation. I doubt you’d get the job back, but they could be liable for the damages caused by moving.
Government jobs love them though, Security+ is required for a lot of DoD jobs.