Rooks on a Chessboard

What this lecture covers

This recitation problem uses the discrete uniform law and the counting principle to find the probability that eight rooks, placed at random on an 8-by-8 chessboard, form a "safe" arrangement where no two rooks share a row or column. It is a drill for counting skills built up earlier in the course, particularly the multiplication (counting) principle applied sequentially.

After watching, you should be able to recognize when the discrete uniform law applies, count the total number of ways to place objects on a grid using a sequential placement argument, and count constrained arrangements by tracking how each placement reduces the number of valid remaining positions.

Key ideas

• Discrete uniform law: when all outcomes in a discrete sample space are equally likely, the probability of an event is the count of outcomes in the event divided by the total count of outcomes.
• Sequential placement: counting problems become manageable by imagining objects placed one at a time and counting the choices available at each stage.
• Counting principle: the total number of ways to complete a multi-stage process is the product of the number of choices at each stage, illustrated with a simple sandwich-building example (bread choices times meat choices).
• Total arrangements: placing 8 rooks on 64 squares with no other restriction gives 64 x 63 x ... x 57, expressible as 64!/56!.
• Safe arrangements: each rook placed eliminates its entire row and column for future rooks, shrinking the effective board; the numbers of remaining safe spots for successive rooks are the perfect squares 64, 49, 36, 25, 16, 9, 4, 1.

Walkthrough

Setting up the problem with the discrete uniform law (2:03)

The problem is defined: eight rooks placed uniformly at random on an 8-by-8 board, with a "safe" arrangement meaning no two rooks share a row or column. Since all spatial arrangements are equally likely, the discrete uniform law reduces the probability calculation to counting safe arrangements over total arrangements.

Counting the total number of arrangements (4:06)

Placing each rook sequentially onto an initially empty board, the first rook has 64 possible squares, the second 63, and so on down to 57 for the eighth, since each square can hold only one piece. The counting principle (illustrated with a sandwich example of choosing bread then meat) justifies multiplying these numbers together.

Counting safe arrangements (10:13)

Each placed rook eliminates its entire row and column from consideration for later rooks. Visualizing this as cutting away the occupied row and column and sliding the remaining board pieces together shows that after one rook is placed, the second rook effectively faces a 7-by-7 board, and each subsequent rook faces a further-shrunk board, giving the sequence of perfect squares 64, 49, 36, 25, 16, 9, 4, 1. Multiplying these via the counting principle gives the number of safe arrangements.

Before you watch

• Review the discrete uniform law and the counting (multiplication) principle from earlier lectures in this course.
• Be comfortable with factorial notation, since it is used to express the total-arrangements count compactly.

Check your understanding

1. Why does placing an object at a random uniform position let you use the discrete uniform law?
2. How does the counting principle justify multiplying the number of choices at each stage of a sequential placement?
3. Why do the numbers of safe positions for successive rooks form the sequence of perfect squares?
4. How would the answer change if the chessboard were a different size or a different number of rooks were placed?