Mon 11 February 2013
Blog

The Pickleball Problem

Here's an interesting puzzle that my Dad ran into when trying to organize a mixed doubles Pickleball tournament.

The Problem

Given a group of n women and n men playing in a mixed doubles tournament (each match is always a woman/man team versus another woman/man team), how do you structure the matches so that you find the "best" woman and the "best" man? In other words, if the men are only competing against the men for prizes, and the women only competing against the women, so how do you maximize fairness for each of the matches - not pairing up a man and woman more than once in the tournament, and not playing against another person more than once in the tournament?

We're trying to solve this in the ballpark of n = 8.

How to solve

The interesting observation is that this can be structured as an exact cover problem. If you write out the matches as a grid, where the women are the columns (1, 2, 3...) and the men are the rows (A, B, C...), each grid entry becomes a tournament match of who that team will play. For n=4:

    1  2  3  4
  +------------
A | XX .. .. ..
B | .. XX .. ..
C | .. .. XX ..
D | .. .. .. XX

The problem is to fill in the empty values in the grid with opposing teams (e.g., C3) such that all of the matches are fair. The diagonal entries are X'd out because a team will not play itself. Further, the entries need to be reflexive - if the entry for row C, column 2 is B4, then the entry for row B column 4 should be C2.

So, for the n=4 problem, the goal is to fill in the values A2, A3, A4, B1, B3, B4, C1, C2, C4, D1, D2, D3 such that each row and column only has one 'A' value, one 'B' value, one 'C' value and one 'D' value, (excepting the value of the row that you are on - row A will not have any 'A' values) and only one '1' value, one '2' value, and so on. Once you do that, you can read off all of the tournament matches for each woman (by reading the columns) or by each man (by reading the rows).

This is similar to solving sudoku, since it is also an exact cover problem. Since I already had a sudoku solver (a brute force with constraint propogation solver, inspired by Peter Norvig's python sudoku solver), I adapted it to solve this problem.

You can see the code here.

Solutions

Here are solutions up to n=9. Any more would require additional cleverness, or days of computation time.

4x4:

    1  2  3  4
  +------------
A | XX B3 C4 D2
B | D3 XX A2 C1
C | B4 D1 XX A3
D | C2 A4 B1 XX

5x5:

    1  2  3  4  5 
  + --------------
A | XX B3 C4 D5 E2
B | C5 XX A2 E1 D3
C | D2 E4 XX A3 B1
D | E3 C1 B5 XX A4
E | B4 A5 D1 C2 XX

6x6:

    1  2  3  4  5  6 
  + -----------------
A | XX B3 C4 D5 E6 F2
B | E4 XX A2 C6 F3 D1
C | F5 E1 XX A3 D2 B4
D | B6 C5 F1 XX A4 E3
E | C2 F4 D6 B1 XX A5
F | D3 A6 B5 E2 C1 XX

7x7:

    1  2  3  4  5  6  7 
  + --------------------
A | XX B1 C2 D5 E6 G3 F4
B | A2 XX F5 G1 C7 E4 D3
C | G6 A3 XX E2 F1 D7 B5
D | E3 G5 B7 XX A4 F2 C6
E | F7 C4 D1 B6 XX A5 G2
F | C5 D6 G4 A7 B3 XX E1
G | B4 E7 A6 F3 D2 C1 XX

8x8:

    1  2  3  4  5  6  7  8 
  + -----------------------
A | XX B1 C2 D3 E4 F5 G6 H7
B | A2 XX D6 E7 F8 H4 C5 G3
C | E6 A3 XX G1 B7 D8 H2 F4
D | H5 E8 A4 XX G2 B3 F1 C6
E | G8 H6 F7 A5 XX C1 B4 D2
F | D7 G4 H1 C8 A6 XX E3 B5
G | C4 D5 B8 F2 H3 A7 XX E1
H | F3 C7 G5 B6 D1 E2 A8 XX

9x9:

    1  2  3  4  5  6  7  8  9
  + --------------------------
A | XX B1 C2 D3 E4 F5 G6 H7 I8
B | A2 XX D1 E8 F7 H9 I3 C6 G4
C | G9 A3 XX I6 H2 B8 F4 E1 D5
D | B3 F8 A4 XX C9 I2 H1 G5 E7
E | C8 I7 H6 A5 XX G1 D9 B4 F2
F | I4 E9 G8 C7 A6 XX B5 D2 H3
G | E6 H4 I5 B9 D8 A7 XX F3 C1
H | D7 C5 F9 G2 I1 E3 A8 XX B6
I | H5 D6 B7 F1 G3 C4 E2 A9 XX
Tagged , , ,