This paper presents a new heuristic solution to the well-known Nurse Scheduling Problem (NSP). The NSP has a lot of constraints to satisfy. Some are mandatory and specified by the hospital administration, these are known as hard constraints. Some constraints are put by the nurses themselves to produce a comfortable schedule for themselves, and these are known as soft constraints. Our solution is based on the practice of shift swapping done by nurses after they receive an unsatisfactory schedule. The constraints are arranged in order of importance. Our technique works on two levels, first we generate a schedule that satisfies all the hard constraints and guarantees fairness. The next level is to attempt to satisfy as many as possible of the soft constraints, by shift-swapping while maintaining the hard constraints. The technique was implemented as a simulation and demonstrated a satisfactory outcome