A Room square of order \(n\) and side \(n − 1\) on an \(n\)‐element set \(S\) is an \(n - 1 \times n - 1\) array filled with \(n\) different symbols in such a way that:

1. Each cell of the array is either empty or contains an unordered pair from the set of symbols
2. Each symbol occurs exactly once in each row and column of the array
3. Every unordered pair of symbols occurs in exactly one cell of the array.

A partial Room square of order \(n\) and side \(n − 1\) on an \(n\)‐element set \(S\) is an \(n - 1 \times n - 1\) array satisfying property (1) above, and also

4. every symbol of \(S\) occurs at most once in each row and at most once in each column of the array
5. every unordered pair of symbols of \(S\) occurs in at most one cell of the array.

A partial Room square is maximal if no further pair of elements of \(S\) can be placed into any unoccupied cell of \(F\) without violating the conditions (1), (4), (5).

Greedy maximal Room squares

There are at least two deterministic methods for generating a maximal partial Room square, as described in Meszka and Rosa (2021).

The first method involves iterating through the cells in a specific order and placing the next available pair of elements into the next empty cell, ensuring that the pair satisfies the conditions of being a partial Room square. This process is known as greedy1.

The second method involves iterating through the set of all unordered pairs and placing the next available pair into the first cell that satisfies the conditions of being a partial Room square without violating any constraints. This process is known as greedy2.

Both greedy1 and greedy2 have been implemented in R and are available at the Github repository (Henderson (2023)) accompanying this blog post.

greedy1

The algorithm greedy1 visits each cell in a predetermined order and places the first available pair of symbols into the cell, provided that doing so does not violate the conditions of creating a partial Room square.

R <- greedy1(6)
plot_room_square_labs(R)

In this plot, the colors indicate the sequence in which the cells were filled. Specifically, lighter colors represent cells that were filled earlier in the process, while darker colors represent cells that were filled later.

is_maximal_proom(R)
#> [1] TRUE

Here are a few more examples of maximal partial Room squares created by greedy1.

greedy2

The algorithm greedy2 iterates through all pairs of symbols in a predetermined order and places the next available pair into the first empty cell, provided that doing so does not violate the conditions of creating a partial Room square.

R <- greedy2(6)
plot_room_square_labs(R)

is_maximal_proom(R)
#> [1] TRUE

Here are a few more examples of maximal partial Room squares created by greedy2.

References