Inspector Roster with a Late Unavailability
A junior engineer must assign four inspectors-P, Q, R, and S-to four sites-W, X, Y, and Z-one site per day from Monday to Thursday. The constraints are: P cannot inspect W or Z; Q must inspect on the day immediately after R; S must inspect X; the site inspected on Wednesday must be Y; and Q must not inspect Z. Each inspector visits exactly one site and each site is visited once. No inspector can visit two sites on the same day. The original roster is prepared and approved. Later, the chief engineer says R is unavailable on Monday and asks for a revised roster without relaxing any original constraint. You must determine whether a valid roster exists and, if not, which single constraint is the minimum that must be relaxed.
1. Reconstruct the only valid roster for Monday to Thursday. Show the deduction, not just the final table.
Read the worked answer
Wednesday is Y. P cannot inspect W or Z, so P must be X or Y. But S must inspect X, so P cannot be X. Therefore P inspects Y on Wednesday.
The remaining days for Q, R and S are Monday, Tuesday and Thursday. Q must be immediately after R. R cannot be Thursday because there is no day after Thursday. If R were Tuesday, Q would be Wednesday, but Wednesday is already P. Therefore R must be Monday and Q must be Tuesday.
S is left for Thursday and inspects X. The remaining sites for R and Q are W and Z. Q must not inspect Z, so Q inspects W and R inspects Z.
Final roster: Monday R-Z; Tuesday Q-W; Wednesday P-Y; Thursday S-X.
2. R is now unavailable on Monday. Can the roster be revised without relaxing any original constraint? If not, identify the minimum constraint that must be relaxed.
Read the worked answer
No valid roster exists under all original constraints.
The earlier deduction forced P to Wednesday-Y because P cannot be W or Z and S occupies X. With Wednesday taken by P, R cannot be Tuesday because Q would then need Wednesday. R cannot be Thursday because Q must follow. Therefore R must be Monday. If R is unavailable on Monday, the forced chain fails.
At least one constraint must be relaxed. The minimum is one of the constraints responsible for forcing R to Monday: for example, allowing Wednesday not to be Y (or allowing P to move off Wednesday-Y), or dropping the requirement that Q immediately follows R. Relaxing only 'Q must not inspect Z' is not enough, because the impossibility arises before that constraint is used.