A Timetable That Passes Every Condition
A small school is fixing the Class VIII timetable for a five-period day. Five subjects are to be placed, one per period: Mathematics (M), Science (S), English (E), Hindi (H) and Social Science (SS). Three teachers cover them: Teacher X takes M and S, Teacher Y takes E and H, and Teacher Z takes only SS. The head lays down four conditions: (i) each subject appears exactly once; (ii) no teacher may take two consecutive periods; (iii) Mathematics must come before Science; (iv) Social Science must be the last period. A colleague drafts this schedule - Period 1 M, Period 2 E, Period 3 S, Period 4 H, Period 5 SS - and the head is ready to circulate it as final. Before signing, the head asks two questions: is the draft safe, and is it the only timetable that satisfies the conditions? Nobody has checked it against the conditions. The bell is in 25 minutes and there is no scheduling software.
1. Test the colleague's draft against each of the four conditions. State which pass and which fail, and identify the trap in the head's first question.
Read the worked answer
Condition by condition:
- (i) Each subject once: M, E, S, H, SS all appear once. Pass.
- (ii) No teacher in consecutive periods: X is at periods 1 and 3 (not consecutive); Y is at periods 2 and 4 (not consecutive). Pass.
- (iii) M before S: period 1 before period 3. Pass.
- (iv) SS last: period 5. Pass.
The draft is valid. The trap is in the head's first question - 'is it safe?' invites a yes/no check against the conditions, and the draft will clear that check. But a timetable can be valid and still not be the timetable. The question that matters is the second one, and it is not answered by the same test: satisfying a set of constraints establishes membership of a set of solutions, not uniqueness within it. A checker who runs only the first question will circulate the draft, discover months later that another arrangement was equally available, and have no way of knowing whether the one chosen was the better one. The disciplined move is to enumerate before signing, which is quick here because the space is tiny.
2. Determine whether the draft is the only timetable satisfying all four conditions. If not, say how many there are and give one extra condition that would make the choice unique.
Read the worked answer
Fix Z first: SS must be period 5, so Z is placed and periods 1-4 must hold M, S, E, H.
Place X: M and S must be non-consecutive among periods 1-4, with M before S. The possible pairs are (1,3), (1,4) and (2,4).
Test each against Y, who must occupy the two remaining periods without being consecutive:
- (1,3): remaining periods 2 and 4 - not consecutive. Works.
- (1,4): remaining periods 2 and 3 - consecutive. Fails.
- (2,4): remaining periods 1 and 3 - not consecutive. Works.
So there are two skeletons: M1 S3 with E and H at 2 and 4; and M2 S4 with E and H at 1 and 3. Within each skeleton English and Hindi can swap, giving four timetables in total. The draft is one of them.
One extra condition for uniqueness: 'English must be in period 2.' That eliminates the M2 S4 skeleton, and within the surviving skeleton it forces H to period 4, giving E1, M2? - no: M1, E2, S3, H4, SS5 exactly as drafted.
A tempting but insufficient condition: 'Science must be in period 4.' This forces the M2 S4 skeleton but leaves E and H free to swap at periods 1 and 3, so two timetables survive. It narrows the set without pinning it, which is the usual failure mode when a constraint is added to fix a schedule.
3. Setting the puzzle aside, what is wrong with deciding a real timetable by constraint-satisfaction logic alone?
Read the worked answer
The model is closed; the school is not. The four conditions are a small, stated subset of what the timetable actually has to satisfy. Unstated constraints include each teacher's total weekly load, room and laboratory availability, free periods for co-curricular duty, Teacher Z's science club which meets only on certain days, examination and assembly days, and the ordinary fact that a teacher with periods 1 and 3 has no real break between them. A schedule can pass every stated condition and still be operationally poor.
Validity is necessary, not sufficient. The draft above shows the failure precisely: it is valid, and it is one of four equally valid arrangements. Logic tells you the set; it does not tell you which member to choose, because choosing requires a preference the constraints do not contain - fewest consecutive loads, protecting a teacher's preparation time, not splitting a double period across a break.
What the head should do: state the objective before solving, then verify the candidate against both the stated and the unstated constraints by asking the two teachers who will actually teach it, and record the assumptions in the minutes. Circulating a draft as 'final' converts a solved puzzle into an authority claim, and the correction will arrive in week three as a reshuffle, which costs more than the 25 minutes saved now.
The general point: a constraint check answers 'is this allowed?'. A judgement answers 'is this the one we want?'. The head was asked the second question and was about to answer the first.